Traveling Salesman Problem mit GMaps

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Traveling Salesman Problem mit GMaps

    Hallo Leute,
    Ich beschäftige mich derzeit mit dem Traveling Salesman Problem und habe dabei ein Problem:
    habe ein Array mit Orten und ein Array mit Positionen. Diese stehen indirekt miteinander in Beziehung
    Das Array mit den Orten wird an Gmaps gesendet und als optimierte Route wieder neu sortiert ausgespuckt.
    Jetzt will ich die Orte abhängig von den Positionen umpositionieren.
    Z.B.

    Quellcode

    1. var pos = array(3,2,1);
    2. var locations = array("Berlin", "Hamburg", München);
    3. var response = GoogleService(locations);
    4. //response: Hamburg, München, Berlin
    5. //Routine()
    6. //gewünschtes Ziel: "München", "Hamburg", "Berlin"


    Später sieht die Liste noch größer aus und das Ziel was ich damit verfolge ist fixe Adressknoten einzufügen die immer zuerst abgefahren werden sollen und der Rest der optimierungslogik von gMaps entsprechen.

    Würde mich um Hilfe von euch stets freuen.
    Stehe derpst aufm Schlauch

    Danke im voraus
  • dadtimo schrieb:

    Hallo Leute,
    Ich beschäftige mich derzeit mit dem Traveling Salesman Problem und habe dabei ein Problem:
    habe ein Array mit Orten und ein Array mit Positionen. Diese stehen indirekt miteinander in Beziehung
    Das Array mit den Orten wird an Gmaps gesendet und als optimierte Route wieder neu sortiert ausgespuckt.
    Jetzt will ich die Orte abhängig von den Positionen umpositionieren.
    Deswegen heißt es doch Traveling Salesman Problem^^ nur Spaß

    Laut deinem Vorhaben hat das nix mit TSP zutun, da du ja Positionen für die Städte vergeben willst und somit eine geplante Route festlegst wird. Falls ich das so richtig verstanden hab.

    TSP: Behandelt das Problem die kürzeste Rundreise, innerhalb von N Städten, zu finden. Und bei N Städten gibt es 0,5(N-1)! Möglichkeiten diese Rundreise zu absolvieren.
    Der Mensch erkennt meistens sowas schnell, der Computer muss das berechnen und benötigt dafür Zeit. Je mehr Städte umso mehr Zeit. Es gibt dafür keinen effizienten
    Algorithmus der dieses Problem in einer sinnvollen Zeit lösen kann.
    Das mal nur als kurzer Einschub, aber jetzt wieder zurück zum Thema.


    dadtimo schrieb:

    var pos = array(3,2,1);
    var locations = array("Berlin", "Hamburg", München);
    var response = GoogleService(locations);
    //response: Hamburg, München, Berlin
    //Routine()
    //gewünschtes Ziel: "München", "Hamburg", "Berlin"
    Kann man überhaupt solche Art von Informationen an G-Maps schicken bzw. können die überhaupt so verarbeitet werden. Ich glaub eher nicht bzw. wird es nicht so einfach gehen.

    dadtimo schrieb:

    Später sieht die Liste noch größer aus und das Ziel was ich damit verfolge ist fixe Adressknoten einzufügen die immer zuerst abgefahren werden sollen und der Rest der optimierungslogik von gMaps entsprechen.
    Wie genau soll das ablaufen, du hast ein Array in der du die Städte speicherst und dann übergeben willst?
    Das wird aber nicht funktionieren, da dein Array eine feste Größe hat und somit in deinem Code nur 3 Felder besitzt.
    Und du kannst nicht einfach die Größe erweitern, bzw die Elemente darin vertauschen. Da brauchst du etwas dynamisches.
    Stichwort: Listen, verkette Liste, doppelt verkette Liste usw.^^
    (Wobei ich nicht weis ob JS sowas bietet)

    Das mit der Positionierung ergibt sich dann aus den Vorteilen einer Liste oder macht es zumindest einfacher ;)
    "Irren ist menschlich. Aber wer richtigen Mist bauen will, braucht einen Computer."