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 800-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 800-cases
Case
 Vehicles
 Distance
 Authors
 Date
c1_8_1 80
 25030,36 M
c1_8_2 74
 25528,55 PGDR 17-oct-07
c1_8_3 72
 24366,83 PGDR 17-oct-07
c1_8_4 72
 23917,70 MB 29-jul-05
c1_8_5 80
 25166,28 RP 25-feb-05
c1_8_6 80
 25160,83 MB 29-jul-05
c1_8_7 77
 26639,13 PGDR 17-oct-07
c1_8_8 74
 25370,02 PGDR 17-oct-07
c1_8_9 72
 24698,05 PGDR 17-oct-07
c1_810 72
 24324,76 PGDR
 17-oct-07

c2_8_1
 24
 11654,81 MB 16-sep-03
c2_8_2 23
 12332,37 PGDR 17-oct-07
c2_8_3 23
 11438,72 PGDR 17-oct-07
c2_8_4 23
 10963,49 MB 16-sep-03
c2_8_5 24
 11432,92 MB 16-sep-03
c2_8_6 24
 11357,86 MB 16-sep-03
c2_8_7 24
 11378,67 PGDR 17-oct-07
c2_8_8 23
 12927,45 MK
 03-feb-05
c2_8_9 23
 12301,63 PGDR
 17-oct-07
c2_810 23
 11163,89 PGDR 17-oct-07

r1_8_1
 79
 39612,2 BVH
r1_8_2 72
 33190,68 PGDR
 17-oct-07
r1_8_3 72
 29943,87 PGDR
 17-oct-07
r1_8_4 72
 26838,04 MB
 16-sep-03
r1_8_5 72
 34247,99 PGDR
 17-oct-07
r1_8_6 72
 31728,99 PGDR
 17-oct-07
r1_8_7 72
 29399,21 PGDR
 17-oct-07
r1_8_8 72
 28191,89 PGDR
 17-oct-07
r1_8_9 72
 33074,30 PGDR
 17-oct-07
r1_810 72
 31730,45 MB
 16-sep-03

r2_8_1
 15
 28392,87 PGDR
 17-oct-07
r2_8_2 15
 23274,22 RP
 25-feb-05
r2_8_3 15
 17992,25 MB
 16-sep-03
r2_8_4 15
 13413,79 RP
 25-feb-05
r2_8_5 15
 24611,39 MB
 16-sep-03
r2_8_6 15
 20697,06 MB
 16-sep-03
r2_8_7 15
 16977,49 RP
 25-feb-05
r2_8_8 15
 12945,52 RP
 25-feb-05
r2_8_9 15
 22588,02 MB
 16-sep-03
r2_810 15
 21092,27 RP
 25-feb-05

rc1_8_1
 72
 35102,79 PGDR
 17-oct-07
rc1_8_2 72
 33361,67 PGDR 17-oct-07
rc1_8_3 72
 30608,16 PGDR 17-oct-07
rc1_8_4 72
 28363,65 PGDR 17-oct-07
rc1_8_5 72
 34481,02 PGDR
 17-oct-07
rc1_8_6 72
 34849,96 PGDR
 17-oct-07
rc1_8_7 72
 33102,75 PGDR 17-oct-07
rc1_8_8 72
 33188,75 PGDR 17-oct-07
rc1_8_9 72
 33350,51 PGDR 17-oct-07
rc1_810 72
 31766,56 PGDR
 17-oct-07

rc2_8_1
 19
 20520,49 PGDR
 17-oct-07
rc2_8_2 17
 18032,89 RP 25-feb-05
rc2_8_3 15
 14800,78 RP 25-feb-05
rc2_8_4 15
 11312,68 MB 29-jul-05
rc2_8_5 16
 18917,65 PGDR
 17-oct-07
rc2_8_6 15
 18600,22 PGDR
 17-oct-07
rc2_8_7 15
 17327,53 MB 29-jul-05
rc2_8_8 15
 16203,18 MB 29-jul-05
rc2_8_9 15
 15622,52 MB 29-jul-05
rc2_810 15
 14892,29 MB
 16-sep-03







Legend:

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

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.

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.