| 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 I 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. 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. The second category of problems includes the min-max k-Traveling Salesmen Problem on a Tree (k-TSPT) and its variants. We have provided an answer to an open question on whether or not the min-max 2-TSPT is strongly NP-hard 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. The third category of problems includes the k-depot Traveling Salesmen Problem ( k-depot TSP) and its variants. 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.;Keywords: min-max, approximability, vehicle routing problem. |
