100 customers
Here you find instance definitions and best known solutions for the 100 customer instances of Solomon's VRPTW benchmark problems from 1987. The version reported here has a hierarchical objective: 1) Minimize number of vehicles 2) Minimize total distance. Distance and time should be calculated with double precision, total distance results are rounded to two decimals. Exact methods typically use a monolithic total distance objective and use integral or low precision distance and time calculations. Hence, results are not directly comparable. By clicking on an instance name in blue, you will open a file with a specification of the detailed solution.

Instance definitions (text)

See Solomon's web page http://web.cba.neu.edu/~msolomon/problems.htm .

As a backup, you will find a zip-file with the 100 instance definitions here.

Best known solution values

See Solomon's web page http://web.cba.neu.edu/~msolomon/problems.htm .

A few new results have been added in the updated table below.

 Instance Vehicles Distance Reference Comment c101 10 828.94 RT Detailed solution by SAM::OPT c102 10 828.94 RT Detailed solution by SAM::OPT c103 10 828.06 RT Detailed solution by SAM::OPT c104 10 824.78 RT Detailed solution by SAM::OPT c105 10 828.94 RT Detailed solution by SAM::OPT c106 10 828.94 RT Detailed solution by SAM::OPT c107 10 828.94 RT Detailed solution by SAM::OPT c108 10 828.94 RT Detailed solution by SAM::OPT c109 10 828.94 RT Detailed solution by SAM::OPT c201 3 591.56 RT Detailed solution by SAM::OPT c202 3 591.56 RT Detailed solution by SAM::OPT c203 3 591.17 RT Detailed solution by SAM::OPT c204 3 590.60 RT Detailed solution by SAM::OPT c205 3 588.88 RT Detailed solution by SAM::OPT c206 3 588.49 RT Detailed solution by SAM::OPT c207 3 588.29 RT Detailed solution by SAM::OPT c208 3 588.32 RT Detailed solution by SAM::OPT r101 19 1650.80 H See note below r102 17 1486.12 RT Detailed solution by SAM::OPT r103 13 1292.68 LLH Detailed solution by Shobb r104 9 1007.31 MBD See note below r105 14 1377.11 RT Detailed solution by SAM::OPT r106 12 1252.03 MBD See note below r107 10 1104.66 S97 Detailed solution by Shobb r108 9 960.88 BBB Detailed solution from BVH r109 11 1194.73 HG Detailed solution by Shobb r110 10 1118.84 MBD See note below r111 10 1096.72 RGP Detailed solution by Shobb r112 9 982.14 GTA r201 4 1252.37 HG Detailed solution by SAM::OPT r202 3 1191.70 RGP Detailed solution by Shobb r203 3 939.50 WL 2009-10-21 r204 2 825.52 BVH r205b 3 994.43 RGP 994.42 reported by RGP is believed to result from a rounding error r206 3 906.14 SSSD Detailed solution by SAM::OPT r207 2 890.61 RP 2005-02-25 r208 2 726.82 MBD See note below r209 3 909.16 H Detailed solution from BVH r210 3 939.37 MBD See note below r211 2 885.71 WL 2009-10-21 rc101b 14 1696.95 TBGGP 1696.94 reported by TBGGP is believed to result from a rounding error rc102 12 1554.75 TBGGP Detailed solution by Shobb rc103 11 1261.67 S98 Detailed solution by Shobb rc104 10 1135.48 CLM Detailed solution by Shobb rc105 13 1629.44 BBB Detailed solution from BVH rc106 11 1424.73 BBB Detailed solution from BVH rc107 11 1230.48 S97 rc108 10 1139.82 TBGGP Detailed solution by Shobb rc201 4 1406.94 MBD See note below rc202 3 1365.65 GCC 2004-03-22 rc203 3 1049.62 CC rc204 3 798.46 MBD See note below rc205 4 1297.65 MBD See note below rc206 3 1146.32 H Detailed solution from BVH rc207 3 1061.14 BVH rc208 3 828.14 IKMUY Detailed solution from BVH

NB!

Earlier, slightly better total distance values were reported for instances R101, R104, R106, R110, R208, R210, RC201, RC204, and RC205. These values were produced using lower precision arithmetic. We are grateful to Bauke Conijn of TU Eindhoven for pointing this out, and for providing us with correct values and detailed solutions for these instances. All detailed solutions have been checked by our solution checker. Some of the detailed solutions were taken from the website of Z. J. Czech. We also thank David Mester for giving us details on how the early results were produced, and for providing us with revised values and detailed solutions that were produced using double precision arithmetic. The solutions and values from the two sources coincide. We know that several other authors have produced solutions with the same values.

References

BBB - J. Berger, M. Barkaoui and O. Bräysy, "A Parallel Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows," Working paper, Defense Research Establishment Valcartier, Canada, 2001.

BVH - R. Bent and P. Van Hentenryck, "A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows," Technical Report CS-01-06, Department of Computer Science, Brown University, 2001.

CC - Z. J. Czech and P. Czarnas, "A Parallel Simulated Annealing for the Vehicle Routing Problem with Time Windows," Proc. 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, Canary Islands, Spain, (January 9--11, 2002), 376--383.

CLM - J.-F. Cordeau,  G. Laporte, and A. Mercier, "A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows," Working Paper CRT-00-03, Centre for Research on Transportation, Montreal, Canada, 2000.

GCC - Agnieszka Debudaj-Grabysz, Zbigniew J.Czech and Piotr Czarnas
Silesia University of Technology and University of Wroclaw, Poland (2004)

GTA - L. M. Gambardella, E. Taillard, and G. Agazzi, "MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows," in New Ideas in Optimization, D. Corne, M. Dorigo and F. Glover (eds), 63-76, McGraw-Hill, London, 1999.

H - J. Homberger, "Verteilt-parallele Metaheuristiken zur Tourenplanung," Gaber, Wiesbaden (2000).

HG - J. Homberger and H. Gehring, "Two Evolutionary Metaheuristics for the Vehicle Routing Problem with Time Windows," INFOR, VOL. 37, 297-318, (1999).

IKMUY - T. Ibaraki, M. Kubo, T. Masuda, T. Uno and M. Yagiura, "Effective Local Search Algorithms for the Vehicle Routing Problem with General Time Windows," Working Paper, Department of Applied Mathematics and Physics, Kyoto University, Japan, 2001.

MBD - D. Mester, O. Bräysy and W. Dullaert. A Multi-parametric Evolution Strategies Algorithm for Vehicle Routing Problems. Working Paper, Institute of Evolution, University of Haifa, Israel (2005).

LLH - H. Li, A. Lim, and J. Huang, "Local Search with Annealing-like Restarts to Solve the VRPTW," Working Paper, Department of Computer Science, National University of Singapore, 2001.

RGP - L.M. Rousseau, M. Gendreau and G. Pesant, "Using Constraint-Based Operators to Solve the Vehicle Routing Problem with Time Windows," Journal of Heuristics, 8: 43–58, 2002.

RP - S. Ropke & D.Pisinger. "A general heuristic for vehicle routing problems",  technical report, Department of Computer Science, University of Copenhagen.

RT - Y. Rochat and E.D. Taillard, "Probabilistic Diversification and Intensification in Local Search for Vehicle Routing," Journal of Heuristics 1, 147-167, (1995).

SAM::OPT - Hasle G., O. Kloster: Industrial Vehicle Routing Problems. Chapter in Hasle G., K-A Lie, E. Quak (eds): Geometric Modelling, Numerical Simulation, and Optimization. ISBN 978-3-540-68782-5, Springer 2007.

SSSD - G. Schrimpf, J. Schneider, H. Stamm-Wilbrandt and G. Dueck, "Record Breaking Optimization Results Using the Ruin and Recreate Principle," Journal of Computational Physics 159, 139-171, (2000).

S97 - P. Shaw, "A New Local Search Algorithm Providing High Quality Solutions to Vehicle Routing Problems," Working Paper, University of Strathclyde, Glasgow, Scotland, 1997.

S98 - P. Shaw, "Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems," In Principles and Practice of Constraint Programming - CP98, Lecture Notes in Computer Science, 417-431, M. Maher and J.-F. Puget (eds), Springer-Verlag, New York, 1998.

TBGGP - E. Taillard, P. Badeau, M. Gendreau, F. Geurtin, and J.Y. Potvin, "A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows," Transportation Science, 31, 170-186, (1997).

WL - Woch M., Łebkowski P.: Sequential Simulated Annealing for the Vehicle Routing Problem with Time Windows. Decision Making in Manufacturing and Services, vol. 3, no. 1-2., s. 87-100, 2009.

Published April 18, 2008