Effizientere Lieferungen durch integrierte Touren- und Beladeoptimie­rung

Die Tourenplanung spielt eine zentrale Rolle in vielen Industrien, insbesondere wenn Transporte effizient und platzsparend gestaltet werden müssen. Eine besondere Herausforderung besteht darin, die dreidimensionale Beladung jedes Fahrzeugs direkt in die Tourenplanung zu integrieren.

In der neuen Publikation mit dem Titel „A branch-and-cut algorithm for vehicle routing problems with three-dimensional loading constraints“ adressiert das Team aus Felix Tamke, Florian Linß, Leopold Kuttner und Udo Buscher dieses Problem. Sie entwickelten ein exaktes Lösungsverfahren, das sowohl die Optimierung der Routen als auch die dreidimensionale Beladung der Fahrzeuge berücksichtigt.

Das Verfahren basiert auf einem branch-and-cut-Ansatz unter Nutzung der sogenannten „infeasible path elimination“-Techniken. Dadurch werden Routen, für die keine zulässige Beladung existiert, automatisch ausgeschlossen. Die Beladung der Fahrzeuge wird exakt über ein flexibles Constraint-Programming-Modell geprüft, während ein spezieller Packheuristik-Ansatz die Anzahl zeitaufwändiger Berechnungen deutlich reduziert.

Ergänzend generiert das Verfahren Startlösungen und kombiniert diese regelmäßig zu neuen, verbesserten Lösungen. Umfangreiche Berechnungsstudien auf bekannten Benchmark-Instanzen zeigen die signifikanten Leistungsverbesserungen: Zahlreiche zuvor heuristisch gefundene Lösungen konnten erstmals als optimal nachgewiesen werden. Zusätzlich wurden für viele Instanzen neue beste teilweise sogar optimale Lösungen eingeführt.

Felix Tamke, Florian Linß, Leopold Kuttner, Udo Buscher, European Journal of Operational Research
https://doi.org/10.1016/j.ejor.2025.10.010