Solution of a Min-Max Vehicle Routing Problem

Abstract

We use a branch-and-cut search to solve the Whizzkids'96 vehicle routing problem, demonstrating that the winning solution in the 1996 competition is in fact optimal. Our algorithmic framework combines the LP-based traveling salesman code of Applegate, Bixby, Chvátal, and Cook, with specialized cutting planes and a distributed search algorithm, permitting the use of a computing network located across Rice, Princeton, AT&T, and Bonn. The 1996 problem instance wasdeveloped by E. Aartsand J. K. Lenstra, and the competition was sponsored by the information technology firm CMG and the newspaper De Telegraaf.