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  
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  
r108 9 960.88 BBB Detailed solution from BVH
r109 11 1194.73 HG  
r110 10 1118.84 MBD See note below
r111 10 1096.72 RGP  
r112 9 982.14 GTA  
 
r201 4 1252.37 HG Detailed solution by SAM::OPT
r202 3 1191.70 RGP  
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  
rc103 11 1261.67 S98  
rc104 10 1135.48 CLM  
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  
 
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
    

 b: Detailed solution by Bauke Conijn, TU Eindhoven


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