800 customers
Here you find instance definitions and the best known solutions (to our knowledge) for the 800 customer instances of Gehring & Homberger's extended VRPTW benchmark problems. 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 800 customer instances.

Best known results for Gehring & Homberger's 800 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
c1_8_1 80 25030.36 M 2002. There are questions whether the solution is valid, several authors report 80/25184.38
c1_8_2 72 26591.87 Q 29-jun-17
c1_8_3 72 24249.35 Q 29-jun-17
c1_8_4 72 23824.17 Q 28-oct-14
c1_8_5q 80 25166.28 RP 25-feb-05
c1_8_6 79 27202.70 Q 15-sep-14
c1_8_7 77 26486.14 Q 25-nov-15
c1_8_8 73 26684.02 Q 09-oct-14
c1_8_9 72 24300.21 Q 14-aug-17
c1_8_10 72 24070.17 Q 04-sep-15
 
c2_8_1 24 11654.81 MB 2005
c2_8_2 23 12285.31 Q 19-mar-18
c2_8_3 23 11410.69 VCGP 31-jul-12
c2_8_4 22 11154.40 VCGP 31-jul-12
c2_8_5b 24 11425.23 NBD 2009
c2_8_6 23 12551.09 Q 09-mar-15
c2_8_7 24 11370.84 BC4 05-apr-12
c2_8_8 23 11288.01 Q 18-mar-15
c2_8_9 23 11592.52 Q 08-jan-18
c2_8_10 23 10977.36 Q 08-jul-16
 
r1_8_1 80 36822.16 SCR 01-mar-18
r1_8_2 72 32485.81 SCR 04-may-18
r1_8_3 72 29361.59 SCR 13-mar-18
r1_8_4 72 26838.04 MB 16-sep-03
r1_8_5 72 33663.61 SCR 10-may-18
r1_8_6 72 30967.86 SCR 29-may-18
r1_8_7 72 28898,89 SCR 23-feb-18
r1_8_8 72 27687.83 SCR 23-feb-18
r1_8_9 72 32358.44 SCR 03-jan-18
r1_8_10 72 31031.27 SCR 16-jan-18
 
r2_8_1
15 28112.36 SCR 01-mar-18
r2_8_2s 15 22795.79 NBD 2009
r2_8_3 15 17714.05 NBD 2009
r2_8_4 15 13206.10 NBD 2009
r2_8_5 15 24276.37 SCR 13-mar-18
r2_8_6 15 20479.46 NBD 2009
r2_8_7 15 16631.77 SCR 22-jun-18
r2_8_8 15 12645.63 NBD 2009
r2_8_9 15 22326.21 SCR 18-jun-18
r2_8_10 15 20373.79 SCR 08-06-18
 
rc1_8_1 72 30907.27 SCR 07-jun-18
rc1_8_2 72 28716.34 SCR 19-apr-18
rc1_8_3 72 27677.10 SCR 12-jun-18
rc1_8_4 72 26774.93 SCR 17-jul-17
rc1_8_5 72 29796.67 SCR 21-nov-17
rc1_8_6 72 29850.79 SCR 24-jul-17
rc1_8_7 72 29276.53 SCR 24-jul-17
rc1_8_8 72 28797.39 SCR 11-jul-17
rc1_8_9 72 28740.44 SCR 24-jul-17
rc1_8_10 72 28474.35 SCR 16-oct-17
 
rc2_8_1 18 20981.14 BC4 05-apr-12
rc2_8_2 16 18181.14 NBD 2009
rc2_8_3 15 14431.11 SCR 17-may-18
rc2_8_4 15 11006.56 VCGP 31-jul-12
rc2_8_5 15 19119.97 SCR 23-may-18
rc2_8_6s 15 18146.03 NBD 2009
rc2_8_7 15 16841.12 SCR 13-jun-18
rc2_8_8 15 15790.21 SCR 18-jun-18
rc2_8_9 15 15352.82 SCR 22-jun-18
rc2_8_10 15 14439.14 NBD 2009
    
b: Detailed solution provided by BC4
q: Detailed solution provided by Q
s: Detailed solution provided by SCR  

NB! The R_1_8_1 entry has been changed to an inferior value. The previous entry was based  on a report without a detailed solution. Later, it appeared that the solution is infeasible, see reference NBD.

The updated entry is based on a detailed solution that has been checked by our solution checker.

References

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.

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.

EOE - Eirik Krogen Hagen, EOE Koordinering DA. Exploring infeasible and feasible regions of the VRPTW and PDPTW through penalty based tabu search. Working paper.

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

JN - Jakub Nalepa, "Parallel memetic algorithm to solve the vehicle routing problem with time windows, Master of Science Thesis, Silesian University of Technology, Gliwice, 2011"

M - D. Mester, "An Evolutionary Strategies Algorithm for Large Scale Vehicle Routing Problem with Capacitate and Time Windows Restrictions," Working Paper, Institute of Evolution, University of Haifa, Israel (2002).

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.

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.

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)

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

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

 

SCR - Piotr Sielski (psielski@emapa.pl), Piotr Cybula, Marek Rogalski, Piotr Beling and Andrzej Jaszkiewicz, Emapa S.A. (http://www.emapa.pl), "New methods of VRP problem optimization", unpublished research funded by The National Centre for Research and Development. project number: POIR.01.01.01.-00-0222/16.

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 April 18, 2008