Tourenplanung
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 Clusterung 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 Standardproblem der Tourenplanung 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. Pickup-and-Delivery-Probleme).
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.
Mathematische Modelle und Algorithmen
Das Grundmodell der Tourenplanung gehört zu der Klasse der NP-schweren Probleme. Daher werden zur Lösung des Problems Heuristiken angewandt. Einfache Lösungsverfahren sind die Savings-Heuristik und der Sweep-Algorithmus. Lösungen mit besserer Qualität beruhen auf evolutionären Algorithmen, simulierter Abkühlung und Tabu-Suche. Sie nutzen lokale Suchstrategien, bei dem die Reihenfolge von Aufträgen bzw. Zuordnung von Aufträgen zu Fahrzeugen getauscht wird. In letzter Zeit wird auch immer häufiger der Ameisenalgorithmus als Problemlösung in Betracht gezogen.
Als Subproblem der Tourenplanung ergibt sich das Problem des Handlungsreisenden, indem man ein Fahrzeug mit unbegrenzter Kapazität betrachtet und dieses mit minimalen Kosten oder Weglänge fahren lässt.
Def.: Eine Menge an Aufträgen ist einer Menge an Transportmitteln unter Berücksichtigung von Distanzen und Restriktionen so zuzuordnen, dass alle gesamten Transportkosten, welche durch den Einsatz von Transportmitteln und die zurückgelegten Distanzen verursacht werden, minimiert werden.
Tourenplanungssoftware
Tourenplanungssoftware unterstützt Unternehmen bei der Planung und Optimierung von Touren. Dazu benötigt die Software als Datenbasis u. a. ein digitales Straßennetz, eine Kundenstammdatei, eine Fahrzeug- und Fahrerliste sowie eine aktuelle Auftragsliste. Entfernungen und Fahrzeiten können grob mithilfe von Koordinaten der georeferenzierten Kundenadressen geschätzt oder aus einem Entfernungswerk entnommen werden, alternativ operieren Algorithmen zur Streckenoptimierung auf einem digitalen Straßennetz. Die Optimierung geschieht, indem der Transportbedarf einer Anzahl Kunden zu einer oder mehreren Touren derart zusammengefasst wird, dass zeitliche Vorgaben der Kunden, Lasten und Kapazitäten der Fahrzeuge, Pausen- und Arbeitszeiten der Fahrer und Wartungszyklen der Fahrzeuge eingehalten werden, während die anfallenden Transportkosten minimiert werden. Diese bestehen möglicherweise aus fixen Kosten für Fahrer, Disponent und Fahrzeug sowie den variablen Fuhrparkkosten bestehend aus Verbrauchskosten, Mautkosten, Wartung und Instandhaltung, Arbeitszeit und Überstunden.
Siehe auch
Literatur
- Wolfgang Domschke und Armin Scholl: Logistik: Rundreisen und Touren. 5. Aufl., Oldenbourg-Verlag, München, Wien 2010. ISBN 978-3486590937.
- Tore Grünert und Stefan Irnich: Optimierung im Transport, Band I: Grundlagen. Shaker Verlag, Aachen 2005. ISBN 978-3832245146.
- Tore Grünert und Stefan Irnich: Optimierung im Transport, Band II: Wege und Touren. Shaker Verlag, Aachen 2005. ISBN 978-3832245153.
- Heinrich Paessens und Philip Herbst: Tourenplanung mit TourMaster 4. expertSoft 82, Expert Verlag, Renningen 2010. ISBN 978-3816929185.
Weblinks
jsprit – Open Source Java Bibliothek zur Lösung komplexer Tourenplanungsprobleme – Herausforderungen an eine Tourenplanungssoftware