Vehicle Routing in Theory and Practice

Abstract

In this thesis, we study combinatorial optimization problems that arise in logistics and can be summarized under the name vehicle routing. We tackle these problems from two different points of view. First, we study their computational complexity. All problems we look at are generalizations of the famous traveling salesperson problem, TSP for short: a driver needs to visit certain customers (e.g., to deliver goods) and return to the starting point at the end of the tour. The goal is to compute a tour of minimum length (or cost). We provide improved approximation guarantees for two well-known natural generalizations of this problem. Both variants are of high relevance in logistics. In the first variant, known as the prize-collecting TSP, we are allowed to reject customer requests, which comes at customer-specific penalties. The goal is then to optimize the sum of tour length and total penalty for rejected inquiries. We improve the best known approximation ratio of roughly 1.914 (due to Goemans) to 1.599, which significantly reduces the gap between the approximability of the TSP and its prize-collecting variant. The second variant of the TSP for which we provide improved approximation guarantees is the capacitated vehicle routing problem. In many applications, the goods that need to be delivered to customers exceed the capacity of a single vehicle. Hence, we need to distribute the goods to several vehicles and compute an efficient route for each of these such that the sum of tour lengths is minimized. We improve and simplify an approach that was initiated in my master’s thesis, which led to the first improvement of the approximation ratio of the classical tour partitioning approach. We obtain a better approximation ratio for several major variants of the problem. Second, we study vehicle routing problems from a practical point of view. On typical real-world instances, the approximation algorithms discussed in the first part of this thesis are not practical, neither in terms of solution quality nor in terms of running time. Moreover, we need to satisfy various additional constraints such as time windows, working time limits, and limited heterogeneous vehicle fleets. We present an algorithm called BonnTour that covers a wide class of vehicle routing problems and provides high-quality solutions in reasonable computation time. On numerous benchmarks, the cost of the computed solution comes close to the optimum or the best known. On some benchmark instances, we present new best known solutions. Our algorithm takes into account time-dependent travel time fluctuations that are caused by congestion, which leads to much more reliable tour plans. We provide a new set of realistic and large-scale benchmark instances for vehicle routing with time-dependent travel times to foster future research on this problem. BonnTour is developed in cooperation with our industry partner Greenplan, and is used on a daily basis to solve real-world vehicle routing problems for various companies.