This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Applegate, D. Articles by Rohe, A. Search for Related Content

Solution of a Min-Max Vehicle Routing Problem

Algorithms and Optimization Department, AT&T Labs—Research, 180 Park Avenue, P.O. Box 971, Florham Park, New Jersey 07932-971, USA
Program in Applied and Computational Mathematics, Princeton University, Fine Hall, Washington Road, Princeton, New Jersey 08544-1000, USA
Program in Applied and Computational Mathematics, Princeton University, Fine Hall, Washington Road, Princeton, New Jersey 08544-1000, USA
Forschungsinstitut für Diskrete Mathematik, Universität Bonn, Lennéstrasse 2, D-53113 Bonn, Germany
david{at}research.att.com
bico{at}math.princeton.edu
sanjeebd{at}math.princeton.edu
rohe{at}or.uni-bonn.de

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.

Key words: Combinatorial Optimization; vehicle Routing; integer Programming; distributed Computing
History: received August 2001; revised October 2001; accepted November 2001.

This article has been cited by other articles:

				A. M. Campbell, D. Vandenbussche, and W. Hermann Routing for Relief Efforts Transportation Science, May 1, 2008; 42(2): 127 - 145. [Abstract] [PDF]

				P. Schermerhorn and M. Scheutz Investigating the Adaptiveness of Communication in Multi-Agent Behavior Coordination Adaptive Behavior, December 1, 2007; 15(4): 423 - 445. [Abstract] [PDF]