Problem Definition

Given n pegs and n slots and a starting point s, we wish to find a shortest tour for a vehicle of capacity k that performs all the deliveries.  The vehicle should visit all the points, so that at any point t on the tour, the number of visited pegs minus the number of visited slots is at least 0 and at most k.

The Algorithms

Chelsani, Motowani and Rao gave the first polynomial approximation algorithm for this problem which achieves an approximation ratio of 9.5.  However, Charikar, Khuller and Raghavachari  were able to modify this algorithm to obtain an approximation of 6.5 (this improved algorithm is referred to here as the CMR algorithm).  Charikar, Khuller and Raghavachari also proposed a new algorithm with a better approximation ratio of at most 5 (this algorithm is referred to here as the CKR algorithm).  Tests were run on the CMR and CKR algorithms for comparison.

For an in-depth treatment of the subject and algorithms please refer:
Moses Charikar, Samir Khuller, Balaji Raghavachari. Algorithms for Capacitated Vehicle Routing. University of Maryland Institute for Advanced Computer Studies~Department of Computer Science, University of Maryland, November 1997.

Implementation

The CMR [source code] and CKR [source code] algorithms were implemented in C++ using the Library of Efficient Data types and Algorithms (LEDA) version 3.5.5.

The Traveling Salesperson algorithm used to calculate TSP tours was based on local search heuristics for non-crossing paths and nearest neighbors implemented by Lionnel Maugis.  The following table compares the cost of the solution generated by this TSP algorithm and the optimal solution for certain instances of the Asymmetric Traveling Salesperson Problem.  The problem instances and OPT values were obtained from TSPLIB.
 

Instance	OPT	TSP
a280	2579	3083.02
berlin52	7542	8236.22
bier127	118282	119718.43
rd400	15281	15944.36
tsp225	3919	4571.83

 

Test Results

1. The following results are for tests run on data sets where the pegs and slots were uniformly distributed throughout the plane.

A. Variation of cost with n for
• k = 4
• k = 10
• k = 20
• k = 50
B. Variation of cost with k for n = 1000

A. Variation of cost with n for

• k = 4
• k = 10
• k = 20
• k = 50
B. Variation of cost with k for n = 1000
 

March 10th, 1998