Was ist der Hintergrund der Tourenplanungsproblematik?
Die Tourenplanung spielt in verschiedenen Branchen eine Rolle. Naheliegend sind natürlich die Auslieferung von Pakten, Essen oder Lebensmitteln, aber auch andere Bereiche arbeiten mit der Tourenplanung, zum Beispiel die Müllabfuhr oder Städte bei der Planung von Busfahrplänen.
Das Ziel der Tourenplanung ist die Optimierung der Route: Es gilt, die kürzesten Strecken zu wählen, um Fahrtkosten und Zeit zu sparen. Letzteres ist vor allem für Unternehmen wichtig, die Kund:innen mit Waren beliefern.
Das Problem der Tourenplanung kennt verschiedene Bezeichnungen. Bekannt ist es seit 1832, mathematisch behandelt wurde es allerdings erstmals 1930. So wurde es erst Botenproblem genannt, bevor es schließlich Travelling Salesman (oder Salesperson) Problem, zu Deutsch: Problem des Handlungsreisenden getauft wurde. Ein Routenplanungsalgorithmus wurde 1959 veröffentlicht. Seitdem gibt es allerdings viele verschiedene Lösungsansätze.
Das Navigationssystem als Graph aus Knoten und Kanten
In diesen werden Karten oder Straßennetze in Knoten und Kanten eingeteilt. Algorithmen von Navigationssystemen modellieren Wege oder Straßen dazu also als Graphen, der aus den Verbindungen der Knoten und Kanten entsteht. Bezogen auf ein Straßennetz stellen Knoten die Kreuzungen und Kanten die Wege dazwischen dar. Die Knoten und Kanten werden mit Gewichten versehen, um nun zu berechnen, welcher der schnellste Weg vom Start zum Ziel ist. Ohne die Abstraktion als Graph wäre das also nicht möglich.
Wie funktioniert der Algorithmus?
Dazu nimmt das Programm die nächsten Knoten, die über die Kanten vom Start aus direkt erreicht werden können. Trifft er auf Knoten, an denen er schon war, wird das als Umweg eingestuft und verglichen, ob der Umweg vielleicht sogar kürzer ist als die Hauptroute. So hangelt sich der Algorithmus durch das Straßennetz, bis er am Ziel angekommen ist. Als Bezugsgröße nimmt er dabei die Luftlinie zur Hilfe für die ungefähre Richtung und Entfernung. Außerdem bevorzugt er Autobahnen, wenn die Nutzer:innen nicht gerade zu Fuß oder mit dem Fahrrad unterwegs sind.
Der Output ist der optimale Weg mit dem Ziel, eine möglichst kurze Tour zu finden. Dieser Algorithmus stammt von Dijkstras, den er 1959 veröffentlicht hat. Eine Gemeinsamkeit anderer Lösungsansätze ist die Graphentheorie, da sie den Raum abstrahiert, was für die Berechnung der Strecke notwendig ist. Die Graphentheorie bildet auch die Grundlage für die Tourenplanung, auch Standardproblem der Tourenplanung oder Vehicle Routing Problem genannt.
Das Standardproblem der Tourenplanung
Das Problem des Handlungsreisenden wurde zum VRP verallgemeinert, dem Vehicle Routing Problem oder Standardproblem der Tourenplanung. Die Tourenplanung arbeitet mit Clustering und Routing. Das Standardproblem der Tourenplanung ist also ein Teil der Tourenplanung. Es dient der Entwicklung von Optimierungsverfahren, also zur Berechnung einer optimalen Route. Formuliert hat es George Dantzig 1959, um es auf die Optimierung von Benzinlieferungen an Tankstellen anzuwenden.
Eine optimale Tour schafft es, die Transportkosten zu minimieren, die notwendige Anzahl an Fahrzeugen und Fahrer:innen zu minimieren, die Fahrzeit und die Zeit für die Beladung zu minimieren, um den Gewinn letztlich zu maximieren. Daher sind optimierte Touren auch heute ein relevanter Aspekt für Kuriere, Paketdienste und andere Lieferdienste.
Die Tourenplanung im Überblick
Der Unterschied zum Dijkstra-Algorithmus, bei dem es um Knoten und Kanten eines Graphen als abstrahiertes Straßennetz geht, ist, dass der Start- und Zielpunkt gleich sind. Es entsteht also eine Rundreise mit einem oder mehreren Zwischenstopps. Letzteres ist auch der Fall bei der Tourenplanung, wobei die Software einerseits berechnet, welche Aufträge zu einer Tour zusammengestellt werden, und in welcher Reihenfolge andererseits die Zwischenhalte bedient werden.
Das Problem des Handlungsreisenden tritt daher häufiger als Unterproblem auf, weil es hauptsächlich auf die kürzeste Strecke vom Start bis zum Ziel abzielt. Bei der Tourenplanung muss aber zum Beispiel auch ein heterogener Fuhrpark berücksichtigt werden sowie vorrangige Kund:innen, die in einem bestimmten Zeitfenster beliefert werden müssen oder wollen. Tourenplanungssoftware unterstützt Unternehmen dabei, Routen bei der Warenauslieferung zu planen und zu optimieren. Die Datenbasis stellen ein Straßennetz und die Kundenstammdaten sowie Fahrzeug- und Fahrerlisten und Auftragslisten dar.