ZRP

ZRP - Routenoptimierung mit Hilfe von Metaheuristiken

Ziel dieses Projektes war es eine leicht zu bedienende Software zur Routenoptimierung zu entwickeln.

Bei der Routenoptimierung ist das größte Problem die Vielzahl möglicher Lösungen. Ab einer bestimmten Anzahl von Orten ist es aufgrund der Komplexität von (n-2)! nicht mehr möglich ein exaktes Ergebnis zu berechnen. Darum entschieden wir uns für Metaheuristiken zur Annäherung an das optimale Ergebnis.

Entstanden ist ZRP (ZeroRoutenPlaner), eine Webapplikation auf Basis von Java, Javascript, Tomcat und Google Maps.

Kurz gefasst macht das Programm Folgendes:

1.Alle möglichen Entfernungen zwischen den Städten von der Google Maps API, mittels Browser/Javascript, ermitteln und an unseren Server senden. Dazu werden Routen abgefragt, nicht wie vereinfacht dargestellt die Luftlinie.

2. Serverseitige Berechnung der kürzesten Route

3. Ausgabe des Ergebnisses mittels Google Maps im Browser

Routenoptimierung ist ein Teilbereich des Faches Operations Research, welches sich mit der Optimierung von Verfahren beschäftigt. Dieses kombinatorische Optimierungsproblem, bei dem die kürzest mögliche Gesamtstrecke ermittelt werden soll, wurde mithilfe dreier Metaheuristiken angegangen:

Ameisenalgorithmus
Simulierte Abkühlung
Evolutionärer genetischer Algorithmus

Ein Ziel dabei war es den für diese Problemstellung am besten geeigneten Algorithmus zu ermitteln.
Bei jedem gilt die zentrale Annahme, dass zu viele Lösungsmöglichkeiten existieren, als dass ein Computer in annehmbarer Zeit jede Einzelne errechnen kann, um auf diesem Wege die beste Lösung zu ermitteln. Deshalb nähern sich die Algorithmen mit immer besser werdenden Ergebnissen dem optimalen Ergebnis an. Dies tun sie auf unterschiedliche Weise. Der Ameisenalgorithmus simuliert die Wegfindung von Ameisen, die simulierte Abkühlung bildet einen Abkühlprozess, wie er exemplarisch beim Härten von Stahl genutzt wird, nach, und der genetische Algorithmus simuliert die Evolution. Jeder der Algorithmen ist zum Beispiel in der Lage auf heutiger Hardware (2,4GHz Doppelkernprozessor) aus den sich bei nur 18 Städten ergebenden 20922789888000 Lösungsmöglichkeiten mit einer hohen Wahrscheinlichkeit innerhalb von 10 Sekunden die optimale Lösung zu ermitteln. Werden es jedoch mehr als 50 Orte, schneiden bei begrenzter Zeit der Ameisenalgorithmus und die simulierte Abkühlung besser ab als der evolutionäre Algorithmus.

Bei Strecken mit wenigen Zwischenstationen liefert ZRP meist das optimale Ergebnis, bei vielen Städten zumindest sehr gute Ergebnisse. Durch die "uneingeschränkte" Anzahl von Wegpunkten ist das Programm besonders interessant für Kurierfahrer oder kleinere Logistikunternehmen.

Der Dienst ist zu erreichen unter zrp.tournament.de

Ein schönes Javaapplet das anhand eines evolutionären Algorithmus Optimierung betreibt und das gleichzeitig grafisch ausgibt: Link
Gleiche Quelle über da Problem des Handlungsreisenden: Link

Comic: http://xkcd.com/399/

Wir sind auf der Seite der HfT Stuttgart.