On the solution of classical and synchronized routing problems
Date issued
Authors
Editors
Journal Title
Journal ISSN
Volume Title
Publisher
License
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.