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.
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
38 configs
Map - Sched891637.720FP - OC2s0s45/4524430Login
 881637.720FP - OC3s0s49/4920480Login
 921637.720FP - OC5s4s9/9195039Login
 841637.720FP - OC8s0s47/4719190Login
38 configs
Map - Sched01466.618FP1s0s0/100Login
 881466.618FP - OC1s0s1/124060Login
 841466.618FP - OC1s0s1/124060Login
 891466.618FP - OC1s0s1/124060Login
 921466.618FP - OC2s2s1/124060Login
38 configs
Map - Sched1141208.714FP9s9s1/1363663Login
 891208.714FP - OC10s0s25/2561840Login
 881208.714FP - OC12s0s27/2757130Login
 921208.714FP - OC16s16s1/1593699Login
 841208.714FP - OC28s0s25/2556940Login
36 configs
Map - Sched114971.511FP17m 47s14m 6s23/2952623420Login
76 configs
Map - Sched901355.315FP9s8s3/32480220Login
 921355.315FP - OC11s8s3/33530259Login
76 configs
Map - Sched971234.613FP33s26s3/33628275Login
 891234.613FP - OC44s0s217/21784030Login
 921234.613FP - OC44s39s5/54936415Login
75 configs
Map - Sched1031064.611FP2m 11s1m 28s3/34874440Login
 931064.611FP2m 28s1m 43s3/34867520Login
69 configs
Map - Sched9932.110FP20m 52s20m 52s1/16724380Login
39 configs
Map - Sched1121146.913FSP4m 1s2m 54s39/4336554987Login
39 configs
Map - Sched95106812FP3m 0s1m 31s19/1937851720Login
39 configs
 891048.712FP - OC24m 59s0s4225/4233366450Login
 951048.712FP35m 5s32m 57s121/143478410516Login
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)


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