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

Instance

Vehicles

Distance

Authors


c1_10_1 100
42478.95 GH

c1_10_2 90
42300.76 VCGP
31-jul-12
c1_10_3 90
40239.23 VCGP 31-jul-12
c1_10_4 90
39468.60 Q 17-apr-13
c1_10_5 100
42469.18 RP 25-feb-05
c1_10_6 99 44108.34 BC4 12-apr-12
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
16432.53 VCGP 31-jul-12
c2_10_10 28
15944.72 VCGP
31-jul-12

r1_10_1
100
53657.99 VCGP
31-jul-12
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
42219.21 BC4
05-apr-12
r2_10_2 19
33567.91 VCGP 31-jul-12
r2_10_3 19
25053.80 VCGP 31-jul-12
r2_10_4 19
18039.77 VCGP 31-jul-12
r2_10_5 19
36335.72 BC4 05-apr-12
r2_10_6 19
30223.14 VCGP 31-jul-12
r2_10_7 19
23381.36 BC4 05-apr-12
r2_10_8 19
17598.63 BC4
05-apr-12
r2_10_9 19
33131.99 BC4 05-apr-12
r2_10_10 19
30598.69 VCGP 31-jul-12

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 12-apr-12
rc2_10_2 18
26327.92 VCGP
31-jul-12
rc2_10_3 18
20053.78 VCGP
31-jul-12
rc2_10_4 18
15747.13 VCGP
31-jul-12
rc2_10_5 18
27237.68 VCGP
31-jul-12
rc2_10_6 18
26965.51 BC4 05-apr-12
rc2_10_7 18
25295.67 VCGP
31-jul-12
rc2_10_8 18
23787.26 VCGP
31-jul-12
rc2_10_9 18
23116.15 VCGP 31-jul-12
rc2_10_10 18
22076.90 VCGP
31-jul-12





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.

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 August 28, 2014