| Article ID: | iaor20032810 |
| Country: | United States |
| Volume: | 14 |
| Issue: | 2 |
| Start Page Number: | 132 |
| End Page Number: | 143 |
| Publication Date: | Apr 2002 |
| Journal: | INFORMS Journal On Computing |
| Authors: | Cook William, Rohe Andr, Applegate David, Dash Sanjeeb |
| Keywords: | programming: integer, programming: branch and bound, programming: travelling salesman |
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 travelling 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 was developed by E. Aarts and J. K. Lenstra, and the competition was sponsored by the information technology firm CMG and the newspaper