Kennt ihr das 'Problem des Handlungsreisenden'? Dabei handelt es sich um ein kombinatorisches Optimierungsproblem bei dem die kürzeste Strecke zwischen n Punkten gefunden werden soll. Das Problem tritt bei vielen praktischen Anwendungen auf, beispielsweise in der Tourenplanung, in der Logistik oder im Design von Mikrochips. Noch häufiger tritt es allerdings als Unterproblem auf, wie zum Beispiel bei der Verteilung von Waren, bei der Planung von Touren eines Kunden- oder Pannendienstes oder bei der Genom-Sequenzierung.
VROOM im Einsatz
Das Problem des Handlungsreisenden ist ein NP-schweres Problem, das heisst (salopp gesagt), dass es keinen Algorithmus gibt, der das Problem in sinnvoller Zeit lösen kann. Bereits bei 18 Punkten, gibt es 177 Billionen Varianten, die untersucht werden müssen. Daher werden in der Regel Näherungsverfahren eingesetzt, um eine fast optimale Route zu berechnen.
Wer selbst vor diesem Problem steht, kann die 'Vehicle Routing Open-source Optimization Machine' (VROOM) verwenden. Die Bedienung ist kinderleicht: man setzt alle Punkte die angefahren werden sollen per Mausklick auf eine Karte und drückt den Zahnrad-Knopf. Schon wird die optimale Route auf der Karte dargestellt. VROOM kann auch mit JSON-Daten gefüttert werden, falls man zu viele Daten hat, um diese per Maus einzugeben. Ausserdem steht die VROOM-Engine auf GitHub zur Verfügung, um das Routing in eigenen Projekten zu verwenden.
Wenn ihr eure nächste Kneipentour plant, dann nehmt doch einfach VROOM.
