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

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_10_1q 100 42478.95 GH 2001
c1_10_2 90 42225.73 SCR 13-sep-18
c1_10_3 90 40101.36 Q 17-sep-15
c1_10_4 90 39468.60 Q 17-apr-13
c1_10_5i 100 42469.18 RP 25-feb-05
c1_10_6 99 43830.21 Q 05-sep-14
c1_10_7 97 43395.88 Q 19-mar-18
c1_10_8 92 43029.97 Q 05-sep-16
c1_10_9 90 40353.52 SCR 23-jan-18
c1_10_10 90 39852.44 SCR 10-sep-18
c2_10_1s 30 16879.24 LL 2001
c2_10_2b 29 17126.39 NBD 2009
c2_10_3 28 16877.39 CAINIAO Sep-18
c2_10_4 28 15652.23 CAINIAO Sep-18
c2_10_5 30 16561.29 VCGP 31-jul-12
c2_10_6 29 16920.33 BC4 05-apr-12
c2_10_7 29 17810.68 CAINIAO Sep-18
c2_10_8 28 16577.32 VCGP 31-jul-12
c2_10_9 29 16364.41 CAINIAO Sep-18
c2_10_10 28 15940.74 CAINIAO Sep-18
r1_10_1 100 53435.98 SCR 22-mar-18
r1_10_2 91 48596.99 SCR 29-mar-18
r1_10_3 91 44935.80 SCR 23-mar-18
r1_10_4 91 42603.79 SCR 17-apr-18
r1_10_5 91 50616.73 SCR 12-jul-18
r1_10_6 91 47080.87 SCR Sep-18
r1_10_7 91 44171.72 SCR 19-apr-18
r1_10_8 91 42410.61 SCR 10-sep-18
r1_10_9 91 49496.36 SCR 17-apr-18
r1_10_10 91 47623.04 SCR 04-may-18
19 42188.86 NB 09-sep-14
r2_10_2 19 33413.05 SCR Sep-18
r2_10_3 19 24927.85 CAINIAO Sep-18
r2_10_4 19 17880.11 NBD 2009
r2_10_5 19 36230.79 CAINIAO Sep-18
r2_10_6 19 30027.92 SCR Sep-18
r2_10_7 19 23234.87 CAINIAO 24-sep-18
r2_10_8 19 17464.50 CAINIAO 27-sep-18
r2_10_9 19 32995.71 CAINIAO Sep-18
r2_10_10 19 30215.24 NB 09-sep-14
rc1_10_1 90 46075.69 SCR 03-apr-18
rc1_10_2 90 43904.36 SCR Sep-18
rc1_10_3 90 42347.83 SCR 04-sep-17
rc1_10_4 90 41507.27 SCR 04-sep-17
rc1_10_5 90 45313.38 SCR 11-sep-17
rc1_10_6 90 45073.27 SCR 08-may-18
rc1_10_7 90 44604.34 SCR 11-sep-17
rc1_10_8 90 44031.75 SCR 08-may-18
rc1_10_9 90 44066.16 SCR 19-apr-18
rc1_10_10 90 43679.61 SCR 11-sep-17
rc2_10_1 20 30276.74 SCR 02-jul-18
rc2_10_2 18 26114.65 SCR Sep-18
rc2_10_3 18 19925.61 SCR Sep-18
rc2_10_4 18 15714.62 CAINIAO 27-sep-18
rc2_10_5 18 27102.55 CAINIAO Sep-18
rc2_10_6 18 26741.27 CAINIAO 27-sep-18
rc2_10_7 18 25058.05 CAINIAO 27-sep-18
rc2_10_8 18 23638.99 CAINIAO Sep-18
rc2_10_9 18 22968.34 CAINIAO Sep-18
rc2_10_10 18 21859.89 SCR Sep-18

b: Detailed solution provided by BC4
i: Detailed solution provided by Pete Bailey, Paul Smith, IFS 360 Scheduling.
q: Detailed solution provided by Q.
s: Detailed solution provided by SCR.


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, BjornSigurdJohansen@hotmail.com, DSolver 09-2004

BSJ2 - Bjørn Sigurd Johansen, BjornSigurdJohansen@hotmail.com, DSolver version2 05-2005.

CAINIAO - Zhu He, Longfei Wang, Weibo Lin, Yujie Chen, Haoyuan Hu (haoyuan.huhy@cainiao.com ), 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).

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.

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.

WA - Ruud Wagemaker. MSc thesis in progress. Tilburg University.

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