Tourenplanung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Tourenplanung ist eine Zuordnung von Speditionsfahrzeugen zu Sammelgut-Aufträgen und die optimale Reihenfolge der zu bedienenden Auftragsstandorte innerhalb des Verkehrsnetz zu finden. 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 stehen dort eine begrenzte oder unbegrenzte Zahl von Fahrzeugen zur Verfügung. Andere Varianten betrachten zusätzliche Kapazitätsrestriktionen für die Fahrzeuge (Capacited Vehicle Routing Problem, CVRP), 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 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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

Literatur[Bearbeiten]

  • 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.

Weblinks[Bearbeiten]

jsprit - Open Source Java Bibliothek zur Lösung komplexer Tourenplannungsprobleme