Tourenplanung

Unter Tourenplanung versteht man das Problem, eine möglichst gute Zuordnung von Fahrzeugen zu Aufträgen und für jedes Fahrzeug eine optimale Reihenfolge der zu bedienenden Auftragsstandorte zu finden. 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, und 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 oder einer komplexeren Kostenfunktion. Beim Standardproblem der Tourenplanung liegen alle Start- oder Zielpunkte in einem Depot und es stehen dort eine begrenzte oder unbegrenzte Zahl von identischen Fahrzeugen mit begrenzter Kapazität zur Verfügung. Andere Varianten betrachten 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, in deren Grenzen ein Fahrzeug beim Kunden eintreffen muss. 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 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-Schwere-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 genetischen 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: Routenplaner

Literatur

• W. Domschke und A. Scholl: Logistik: Rundreisen und Touren. 5. Aufl., Oldenbourg-Verlag, München - Wien 2010.
• T. Grünert und S. Irnich: Optimierung im Transport, Band I: Grundlagen. Shaker Verlag, Aachen 2005.
• T. Grünert und S. Irnich: Optimierung im Transport, Band II: Wege und Touren. Shaker Verlag, Aachen 2005.
• H. Paessens und P. Herbst: Tourenplanung mit TourMaster 4. expertSoft 82, Expert Verlag, Renningen 2010.