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


Best known results for Gehring & Homberger's 600 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_6_1 60 14095.64 GH 2001  Detailed solution by Q
c1_6_2 56 14163.31 PGDR 17-oct-07 Detailed solution by Q
c1_6_3 56 13777.81 BC4 05-apr-12  
c1_6_4 56 13558.54 Q 30-sep-13  
c1_6_5 60 14085.72 VCGP 31-jul-12  
c1_6_6 59 15832.68 SCR Apr-19  
c1_6_7 57 15731.20 SCR 19-dec-21  
c1_6_8 56 14385.80 SCR 19-dec-21  
c1_6_9 56 13693.42 VCGP 31-jul-12  
c1_6_10 56 13637.34 NBD 2009 Detailed solution by VCGP
c2_6_1 18 7774.10 MB 16-sep-03  There are questions whether 7774.10 is valid, several authors report 7774.16
c2_6_2 17 8258.20 CAINIAO
Nov-18 Tie 
c2_6_3 17 7506.62 SCR Nov-18  
c2_6_4 17 6909.58 Q 18-mar-15  
c2_6_5 18 7575.20 BSJ2 20-sep-07 Detailed solution by SCR 
c2_6_6 18 7470.36 MB2 18-jul-12 There are questions whether 7470.36 is valid, several authors report 7471.17  
c2_6_7 18 7512.07 BC4 05-apr-12  
c2_6_8 17 7539.73 Q 08-jul-16  
c2_6_9 17 7911.61 CAINIAO Sep-18  
c2_6_10 17 7255.69 VCGP 31-jul-12  
r1_6_1 59 21394.95 CAINIAO
Apr-19 Tie 
r1_6_2 54 18585.00 SCR 19-dec-21  
r1_6_3 54 16900.67 SCR 19-dec-21  
r1_6_4 54 15748.07 SCR 19-dec-21  
r1_6_5 54 19381.52 SCR 19-dec-21  
r1_6_6 54 17790.97 SCR 19-dec-21  
r1_6_7 54 16522.52 SCR 19-dec-21  
r1_6_8 54 15610.00 SCR Apr-19  
r1_6_9 54 18530.96 SCR Jun-19  
r1_6_10 54 17610.12 SCR Apr-19  
r2_6_1 11 18205.58 CAINIAO Sep-18  
r2_6_2 11 14754.13 CAINIAO Dec-18  
r2_6_3 11 11188.70 SCR 23-jul-18  
r2_6_4 11 8008.14 CAINIAO Feb-19  
r2_6_5 11 15067.34 SCR Oct-18  
r2_6_6 11 12498.27 SCR Oct-18  
r2_6_7 11 10064.56 SCR 18-sep-18  
r2_6_8 11 7571.99 SCR Oct-18  
r2_6_9 11 13377.56 NBD 2009 Detailed solution by BC4
r2_6_10 11 12202.28 SCR Oct-18  
rc1_6_1 55 16982.86 SCR Jun-19  
rc1_6_2 55 15914.70 CAINIAO Oct-18  
rc1_6_3 55 15204.64 Q 23-dec-16  
rc1_6_4 55 14777.19 SCR 08-sep-18  
rc1_6_5 55 16559.78 SCR 19-dec-21  
rc1_6_6 55 16496.88 SCR 19-dec-21  
rc1_6_7 55 16077.12 Q 07-sep-17  
rc1_6_8 55 15914.91 Q 23-dec-16  
rc1_6_9 55 15826.24 Q 23-dec-16  
rc1_6_10 55 15675.53 SCR 19-dec-21  
14 13324.93 BC4 05-apr-12  
rc2_6_2 12 11555.51 BC4 05-apr-12  
rc2_6_3 11 9438.52 SCR Nov-18  
rc2_6_4 11 7057.94 CAINIAO Nov-18  
rc2_6_5 11 12909.07 SCR 19-dec-21  
rc2_6_6 11 11913.11 CAINIAO Dec-18  
rc2_6_7 11 10711.85 SCR 19-dec-21


rc2_6_8 11 9990.40 CAINIAO Oct-18  
rc2_6_9 11 9574.99 CAINIAO 19-Sep-18  
rc2_6_10 11 9058.90 SCR Apr-19  


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

CAINIAO - Zhu He, Longfei Wang, Weibo Lin, Yujie Chen, Haoyuan Hu ( ), Yinghui Xu, & VRP Team (Ying Zhang, Guotao Wu, Kunpeng Han et al.). Unpublished work by CAINIAO AI.

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

JG - Jakub Grzegorek (2017). Improved Hybrid Genetic Search with Advanced Diversity Control, forthcoming MEng thesis, Imperial College London.

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 (), Piotr Cybula, Marek Rogalski (), Mariusz Kok, Piotr Beling, Andrzej Jaszkiewicz, Przemysław Pełka. 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.

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