200 customers
Here you find instance definitions and the best known solutions (to our knowledge) for the 200 customer instances of Gehring & Homberger's extended VRPTW benchmark. 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 total distance objective and use integral or low precision distance and time calculations. Hence, results are not directly comparable.

Instance definitions (text)

Here is a zip file with the 200 customer instances.

Best known results for Gehring & Homberger's 200 customer instances

The instance names in blue are hyperlinks to files with corresponding detailed solutions. They have all been checked by our solution checker. Note that many best known solutions do not have a reference to a peer reviewed publication. For these, important details on the solution algorithm, the computing time, and the experimental platform are probably not available. Further, there is no guarantee that the solutions have been produced without using external information, such as detailed solutions published earlier. We may later introduce two categories: 'properly published' and 'freestyle', the latter with no restrictions.   

Instance Vehicles Distance Reference Date             Comment
c1_2_1 20 2704.57 GH 2001  Detailed solution by SAM::OPT
c1_2_2 18 2917.89 BVH 2001   
c1_2_3 18 2707.35 BSJ2 20-sep-07  
c1_2_4 18 2643.31 BSJ2 20-sep-07  
c1_2_5 20 2702.05 GH 2001 Detailed solution by SAM::OPT
c1_2_6 20 2701.04 GH 2001 Detailed solution by SAM::OPT
c1_2_7 20 2701.04 GH 2001 Detailed solution by SAM::OPT
c1_2_8 19 2775.48 BC4 05-apr-12  
c1_2_9 18 2687.83 MB 02-sep-13  
c1_2_10 18 2643.51 MB 10-may-05 There are questions whether 2643.51 is valid, several authors report 2643.55
 
c2_2_1 6 1931.44 GH 2001 Detailed solution by SAM::OPT
c2_2_2 6 1863.16 GH 2001 Detailed solution by SAM::OPT
c2_2_3 6 1775.08 NBD 2009 Detailed solution by BC4 
c2_2_4 6 1703.43 PGDR 17-oct-07  
c2_2_5 6 1878.85 BVH 2001  
c2_2_6 6 1857.35 B 2001 Detailed solution by SAM::OPT
c2_2_7 6 1849.46 GH 2001 Detailed solution by SAM::OPT
c2_2_8 6 1820.53 RP 25-feb-05  
c2_2_9 6 1830.05 RP 25-feb-05  
c2_2_10 6 1806.58 NBD 2009 Detailed solution by BC4 
 
r1_2_1 20 4784.11 NBD 2009 Detailed solution by BC4 
r1_2_2 18 4039.86 MB2 18-jul-12 There are questions whether 4039.86 is valid
r1_2_3 18 3381.96 BSJ2 20-sep-07  
r1_2_4 18 3057.81 NBD 2009 Detailed solution by VCGP 
r1_2_5 18 4107.86 PGDR 17-oct-07  
r1_2_6 18 3583.14 PGDR 17-oct-07  
r1_2_7 18 3150.11 BSJ2 20-sep-07  
r1_2_8 18 2951.99 NBD 2009 Detailed solution by VCGP 
r1_2_9 18 3760.58 PGDR 17-oct-07  
r1_2_10 18 3301.18 BSJ2 20-sep-07  
 
r2_2_1 4 4483.16 BSJ2 20-sep-07  
r2_2_2 4 3621.20 BSJ2 20-sep-07  
r2_2_3 4 2880.62 BSJ2 20-sep-07  
r2_2_4 4 1981.29 MB 16-sep-03 There are questions whether 1981.29 is correct, several authors report 1989.30 
r2_2_5 4 3366.79 BSJ2 20-sep-07  
r2_2_6 4 2913.03 PGDR 17-oct-07  
r2_2_7 4 2451.14 BSJ2 20-sep-07  
r2_2_8 4 1849.87 MB 16-sep-03  
r2_2_9 4 3092.04 NBD

2009

Detailed solution by BC4 
r2_2_10 4 2654.97 BSJ2 20-sep-07  
 
rc1_2_1 18 3602.80 PGDR 17-oct-07  
rc1_2_2 18 3249.05 BC4 05-april-12  
rc1_2_3 18 3008.33 BSJ2 20-sep-07  
rc1_2_4 18 2851.68 NBD 2009 Detailed solution by VCGP 
rc1_2_5 18 3371.00 BC4 05-april-12  
rc1_2_6 18 3324.80 PGDR 17-oct-07  
rc1_2_7 18 3189.32 BSJ2 20-sep-07  
rc1_2_8 18 3083.93 PGDR 17-oct-07  
rc1_2_9 18 3081.13 NBD 2009 Detailed solution by VCGP 
rc1_2_10 18 3000.30 VCGP 31-jul-12  
 
rc2_2_1 6 3099.53 BSJ2 20-sep-07  
rc2_2_2 5 2825.24 PGDR 17-oct-07  
rc2_2_3 4 2601.87 NBD 2009 Detailed solution by BC4  
rc2_2_4 4 2038.56 BC4 2009  
rc2_2_5 4 2911.46 BSJ2 20-sep-07  
rc2_2_6 4 2873.12 NBD 2009 Detailed solution by BC4 
rc2_2_7 4 2525.83 BSJ2 20-sep-07  
rc2_2_8 4 2292.53 VCGP 31-jul-12  
rc2_2_9 4 2175.04 BSJ2 20-sep-07  
rc2_2_10 4 2015.60 MB 16-sep-03 There are questions whether 2015.60 is correct. Several authors report 2015.61 
    

NB!

The C1_2_8 and R1_2_1 entries have been changed to inferior values. The previous entries were based on reports without detailed solutions. Later, it appeared that the solutions are infeasible, see reference NBD.

Similarly, the original C1_2_9 result of Mester & Bräysy 18/2642.82 turned out to represent an infeasible solution, given the double precision requirement.

The updated entries are based on detailed solutions that have been checked by our solution checker.

References

B - O. Bräysy, "A Reactive Variable Neighborhood Search Algorithm for the Vehicle Routing Problem with Time Windows," Working Paper, University of Vaasa, Finland, 2001.

BC4, Mirosław BŁOCHO, Zbigniew J. CZECH, "A parallel memetic algorithm for the vehicle routing problem with time windows".  3PGCIC 2013, 8th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing.

BSJ2 - Bjørn Sigurd Johansen, BjornSigurdJohansen@hotmail.com, DSolver version2 05-2005.

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.

G - Tomasz Gandor: "Approximate Solutions for the Vehicle Routing Problem with Time Windows for a Large Number of Customers". "Systemy Wspomagania Decyzji" (Decision Support Systems), 2008, Zakopane, Poland.

GH - H. Gehring and J. Homberger, "A Parallel Two-phase Metaheuristic for Routing Problems with Time Windows," Asia-Pacific Journal of Operational Research, 18, 35-47, (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).


MB - Mester, D. and O. Bräysy (2005), “Active Guided Evolution Strategies for Large Scale Vehicle Routing Problems with Time Windows”. Computers & Operations Research 32, 1593-1614.

MB2 - Mester, D & O. Bräysy (2012). "A new powerful metaheuristic for the VRPTW”, working paper, University of Haifa, Israel.

NBD - Yuichi Nagata, Olli Bräysy, and Wout Dullaert (2010). A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Comput. Oper. Res. 37, 4 (April 2010), 724-737.

PGDR - Eric Prescott-Gagnon, Guy Desaulniers and Louis-Martin Rousseau. A Branch-and-Price-Based Large Neighborhood Search Algorithm for the Vehicle Routing Problem with Time Windows. (2007).

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

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.

VCGP - T. Vidal, T. G. Crainic, M. Gendreau, C. Prins. "A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows", Computers & Operations Research, Vol. 40, No. 1. (January 2013), pp. 475-489.

Published April 18, 2008