Metaheuristic optimization for complex routing problems

Theiß, Alina; Schneider, Michael David; Peis, Britta

doi:HT031273234

Metaheuristic optimization for complex routing problems

Theiß, Alina^RWTH*

2025

Verantwortlichkeitsangabevorgelegt von Alina Theiß

ImpressumAachen : RWTH Aachen University 2025

Umfang1 Online-Ressource : Illustrationen

Dissertation, Rheinisch-Westfälische Technische Hochschule Aachen, 2025

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak08

Hauptberichter/Gutachter
Schneider, Michael David (Thesis advisor)^RWTH* ; Peis, Britta (Thesis advisor)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2025-08-26

Online
DOI: 10.18154/RWTH-2025-07568
URL: https://publications.rwth-aachen.de/record/1017789/files/1017789.pdf

Einrichtungen

Lehrstuhl für Computational Logistics (813210)

Inhaltliche Beschreibung (Schlagwörter)
depot operations (frei) ; iterated local search (frei) ; last-mile delivery (frei) ; logistics optimization (frei) ; metaheuristics (frei) ; routing problems (frei) ; tabu search (frei)

Thematische Einordnung (Klassifikation)
DDC: 330

Kurzfassung
Die Optimierung von Transportsystemen ist zu einem zentralen Aspekt geworden, um heutigen logistischen Herausforderungen gewachsen zu sein. Mit dem stetigen Wachstum des Welthandels und den steigenden Kundenerwartungen an schnelle Lieferungen stehen Unternehmen zunehmend unter Druck, ihre Leistungen sowohl zeit- als auch kosteneffizient zu erbringen. Diese Dissertation behandelt vier Routenoptimierungsprobleme: Erstens das Single Truck and Trailer Routing Problem with Satellite Depots (STTRPSD), das zur Modellierung der Routenplanung von Zusteller:innen in der letzten Meile eines Postnetzwerks verwendet werden kann. Zweitens das Vehicle Routing Problem with Depot Operation Constraints (VRP-DOC), das zusätzlich die Zuordnung von Haushalten zu Zusteller:innen in die Routenplanung einbezieht und Depotprozesse berücksichtigt. Drittens das Angular-Metric Traveling Salesman Problem (ATSP) sowie das Angular-Distance-Metric Traveling Salesman Problem (ADTSP), die insbesondere für die Minimierung von scharfen Kurven beim Einsatz schwerer Fahrzeuge relevant sind. Schließlich das Capacitated Team Orienteering Problem with Time-Dependent and Piecewise-Linear Score Functions (C-TOP-TDPLSF), das häufig im Kontext kundenorientierter Lieferungen auftritt. Zur effizienten Lösung praxisrelevanter Instanzen dieser NP-schweren Probleme nutzen wir Metaheuristiken wie Iterated Local Search und Tabu Search. Dabei integrieren wir problemspezifische Eigenschaften in die Gestaltung der Heuristiken, um die Performance zu erhöhen. Umfassende Rechenexperimente zeigen dabei deutliche Verbesserungen im Vergleich zu aktuellen Verfahren aus der Literatur sowie zu in der Praxis eingesetzten Lösungen. Für das STTRPSD nutzen wir die Zerlegung des Problems in Teilprobleme im Design unserer Heuristik. Damit lassen sich die Fahrzeiten im Vergleich zu den Lösungen unseres Industriepartners im Durchschnitt um etwa 2 % reduzieren. Im Rahmen des VRP-DOC gehört unsere Arbeit zu den ersten Ansätzen, die Depotprozesse in die Routenplanung einbeziehen. Unser Algorithmus integriert sowohl problemspezifische Nachbarschaftsoperatoren als auch die Struktur realer Straßennetze. Auf Praxisinstanzen reduziert unsere Heuristik die Fahrzeiten im Vergleich zu den aktuell eingesetzten Lösungen unseres Industriepartners nicht nur um etwa 6,5 %, sondern liefert auch erheblich einfachere Lösungen in Bezug auf die Prozesse im Depot. Für das ATSP und das ADTSP nutzen wir geometrischen Eigenschaften der Probleme. Unsere Heuristik erzielt einen guten Kompromiss zwischen Rechenzeit und Lösungsqualität und liefert für rund 80 % der Benchmark-Instanzen ohne bekannte Optimallösung neue Bestlösungen. Für das C-TOP-TDPLSF nutzen wir in unserer Heuristik gezielt die Struktur der Scorefunktion. Durch eine detaillierte Analyse der erzielten Lösungen geben wir praktische Handlungsempfehlungen für Unternehmen und liefern wertvolle Erkenntnisse zur Verbesserung der Effizienz und Entscheidungsfindung.

Optimizing transportation systems has become essential for addressing today's logistics challenges. As global trade grows consistently and consumer expectations for faster and on-time deliveries rise, companies face increasing pressure to deliver quickly and cost-efficiently. This thesis addresses four routing problems: First, the single truck and trailer routing problem with satellite depots (STTRPSD), which can be used to model the problem of optimizing routes of mail carriers in the last mile delivery stage of a mail delivery network. Second, the vehicle routing problem with depot operation constraints (VRP-DOC), which additionally includes the assignment of households to mail carriers in the route planning and incorporates depot operations. Third, the angular-metric traveling salesman problem (ATSP) and the angular-distance-metric traveling salesman problem (ADTSP), relevant for minimizing sharp turns in the routing of heavy vehicles. Last, the capacitated team orienteering problem with time-dependent and piecewise-linear score functions (C-TOP-TDPLSF) often used in the context of customer-focused deliveries. To efficiently solve realistically sized instances of these NP-hard problems, we use metaheuristics like iterated local search or tabu search. Each heuristic is designed to incorporate problem specific features to enhance their performance. Extensive computational experiments show significant improvements compared to state-of-the-art algorithms from the literature and practices implemented in the real world. For the STTRPSD, we use its natural decomposition into subproblems in the design of our heuristic, that reduces the travel times of real-world solutions currently used in practice by our industry partner on average by approximately 2%. Addressing the VRP-DOC, our work is one of the first ones to incorporate depot operations into the route planning. In our algorithm, we use problem-specific neighborhood operators and incorporate the instance structure of real-world street networks. On real-world instances, our heuristic is not only reducing total travel times by approximately 6.5% compared to the currently implemented solutions from our industry partner but also provides significantly simpler solutions with regards to the letter handling operations at the depot, highlighting the operational benefits of considering depot operation constraints. For the ATSP and the ADTSP, we incorporate the geometric features of the problems. Our heuristic provides a good trade-off between runtime and solution quality, and we find new best-known solutions for around 80% of benchmark instances for which an optimal solution was not available. For the C-TOP-TDPLSF, our heuristic is tailored to the specific structure of the score function. Through in-depth analysis of the obtained solutions, we provide practical recommendations to companies, offering insights into improving operational efficiency and decision-making.

OpenAccess:
PDF
(additional files)