Tourenplanung

engl.: route planning

Die Tourenplanung beschäftigt sich mit der Problematik zwischen verschiedenen Standorten die optimale Verbindung zu generieren. Bei der Lösung des Routenplanungsproblems stehen die beiden Aspekte Clusterung und Routing im Vordergrund. Die Clusterung gibt an, welche Aufträge zu einer Tour zusammengefasst werden, das Routing, in welcher Reihenfolge die Punkte innerhalb einer Tour bedient werden. Bei Touren- und Routenplanungsproblemen handelt es sich um ein mathematisch einfach zu beschreibendes Optimierungsverfahren zwischen vorgegebenen Punkten den minimalen Weg zu ermitteln. Diese Aufgabe ist aber aufgrund ihrer enormen Anzahl an Varianten auch mit modernsten Rechnern noch nicht exakt bestimmbar. [1] Zur Lösung gibt es eine Vielzahl von Algorithmen, die eine Näherungslösung in kurzer Rechenzeit mit akzeptabler Genauigkeit liefern. Das klassische Rundreiseproblem, auch Vehicle Routig-, Dispatching-, Vehicle Scheduling-, Vehicle Loading- oder Delivery Problem genannt, besteht darin, die kürzeste Wegstrecke zwischen vorgegebenen Liefer- bzw. Abholorten zu ermitteln.

Bekannte Tourenplanungsmethoden sind:

• Sweep Verfahren
• Savings Verfahren
• Verfahren des nächsten Nachfolgers

Zu unterscheiden sind lang- und kurzfristige Planungsaufgaben. Bei der strategischen Planung im Transportwesen geht es um die langfristige Festlegung von Transportstrategien, die Standortplanung für Produktionsstätten und Lägern (Warehouse Location Problem), die Planung der Verkehrswege und der Transportmittel sowie der Kapazitätsplanung. Im Gegensatz dazu ist die Aufgabe der kurzfristigen operativen Planung die Optimierung der Fahrzeugauslastung, des Personaleinsatzes sowie die Minimierung der Kosten bei vorhandenem Mitteleinsatz. Für diese unterschiedlichen Aufgabenstellungen werden für das Einsatzgebiet angepasste Algorithmen verwendet. [2] Die Abbildung enthält eine Klassifizierung der Problemlösungsalgorithmen:

Verfahren zur Lösung von Tourenproblemen[1]

• Exakte Verfahren
  • Heuristische Verfahren
    • Kantenorientierte Probleme
    • Kombination oder Einzelanwendungen für knotenorientierte Probleme
  • Zweistufige Sukzessivverfahren
    • Route first-Cluster second
    • Cluster First Route Second
  • Einstufige Sukzessivverfahren
    • Konstruktionsverfahren
    • Verbesserungsverfahren
• Eröffnungsverfahren
  • Verbesserungsverfahren

In der Praxis ergeben sich oftmals weitere zusätzliche Besonderheiten und Nebenbedingungen, welche bei der Tourenplanung berücksichtigt werden müssen:

• Zeitfenster: Bedarfsorte oder Städte dürfen nur innerhalb bestimmter Zeitspannen angefahren bzw. durchfahren werden
• Zeitrestriktionen: Eine einzelne Rundreise für alle oder bestimmte Fahrzeuge darf eine bestimmte Zeitdauer nicht überschreiten (z.B. Berücksichtigung der Lenkzeiten)
• Längenrestriktionen: eine einzelne Rundreise für alle oder bestimmte Fahrzeuge darf aufgrund verkehrswegebedingter Restriktionen eine bestimmte Länge nicht überschreiten
• Aus- und Rücklieferungen
• Ladungsrestriktionen: Nicht alle Güter können mit jedem beliebigen Transportmittel ausgeliefert werden

Quellen

[1] Lontke, M.: Graphensuchverfahren und genetische Algorithmen als Problemlösungsmethoden- dargestellt am Standardproblems der Tourenplanung, Bremen: Universität Bremen 1994.

[2] Jonas Buchholz, Uwe Clausen, Alex Vastag: Handbuch der Verkehrslogistik, Berlin, New York, Heidelberg: Springer Verlag 1998.