A Priori Approaches to Vehicle Routing in Theory and Practice

Abstract

This thesis is devoted to combinatorial optimization problems that arise in logistics. In particular, we deal with problems that need to be solved before having complete information about the exact setting. We approach these problems from two directions. In the first part, we look at theoretical problems arising in the context of logistical tasks. They are generalizations of the Traveling Salesperson Problem (with triangle inequality), short TSP. In the TSP, we are given a finite set V and costs c : V² → R≥0 fulfilling the triangle inequality. We ask for a cheapest tour visiting all elements of V and returning to the start point. In the A Priori TSP, we are additionally given activation probabilities p : V → [0, 1]. The goal is to find a tour visiting all customers in V minimizing the expected cost when cut short to the active customers. In our model, each customer v ∈ V is active independently with probability p(v). Since the A Priori TSP contains the TSP, it is NP-hard, which is why we consider approximation algorithms. For the Symmetric A Priori TSP (where we demand c(v, w) = c(w, v) for all v, w ∈ V ), we obtain a randomized approximation algorithm with approximation ratio less than 3.1, improving upon the previously best known ratio of 3.5. We complement this with a lower bound example proving that one cannot achieve an approximation ratio better than 3.049 when using a sampling approach. Furthermore, we obtain a deterministic algorithm with approximation ratio less than 5.9, improving upon the previously best known ratio of 6.5. For the general (asymmetric) A Priori TSP, we give the first non-trivial approximation al- gorithm, obtaining an approximation ratio of O(sqrt(|V|)).Moreover, we provide an algorithm with quasi-polynomial running time that computes a solution with a poly-logarithmic approximation ratio. The second part of this thesis is about solving tour planning problems in practice. The Research Institute for Discrete Mathematics of the University of Bonn, in cooperation with our industry partner Greenplan, has developed a software package called “BonnTour”. One key feature of BonnTour is that it works with time-dependent travel times. In this thesis, we take a closer look at some pre-processing steps performed in BonnTour: Contraction Hierarchies enable us to quickly answer the question how long it takes to get from one address to another, even though they are computed from the road graph before we know the addresses that need to be visited. We present improvements made to the implementation of Contraction Hierarchies in BonnTour, allowing us to use them in practice on a daily basis. In the Address Mapping and Shared Parking pre-processing, we find good parking positions at addresses before knowing from which direction we arrive there. We conclude the thesis with the presentation of experimental results, giving empirical proof that the techniques discussed in this thesis lead to good outcomes.