Mini-Routenplaner ...

[hiltwin]

... hat sich schon mal jemand mit dem Thema beschäftigt?

Muss ja das Rad nicht neu erfinden, falls jemand Ideen oder Anregungen hat.

Als Teil eines Gesamtprojektes möchte ich zwischen 50 und 100 Städte miteinander verbinden und eine Routenplanungslösung anbieten ...

Frdl. Gruss
Hiltwin

[PMV]

einen Routenplaner erstellen

Ist dir der Umfang eigentlich bewusst, was solch ein Teil überhaupt
können muss? Wobei das schwerste (Zeitraubendste) wohl erst mal
ist, die ganzen Daten überhaupt zu bekommen ...

Oder willste das mit einer öhm Fantasielandschaft machen?

Oder was hast du da genau vor ... beschäftigt hab ich mich damit noch
nicht, werd ich aber wohl auch nicht, da es schon einige Routenplaner
gibt und manche Räder sind zu groß, um sie noch mal selber zu
erfinden

MFG PMV

[nicolaus]

Also ich finde deine Idee richtig gut.

ABER das ist nich so leicht wie man sich sowas denkt.

Du mußt beachten das du die ganzen GPS Daten aller Strassen und so weiter brauchst um auch genau arbeiten zu können.

Solche Daten bekommst du nicht geschenkt. Ich habe selber mal in einem Team mitgearbeitet wo wir für Flughäfen eine Software entwickelt habenund da haben allein die GPS daten für die Start- und Landebahnen 5000€ gekostet.

Und das wäre nur eins der Probleme die du da zu lösen hättest.

Gruß,
Nico

[hiltwin]

... ich habe wohl das falsche Wort gewählt ;o)

Routenplaner ist dann nicht richtig, sondern Reiseplaner ...

Mir schwebt im entferntesten vor, noch mit GPS-Daten zu arbeiten ....

Also, vielmehr folgendes

Tabelle ausm alten Westermann-Atlas

Entfernung Hamburg - Berlin 250 km
Entfernung Hamburg - Hannover 180 km
Entfernung Hamburg - Bremen 130 km
Entfernung Hamburg - Köln 450 km
Entfernung Bremen - Hannover 160 km
Entfernung Hamburg - Berlin 450 km
Entfernung Köln - Hannover 330 km
Entfernung Kassel - Hannover 160 km
Entfernung Würzburg - Kassel 190 km
Entfernung Würzburg - Köln 180 km

(hatte den Westermann-Atlas nicht vor mir, Entfernungen sind geschätzt ;o) )

Und nun errechne mir, in welcher Reihenfolge ich die beteiligten Städte am sinnvollsten abfahre, um so wenig wie möglich Kilometer zu fahren.
Evtl. noch ergänzt mit dem Vorschlag: Lass Hannover weg - ist sowieso zu provinziell

Das soll mehr so in die Richtung gehen ...

[nicolaus]

Ich denke mit der Tabelle aus dem Atlas wird das nix den das sind angaben für "Luftlinie".
Also die nehmen da die netfernung von Stadtmitte zu Stadtmitte auf dem direkten geraden weg. Wenn du aber nun mit dem Auto von München nach Hamburg fährst kannst du ja nich qeur feld ein fahren sondern mußt normale Strassen fahren die ja Kurven und so haben und somit stimmt die angabe der km nicht aus dem atlas.


Gruß Nico

[hiltwin]

das ist mir auch schon klar ;o) werd dann natürlich als richtige Entfernung nen richtigen Routenplaner von Stadtmitte zu Stadtmitte zu Rate ziehen. Es geht halt nicht darum, die Route auf die jeweils nächste kommende Kreuzung zu beschreiben, sondern nur als Teilangebot die Routenplanung als sinnvolle Abfolge der gewählten Ziele auf Reihe zu bringen ...

[NicTheQuick]

Angenommen man hat 29 Städte. Dann gibt es 29! mögliche Wege, von
denen du die Entfernungen ausmessen müsstest. Und immer dran
denken: 29! = 8.841.761.993.739.701.954.543.616.000.000. In Worten
über 8 Quintillionen Möglichkeiten. Da brauchst du also ein paar Jahre um
die günstigste Fluglinie auszurechnen. Ab da gehts also ran ans
optimieren.

[Sylvia]

Das Thema "Pathfinding" ist hochinteressant und nicht so trivial, wie
allgemein angenommen. Dennoch kann es in seiner einfachsten Methode
(BruteForce) auf minimalen Aufwand reduziert werden. Soll heissen:
Kleiner Code, aber hoher Rechenaufwand.

Z.B. 4 Punkte stehen in Verbindung zueinander: A B C D

Alle Informationen (Entfernung) sind bekannt:

A/B=100 Km
A/C=80
A/D=50

B/C=60
B/D=80

C/D=90

Aufgabenstellung: Alle Punkte auf dem kürzesten Wege miteinander
verbinden.

Die BruteForce-Methode bildet in diesem Fall alle Variationen (nicht Kombinationen!!
Irgendwie verfolgt mich dieses Thema, guckst du hier):

4! (bedeutet Fakultät von 4) = 1*2*3*4 = 24

und berechnet die jeweilige Gesamtentfernung für jede dieser
Variationen. Die Variation mit der kleinsten Gesamtentfernung ist das
gesuchte Ergebnis.

Leichter gesagt als getan (für den Computer). 4 oder 8 oder 10 Ziele so
zu routen ist ja noch ein Kinderspiel (8!=40320 Variationen, 10!=3628800).
Sobald es aber mehr Varianten sind (wie hier: 50! = 3*10 hoch 63) gehen
jedem GHz Bolzen die Lötstellen auf.

Code: Alles auswählen

OpenConsole()

Dim POI(4,4) ; Points of Interest's

a=1  ; Ort A
b=2  ; Ort B
c=3  ; Ort C
d=4  ; Ort D

; die Entfernungen der Orte zueinander
; in eine Tabelle eintragen

POI(a,b)=100: POI(b,a)=100
POI(a,c)=80 : POI(c,a)=80
POI(a,d)=50 : POI(d,a)=50

POI(b,c)=60 : POI(c,b)=60
POI(b,d)=80 : POI(d,b)=80

POI(c,d)=90 : POI(d,c)=90


MinKm =100+60+90    ; vorbelegen mit Entfernung Route "ABCD"
Route$="ABCD"       ; beste bisherige Route



; Routing, Bildung aller Variationen

For V1=a To d
     For V2=a To d
          For V3=a To d
               For V4=a To d
                    
                    ; um zu verhindern, dass 2x der gleiche Ort angefahren wird...
                    If V1=V2 Or V1=V3 Or V1=V4 Or V2=V3 Or V2=V4 Or V3=V4 
                    Else
                         
                         AktEntfernung=POI(V1,V2)+POI(V2,V3)+POI(V3,V4)
                         
                         If AktEntfernung<MinKm 
                              
                              ; neue, kürzere Route gefunden
                              MinKm=AktEntfernung
                              Route$=Chr(64+V1)+Chr(64+V2)+Chr(64+V3)+Chr(64+V4)
                              
                         EndIf
                         
                    EndIf
                    
               Next V4
          Next V3
     Next V2
Next V1

PrintN("kuerzeste Route: "+Route$+" mit "+Str(MinKm)+" Km")

Input()
CloseConsole()

Auf dem Gebiet der Schachprogrammierung (aber nicht nur hier) gibt es
div.Methoden, um die Folgen des BruteForce-Prozess einzudämmen.
Stichwort: Alpha/Beta. Alpha/Beta ist, wenn man es einmal begriffen hat,
recht einfach anzuwenden (wer mehr wissen möchte ->Google).

Um die Funktion von Alpha/Beta in einem Satz zu beschreiben: Wenn ich
an einem bestimmten Punkt feststelle, dass das Teilergebnis bereits
schlechter als das bisherige beste (Gesamt-)Ergebnis ist, dann kann ich
die Berechnung bereits an dieser Stelle abbrechen und wieder hierarchisch
eine Iterationsebene (bei der Bildung der Variationen) zurückgehen.

[hiltwin]

Angenommen man hat 29 Städte. Dann gibt es 29! mögliche Wege, von
denen du die Entfernungen ausmessen müsstest. Und immer dran
denken: 29! = 8.841.761.993.739.701.954.543.616.000.000. In Worten
über 8 Quintillionen Möglichkeiten. Da brauchst du also ein paar Jahre um
die günstigste Fluglinie auszurechnen. Ab da gehts also ran ans
optimieren.

Wie kommst Du auf die Fantastillionen Möglichkeiten???
Ich würd die Entfernungen wie folgt bei 29 Städten ermitteln:
Stadt 29: 28 mal Entfernungen
Stadt 28: 27 mal Entfernungen
Stadt 27: 26 mal Entfernungen
Stadt 2: 1 mal Entfernung

ermitteln. Das gibt nach Excel 406 zu ermittelnde Wegstrecken ...

Danke Sylvia, hab noch keine Zeit gefunden, genau nachzulesen. Mach ich noch ...

[NicTheQuick]

Sylvia hats ja genauer erklärt. Einfach durchlesen.

Wenn du 29 Städte hast, dann hast du 29 Möglichkeiten anzufangen. Bist
du bei dieser Stadt, hast du noch 28 Möglichkeiten für die nächste Stadt,
bist du auch dort gewesen sind es noch 27 Möglickeiten, ..., und wenn du
die zweitletzte Stadt angereist hast, dann gibt es nur noch eine
Möglichkeit. Das sind dann 29*28*27*...*3*2*1 Möglichkeiten, also 29!,
also 8.841.761.993.739.701.954.543.616.000.000.
Ich mache im Mathe-LK gerade Wahrscheinlichkeitsrechnung und
Kombinatorik und bin mir somit sehr sicher, dass ich da richtig liege.
Probier das ganze doch mal mit 4 Möglichkeiten aus, dann kommst du auf
24 Möglichkeiten, wie du deine Reise durchführen könntest.