Routenoptimierung

    Sorry, falls maein Anliegen irgendwo in den Archiven schon brach liegt.....


    Ich wünschte mir eine Route mit x Zielen. Wahllos auf einer Route zusammengestellt.


    Und nun wünschte ich mir (interessant für Botendienste oder Kundenbesuche), dass mir die Navigationssoftware die Reihenfolge der Erreichbarkeit innerhalb einer Route A --> B automatisch "sortiert".


    That's it.

    Navigation mit Google Maps über Android Auto und AAWireless im Nissan Qashqai Akari Automatik. Zusätzlich ist POIbase NAVI ein treuer Beegleiter meiner Fahrten  ;)

    OHO - Da stellst Du eine einfach klingende aber fast unendlich komplizierte Anforderung!


    Da gibt es eine bekannte Aufgabe (Das Vertriebler-Problem oder so ähnlich) bei dem gegebene Punkte zu einer möglichst schnellen und sparsamen Route verbunden werden sollen... Du ahnst ja nicht wie komplex diese Thema wird, wenn Du mal ein paar Ziele definierst!


    Ich glaube an den UNIs für Informatiker wird sowas gerne als Beispiel genommen... Es gibt auch sündhaft teure Software, die sowas _versucht_ möglichst optimal zu lösen - meist mit vordefinierten Kompromissen... Routenplanung ist nicht einfach ...


    nSonic


    Naja, ich denke mal, wir reden von einer Route mit einem Startpunkt N-O-S-W und einem Endpunkt N-O-S-W.


    Und aufgrund der N-O-S-W-Koordinaten der Zwischenziele sollte das doch auch ohne grössere mathematischen Berechnungen machbar sein?


    Wüsste ich die Koordinaten, würde ich Excel für eine Zehntel Sekunde bemühen... :)

    Navigation mit Google Maps über Android Auto und AAWireless im Nissan Qashqai Akari Automatik. Zusätzlich ist POIbase NAVI ein treuer Beegleiter meiner Fahrten  ;)

    Wenn Du die Reihenfolge zwischen den Zwischenzielen und dem Ziel (inkl. dem Ziel?) aber optimieren möchtest, dann kann das knifflig werden:


    welcher Weg soll es denn sein? ("S" (oben) ist der Start)


    [Blockierte Grafik: http://www.nsonic.de/temp/routing.gif]


    aber vielleicht denke ich da auch zu kompliziert und Du meinst etwas viel einfacheres?


    nSonic


    Ja,
    das "TSP" quaelt ganze Generationen von Informatikern seit (in DL) mind 30 Jahren.
    @michi,
    schau mal in den Archiven von "Mama Blue" nach;
    dort muesste es mind ein halbes Dutzend von Approximationen geben.
    Wolf
    ... z.Zt. an ungewohnter Tastatur.
    ---> Nachtrag: ...und noch ne Woche....

    Einmal editiert, zuletzt von WolfL ()

    Ich will ja nicht andere Produkte loben -ne, wirklich nicht- aber Map&Guide kann das sehr gut. Das ist auch der Grund, warum bei uns einige Aussendienstler mit dem Travelbook fahren. Zusätzlich hat das Ding sogar noch die Möglichkeit Alternativrouten zu berechnen. Ist aber eine PC-Variante. Die Umsetzung auf PDA ist nicht erwähnenswert, da das keine Umsetzung sondern eher eine Designstudie ist.


    Ich dachte ganz einfach: Auf der Strecke A bis Z liegen D, F, B, R, N, und die möchte ich abfahren als A, B, D, F, N, R, Z


    :-D) :-D) : drink : drink

    Navigation mit Google Maps über Android Auto und AAWireless im Nissan Qashqai Akari Automatik. Zusätzlich ist POIbase NAVI ein treuer Beegleiter meiner Fahrten  ;)

    ach so - Du meinst:


    Den Startpunkt gibst Du vor, und dann diverse Ziele.


    Nun soll er Dir eine Route vom Start bis zum nächstgelegenen Ziel berechnen. Und von diesem Ziel wieder weiter zum nächstgelegenen nächsten Ziel ... etc...


    Das könnte man wohl lösen wenn man als Entfernung z.B. Luftlinie annimmt... Ansonsten müsste man ja jede Strecke (von A zu jedem Ziel) berechnen lassen um dann zu wissen, welche kürzer ist - die Luftlinien-Entfernung ergibt sich dagegen schon aus den Koordinaten und man könnte so eine Reihenfolge vorgeben.


    Meinst Du das?


    nSonic

    @nSonic
    Willst Du das gerade programmieren? Oder warum fragst Du so genau nach?


    Bei Map&Guide geben ich den Startpunkt und meine ganzen Ziele an. Dann sage ich: "Optimale Route berechnen". Dann dauert es etwas, der PC verfällt ins denken und fluchen und am Ende gibt er die Route aus.


    Als Krönung kann ich sogar noch angeben, daß ich bei Kunden X um 12:00 sein muß und bei Kunden y um 15:30, mit Angabe der Verweildauer. Doll, ne?


    Nicht umsonst kostet M&G mehr als der Navigator.

    Ne - programmieren will ich das nicht... und schon garnicht "gerade mal so" :D


    wollte nur genau wissen, was gemeint war.


    Und der Vergleich mit dem PC hinkt ziemlich gewaltig - denn wenn der PC schon eine Weile ins Nachdenken verfällt, dann ist das Geschrei am PPC extrem groß... wer will schon 15 Minuten auf seine Route warten :D (den meisten ist schon die einfache Routenberechnung viel zu lahm wenn man mal mehr als 100km fahren möchte)


    nSonic

    25 Kunden in einem Umkreis von 100 km mit einer Anfahrt von ca. 300 km dauern am PC ca. 30 sec. Da ich ungeduldig bin (ja ich gebe es zu), empfinde ich das als lange.