NB! The benchmark and results part of these pages have been moved to

http://www.sintef.no/projectweb/top

The old pages will soon be unavailable.

Best Known Solutions for 1000-customer Benchmark Instances by Gehring and Homberger (1999)


Solutions are compared primarily on the criterion lowest number of vehicles utilised, and secondarily on shortest distance. A third criterion, waiting-time, may be considered as a further option for comparison.

Best Known Results for 1000-cases
Case
 Vehicles
 Distance
 Authors
 Date
c1_10_1 100
 42478,95 GH
c1_10_2 91
 42242,95 BSJ2
 23-may-05
c1_10_3 90
 40376,43 RP 25-feb-05
c1_10_4 90
 39735,30 MB 5-sept-05
c1_10_5 100
 42469,18 RP 25-feb-05
c1_10_6 100
 42470,04 MB 5-sept-05
c1_10_7 98
 42824,09 PGDR 17-oct-07
c1_10_8 93
 42499,59 PGDR 17-oct-07
c1_10_9 90
 41318,12 PGDR 17-oct-07
c1_1010 90
 40586,60 PGDR
 17-oct-07

c2_10_1
 30
 16879,24 LL
c2_10_2 29
 17144,29 BSJ2
 20-jul-05
c2_10_3 29
 16367,59 MB
 16-sep-03
c2_10_4 29
 15919,46 MB
 5-sept-05
c2_10_5 30
 16561,70 MB
 5-sept-05
c2_10_6 30
 16341,67 MB
 5-sept-05
c2_10_7 30
 16435,10 BSJ2
 20-jul-05
c2_10_8 29
 16315,89 BSJ2
 20-jul-05
c2_10_9 29
 16751,82 PGDR 17-oct-07
c2_1010 29
 15885,41 MB
 5-sept-05

r1_10_1
 100
 53904,23 PGDR
 17-oct-07
r1_10_2 91
 50701,78 PGDR
 17-oct-07
r1_10_3 91
 46169,17 PGDR
 17-oct-07
r1_10_4 91
 43461,84 MB
 16-sep-03
r1_10_5 91
 54032,44 PGDR
 17-oct-07
r1_10_6 91
 49059,80 MB
 16-sep-03
r1_10_7 91
 45729,79 PGDR
 17-oct-07
r1_10_8 91
 42767,77 MB
 16-sep-03
r1_10_9 91
 51391,80 MB
 16-sep-03
r1_1010 91
 49348,36 MB
 16-sep-03

r2_10_1
 19
 42467,87 MB
 5-sept-05
r2_10_2 19
 33589,08 BSJ2 20-jul-05
r2_10_3 19
 25321,00 BSJ2 09-jun-05
r2_10_4 19
 18222,30 BSJ2 20-jul-05
r2_10_5 19
 36735,20 MB 5-sept-05
r2_10_6 19
 30261,75 MB 16-sept-05
r2_10_7 19
 23463,80 BSJ2 09-jun-05
r2_10_8 19
 17705,20 BSJ2
 09-jun-05
r2_10_9 19
 33519,84 BSJ2 20-jul-05
r2_1010 19
 30706,00 BSJ2 20-jul-05

rc1_10_1
 90
 47143,90 MB
 16-sep-03
rc1_10_2 90
 44906,58 MB 16-sep-03
rc1_10_3 90
 43390,58 PGDR 17-oct-07
rc1_10_4 90
 41917,14 MB 16-sep-03
rc1_10_5 90
 46631,89 PGDR 17-oct-07
rc1_10_6 90
 46391,60 MB 16-sep-03
rc1_10_7 90
 46157,71 MB 16-sep-03
rc1_10_8 90
 45406,46 PGDR 17-oct-07
rc1_10_9 90
 45149,72 PGDR 17-oct-07
rc1_1010 90
 44947,71 PGDR 17-oct-07

rc2_10_1
 21
 29754,06 BSJ2
 20-jul-05
rc2_10_2 18
 27552,05 RP
 25-feb-05
rc2_10_3 18
 20276,16 BSJ2
 20-jul-05
rc2_10_4 18
 15954,60 BSJ2
 09-jun-05
rc2_10_5 18
 27766,56 BSJ2
 20-jul-05
rc2_10_6 18
 27003,30 MB 16-sep-03
rc2_10_7 18
 25526,73 BSJ2
 20-jul-05
rc2_10_8 18
 24335,40 BSJ2
 20-jul-05
rc2_10_9 18
 23465,51 BSJ2 20-jul-05
rc2_1010 18
 22481,03 BSJ
 20-sep-04







Legend:

BSJ - Bjørn Sigurd Johansen, BjornSigurdJohansen@hotmail.com, DSolver 09-2004

BSJ2 - Bjørn Sigurd Johansen, BjornSigurdJohansen@hotmail.com, 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.

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)

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