200 customers

Here you find instance definitions and the best known solutions (to our knowledge) for the 200 customer instances of 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

Instance

Vehicles

Distance

Authors

Date
c1_2_1 20
2704.57 GH

c1_2_2 18
2917.89 BVH

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

c1_2_6 20
2701.04 GH

c1_2_7 20
2701.04 GH

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

c2_2_1
6
1931.44 GH

c2_2_2 6
1863.16 GH

c2_2_3 6
1775.08 BC4
05-apr-12
c2_2_4 6
1703.43 PGDR
17-oct-07
c2_2_5 6
1878.85 BVH

c2_2_6 6
1857.35 B

c2_2_7 6
1849.46 GH

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 BC4
05-apr-12

r1_2_1
20
4784.11 BC4
05-apr-12
r1_2_2 18
4039.86 MB2
18-jul-12
r1_2_3 18
3381.96 BSJ2
20-sep-07
r1_2_4 18
3057.81 VCGP
31-jul-12
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 VCGP
31-jul-12
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
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 BC4

05-apr-12

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 VCGP
31-jul-12
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 VCGP
31-jul-12
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 BC4
05-apr-12
rc2_2_4 4
2038.56 BC4
05-apr-12
rc2_2_5 4
2911.46 BSJ2
20-sep-07
rc2_2_6 4
2873.12 BC4
05-apr-12
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





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:

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. DOI=10.1016/j.cor.2009.06.022 http://dx.doi.org/10.1016/j.cor.2009.06.022

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.

Legend

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, Beskyttet adresse, 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.

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.

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 November 20, 2013