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:

ACVRPTW context

Capacitated Vehicle Routing Problem with Time Window
Java code version 12 will be freely available...soon.
IBM ILog CPLEX 12.6 (simplex) is used to solve the master instances of the column generation processes.
Bibliography
Tested on Solomon's benchmark: R1xx.100 instances (Random location for the 100 customers - 12 instances xx)
numerical experiments performed and saved in the database (see below)
The main results found in the literature are summarized on this page

Results for Solomon's instances

Please, select your parameters:
Results: Only the best results for each dataset
All the experiments for this dataset:

Number of clients:
Truck capacity: 200
Branch & Price:
Instance(1)SolutionconfigDist#Vehicspprctimetime best#nodes#Routes#SRCDetails
R101.100
38 configs
Map - Sched891637.720FP - OC2s0s45/4524430Login
 871637.720FP3s1s47/5716660Login
 881637.720FP - OC3s0s49/4920480Login
 911637.720FP3s2s9/916459Login
 91637.720FP4s3s9/9169941Login
 901637.720FP4s3s9/9169941Login
 931637.720FP4s3s9/9169941Login
 941637.720FP4s3s9/9169941Login
 951637.720FP4s3s9/9169941Login
 971637.720FP4s3s9/9169941Login
 1061637.720FP4s3s9/9169941Login
 1121637.720FSP4s3s9/9169941Login
 1131637.720FSP4s3s9/9169941Login
 1141637.720FP4s3s9/9169941Login
 1151637.720bidirsorted4s3s9/9169535Login
 731637.720FP5s4s9/9169941Login
 921637.720FP - OC5s4s9/9195039Login
 961637.720FP5s3s9/9178733Login
 1001637.720bidir5s4s9/9171139Login
 1011637.720bidir5s4s9/9170235Login
 1021637.720bidir5s4s9/9170235Login
 1031637.720FP5s4s9/9174447Login
 1041637.720FP5s3s9/9166441Login
 1051637.720FP5s3s9/9178733Login
 01637.720FP8s0s0/5900Login
 41637.720pulse8s5s0/5980Login
 51637.720FP8s5s0/5916700Login
 61637.720FP8s5s0/5916910Login
 521637.720FP8s5s47/5916530Login
 621637.720FP8s4s47/5915040Login
 631637.720FP8s5s47/5917010Login
 851637.720FP8s5s47/5915040Login
 841637.720FP - OC8s0s47/4719190Login
 981637.720F8s5s47/5915370Login
 11637.720bidir9s0s47/5915365Login
 991637.720bidir9s6s47/5915360Login
 31637.720FP12s0s0/5711700Login
 861637.720FP12s8s47/5715040Login
R102.100
38 configs
Map - Sched01466.618FP1s0s0/100Login
 11466.618bidir1s0s1/125751Login
 31466.618FP1s0s0/116960Login
 51466.618FP1s1s0/116960Login
 61466.618FP1s1s0/121930Login
 91466.618FP1s1s1/121970Login
 521466.618FP1s1s1/123720Login
 621466.618FP1s1s1/121970Login
 631466.618FP1s1s1/123090Login
 731466.618FP1s1s1/121970Login
 851466.618FP1s1s1/121970Login
 861466.618FP1s1s1/121970Login
 871466.618FP1s1s1/121970Login
 881466.618FP - OC1s0s1/124060Login
 841466.618FP - OC1s0s1/124060Login
 891466.618FP - OC1s0s1/124060Login
 901466.618FP1s1s1/121970Login
 911466.618FP1s1s1/121970Login
 931466.618FP1s1s1/121970Login
 941466.618FP1s1s1/121970Login
 951466.618FP1s1s1/121620Login
 961466.618FP1s1s1/121620Login
 971466.618FP1s1s1/121970Login
 1031466.618FP1s1s1/121620Login
 1041466.618FP1s1s1/121620Login
 1051466.618FP1s1s1/121970Login
 1061466.618FP1s1s1/121970Login
 1121466.618FSP1s1s1/121620Login
 1141466.618FP1s1s1/121620Login
 921466.618FP - OC2s2s1/124060Login
 1131466.618FSP2s2s1/121850Login
 41466.618pulse3s1s0/117230Login
 1011466.618bidir4s4s1/125150Login
 1021466.618bidir6s6s1/125470Login
 991466.618bidir9s9s1/126370Login
 1001466.618bidir11s11s1/126370Login
R103.100
38 configs
Map - Sched1141208.714FP9s9s1/1363663Login
 891208.714FP - OC10s0s25/2561840Login
 961208.714FP10s10s1/1363663Login
 1031208.714FP10s10s1/1363663Login
 1041208.714FP10s10s1/1363663Login
 951208.714FP11s11s1/1363663Login
 871208.714FP12s11s27/4736710Login
 881208.714FP - OC12s0s27/2757130Login
 1121208.714FSP13s13s1/13784102Login
 971208.714FP14s14s1/1389481Login
 731208.714FP15s15s1/1382849Login
 901208.714FP15s15s1/1389293Login
 931208.714FP15s15s1/1389293Login
 1051208.714FP15s15s1/1389293Login
 1131208.714FSP15s15s1/1389293Login
 91208.714FP16s16s1/1389293Login
 921208.714FP - OC16s16s1/1593699Login
 941208.714FP16s16s1/1389293Login
 1061208.714FP17s17s1/1389293Login
 911208.714FP24s24s5/7445390Login
 621208.714FP27s26s23/3947810Login
 521208.714FP28s26s23/3943960Login
 851208.714FP28s26s23/3947810Login
 841208.714FP - OC28s0s25/2556940Login
 861208.714FP29s27s23/3947810Login
R104.100
36 configs
Map - Sched114971.511FP17m 47s14m 6s23/2952623420Login
R105.100
76 configs
Map - Sched901355.315FP9s8s3/32480220Login
 951355.315FP9s7s3/32480220Login
 971355.315FP9s7s3/32455247Login
 1031355.315FP10s10s3/52542334Login
 1121355.315FSP10s10s3/52602348Login
 1141355.315FP10s10s3/52606367Login
 921355.315FP - OC11s8s3/33530259Login
 961355.315FP11s11s3/52542368Login
 1041355.315FP11s11s3/52542355Login
 1051355.315FP11s11s3/52542355Login
 1061355.315FP11s11s3/52771368Login
 1131355.315FSP11s11s3/52771368Login
 91355.315FP12s10s3/32584296Login
 931355.315FP13s13s3/52542372Login
 941355.315FP13s13s3/52771368Login
 731355.315FP17s14s3/32638181Login
 911355.315FP24s22s19/332364319Login
 331355.315FP28s22s0/26714660Login
R106.100
76 configs
Map - Sched971234.613FP33s26s3/33628275Login
 951234.613FP36s32s5/73471380Login
 891234.613FP - OC44s0s217/21784030Login
 921234.613FP - OC44s39s5/54936415Login
 931234.613FP51s44s3/33844420Login
 961234.613FP51s47s5/73579497Login
R107.100
75 configs
Map - Sched1031064.611FP2m 11s1m 28s3/34874440Login
 931064.611FP2m 28s1m 43s3/34867520Login
R108.100
69 configs
Map - Sched9932.110FP20m 52s20m 52s1/16724380Login
R109.100
39 configs
Map - Sched1121146.913FSP4m 1s2m 54s39/4336554987Login
R110.100
39 configs
Map - Sched95106812FP3m 0s1m 31s19/1937851720Login
R111.100
39 configs
 891048.712FP - OC24m 59s0s4225/4233366450Login
 951048.712FP35m 5s32m 57s121/143478410516Login
R112.100
36 configs
 112948.610FSP1h 41m 26s1h 28m 33s85/135518413120Login



Legend for the results:

  • Instance: name of Solomon's instance
      Solomon's description:

      The geographical data are randomly generated in problem sets R1 and R2, clustered in problem sets C1 and C2, and a mix of random and clustered structures in problem sets by RC1 and RC2. Problem sets R1, C1 and RC1 have a short scheduling horizon and allow only a few customers per route (approximately 5 to 10). In contrast, the sets R2, C2 and RC2 have a long scheduling horizon permitting many customers (more than 30) to be serviced by the same vehicle.

      The customer coordinates are identical for all problems within one type (i.e., R, C and RC). The problems differ with respect to the width of the time windows. Some have very tight time windows, while others have time windows which are hardly constraining. In terms of time window density, that is, the percentage of customers with time windows, I created problems with 25, 50, 75 and 100 % time windows.

      The larger problems are 100 customer euclidean problems where travel times equal the corresponding distances. For each such problem, smaller problems have been created by considering only the first 25 or 50 customers.

      Remark: .25/.50/.100 -> number of cities. Euclidean distances are truncated at the first decimal digit (as done by other authors).

      R101: 100% clients with TW=10R105: 100% clients with TW=30R109: 100% clients with TW= around N(60,9)
      R102: 75% clients with TW=10R106: 75% clients with TW=30R110: 100% clients with TW= around N(86,40)
      R103: 50% clients with TW=10R107: 50% clients with TW=30R111: 100% clients with TW= around N(93,54)
      R104: 25% clients with TW=10R108: 25% clients with TW=30R112: 100% clients with TW= around N(117,17)
      Depot: TW=[0;230]
  • Capa: Trucks capacity
  • #Veh: Number of vehicles in the optimal solutions.
  • Distance: Total distance for the optimal solution.
  • Exec time: real (not CPU) elapsed time in seconds - Computed on a personal laptop, Intel core i7, 8GB RAM (Java memory max heap: 1.8GB), Win7 - IBM ILog CPLEX 12.5 - March 2013
  • #Routes: maximal number of routes (columns/variables) in the biggest instance of the Column Generation master problem.
  • #nodes: number of nodes constructed by the Branch and Bound process (some could not be considered due to cuts)
  • Detailed routes: pictures representing the solution: geographical map with the sequences of visited cities by each vehicle + schedule
    This is the solution found by the algorithm. Other solutions with a same objectieve value could exist.

Some first remarks

  • The config that seems to work the best most of the time is:
  • The clustered instances are solved directly by the column generation! No need of a Branch and Bound framework (it explains why there is no simulation for the different BB parameters)
  • Confirmation: easier to solve instances with strong TW.
    Layout also matters (Random vs Cluster)
  • Strengthening the time windows (even with my adaption) doesn't seem to help!

More about the algorithm: references

  • Context: Gutiérrez-Jarpa et al.(2010), Laporte G. (1992),Toth P. and Vigo D. (2002)
  • Preprocessing - Heuristic for an initial upper bound: greedy - home made / preprocessing recommended in Kallehauge et al. (2005)
  • Preprocessing - Strengthening initially the time windows: Kallehauge et al. (2005)
  • Branch and Price: Gutiérrez-Jarpa et al.(2010), Desrosiers and Lübbecke (2005), Feillet (2010),
  • Branch and Bound - Branching strategies: home made - broad vs. deep, selection of var, selection of val
  • Branch and Bound - Strengthening globally the time windows: home made - new?
  • Branch and Bound - heuristics to find an upper bound during BB: greedy - home made / preprocessing recommended in Kallehauge et al. (2005),Desaulniers et al. (2008)
  • Branch and Bound - remove "useless" routes: home made - 3 strategies (1 new?)/ preprocessing recommended in Kallehauge et al. (2005),Desaulniers et al. (2002),Larsen (2004)
  • Column Generation - replace ESPPRC by a heuristic when suitable: home made - based on Bellman's SPP / replacing idea mentioned in the literature
  • ESSPRC (Elementary Shortest Path Problem with Resource Constraint): Gutiérrez-Jarpa et al.(2010), Feillet et al. (2004), Irnich and Desaulniers (2005)
  • ESPPRC - bidirectional vs. forward only: Righini and Salani (2006), Gutiérrez-Jarpa et al.(2010)
  • ESPPRC - stop when a given number of routes is found (forced early stop): Kallehauge et al. (2005), Larsen (1999)
  • ESPPRC - "relaxation" of the dominance criterium: home made but (to check) some analogies with Gutiérrez-Jarpa et al.(2010) citing Feillet et al. (2004) + Desaulniers et al (2008)

Bibliography

Main papers read to develop this software
  1. Baldacci R., Mingozzi A. and R. Roberti, 2012, Recent exact algorithms for solving the vehicle routing problem under capacity and time windows constraints, European Journal of Operational Research, 218, 1-6.
  2. Cordeau JF., Desaulniers G., Desrosiers J., Solomon M. and F. Soumis, 2002, Vehicle Routing Problems with Time Windows, In: Toth P. and D. Vigo (Editors), "The Vehicle Routing Problem", Siam monographs on Discrete Mathematics and Applications, 157-195.
  3. Desaulniers G., Lessard F. and A. Hadjar, 2008, Tabu Search, Partial Elementary, and Generalized k-Path Inequalitites for the Vehicle Routing Problem with Time Windows, "Transportation Science", 42(3),387-404.
  4. Desrochers M., Desrosiers J. and M. Solomon, 1992, A new optimization algorithm for the vehicle routing problem with time windows, "Operations Research", 40, March-April, 342-354
  5. Desrosiers J. and M.E. Lübbecke, 2005, A primer in column generation, In: Desrosiers, Desaulniers, Solomon (Editors), "Column Generation", Springer, (GERAD, 25th anniversary)
  6. Feillet D., 2010, A tutorial on column generation and branch-and-price for vehicle routing problems, "4OR-Q J Oper Res", 8, 407-424
  7. Feillet D., Dejax P., Gendreau M. and C. Gueguen, 2004,An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints: Application to some Vehicle Routing Problems, Networks, 44, 216-229
  8. Feillet D., Gendreau M. and LM Rousseau, ?after 2007?, New Refinements for the Solution of Vehicle Routing Problems with Branch and Price, Gerad, http://...
  9. Gambardella L., Taillard E. and G. Agazzi, 1999, MACS-VRPTW: a multiple ant colony system for Vehicle Routing Problems with time windows, In: Corne D., Dorigo M. and F. Glover (Editors), "New Ideas in Optimization", McGraw-Hill.
  10. Gutiérrez-Jarpa G., Desaulniers G., Laporte G. and V. Marianov, 2010, A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows", "European Journal of Operational Research", 206, 341-349.
  11. Irnich, S. and G. Desaulniers, 2005, Shortest path with resource constraints, In: Desrosiers, Desaulniers, Solomon (Editors), "Column Generation", Springer, (GERAD, 25th anniversary)
  12. 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.
  13. Kallehauge B., Larsen J., Madsen O. and M. Solomon, 2005, Vehicle routing problem with time windows, In: Desrosiers, Desaulniers, Solomon (Editors), "Column Generation", Springer, (GERAD, 25th anniversary)
  14. Laporte G., 1992, The Vehicle Routing Problem: An Overview of exact and approximate algorithms, "European Journal of Operational Research, 59, 345-358.
  15. Lozano, L., Medaglia, A. L., 2012, An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints, Tech. Rep. COPA-2012-2, Universidad de los Andes.
  16. Righini G. and M. Salani, 2006, Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints, "Discrete Optimization", 3, 255-273.
  17. Righini G. and M. Salani, 2008, New Dynamic Programming Algorithms for the Resource Constrained Elementary Shortest Path Problem, "Networks", 51(3), 155-170.
  18. Toth P. and D. Vigo (Editors), 2002, "The Vehicle Routing Problem", Siam monographs on Discrete Mathematics and Applications
Other papers
  1. Baldacci R., Christofides N. and A. Mingozzi, 2008, An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts, Mathematical Programming Series A, 115(2), 351-385
  2. Baldacci R., Mingozzi A., Roberti R., 2011, New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem, Operations Research, Vol 59(5), pp 1269-1283.
  3. Boland N., Dethridge J. and I. Dumitrescu, 2005, Accelerated label setting algorithms for the elementary resource constrained shortest path problem, "Oper Res Lett", 34(1), 58-68.
  4. [not yet read] Desaulniers G., Desrosiers J. and M. Solomon, 2002, Accelerating Strategies in column generation methods for vehicle routing and crew scheduling problems, In: Ribeiro C. and P. Hansen (Editors), "Essays and Surveys in Metaheuristics", Kulwer Academic Publishers, 309-324.
  5. Desaulniers G., Desrosiers J., Spoorendonk S., 2011, Cutting Planes for Branch-and-Price Algorithms, Networks, vol 58(4), pp301-310.
  6. Fukasawa R., Longo H., Lysgaard J., Poggi de Arag&atild;o M., Reis M., Uchoa E., Werneck R., 2006, Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem, Math. Program. Ser. A, vol 106, pp 491-511.
  7. [not yet read] Larsen J., 2004, Refinements of the column generation process for the vehicle routing problems with time windows, Journal of Systems Science and Systems Engineering, 13(3), 326-341.
  8. Lysgaard J., Lechtford A., Eglese R., 2004, A new branch-and-cut algorithm for the capacitated vehicle routing problem, Math Program. Ser. A, vol 100, pp 423-445
  9. [to read] Nagata Y., O. Bräysy and W. Dullaert, 2010, A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows, Computers & Operations Research, 37(4), 724-737.
  10. [not yet read] Spoorendonk S., Desaulniers G., 2010, Clique inequalities applied to vehicle routing problem with time windows, INFOR, vol 48, pp53-67.

 
 
  Michaël Schyns - Management Information Systems
Useful links: University of Liège - HEC-Management School - QuantOM - Chaudfontaine
Email: M.Schyns