Optimierung von innovativen Zustellkonzepten auf der letzten Meile

Abstract

Die Forschung an innovativen Zustellkonzepten für die letzte Meile der Logistik hat in den vergangenen Jahren erhebliche Fortschritte gemacht. Autonome Zustellkonzepte mit Zustellrobotern und Paketdrohnen werden weltweit erprobt oder bereits eingesetzt. Durch ihre Autonomie ermöglichen sie Zustellungen innerhalb vorgegebener Zeitfenster. Allerdings ist ihre Transportkapazität begrenzt, sodass häufig Pendeltouren zwischen Mikrodepots und Empfängern erforderlich sind. Die beiden Transportmittel unterscheiden sich grundlegend in ihrer Fortbewegung und Geschwindigkeit. Paketdrohnen fliegen mit hoher Geschwindigkeit auf direktem Weg durch die Luft, während Zustellroboter sich mit Schrittgeschwindigkeit auf Gehwegen bewegen. Bei Zustellrobotern ist die begrenzte Akkukapazität besonders relevant, da das Aufladen Zeit erfordert. Paketdrohnen hingegen erhalten bei ihrer Rückkehr ins Mikrodepot einen geladenen Akku. Aufgrund der hohen Geschwindigkeit steht bei Drohnen der Energieverbrauch im Fokus. Beide Transportmittel werden daher im Rahmen dieser Dissertation separat betrachtet. Der Fokus dieser Arbeit liegt auf der Optimierung der letzten Meile unter Verwendung von Zustellrobotern und Paketdrohnen. Der Zustellprozess beginnt mit dem Transport der Sendungen von einem Depot in das Zustellgebiet, wo sie in Mikrodepots zwischengelagert werden. Anschließend erfolgt die Zustellung innerhalb definierter Zeitfenster mithilfe von Zustellrobotern oder Paketdrohnen. Nach jeder Zustellung kehren die Transportmittel zu einem Mikrodepot zurück, um eine neue Sendung aufzunehmen. Für Zustellroboter wird ein Algorithmus zur Auftragsverteilung entwickelt, der die Anzahl zugestellter Sendungen maximiert. Dabei steht eine Flotte von Robotern zur Verfügung. Die Zustellung muss innerhalb der vorgegebenen Zeitfenster der Empfänger erfolgen und der Akku der Roboter muss an den Mikrodepots wieder aufgeladen werden. Zur Lösung kommt ein Branch-and-Price-Algorithmus zum Einsatz. Dazu wird zuerst das Teilproblem mit einem einzelnen Roboter und einer beliebigen, festen Empfängerreihenfolge betrachtet. Hierfür gilt es zu entscheiden, welche Mikrodepots zwischen den Empfängern angefahren werden, wie lange die Ladevorgänge dauern und ob überhaupt eine zulässige Lösung existiert. Dazu wird ein polynomieller Algorithmus entwickelt, dessen Ergebnisse in den Branch-and-Price-Algorithmus integriert werden. Laufzeitexperimente zeigen, dass Instanzen mit bis zu 60 Empfängern gelöst werden können. Für Paketdrohnen ist die Problemstellung vergleichbar, wobei der Fokus auf der Minimierung des Gesamtenergieverbrauchs liegt. Auch hier wird zunächst eine feste Empfängerreihenfolge für eine einzelne Drohne betrachtet. Die Berechnung der optimalen Geschwindigkeiten erfolgt mithilfe eines aus der Literatur bekannten Algorithmus, der in polynomieller Zeit arbeitet. Im Rahmen dieser Arbeit wird dieser Algorithmus erweitert, um Mindest- und Höchstgeschwindigkeiten zu berücksichtigen. Darauf aufbauend wird ein weiterer Algorithmus entwickelt, der alle relevanten Belieferungszeitpunkte des letzten Empfängers einer gegebenen Kundenreihenfolge sowie die optimalen Geschwindigkeitsvektoren und Energieverbräuche berechnet. Beide Verfahren fließen in einen Branch-and-Price-Algorithmus ein, bei dem die berechneten Ankunftszeiten zur Formulierung einer Dominanzregel verwendet werden. Der entwickelte Algorithmus übertrifft bestehende Verfahren signifikant und ist im Durchschnitt über 17,5-mal schneller. Abschließend wird eine Simulationsstudie vorgestellt, die die Paketzustellung mit Zustellrobotern und Paketdrohnen abbildet und den Mehrwert der Optimierungsansätze in verschiedenen Szenarien demonstriert.

The research in the field of innovative delivery concepts for the last mile of logistics has made significant progress in recent years. Autonomous delivery solutions using delivery robots and parcel drones are being tested or have already been deployed worldwide. Thanks to their autonomy, these transport systems enable deliveries within predefined time windows. However, their transport capacity is limited, necessitating frequent shuttle trips between micro depots and recipients. The two transport systems differ fundamentally in terms of movement and speed. Parcel drones fly at high speeds on a direct path through the air, while delivery robots move at walking pace along sidewalks. For delivery robots, limited battery capacity is particularly critical, as recharging takes time. Parcel drones, on the other hand, return to the micro depot with a charged battery. Due to their high speed, energy consumption is a key factor. For this reason, both innovative delivery concepts are examined separately in the context of this dissertation. The focus of this thesis is the optimization of last-mile delivery using delivery robots and parcel drones. The delivery process begins with the transport of parcels from a central depot to the delivery area, where they are temporarily stored in micro depots. Deliveries are then carried out within specified time windows using delivery robots or parcel drones. After each delivery, the vehicle returns to a micro depot to pick up the next parcel. For delivery robots, an assignment algorithm is developed to maximize the number of deliveries. A fleet of robots is available for this purpose. Deliveries must take place within the specified time windows of the recipients, and the robots must recharge their batteries at the micro depots. A Branch-and-Price algorithm is employed to solve the problem. To this end, a subproblem is first considered: a single robot with an arbitrary, fixed customer sequence. The key decisions include which micro depots to visit between deliveries, how long to charge at each stop, and whether a feasible solution exists at all. A polynomial-time algorithm is developed for this subproblem, and its results are integrated into the overall Branch-and-Price framework. Runtime experiments show that this approach efficiently solves instances with up to 60 recipients. The problem for parcel drones is comparable, although the focus here is on minimizing total energy consumption. Again, a fixed customer sequence for a single drone is considered initially. The optimal speeds are computed in polynomial time using a known algorithm, which is extended in this work to incorporate minimum and maximum speed limits. Building on this, an additional algorithm is developed to determine all relevant delivery times for the last recipient of a given customer sequence, as well as the corresponding optimal speed vectors and energy consumption values. Both procedures are integrated into a Branch-and-Price algorithm, in which the computed arrival times are used to formulate a dominance rule. The developed algorithm significantly outperforms existing methods and is, on average, more than 17.5 times faster. Finally, a simulation study is presented that models parcel delivery using delivery robots and parcel drones, demonstrating the added value of the proposed optimization approaches across various scenarios.