Approximation algorithms of VRP

The vehicle routing problem is a generalization of the traveling salesman problem, but is a special case of the pickup and delivery problems. In this problem, we are given $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. An extensive coverage of VRP can be found in [52]

Techniques used

We have made significant progress in the design of approximation algorithms for various forms of vehicle routing problems. For two models of CVRPPD, namely the Dial-a-Ride problem and the $k$ -delivery TSP on paths and trees, we propose a strategy called the come back rule. Our algorithms are all based on this strategy. Under the come back rule[34], the vehicle would not be allowed to cross a particular edge $e$ if some condition is met. Such a condition varies for different problems. The existing method for these problems, follows the strategy (first introduced in [17]) that, the vehicle would continue to pick up (deliver) items if possible. The come back rule differs from this method in that, under the come back rule the vehicle may not deliver its load immediately, but come back and pick up more items for a better schedule. As a consequence, on its way back, the vehicle may traverse several edges without servicing any jobs, even when it is carrying a large load. This is somewhat contrary to our intuition. For two problems in the category of MVRP, namely MDCVRP and MVSP in trees, we propose a new way of using dynamic programming to design constant-factor approximation algorithms. Under this approach, dynamic programming is used to decompose a problem instance $P$ indirectly to a set of disjoint subproblems. As it is not possible to try all the configurations of the subproblems by directly obtaining solutions for $P$ , we instead find another problem $P'$ and locate a set $S$ of disjoint subproblems by using dynamic programming to solve $P'$ in the underlying graph. We then work on approximation algorithms for the subproblems in $S$ . It is guaranteed that a good approximation for $P$ can be obtained by approximating these subproblems well. To achieve this, we choose $P'$ in a way such that $P'$ satisfies some property inherent in the optimal solution of $P$ . $P'$ is much simpler and can be solved well by using dynamic programming in the underlying tree. More importantly, as $P'$ is a relaxation of $P$ , after solving $P'$ we not only find a lower bound on $OPT_P$ , but also obtain a set of subproblems with good properties which can be used to approximate $P$ . This method is used to give a 2-approximation and a 3-approximation for MDCVRP and MVSP in trees, respectively. No constant-ratio approximation algorithms are previously known for these two problems.

The results are summarized in Table 1.

Table 1: Results obtained so far. TSP: Travelling Salesman Problem; BWTSP: Black and White TSP; kCCPSC: k Cycle Covering Problem with Short Cycles; SVSP: Single Vehicle Scheduling Problem; MDCVRP: MultiDepot Capacitated Vehicle Routing Problem; MVSP: MultiVehicle Sceduling Problem

Problem	Previous approximation ratio	Our results
$k$ -delivery TSP on paths [34]	$O(n^2/min(k,n))$ time, exact	optimal
$k$ -delivery TSP in trees [34]	2	$\frac{5}{3}$
dial-a-ride on paths [34]	3	$2.5$
dial-a-ride on height balanced trees [34]	$8\sqrt k$	$6 \sqrt k$
BWTSP [12]	none	$(4-\frac{3}{2Q})$
BWTSP [12] , exact	none	$(4-\frac{15}{8Q})$
constrained $k$ CCP [34]	none	2
$k$ CCPSC [34]	no constant factor	2
SVSP on paths [9]	$\frac{5}{3}$	1.5
SVSP in trees [9]	2	$\frac{11}{6}$
SVSP in cycles [9]	none	$\frac{9}{5}$
MDCVRP on paths [34]	none	$O(n^3)$ time, exact
MDCVRP in trees [34]	none	2
MDCVRP in general graphs [34]	none	$\min \{k, O(\log n) \}$
MVSP in trees [34]	no constant factor	3