Hallo,
ich habe mich entschlossen einen Routenplaner mit OSM zu Programmieren.
Bin gerade am Informationen sammeln und wüsste mal gerne was erfahrene Leute in dem Thema davon halten.
Mein Programm soll die Karten von ganz Deutschland beinhalten. Die passende XML-Datei habe ich mir dazu schon von hier besorgt.
Den Aufbau der XML Datei hab ich mir auch angeschaut. Da ich in der Datei nicht alle Informationen benötige würde ich die XML
Datei erstmal in ein eigenes Format parsen. Nun zur ersten Frage die ich habe. Würdet ihr um eine Strecke zu suchen die XML Datei nehmen
oder glaubt ihr, es ist sinnvoll die Daten in eine Datenbank zu nehmen. Ein entsprechender Server dazu wäre kein Problem.
Als zweites stellt sich mir die Frage, welchen Suchalgorithmus ich am besten nehme. Habe mir bisher Ford, A* und Dijkstra angesehen.
Ford ist mir zu langsam. A* ist nur modifiziert so schnell wie Dijkstra. Dijkstra ist mit n log n der schnellste Algorithmus.
Kennt ihr noch einen anderen Suchalgorithmus, welchen ich mir anschauen sollte oder könnt ihr mir einen dieser 3 empfehlen.
Ich werde das ganze mit Java Programmieren. Außerdem würde ich das ganze gerne Web-Basiert machen. Als Oberflächen kämen dann für
mich JavaFX, JSP, Java Applet(Swing) und GWT (GoogleWeb Tool). Außer mit Swing habe ich mit den anderen Sprachen keine Erfahrung.
Ich würde aber wirklich mal gerne GWT lernen. Hat hier jemand schonmal was in der Richtung gemacht und kann mir seine Erfahrungen berichten.
Würdet ihr was anderes Empfehlen uum eine Oberfläche zu erstellen.
Datenbank oder XML?
Das kommt drauf an, wie Du fortfahren möchtest. Es ist nicht ganz ersichtlich, ob es eine Online-Anwendung werden soll die auf Deinem Server läuft und der User nur eine Webseite bekommt, oder ob es ein Offline-Programm für den User werden soll.
Soll es eine 100%ige Webanwendung werden, wenn wäre eine Datenbank sicher der schnellere Weg. Denn je mehr User auf der Website sind, desto mehr macht sich die Speed bemerkbar.
Soll es nur ein Zwischenformat für den User sein (so wie bei WeTravel) ist eine externe Datenbank Katastrophe. Weil dann müsste jeder User auf seinem PC erstmal MySQL oder sonst was installieren. Wenn Du Datenbanktreiber natürlich gleich mitbringst und der User davon gar nichts bemerkt ist eine Datenbank sicher auch der schnellere Weg.
Welcher Suchalgorithmus?
Du meinst zum finden des kürzesten Weges? Gar keiner - du musst den “Besten” Weg finden. Das dürfte zu 90% der schnellste sein. Hier sind die Max-Speed Werte wichtig. Auch pro Ampel kannst Du ein paar Sekunden Standzeit hinzurechnen. Allerdings sind Suchalgorithmen nicht meine Stärke.
Wie die Oberfläche gestallten?
Ich kenne die drei Programme nicht, jedoch zählt bei der Oberfläche nur sein. Userfreundlichkeit. Wenn der User sich erstmal 10 Programme installieren und konfigurieren muss, damit Dein Routenplaner funktioniert, ist es eine Katastrophe.
Je nachdem, wie Du fortfährst, der Weg von einem guten Routenplaner zu einem Navigationsgerät ist nicht mehr sehr groß. Evtl. solltest Du das von Anfang an mit beachten. Allerdings ist alles zusammen sicher mehr als ein 1-Mann-Projekt.
ich bin mir noch nicht sicher in welche Richtung ich entwickele, bin deswegen zurzeit am Informationen sammeln. Mein Wunsch wäre es einen eigenen Server laufen zu lassen und darauf die Web-Anwendung. User können übers Internet die Seite benutzen. Also genauso wie die meisten anderen Routenplaner. Eine Erweiterung für ein Navigationsprogramm ist nicht geplant, aber du hast recht, man könnte beim planen mal dran denken. Bin auch in dem Projekt nicht alleine und habe ein paar Leute die mir dabei helfen.
Mein nächster Schritt wird nun sein eine DB-Modell zu entwerfen und die Daten da rein zu importieren.
Zum berechnen der schnellsten Route werde ich wohl nun den Dijkstra Algorithmus nehmen, falls mich hier nun keiner mehr von was anderem überzeugt.
Die Oberfläche stell ich nun mal ganz nach hinten. Werde mich wenn es dann soweit ist wieder drum kümmern und überlegen ob ich es mit GWT machen kann.
Ich verstehe den Sinn dieser Aussage nicht. Natürlich braucht man einen Suchalgorithmus, sonst kommt man gar nicht weit. Auch eine einfache Schleife ist ein Algorithmus…
Und was das “Beste” angeht, so ist es sicherlich sinnvoll den Algorithmus kostenbasiert zu Gestalten (Fachbegriff ist mir grad entfallen). Also nicht nur die Länge berücksichtigen, sondern alles mögliche dazu. Das könnte zum Beispiel, wenn man den schnellsten Weg möchte (ist noch ganz simpel gehalten, und im Grunde auch keiner der genannten Algorithen, sondern wäre hier zur nachträglichen Kostenanalyse und zur Bestimmung des schnellsten Weges geeignet):
k soll minimal werden:
k = Σ(i=0; n-Wege) Weglänge(i)/(wenn, dann maxspeed(i), sonst rateMaxspeedAusHighway(i)) + Σ(i=0; n-Knoten) (Wenn hatTag(highway=traffic_signals, Knoten(i)) dann 1 , sonst 0)
Ja also ich würde dir auch empfehlen, dass du bestehende Software verbesserst. Die sind alle nicht schlecht aber haben große Defizite beim Deployen und der Usability. Für Windows gibt es keine gangbare Lösung. Die Algorithmen sind hinreichent untersucht also A-Star oder Djikstra, da erfindet man nichts neues mehr www.openrouteservice.org
Datenbank oder XML?
Wenn es halbwegs performant laufen soll, brauchst du eine Datenbank (oder eine andere Form von Binärformat). Ich kann mir nicht vorstellen, dass es möglich ist XML während des Routings in akzeptabler Geschwindigkeit zu parsen.
Welcher Suchalgorithmus?
Das hängt davon ab welche Art von Routen du berechnen möchtest. Wer ist deine Zielgruppe? Welche Anforderungen musst du erfüllen?
Bei kurzen Routen, die keine Gemeinsamkeiten aufweisen, könntest du einen der genannten Algorithmen umsetzen. Falls die Routen lang sein könnten, würde es außerdem Sinn machen von beiden Richtungen aus zu Suchen und eventuell (je nach zu erwartendem Straßennetz) eine tendenzielle Richtung vorzugeben. Es kann auch hilfreich sein schnell auf hochklassifizierte Straßen zu Routen und bevorzugt darauf zu verbleiben.
Ameisen-inspirierte Routing Algorithmen sind interessant falls du auf überraschende Ereignisse reagieren möchtest. Außerdem lassen sich mittels simulierter Evolution relativ komplexe Routen in akzeptabler Zeit berechnen. Diese Art von Algorithmen liefern zufällige Ergebnisse – meistens jedoch akzeptable. Stichwörter zum Einlesen wären hier: Emergent Computing, Evolutionary Algorihms, Ant Routing, Ant Colony Optimization
Wie bereits erwähnt, solltest du die Berechnungen nicht auf Basis der Entfernung durchführen, sondern eine Kostenfunktion / Fitness zu Grunde legen. Damit lassen sich dann relativ einfach verschiedene Routing-Profile erstellen. Letztendlich kommt es außerdem nicht darauf an die optimale Route zu finden, sondern eine gute Route in akzeptabler Zeit.
Wie die Oberfläche gestalten?
Das hängt ebenfalls von deiner Zielgruppe ab.
Die Frage der Technik stellt sich dabei noch nicht – zumal alles was du ursprünglich erwähnt hattest sowieso Java ist. Die Berechnungen solltest du unabhängig von der Oberfläche entwickeln können.
Übrigens: Das von Islanit angesprochene Traveling Salesman ist nicht die Problemstellung sondern ein Routing-Programm von Marcus Wolschon.
Du schriebst später, dass du das Traveling Salesman Problem lösen willst. Ist das dann dein Anwendungsfall? Sprechen wir dabei eher von 5 Zielen, 100 Zielen oder noch mehr?
Erläutere bitte einmal genau was du mit deinem Programm erreichen möchtest.
- du musst den “Besten” Weg finden. Das dürfte zu 90% der schnellste sein. Hier sind die Max-Speed Werte wichtig. Auch pro Ampel kannst Du ein paar Sekunden Standzeit hinzurechnen. Allerdings sind Suchalgorithmen nicht meine Stärke.