Vehicle routing problem

rdf:langString Tourenplanung

rdf:langString Tourenplanung ist ein Planungsvorgang, bei dem (Transport-)Aufträge zu Touren gruppiert und in eine Reihenfolge gebracht werden. Dabei wird in der Regel eine Tour von einer Person oder einem Fahrzeug durchgeführt. Dieser Planungsprozess ist in allen Bereichen bedeutend, in denen eine Vielzahl von Aufträgen und Touren geplant werden muss. Beispiele sind die Belieferung von Filialen eines Händlers, die Abholung von Post, die Mülleinsammlung, die Personenbeförderung und der Einsatz von Servicepersonal. Bei regelmäßigen Strecken wie im Kurier-Express-Paket-Dienst bilden sich so Transportnetzstrukturen. Ein Auftrag besteht meist darin, eine bestimmte Anzahl Einheiten einer Sendung von einem Start zu einem Ziel zu bringen. Eine Lösung eines Tourenplanungsproblems hat daher meist zwei Aspekte: * die gibt an, welche Aufträge zu einer Tour zusammengefasst werden * das Routing definiert, in welcher Reihenfolge die Punkte innerhalb einer Tour bedient werden. Zielsetzung einer Tourenplanung ist zum Beispiel die Minimierung der Anzahl der eingesetzten Fahrzeuge, der zurückgelegten Strecke, der Einsatzzeit, des CO2-Ausstoßes oder einer komplexeren Kostenfunktion. Beim liegen alle Start- oder Zielpunkte in einem Depot und es steht dort eine begrenzte oder unbegrenzte Zahl von identischen Fahrzeugen mit beschränkter Kapazität zur Verfügung. Andere Varianten betrachten zusätzliche Restriktionen wie z. B. Zeitfenster, mehrere Depots oder beliebige Start- und Zielpunkte (sog. ). In der Realität wird die Aufgabenstellung noch durch viele Restriktionen erweitert. Beispielsweise betrachtet man mehrere Depots, einen heterogenen Fuhrpark oder Vorrangbeziehungen zwischen Aufträgen. Eine andere mögliche Zusatzaufgabe ist die Betrachtung von Zeitfenstern, innerhalb derer ein Fahrzeug beim Kunden eintreffen muss, um die von einem Zeitfenstermanagement vergebenen oder gebuchten Slots einzuhalten. Von einer dynamischen Tourenplanung spricht man dann, wenn sich die Auftragslage während der Planung dynamisch verändert (zum Beispiel durch neu hinzukommende oder stornierte Aufträge). Anwendungen existieren neben dem Logistikbereich in allen Wirtschaftszweigen, die ihre Kunden beliefern (zum Beispiel Möbelindustrie, Müllabfuhr oder Automatenbeschicker). In vielen Unternehmen wird eine Tourenplanungssoftware eingesetzt, um die anfallenden Touren zusammenzustellen und anhand von Kriterien, wie zum Beispiel der Einhaltung von Zeitvorgaben oder Gewichtschranken, sowie Transportkosten zu optimieren.