Re: suche Empfehlungen für Routenplaner mit OSM

- 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.

Es kann natürlich auch Sinn machen verschiedene Techniken zu kombinieren um beispielsweise mehrere Zielsetzungen abzuwägen. Beispiel: Building low CO2 solutions to the Vehicle Routing Problem with Time Windows using an Evolutionary Algorithm (oder bei Google docs).

- 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.