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: Automatic Aircraft Cargo Load Planning Airline Joint Revenue Management Responsive Dynamic VRPTW - airport case Vehicle Routing Problems Robust statistics (Old) Financial portfolio optimization

ACVRPTW context

Results for Solomon's instances

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=10	R105: 100% clients with TW=30	R109: 100% clients with TW= around N(60,9)
  R102: 75% clients with TW=10	R106: 75% clients with TW=30	R110: 100% clients with TW= around N(86,40)
  R103: 50% clients with TW=10	R107: 50% clients with TW=30	R111: 100% clients with TW= around N(93,54)
  R104: 25% clients with TW=10	R108: 25% clients with TW=30	R112: 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

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

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.