Approximation algorithms for vehicle routing problems

The vehicle routing problem is a generalization of the traveling salesman problem, but is a special case of the pickup and delivery problem. In this problem, we are give $p$ vehicles and a complete graph $G$, and the objective is to find a separate tour for each vehicle with respect to minimizing or maximizing some objective function, such as the total cost of the tours. This problem has direct relevance to the industry-related research we are pursuing. The vehicle routing problem has numerous variations, and has been extensively investigated by many researchers. Various techniques, such as linear programming, local search, and even clustering, have been applied or invented to solve these problems. However, as a well recognized method of dealing with $NP$-$hard$ problems, good approximation algorithms have not been well explored for this problem. In this project, we want to devise approximation algorithms for the vehicle routing problems with two constraints, one is the vehicle capacity constraint and the other is the job time window constraint.

In the capacitated vehicle routing problem, each vehicle has a capacity constraint, where it can be applied in different ways. In the $k$-delivery problem, $n$ identical pegs and also $n$ identical slots are located in a undirected complete graph $G$, a vehicle which can carry at most $k$ pegs at a time is going to deliver all pegs to slots, and the objective is to minimize the total length of the tour. And in the black and white traveling salesman problem, we have a white node set and black node set also in a undirected complete graph. The capacity constraint forces that in the final tour, no more than $k$ white vertices can appear between two consecutive black vertices. The vehicle routing problem with capacity constraint can be formulated as a black and white TSP. For the $k$-delivery problem, Charikar et. al. [28] got an approximation algorithm with a ratio 5. For the black and white traveling salesman problem, we designed an approximation algorithm with a ratio 4 [21]. The techniques used for the two problems are quite similar, they all adopt a strategy of first obtaining a TSP, then cutting the TSP into pieces, and finally attach these pieces by matching edges. This strategy is used successfully by Chalasani and Motwani in [29], where they got the first constant factor approximation algorithm for the general $k$-delivery problem, and also an algorithm with ratio 2 for the 1-delivery problem by using the matroid intersection.

In the vehicle routing problem with time windows each job has a time window, which is defined by a starting time, an ending time, and maybe also a handling time. The best known approximation algorithm for this type of problems in general graphs with arbitrary time windows is given by Bansal et. al. [2]. In their paper, they considered the deadline-TSP problem, where each node in a general metric $G$ is associated with a deadline $D(V)$, and given a start $r$, find a path starting at $r$ visits as many nodes as possible by their deadlines; and also the more general vehicle routing problem with time windows problem, where each node also has a release time $R(V)$, and the goal is to find a path visits as many nodes as possible within their time windows. They gave a $log(n)$ approximation algorithm for the deadline-TSP problem, and also a $log^2(n)$ extension for the latter problem. They used the dynamic programming approach extensively, and also a subroutine $P2P$ which is a 3-approximation algorithm for the point to point orienteering problem. The orienteering problem is to find a path with the maximum reward starts from a fixed node and not exceeds a hard length limit in a graph $G$, where each node in $G$ has a predefined reward. The complexity of these approximation algorithms are quite high, e.g. the $O(log(n))$ approximation requires $O(n^6)$ calls to the subroutine $P2P$, and this subroutine will call $O(n^2)$ times another subroutine which solves another subproblem in [22].

The orienteering problem is related with the $k$-MST problem, which is defined as finding a minimum cost tree spanning exact $k$ vertices in a general graph. The 2-approximation algorithm for the $k$-MST problem uses a general primal-dual technique which is proposed by Goemans and Williamson [38] for general constraint forest problems. This is a powerful technique which is capable of solving a large class of hard problems, and it's particularly suitable for solving the vehicle routing problem. Thus we will try to use the techniques of matching, the primal-dual method, dynamic programming, scaling, etc., or even discover new techniques to devise an approximation algorithm for the capacitated vehicle routing problem with time windows. In this process, we also believe the following directions are important for the project.

First, we want to consider the approximation algorithms for the vehicle routing problem on restricted graphs. For example, we can choose to work on tree graphs, cactus graphs, etc. As mentioned in [3], an approximation algorithm on a tree with the ratio $\alpha$ implies an $\alpha{log(n)}$ approximation in general metrics. Although some approximation algorithms for some version of the vehicle routing problem with releasing time or ending time have been proposed, e.g., the 2-approximatin algorithm by Karuno et. al. [41] for the vehicle routing problem with multiple vehicles where each vertex is associated a releasing time and a handling time, the problem with both releasing and ending times remains unsolved in path and tree graphs.

Second, we want to investigate some variations of this problem on the restricted and also general graphs. For example, we can devise approximation algorithms for the cycle cover problem with different constraints. The cycle cover problem with the constraint that each cycle contains at least $k$ vertices can be approximated within twice of the optimum [38], but no approximation algorithms is known for the same problem with an additional constraint that the total number of cycles $=p$ or $\leq{p}$.

Third, we can also try to approximate different metrics for the problems, or consider them in directed graphs. For example, we can choose to minimize the maximum length of a tour among all $p$ vehicles, or to minimize the number of vehicles used to serve all customers, or to minimize the cost of violating the time windows. It is easy to see that for different metrics and asymmetric edge costs, new approximation algorithms are needed for all problems mentioned above.