SHORT BIO RESEARCH TEACHING
 
 

Vehicle Routing Problems: Algorithms and Solutions

M. Schyns, QuantOM research centre, HEC-Management School of the University of Liège.
Goals of this research:
  • Computation of the optimal solutions for the Vehicle Routing Problems with Time Windows. Approach: Branch-and-Cut-and-Price
  • Numerical experiments to test, simultaneously, many approaches found in the literature and a few new ideas
  • Selection and analysis of optimal parameters
  • Complete Java source code freely available for people interested
Other Tools developed for research:

Exact solutions for Solomon's VRPTW benchmarks

See bibliography below for explanations about the methods and environments
Times provided by the authors using different computers and at different periods of time(over 20 years).
In bold: first paper with a solution for this dataset.
Solomon's benchmark webpage.
R1xx.50R1xx.100
Instance#VehicDistPaperTime (s)
R101.50121044.0JPSP 20080.09
 FGR 20071.3
 KDMSS 19990.95
 CR 19991.67 (1p)*
R102.5011909.0JPSP 20080.27
 FGR 20072.2
 KDMSS 19993.66
 CR 19991.43 (1p)*
R103.509772.9JPSP 20082.02
 FGR 200721.1
 KDMSS 1999>57.66*
 CR 199947.37 (1p)*
R104.506625.4JPSP 20086.73
 FGR 2007319.4
 KDMSS 1999>1459.42*
 CR 1999489.87 (1p)*
R105.509899.3JPSP 20081.15
 FGR 200710.7
 KDMSS 1999>6.60*
 CR 19995.51 (1p)*
R106.508793.0JPSP 20080.83
 FGR 20076.0
 KDMSS 19998.75
 CR 19994.19 (1p)*
R107.507711.1JPSP 20084.76
 FGR 200780.5
 KDMSS 1999>95.93*
 CR 199967.07 (1p)*
R108.506617.7JPSP 20081601.68
 CR 19996359.41 (32p)**
 KLM 2000 
R109.507786.8JPSP 200811.54
 FGR 2007103.2
 KDMSS 1999>145.54*
 CR 199991.88 (1p)*
R110.507697.0JPSP 20081.46
 FGR 200712.8
 KDMSS 1999>21.20*
 CR 199912.16 (1p)*
R111.507707.2JPSP 20083.67
 FGR 2007237.5
 CR 1999477.35 (1p)*
 KLM 2000 
R112.506630.2JPSP 200835.67
 FGR 20073327.3
 CR 199943675.00 (1p)*
 KLM 2000 
Instance#VehicDistPaperTime (s)
R101.100201637.7JPSP 20081.87
 DLH 20088
 FGR 200718.3
 BMR 2011108
 CR 199937.51 (1p)*
 KDMSS 1999 
R102.100181466.6JPSP 20084.39
 DLH 20083
 FGR 200717.5
 BMR 2011119
 KDMSS 1999136.40
 CR 199934.92 (1p)*
R103.100141208.7JPSP 200823.85
 DLH 200820
 FGR 2007265
 BMR 2011123
 CR 1999741.60 (1p)*
 L 
R104.10011971.5JPSP 200832344
 DLH 20082260
 BMR 2011343
 IV 2006268106
R105.100151355.3JPSP 200843.12
 DLH 200825
 FGR 2007260.3
 BMR 2011113
 KDMSS 1999>386.13
 CR 1999251.37 (1p)*
R106.100131234.6JPSP 200875.42
 DLH 200887
 FGR 20071920.8
 BMR 2011129
 CR 199913975.23 (1p)*
 KLM 2000 
R107.100111064.6JPSP 20081310
 DLH 2008281
 BMR 2011193
 CR 19994050.73 (32p)*
 KLM 2000 
R108.100 932.1JPSP 20085912
 DLH 2008875
 BMR 2011344
R109.100131146.9JPSP 20081432
 DLH 20081127
 BMR 2011156
 CR 199919135.05 (32p)*
 KLM 2000 
R110.100121068.0JPSP 20081068
 DLH 2008426
 BMR 2011259
 CR 1999457024.92 (32p)*
 KLM 2000 
R111.100121048.7JPSP 200883931
 DLH 20085145
 BMR 2011255
 CR 199941879.97 (32p)*
 KLM 2000 
R112.100 948.6JPSP 2008202804
 DLH 200816073
 BMR 2011865
R2xx.50R2xx.100
Instance#VehicDistPaperTime (s)
R201.50 791.9JPSP 20084.97
 FGR 20077.0
 BMR 20115
 CR 1999 
 KLM 2000 
R202.50 698.5JPSP 20089.88
 FGR 200722.9
 BMR 20118
 CR 1999 
 KLM 2000 
R203.505605.3JPSP 200850.80
 FGR 2007381.5
 BMR 201162
 IV 2006470.4
 C 20063320.9
 CR 1999 
 KLM 2000 
R204.502506.4BMR 2011131
 IV 200623749.5
R205.504690.1JPSP 200815.45
 FGR 2007565.7
 BMR 201162
 IV 20061091.4
 C 2006531.0
R206.504632.4JPSP 2008190.86
 BMR 201174
 IV 200622455.3
 C 20064656.1
R207.50 575.5JPSP 200834407
 BMR 2011154
R208.50 487.7BMR 2011537
R209.504600.6JPSP 200816.63
 FGR 200792.6
 BMR 201160
 IV 2006255.4
 C 2006195.4
R210.504645.6JPSP 200818546
 BMR 201194
 IV 200611551.4
 C 200665638.6
R211.503535.5JPSP 200810544
 BMR 2011179
 IV 200621323.0
 DLP 200594411
Instance#VehicDistPaperTime (s)
R201.100 1143.2JPSP 2008139.03
 DLH 200878
 FGR 20071104.4
 BMR 2011180
 KLM 2000 
R202.100 1029.6JPSP 20088282
 DLH 20081365
 BMR 20113406
R203.100 870.8JPSP 200854187
 DLH 2008641
 BMR 20112139
R204.1005731.3BMR 2011216367
R205.100 949.8DLH 20086904
 BMR 20111433
R206.100 875.9DLH 200826940
 BMR 20116675
R207.100 794.0DLH 20084214
 BMR 20111401
R208.100 701.2  
R209.100 854.8JPSP 200878560
 DLH 200810270
 BMR 20114496
R210.100 900.5DLH 2008400904
 BMR 201139711
R211.1004746.7BMR 201110993
RC1xx.50RC1xx.100
Instance#VehicDistPaperTime (s)
RC101.508944.0JPSP 20082.12
 FGR 20076.8
 KDMSS 1999>11.19*
 CR 19996.98 (1p)*
RC102.507822.5JPSP 20088.68
 FGR 2007251.0
 KDMSS 1999>671.11*
 CR 1999671.32 (1p)*
RC103.506710.9JPSP 200840.05
 FGR 200726.2
 KDMSS 1999>25.22*
 CR 199944.5 (1p)*
RC104.505545.8JPSP 20085.71
 FGR 200717.5
 KDMSS 1999>169.02*
 CR 199958.89 (1p)*
RC105.508855.3JPSP 20084.31
 FGR 200711.6
 KDMSS 1999>41.00*
 CR 199938.83 (1p)*
RC106.506723.2JPSP 20083.88
 FGR 200736.6
 KDMSS 1999>54.07*
 CR 199929.61 (1p)*
RC107.506642.7JPSP 20084.49
 FGR 200760.9
 KDMSS 1999>251.08*
 CR 1999139.08 (1p)*
RC108.506598.1JPSP 2008260.95
 FGR 2007243.8
 KDMSS 1999>723.37*
 CR 199956.80 (1p)*
Instance#VehicDistPaperTime (s)
RC101.100141619.8JPSP 200812.39
 DLH 200817
 FGR 2007222.5
 BMR 2011105
 KDMSS 1999>138.51*
 CR 1999136.23 (1p)*
RC102.100141457.4JPSP 200876.69
 DLH 2008118
 BMR 2011138
 CR 199942150.49 (32p)*
RC103.100111258.0JPSP 20082706
 DLH 2008295
 BMR 2011435
 CR 199984438.90 (32p)*
RC104.100101132.3JPSP 200865807
 DLH 20082874
 BMR 2011561
 IV 2006986809.0
RC105.100151513.7JPSP 200826.73
 DLH 200814
 FGR 2007199.4
 BMR 2011116
 KDMSS 1999>278.06*
 CR 1999502.27 (1p)*
RC106.100 1372.7JPSP 200815892
 DLH 20083045
 BMR 2011413
RC107.100121207.8JPSP 2008153.8
 DLH 200892
 BMR 2011127
 IV 200642770.7
RC108.100111114.2JPSP 20083365
 DLH 2008279
 BMR 2011315
 IV 200671263.0
RC2xx.50RC2xx.100
Instance#VehicDistPaperTime (s)
RC201.50 684.8JPSP 20083
 FGR 20073.4
 BMR 20118
RC202.505613.6JPSP 200810.69
 FGR 200713.0
 BMR 20117
 IV 2006503.3
 C 200613.0
RC203.504555.3JPSP 2008190.88
 FGR 2007702.7
 BMR 201115
 IV 200654229.2
 C 20064481.5
RC204.503444.2BMR 201127
 DLP 200584059
RC205.505630.2JPSP 20085.88
 FGR 20077.7
 BMR 20119
 IV 200682.4
 C 200610.6
RC206.505610.0JPSP 20088.17
 FGR 20075.8
 BMR 20119
 IV 2006934.9
 C 20069.4
RC207.504558.6JPSP 200821.53
 FGR 200746.3
 BMR 20118
 C 200671.1
RC208.50 476.7JPSP 20081639.40
 BMR 2011129
Instance#VehicDistPaperTime
RC201.100 1261.8JPSP 2008229.27
 DLH 200892
 FGR 2007992.2
 BMR 2011157
RC202.10081092.3JPSP 2008312.57
 DLH 200889
 FGR 20073526.2
 BMR 2011183
 IV 2006124018.0
 C 200619636.5
RC203.100 923.7JPSP 200814917
 DLH 2008324
 BMR 2011252
RC204.1004783.5BMR 20111052
RC205.10071154.0JPSP 2008221.24
 DLH 2008111
 BMR 2011172
 IV 200613295.9
 C 200615151.7
RC206.100 1051.1JPSP 2008339.69
 DLH 2008344
 BMR 2011227
RC207.100 962.9DLH 200891405
 BMR 201126903
RC208.1004776.1BMR 20111195
xx.200
Instance#VehicDistPaperTime
C1.200 2698.6CR 1999106.98 (4p)
C2.200 2694.3CR 19996121.15 (4p)
C5.200 2694.9CR 1999140.49 (4p)
C6.200 2694.9CR 1999190.80 (4p)
C7.200 2694.9CR 1999228.97 (4p)
C8.200 26984.0CR 199911850.68 (4p)
R1.200 4667.2CR 19993587.01 (4p)

References

  • [BMR] R. Baldacci, A. Mingozzi, R. Roberti, 2011, "New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem", Operations Research, Vol 59(5), 1269-1283.
    Environment: 2.93GHz Intel Xeon X7350 with 16GB, CPLEX 12.1, Fortran 77.
  • [C] A. Chabrier, 2006, "Vehicle Routing Problem with Elementary Shortest Path based Column Generation.", Computers and Operations Research, 33, pp2972-2990
    Environment: 1.5Ghz Pentium IV with 256MB, ILOG JNI CPLEX 7.5, ILOG JSolver 1.0, Java VM, Linux
    Routes not provided, partial results for C1,R1,RC1,C2,R2 and RC2
  • [CR] W. Cook and J. L. Rich, 1999, "A parallel cutting plane algorithm for the vehicle routing problem with time windows," Working Paper, Computational and Applied Mathematics, Rice University, Houston, TX.
    Environment: 300MHz Pentium II with 256MB, 32 parallel workstations, CPlex 5.0, C programming language, unix
    *1p=1 processor,16p=16 processors, 32p=32 processors.
    Routes not provided, partial results for other sets.
  • [DLH] G. Desaulniers, F. Lessard, A. Hadjar, 2008, "Tabu Search, Partial Elementary, and Generalized k-Path Inequalities for the Vehicle Routing Problem with Time Windows", Transportation Science, 42(3), 387-404.
    Environment: AMD Dual Core 2.6GHz, Linux, Gencol software with CPLEX 9.0.
    Remark: different methods are proposed. Only the best time provided (not always the same method)
  • [DLP] E. Danna and C. Le Pape, 2005, "Accelerating branch-and-price with local search: A case study on the vehicle routing problem with time windows," In: Column Generation, G. Desaulniers, J. Desrosiers, and M. M. Solomon (eds.), 99-130, Kluwer Academic Publishers.
    Environment:1.5GHz Pentium IV with 256MB, ILOG CPLEX 8.1, ILOG SOLVER 5.3, ILOG DISPATCHER 3.3
  • [FGR] D. Feillet, M. Gendreau, LM Rousseau, 2005, New Refinements for the Solution of Vehicle Routing Problems with Branch and Price”, Information System and Operations Research (INFOR) 45:4, 239-256.
    Environment: 1.6GHz with 256MB, CPLEX 9.0
  • [IV] S. Irnich and D. Villeneuve, 2006, The shortest path problem with k-cycle elimination (k = 3): Improving a branch-and-price algorithm for the VRPTW.", INFORMS Journal of Computing, Vol 18(3), 391-406
    Environment: 600MHz Pentium III with 512MB, CPLEX 7.0, C++.
  • [JPSP]
  • Jepsen M., Petersen B., Spoorendonk S., D. Pisinger, 2008, "Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows", Operations Research, 56(2), pp497-511.
  • [KDMSS] N. Kohl, J. Desrosiers, O. B. G. Madsen, M. M. Solomon, and F. Soumis, 1999, "2-Path Cuts for the Vehicle Routing Problem with Time Windows," Transportation Science, Vol. 33 (1), 101-116.
    Environment: 100MHz PA7200 (HP9000/829), CPLEX 3.0, C programming language, unix, cpu-times
    Other optimal solutions found but without proof of optimality (if I've well understood)=> ">&x seconds=time to find optim
  • [KLM] B. Kallehauge, J. Larsen, and O.B.G. Madsen, 2000, "Lagrangean duality and non-differentiable optimization applied on routing with time windows - experimental results." Internal report IMM-REP-2000-8, Department of Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark.
  • [L] J. Larsen, 1999, "Parallelization of the vehicle routing problem with time windows." Ph.D. Thesis IMM-PHD-1999-62, Department of Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark.

Exact results not (yet) incorporated in the tables:
 
 
  Michaël Schyns - Management Information Systems
Useful links: University of Liège - HEC-Management School - QuantOM - Chaudfontaine
Email: M.Schyns