New heuristics for routing problems in the e-commerce era

Löffler, Maximilian Friedrich Emil; Boysen, Nils; Schneider, Michael David

doi:HT030755084

New heuristics for routing problems in the e-commerce era

Löffler, Maximilian Friedrich Emil^RWTH*

2024

Verantwortlichkeitsangabevorgelegt von Maximilian Friedrich Emil Löffler

ImpressumAachen : RWTH Aachen University 2024

Umfang1 Online-Ressource : Illustrationen

Dissertation, Rheinisch-Westfälische Technische Hochschule Aachen, 2024, Kumulative Dissertation

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak08

Hauptberichter/Gutachter
Schneider, Michael David (Thesis advisor)^RWTH* ; Boysen, Nils (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2024-04-24

Online
DOI: 10.18154/RWTH-2024-05319
URL: https://publications.rwth-aachen.de/record/986695/files/986695.pdf

Einrichtungen

Deutsche Post Lehrstuhl für Optimierung von Distributionsnetzwerken (813210)

Inhaltliche Beschreibung (Schlagwörter)
heuristics (frei) ; logistics (frei) ; optimization (frei) ; routing (frei) ; warehousing (frei)

Thematische Einordnung (Klassifikation)
DDC: 330

Kurzfassung
Diese Dissertation liefert methodische Beiträge zu einer Auswahl von Tourenplanungsproblemen von hoher aktueller Relevanz. Sie enthält sechs Artikel, die alle in renommierten internationalen Fachzeitschriften veröffentlicht wurden. Kapitel 1 beginnt mit einer kurzen Einführung, die die Motivation für die durchgeführte Forschung sowie eine Übersicht über die betrachteten Problemtypen und Forschungsziele bietet. Die Kapitel 2 und 3 befassen sich mit dem Capacitated Location-Routing Problem (CLRP). Der im Kapitel 2 vorgestellte baumbasierte Suchalgorithmus (TBSA) erreicht auf den gängigen Benchmark-Instanzen bessere Lösungsqualität bei kürzeren Laufzeiten als alle bisher veröffentlichten heuristischen Lösungsmethoden. Kapitel 3 schlägt einen hybriden Algorithmus vor, der eine GRASP-Phase, die einen Variable Nieghborhood Descent zur Verbesserung der Standordentscheidung nutzt, mit einer Variable Neighborhood Search (VNS) in der Routing-Phase kombiniert. Der Einfluss der algorithmischen Komponenten auf Lösungsqualität und Laufzeit wird anhand der gängigen CLRP-Benchmark-Instanzen analysiert. Der im Kapitel 4 vorgestellte Artikel befasst sich mit der Tourenplanung von elektrischen Nutzfahrzeugen. Der Artikel schlägt eine Variante des Electric Vehicle Routing Problems with Time Windows and Single Recharges (EVRPTWS) vor und präsentiert einen Hybrid aus Large Neighborhood Search und granularer Tabusuche, um qualitativ hochwertige Lösungen für Instanzen mit bis zu 100 Kunden zu generieren. In zusätzlichen Studien werden das Kosteneinsparungspotenzial von Teilaufladungen im Vergleich zu vollständigen Aufladungen der Fahrzeugbatterien unter Berücksichtigung von Zeitfensterbeschränkungen, sowie die Faktoren, welche dieses Kosteneinsparungspotenzial beeinflussen, untersucht. Die Kapitel 5 und 6 befassen sich mit Tourenplanungsproblemen in robotisierten "Picker-to-Parts"-Lagersystemen, die durch einen hohen Automatisierungsgrad gekennzeichnet sind. Das in Kapitel 5 betrachtete System zielt darauf ab, unproduktive Wegzeit zu reduzieren, indem jedem Kommissionierer ein fahrerloses Transportsystem zugeordnet wird. Es wird ein exakter Polynomialzeitalgorithmus für den Fall einer vorgegebenen Kommissionierauftragsreihenfolge vorgestellt. Für den Fall, dass die Auftragsreihenfolge offen ist, werden, nach einer Transformation des Problems in ein Standard-TSP, der hocheffektive TSP-Solver Concorde und der Lin-Kernighan-Algorithmus von Helsgaun (LKH) verwendet. Die numerischen Studien zeigen, dass die Wegzeit der Kommissionierer im Vergleich zu einem klassischen System ohne Roboterunterstützung um etwa 20% reduziert werden können. Kapitel 6 erweitert die Problemstellung dahingehend, dass Roboter nicht mehr fest einem einzelnen Kommissionierer zugeordnet sind. Das Ziel ist eine Koordination von Kommissionierern und Robotern, die die Gesamtbearbeitungszeit für eine gegebene Menge von Kommissionieraufträgen minimiert. Es wird eine heuristische Lösungsmethode vorgeschlagen, die den Anforderungen großer Fulfillment-Center im Bereich des Onlinehandels gerecht wird und Instanzen mit bis zu 1500 Kommissionierpositionen mit überzeugender Lösungsqualität und kurzer Laufzeit löst. Die Ergebnisse zeigen, dass im Vergleich zur Strategie aus Kapitel 5 deutlich verbesserte Durchlaufzeiten erwartet werden können. Das im Kapitel 7 vorgestellte Verfahren zielt darauf ab, das Infektionsrisiko bei manueller Kommissionierung zu verringern. Dies kann erreicht werden, indem eine Reihe von Kommissioniertouren so ausgeführt wird, dass die Zeit, die Kommissionierer gleichzeitig in denselben Kommissioniergängen verbringen, minimiert wird, ohne die Wegzeit zu erhöhen. Dies wird durch Ausnutzung von Freiheitsgraden erreicht, die dadurch entstehen, dass Kommissioniertouren Zyklen enthalten, die in beide Richtungen durchlaufen werden können. Das resultierende Problem der Kommissioniertourausführung wird als gemischt-ganzzahliges Programm formuliert und eine effiziente Iterated Local Search (ILS) zur Lösung vorgeschlagen. In umfangreichen numerischen Studien kann eine durchschnittliche Reduktion der gesamten zeitlichen Überlappung um 50% erreicht werden. Abschließend fasst Kapitel 8 die vorgestellten Artikel zusammen, wiederholt die Kernbefunde sowie Managementeinblicke und gibt zeigt Richtungen für zukünftige Forschung auf.

This thesis provides methodological contributions to a selection of routing problems of high contemporary relevance. It contains six articles, all of which have been published in reputable international journals. Chapter 1 begins with a short introduction, providing the motivation for the conducted research as well as an outline of the considered problem types and research goals.Chapters 2 and 3 address the capacitated location routing problem (CLRP). The tree-based search algorithm (TBSA) presented in Chapter 2 is able to dominate all previously published heuristic solution methods on the commonly used benchmark instances, meaning it achieves better solution quality within shorter run-times. Chapter 3, proposes a hybrid algorithm combining a GRASP phase that uses a variable neighborhood descent for local improvement in the location stage and a variable neighborhood search (VNS) in the routing stage. The impact of the algorithmic components on solution quality and runtime is analyzed on the commonly used CLRP benchmark instances.The article presented in Chapter 4 addresses the routing of electric commercial vehicles (ECVs). The paper proposes a variant of the electric vehicle routing problem with time windows featuring single recharges, called EVRPTWS and presents a hybrid of large neighborhood search and granular tabu search to generate high-quality solutions for instances with up to 100 customers. Additional studies investigate the cost savings potential of partial recharges in comparison to full recharges in the presence of time-window constraints, and examine the factors that influence this cost saving potential.Chapters 5 and 6 address routing problems in robotized picker-to-parts warehousing systems, characterized by a high level of automation. The system considered in Chapter 5 aims at reducing unproductive walking times by complementing each picker with an automated guided vehicle (AGV) during the picking process. An exact polynomial time routing algorithm is presented for the case of a given picking order sequence. For the case in which the order sequence is open, we make use of the highly effective TSP solver Concorde and the Lin-Kernighan algorithm of Helsgaun (LKH), which can be applied after a transformation of the problem into a standard TSP. The numerical studies reveal that picker walking can be reduced by about 20% compared to a traditional setting.Chapter 6 extends the problem setting as robots are no longer fixedly assigned to a single order picker. The aim is a coordination of pickers and robots that minimizes the makespan for a given set of picking orders. A heuristic solution method is proposed that can handle the requirements of large e-commerce fulfillment centers and solves instances with up to 1500 picking positions with convincing solution quality and runtime. We find that, compared to the strategy from Chapter 5, largely improved makespans can be expected.The article presented in Chapter 7 aims to mitigate the risk of infection in manual order picking. This can be achieved by executing a set of picking tours in a way that minimizes the time pickers simultaneously spend in the same picking aisles without increasing total travel distance. This is achieved by exploiting the degrees of freedom induced by the fact that picking tours contain cycles which can be traversed in both directions. We formulate the resulting picking tour execution problem as a mixed integer program and propose an efficient iterated local search heuristic to solve it. In extensive numerical studies, an average reduction of 50% of the total temporal overlap between pickers can be achieved without increasing the overall routing costs.Finally, Chapter 8 concludes the presented articles, restating the core findings and managerial insights. In addition, possible directions for future research are provided.

OpenAccess:
PDF
(zusätzliche Dateien)