1000 customers
Here you find instance definitions and the best known solutions (to our knowledge) for the 1000 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 you find a zip file with the 1000 customer instances.

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

InstanceVehiclesDistanceAuthors  
c1_10_1 100 42478.95 GH  
c1_10_2 90 42278.45 NB 09-sep-14
c1_10_3 90 40221.66 Q 12-dec-14
c1_10_4 90 39468.60 Q 17-apr-13
c1_10_5 100 42469.18 RP 25-feb-05
c1_10_6 99 43830.21 Q 05-sep-14
c1_10_7 97 43453.92 Q 11-apr-14
c1_10_8 93 42149.58 Q 25-aug-14
c1_10_9 90 40570.60 VCGP 31-jul-12
c1_10_10 90 39933.06 VCGP 31-jul-12
 
c2_10_1 30 16879.24 LL  
c2_10_2 29 17126.39 BC4 05-apr-12
c2_10_3 28 16884.08 BC4 05-apr-12
c2_10_4 28 15656.75 VCGP 31-jul-12
c2_10_5 30 16561.29 VCGP 31-jul-12
c2_10_6 29 16920.33 BC4 05-apr-12
c2_10_7 29 17882.42 BC4 05-apr-12
c2_10_8 28 16577.32 VCGP 31-jul-12
c2_10_9 29 16370.44 NB 09-sep-14
c2_10_10 28 15944.72 VCGP 31-jul-12
 
r1_10_1 100 53560.85 NB 09-sep-14
r1_10_2 91 49105.21 VCGP 31-jul-12
r1_10_3 91 45237.29 VCGP 31-jul-12
r1_10_4 91 42787.19 MB2 18-jul-12
r1_10_5 91 51830.36 MB2 18-jul-12
r1_10_6 91 47849.05 VCGP 31-jul-12
r1_10_7 91 44435.50 MB2 18-jul-12
r1_10_8 91 42485.38 MB2 18-jul-12
r1_10_9 91 50490.49 VCGP 31-jul-12
r1_10_10 91 48294.71 MB2 18-jul-12
 
r2_10_1
19 42188.86 NB 09-sep-14
r2_10_2 19 33512.83 NB 09-sep-14
r2_10_3 19 24940.32 NB 09-sep-14
r2_10_4 19 17926.45 NB 09-sep-14
r2_10_5 19 36232.18 NB 09-sep-14
r2_10_6 19 30091.93 NB 09-sep-14
r2_10_7 19 23257.36 NB 09-sep-14
r2_10_8 19 17495.51 NB 09-sep-14
r2_10_9 19 33002.36 NB 09-sep-14
r2_10_10 19 30215.24 NB 09-sep-14
 
rc1_10_1 90 46272.07 VCGP 31-jul-12
rc1_10_2 90 44129.42 VCGP 31-jul-12
rc1_10_3 90 42487.54 VCGP 31-jul-12
rc1_10_4 90 41613.58 VCGP 31-jul-12
rc1_10_5 90 45564.81 VCGP 31-jul-12
rc1_10_6 90 45303.67 VCGP 31-jul-12
rc1_10_7 90 44903.80 VCGP 31-jul-12
rc1_10_8 90 44366.01 VCGP 31-jul-12
rc1_10_9 90 44280.84 VCGP 31-jul-12
rc1_10_10 90 43896.78 VCGP 31-jul-12
 
rc2_10_1 20 30278.50 BC4 05-apr-12
rc2_10_2 18 26327.92 VCGP 31-jul-12
rc2_10_3 18

20050.71

NB 09-sep-14
rc2_10_4 18 15747.13 VCGP 31-jul-12
rc2_10_5 18 27237.68 VCGP 31-jul-12
rc2_10_6 18 26797.76 NB 09-sep-14
rc2_10_7 18 25112.77 NB 09-sep-14
rc2_10_8 18 23709.29 NB 09-sep-14
rc2_10_9 18 23028.10 NB 09-sep-14
rc2_10_10 18 21965.94 NB 09-sep-14
    

Legend:

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.

BSJ - Bjørn Sigurd Johansen, Beskyttet adresse, DSolver 09-2004

BSJ2 - Bjørn Sigurd Johansen, Beskyttet adresse, DSolver version2 05-2005.

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).

LL - H. Li and A. Lim, "Large Scale Time-Constrained Vehicle Routing Problems: A General Metaheuristic Framework with Extensive Experimental Results," Submitted to Artificial Intelligence Review, 2001.

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.

MK - M. Koch, "An approach combining two methods for the vehicle routing problem with time windows",  The solutions were presented at EURO and EURO XX Conference 2004.

NB - Jakub Nalepa, Miroslaw Blocho. "Co-operation in the Parallel Memetic Algorithm", International Journal of Parallel Programming 214, pp 1-28. http://dx.doi.org/10.1007/s10766-014-0343-4

NBC - Jakub Nalepa, Miroslaw Blocho, and Zbigniew J. Czech. "Co-operation schemes for the parallel memetic algorithm". In Roman Wyrzykowski, Jack Dongarra, Konrad Karczewski, and Jerzy Waniewski, editors, Parallel Processing and Applied Mathematics, Lecture Notes in Computer Science, pages 191–201. Springer Berlin Heidelberg, 2014. ISBN 978-3-642-55223-6. doi: 10.1007/978-3-642-55224-3 19.

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)

Q - Quintiq. http://www.quintiq.com/optimization-world-records.aspx.

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

WW - Witoslaw Wierzbicki. "Design and implementation of parallel programs with shared memory". Master of Science Thesis, University of Silesia, Sosnowiec, 2012.

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 December 12, 2014