Approximability of vehicle routing problems

Abstract

Vehicle Routing Problems (VRPs) can be described as a class of combinatorial optimization problems that seek to determine a set of feasible routes for a fleet of vehicles to serve customers at different locations, so as to optimize certain objective functions. Due to the growth of the transportation and logistics industries, many new VRPs are emerging in different contexts. Since they are usually NP-hard, these problems call for the design of approximation algorithms that achieve constant approximation ratios. Moreover, in the existing literature there are several VRPs whose constant-ratio approximation algorithms are either unknown or improvable. Therefore, in this thesis we study the approximability of the following three categories of VRPs, by either developing the constant-ratio approximation algorithms or deriving approximation hardness results. The first category of problems includes the min-max Path Cover Problem (PCP) and its variants, which aim to determine a set of k paths for k vehicles to serve customers in a metric undirected graph, so that the maximum total edge and vertex weight among all paths is minimized. This category of problems was introduced in the literature in the context of "vehicle routing for relief efforts". Since they are relatively new in the literature, approximation algorithms are almost unknown. We consider four variants of the min-max PCP, in which the vehicles have either unlimited or limited capacities, and they start from either a given depot or any depot of a given depot set. We have developed approximation algorithms for these variants, which achieve approximation ratios of max{3 - 2/k, 2}, 5, max{5 - 2/k, 4}, and 7, respectively. For these four variants of PCP, we have also proved their first approximation hardness results, by showing that unless P=NP, it is impossible for them to achieve approximation ratios less than 4/3, 3/2, 3/2, and 2, respectively. The second category of problems includes the min-max k-Traveling Salesmen Problem on a Tree (k-TSPT) and its variants. With k a given positive integer denoting the number of salesmen, which is independent of the input size, the min-max k-TSPT aims to determine a set of k tours for the k salesmen to serve all the customers that are located in a tree, such that the k tours all start from and return to the depot, so as to minimize the maximum length of the k tours. In the literature, the question as to whether or not the min-max 2-TSPT yields a pseudo-polynomial time exact algorithm has remained open for a decade. We have provided a positive answer to this open question by developing a pseudo-polynomial time exact algorithm using a dynamic programming approach. Based on this dynamic program, we have further developed a fully polynomial time approximation scheme for the problem. Moreover, we have generalized these algorithms for the min-max k-TSPT for any given constant k ≥ 2, and we have extended them to other variants. The third category of problems includes the k-depot Traveling Salesmen Problem (k-depot TSP) and its variants. The k-depot TSP is an extension of the single-depot TSP, and it aims to determine a set of k tours for the k vehicles to serve all the customers on a metric undirected graph so that the total length of the tours is minimized. We have shown that a non-trivial extension of the well-known Christofides' heuristic has a tight approximation ratio of 2 - 1/k, which is better than the existing 2-approximation algorithm available in the literature. This result is significant when k is small. Moreover, we have demonstrated how this algorithm can be applied to the development of approximation algorithms for other multiple-depot VRPs.