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 600-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 600-cases
Case
 Vehicles
 Distance
 Authors
 Date
c1_6_1 60
 14095,64 GH
c1_6_2 56
 14163,31 PGDR
 17-oct-07
c1_6_3 56
 13781,19 PGDR
 17-oct-07
c1_6_4 56
 13571,88 MB
 18-jul-05
c1_6_5 60
 14085,70 BVH
c1_6_6 60
 14089,56 MB
 18-jul-05
c1_6_7 58
 14851,65 PGDR
 17-oct-07
c1_6_8 56
 14541,53 PGDR
 17-oct-07
c1_6_9 56
 13718,23 PGDR
 17-oct-07
c1_610 56
 13669,88 PGDR
 17-oct-07

c2_6_1
 18
 7774,10 MB
 16-sep-03
c2_6_2 17
 8380,49 PGDR
 17-oct-07
c2_6_3 17
 7595,43 PGDR
 17-oct-07
c2_6_4 17
 6993,77 RP
 25-feb-05
c2_6_5 18
 7575,20 BSJ2
 20-sep-07
c2_6_6 18
 7472,24 PGDR
 17-oct-07
c2_6_7 18
 7512,33 PGDR
 17-oct-07
c2_6_8 17
 7778,30 PGDR
 17-oct-07
c2_6_9 18
 7350,94 MB
 16-sep-03
c2_610 17
 7523,34 MB
 16-sep-03

r1_6_1
 59
 21131,09 MB
 16-sep-03
r1_6_2 54
 19147,38 PGDR
 17-oct-07
r1_6_3 54
 17216,16 PGDR
 17-oct-07
r1_6_4 54
 15947,03 PGDR
 17-oct-07
r1_6_5 54
 20017,80 PGDR
 17-oct-07
r1_6_6 54
 18237,76 PGDR
 17-oct-07
r1_6_7 54
 16796,63 PGDR
 17-oct-07
r1_6_8 54
 15725,86 MB
 16-sep-03
r1_6_9 54
 19015,51 PGDR
 17-oct-07
r1_610 54
 18204,18 PGDR
 17-oct-07

r2_6_1
 11
 18291,18 PGDR
 17-oct-07
r2_6_2 11
 14995,76 MB
 18-jul-05
r2_6_3 11
 11255,49 MB
 18-jul-05
r2_6_4 11
 8126,87 MB
 18-jul-05
r2_6_5 11
 15357,25 MB
 18-jul-05
r2_6_6 11
 12803,83 MB
 18-jul-05
r2_6_7 11
 10172,17 MB
 18-jul-05
r2_6_8 11
 7752,78 RP
 25-feb-05
r2_6_9 11
 13567,84 MB
 16-sep-03
r2_610 11
 12513,45 MB
 18-jul-05

rc1_6_1
 55
 17317,13 PGDR
 17-oct-07
rc1_6_2 55
 16123,40 PGDR
 17-oct-07
rc1_6_3 55
 15358,13 PGDR
 17-oct-07
rc1_6_4 55
 14872,79 MB
 18-jul-05
rc1_6_5 55
 16934,45 PGDR
 17-oct-07
rc1_6_6 55
 16842,27 PGDR
 17-oct-07
rc1_6_7 55
 16450,42 PGDR
 17-oct-07
rc1_6_8 55
 16164,82 PGDR
 17-oct-07
rc1_6_9 55
 16153,00 MB
 16-sep-03
rc1_610 55
 15936,81 PGDR
 17-oct-07

rc2_6_1
 15
 13163,03 RP
 25-feb-05
rc2_6_2 12
 11853,72 RP
 25-feb-05
rc2_6_3 11
 9816,47 MB
 18-jul-05
rc2_6_4 11
 7197,11 MB
 18-jul-05
rc2_6_5 12
 12168,79 PGDR
 17-oct-07
rc2_6_6 11
 12282,52 RP
 25-feb-05
rc2_6_7 11
 10929,56 MB
 18-jul-05
rc2_6_8 11
 10474,95 MB
 16-sep-03
rc2_6_9 11
 9821,39 MB
 18-jul-05
rc2_610 11
 9339,41 MB
 16-sep-03







Legend:

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

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

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.