On the solution of classical and synchronized routing problems

Abstract

The focus of this thesis is to contribute to the development of exact and heuristic solution methods for classical and synchronized routing problems. In particular, we present a problem-tailored iterated local search (ILS) algorithm to solve the Generalized Traveling Salesman Problem (GTSP) and derive full-fledged branch-price-and-cut (BPC) algorithms to solve three routing problems with synchronization constraints, namely the Last-Mile Delivery Problem with Scheduled Lines, the Vehicle Routing Problem with Drones, and the Vehicle Routing Problem with Drones and Time Windows. In all approaches, we employ the individual, problem-specific structure to model effective solution methods. For the GTSP, we develop three new GTSP neighborhoods and combine them with existing neighborhoods from the literature within the local search part of the ILS. For all routing problems with synchronization constraints, the focus is on designing effective labeling algorithms to solve the corresponding pricing problems and on strengthening the linear relaxation of the master problem with valid inequalities. In extensive computational analyses, we consider different objective functions, provide managerial insights, and prove the usefulness of the proposed methods.

Die vorliegende Dissertation leistet einen Beitrag zur Entwicklung von exakten und heuristischen Lösungsverfahren für verschiedene Tourenplanungsprobleme. Insbesondere werden ein maßgeschneideter Iterated-Local-Search-Algorithmus (ILS) zur Lösung des Generalized Traveling Salesman Problem (GTSP) vorgestellt und vollwertige Branch-Price-and-Cut-Algorithmen (BPC) zur Lösung der folgenden Tourenplanungsprobleme mit Synchronisationsbedingungen entwickelt: das Last-Mile Delivery Problem with Scheduled Lines, das Vehicle Routing Problem with Drones und das Vehicle Routing Problem with Drones and Time Windows. Für alle genannten Probleme wird die individuelle, problemspezifische Struktur ausgenutzt, um leistungsfähige Algorithmen zu entwickeln. Für das GTSP werden drei neue GTSP-Nachbarschaften vorgestellt und mit bestehenden Nachbarschaften aus der Literatur innerhalb der lokalen Suche der ILS kombiniert. Für alle weiteren Probleme liegt der Schwerpunkt auf der Entwicklung effektiver Labeling-Algorithmen zur Lösung der problemspezifischen Pricing-Probleme sowie auf der Stärkung der linearen Relaxation des Master-Problems mittels gültiger Ungleichungen. In umfangreichen Rechenstudien werden verschiedene Zielfunktionen betrachtet, betriebswirtschaftliche Erkenntnisse gewonnen und die Wirksamkeit der vorgestellten Algorithmen belegt.