Tech Report CS-01-06

A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows

Russell Bent and Pascal Van Hentenryck

September 2001


The vehicle routing problem with time windows is a hard combinatorial optimization problem which has received considerable attention in the last decades. This paper proposes a two-stage hybrid algorithm for this transportation problem. The algorithm first minimizes the number of vehicles using simulated annealing. It then minimizes travel cost using a large neighborhood search which may relocate a large number of customers. Experimental results demonstrate the effectiveness of the algorithm which has improved 13 (23%) of the 58 best published solutions to the Solomon benchmarks, while matching or improving the best solutions in 47 problems (84%). More important perhaps, the algorithm is shown to be very robust. With a fixed configuration of its parameters, it returns either the best published solutions (or improvements thereof) or solutions very close in quality on all Solomon benchmarks. Results on the extended Solomon benchmarks are also given.

(complete text in pdf or gzipped postscript)