A heuristic framework for dynamic vehicle routing with site-dependent constraints

Abstract

Im Rahmen dieser Arbeit wurde ein auf variable Nachbarschaftssuche (VNS) basierender Algorithmus entwickelt, um eine Variante des Site-Dependent Vehicle Routing Problem with Time Windows (SDVRPTW) zu lösen. Die Besonderheit dieser Variante ist, dass zum einen nicht alle Kunden von allen Fahrzeugen beliefert werden dürfen und zum anderen, dass jeder Kunde nur innerhalb eines vorgegebenen Zeitfensters beliefert werden darf. Motivation dieser Arbeit war weitere für die Praxis relevante Eigenschaften zu berücksichtigen, wie zum Beispiel große Test-Instanzen mit einen Planungshorizont über mehrere Wochen. Der Planungshorizont wird dynamisch um jeweils einen Tag verschoben, sodass neue Kundenaufträge hinzugefügt werden und alte Aufträge aus dem Planungshorizont herausfallen. Ein anderes Szenario wäre, dass sich ein Zeitfenster von einem Kunden ändert und dieser neu eingeplant werden muss oder, dass ein Kunde nur von einem bestimmten Fahrzeug beliefert werden kann. In dieser Arbeit wurden sowohl exakte als auch heuristische Methoden für das beschriebene Problem entworfen. Die heuristische Methode basiert auf der VNS Metaheuristik, welche systematisch und teilweise randomisiert nach besseren Lösungen sucht. Eine Besonderheit ist, dass der Algorithmus ohne einen expliziten Konstruktionsalgorithmus auskommt, da die benutzten Nachbarschaften in der Lage sind, eine Lösung zu erzeugen bzw. zu erweitern. Die VNS braucht daher keine Initial-Lösung, sondern kann mit einer leeren Lösung oder einer Teillösung starten. Die Ergebnisse des entwickelten Algorithmus wurden mit den publizierten Ergebnissen von der Literatur verglichen. Es lässt sich zeigen, dass die Ergebnisse robust sind sowie eine hohe Lösungsgüte besitzen. Des Weiteren, wurde eine auf Techniken der mathematischen Programmierung basierende exakte Methode entwickelt. Das zugrundeliegende Modell basiert auf einer Miller-Tucker-Zemlin Formulierung, die durch die dynamische Separierung von weiteren Ungleichungen gestärkt wird. Diese exakte Methode ist in der Lage, kleine Problem-Instanzen des SDVRPTW zu lösen. Trotz des Schwerpunktes auf der operativen Anwendbarkeit in der Praxis im dynamischen Kontext erreichen die Algorithmen nahe state-of-the-art Ergebnisse auch auf akademischen Benchmark-Instanzen für die statische Problemvariante.

In this work a Variable Neighborhood Search (VNS) algorithm is developed to tackle an extension of the Site-Dependent Vehicle Routing Problem with Time Windows (SDVRPTW). That is, not all vehicles are allowed to visit all customers and each customer could only be serviced within a specific time window. The motivation was to design algorithms which are able to solve large real-world instances which have a planning horizon over several weeks. The planning horizon is shifted day by day, such that customers continuously leave and enter the planning horizon. The algorithms must handle cases where for instance customers are additionally added to the original problem. Another scenario may be that a customer's time window changed and the customer must be rescheduled or there may be situations where a customer should only be serviced by a particular vehicle. Within this thesis, both, heuristic and exact methods are developed for the considered problem. The heuristic method is based on VNS, which searches neighboring solutions of a current incumbent solution in a systematic, but also randomized way. One of the main characteristics of the presented algorithm is that it does not require an explicit construction algorithm, since the neighborhoods are able to construct and enhance solutions. The results of the proposed algorithm are compared to recent results published in the literature for some benchmark instances and it is shown that the algorithms have good overall performance regarding robustness, solution quality and time. In addition to the heuristic VNS approach, a mathematical programming formulation based on Miller-Tucker-Zemlin inequalities is presented. Moreover, the approach is extended to a branch-and-cut algorithm by separating set inequalities to eliminate invalid subtours. These exact methods are able to solve small instances of the SDVRPTW. Despite the strong focus on applicability for real world operational use in context of the dynamic problem variant, the algorithms also closely achieve state-of-the-art results on academic benchmark instances for the static problem variant.