Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Generic Exact Solver for Vehicle Routing and Related Problems

  • Conference paper
  • First Online:
Integer Programming and Combinatorial Optimization (IPCO 2019)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 11480))

Abstract

Major advances were recently obtained in the exact solution of Vehicle Routing Problems (VRPs). Sophisticated Branch-Cut-and-Price (BCP) algorithms for some of the most classical VRP variants now solve many instances with up to a few hundreds of customers. However, adapting and reimplementing those successful algorithms for other variants can be a very demanding task. This work proposes a BCP solver for a generic model that encompasses a wide class of VRPs. It incorporates the key elements found in the best recent VRP algorithms: ng-path relaxation, rank-1 cuts with limited memory, and route enumeration; all generalized through the new concept of “packing set”. This concept is also used to derive a new branch rule based on accumulated resource consumption and to generalize the Ryan and Foster branch rule. Extensive experiments on several variants show that the generic solver has an excellent overall performance, in many problems being better than the best existing specific algorithms. Even some non-VRPs, like bin packing, vector packing and generalized assignment, can be modeled and effectively solved.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 59.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 79.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Archetti, C., Bianchessi, N., Speranza, M.: Optimal solutions for routing problems with profits. Discrete Appl. Math. 161(4–5), 547–557 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  2. Archetti, C., Feillet, D., Hertz, A., Speranza, M.G.: The capacitated team orienteering and profitable tour problems. J. Oper. Res. Soc. 60(6), 831–842 (2009)

    Article  MATH  Google Scholar 

  3. Avella, P., Boccia, M., Vasilyev, I.: A computational study of exact knapsack separation for the generalized assignment problem. Comput. Optim. Appl. 45(3), 543–555 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  4. Baldacci, R., Bartolini, E., Mingozzi, A.: An exact algorithm for the pickup and delivery problem with time windows. Oper. Res. 59(2), 414–426 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  5. Baldacci, R., Christofides, N., Mingozzi, A.: An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Program. 115, 351–385 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  6. Baldacci, R., Mingozzi, A.: A unified exact method for solving different classes of vehicle routing problems. Math. Program. 120(2), 347–380 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  7. Baldacci, R., Mingozzi, A., Roberti, R.: New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5), 1269–1283 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  8. Balinski, M., Quandt, R.: On an integer program for a delivery problem. Oper. Res. 12(2), 300–304 (1964)

    Article  Google Scholar 

  9. Bartolini, E., Cordeau, J.F., Laporte, G.: Improved lower bounds and exact algorithm for the capacitated arc routing problem. Math. Program. 137(1), 409–452 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  10. Beasley, J.E.: OR-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11), 1069–1072 (1990)

    Article  Google Scholar 

  11. Belenguer, J., Benavent, E.: The capacitated arc routing problem: valid inequalities and facets. Comput. Optim. Appl. 10(2), 165–187 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  12. Belov, G., Scheithauer, G.: A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. Eur. J. Oper. Res. 171(1), 85–106 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  13. Bianchessi, N., Mansini, R., Speranza, M.G.: A branch-and-cut algorithm for the team orienteering problem. Int. Trans. Oper. Res. 25(2), 627–635 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  14. Bode, C., Irnich, S.: Cut-first branch-and-price-second for the capacitated arc-routing problem. Oper. Res. 60(5), 1167–1182 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  15. Brandão, F., Pedroso, J.P.: Bin packing and related problems: general arc-flow formulation with graph compression. Comput. Oper. Res. 69, 56–67 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  16. Bulhoes, T., Hà, M.H., Martinelli, R., Vidal, T.: The vehicle routing problem with service level constraints. Eur. J. Oper. Res. 265(2), 544–558 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  17. Bulhoes, T., Sadykov, R., Uchoa, E.: A branch-and-price algorithm for the minimum latency problem. Comput. Oper. Res. 93, 66–78 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  18. Caprara, A., Toth, P.: Lower bounds and algorithms for the 2-dimensional vector packing problem. Discrete Appl. Math. 111(3), 231–262 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  19. Chao, I.M., Golden, B.L., Wasil, E.A.: The team orienteering problem. Eur. J. Oper. Res. 88(3), 464–474 (1996)

    Article  MATH  Google Scholar 

  20. Christofides, N., Eilon, S.: An algorithm for the vehicle-dispatching problem. Oper. Res. Q. 20, 309–318 (1969)

    Article  Google Scholar 

  21. Christofides, N., Mingozzi, A., Toth, P.: The vehicle routing problem. In: Christofides, N., Mingozzi, A., Toth, P. (eds.) Combinatorial Optimization, pp. 315–338. Wiley, Chichester (1979)

    MATH  Google Scholar 

  22. Clautiaux, F., Hanafi, S., Macedo, R., Émilie Voge, M., Alves, C.: Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints. Eur. J. Oper. Res. 258(2), 467–477 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  23. Contardo, C., Martinelli, R.: A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optim. 12, 129–146 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  24. Cordeau, J.F., Gendreau, M., Laporte, G.: A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30(2), 105–119 (1997)

    Article  MATH  Google Scholar 

  25. Dantzig, G., Ramser, J.: The truck dispatching problem. Manage. Sci. 6(1), 80–91 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  26. Delorme, M., Iori, M., Martello, S.: Bin packing and cutting stock problems: mathematical models and exact algorithms. Eur. J. Oper. Res. 255(1), 1–20 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  27. Desaulniers, G., Desrosiers, J., loachim, I., Solomon, M.M., Soumis, F., Villeneuve, D.: A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. In: Crainic, T.G., Laporte, G. (eds.) Fleet Management and Logistics. CRT, pp. 57–93. Springer, Boston (1998). https://doi.org/10.1007/978-1-4615-5755-5_3

    Chapter  Google Scholar 

  28. Desaulniers, G., Lessard, F., Hadjar, A.: Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows. Transp. Sci. 42(3), 387–404 (2008)

    Article  Google Scholar 

  29. Dunning, I., Huchette, J., Lubin, M.: JuMP: a modeling language for mathematical optimization. SIAM Rev. 59(2), 295–320 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  30. Eglese, R.W., Li, L.Y.O.: Efficient routeing for winter gritting. J. Oper. Res. Soc. 43(11), 1031–1034 (1992)

    Article  Google Scholar 

  31. El-Hajj, R., Dang, D.C., Moukrim, A.: Solving the team orienteering problem with cutting planes. Comput. Oper. Res. 74, 21–30 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  32. Falkenauer, E.: A hybrid grouping genetic algorithm for bin packing. J. Heurist. 2, 5–30 (1996)

    Article  Google Scholar 

  33. Fukasawa, R., et al.: Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Program. 106(3), 491–511 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  34. Gehring, H., Homberger, J.: Parallelization of a two-phase metaheuristic for routing problems with time windows. J. Heurist. 8(3), 251–276 (2002)

    Article  MATH  Google Scholar 

  35. Gschwind, T., Irnich, S., Rothenbächer, A.K., Tilk, C.: Bidirectional labeling in column-generation algorithms for pickup-and-delivery problems. Eur. J. Oper. Res. 266(2), 521–530 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  36. Gurobi Optimization, Inc.: Gurobi optimizer reference manual, version 7.5 (2017). http://www.gurobi.com

  37. Heßler, K., Gschwind, T., Irnich, S.: Stabilized branch-and-price algorithms for vector packing problems. Eur. J. Oper. Res. 271(2), 401–419 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  38. Jepsen, M., Petersen, B., Spoorendonk, S., Pisinger, D.: Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2), 497–511 (2008)

    Article  MATH  Google Scholar 

  39. Kallehauge, B., Larsen, J., Madsen, O.: Lagrangian duality applied to the vehicle routing problem with time windows. Comput. Oper. Res. 33(5), 1464–1487 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  40. Laporte, G., Nobert, Y.: A branch and bound algorithm for the capacitated vehicle routing problem. Oper.-Res.-Spektrum 5(2), 77–85 (1983)

    Article  MATH  Google Scholar 

  41. Li, H., Lim, A.: A metaheuristic for the pickup and delivery problem with time windows. Int. J. Artif. Intell. Tools 12(02), 173–186 (2003)

    Article  Google Scholar 

  42. Lysgaard, J.: CVRPSEP: a package of separation routines for the capacitated vehicle routing problem. Aarhus School of Business, Department of Management Science and Logistics (2003)

    Google Scholar 

  43. Lysgaard, J., Letchford, A.N., Eglese, R.W.: A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Program. 100(2), 423–445 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  44. Nauss, R.M.: Solving the generalized assignment problem: an optimizing and heuristic approach. INFORMS J. Comput. 15(3), 249–266 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  45. Pecin, D., Pessoa, A., Poggi, M., Uchoa, E.: Improved branch-cut-and-price for capacitated vehicle routing. In: Lee, J., Vygen, J. (eds.) IPCO 2014. LNCS, vol. 8494, pp. 393–403. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07557-0_33

    Chapter  MATH  Google Scholar 

  46. Pecin, D., Contardo, C., Desaulniers, G., Uchoa, E.: New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS J. Comput. 29(3), 489–502 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  47. Pecin, D., Pessoa, A., Poggi, M., Uchoa, E.: Improved branch-cut-and-price for capacitated vehicle routing. Math. Program. Comput. 9(1), 61–100 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  48. Pecin, D., Pessoa, A., Poggi, M., Uchoa, E., Santos, H.: Limited memory rank-1 cuts for vehicle routing problems. Oper. Res. Lett. 45(3), 206–209 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  49. Pecin, D., Uchoa, E.: Comparative analysis of capacitated arc routing formulations for designing a new branch-cut-and-price algorithm. Transp. Sci. (2019, to appear)

    Google Scholar 

  50. Pessoa, A., Sadykov, R., Uchoa, E.: Enhanced branch-cut-and-price algorithm for heterogeneous fleet vehicle routing problems. Eur. J. Oper. Res. 270, 530–543 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  51. Pessoa, A., Sadykov, R., Uchoa, E., Vanderbeck, F.: Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS J. Comput. 30(2), 339–360 (2018)

    Article  MathSciNet  Google Scholar 

  52. Poggi de Aragão, M., Uchoa, E.: Integer program reformulation for robust branch-and-cut-and-price. In: Wolsey, L. (ed.) Annals of Mathematical Programming in Rio, Búzios, Brazil, pp. 56–61 (2003)

    Google Scholar 

  53. Posta, M., Ferland, J.A., Michelon, P.: An exact method with variable fixing for solving the generalized assignment problem. Comput. Optim. Appl. 52, 629–644 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  54. Roberti, R., Mingozzi, A.: Dynamic ng-path relaxation for the delivery man problem. Transp. Sci. 48(3), 413–424 (2014)

    Article  Google Scholar 

  55. Røpke, S.: Branching decisions in branch-and-cut-and-price algorithms for vehicle routing problems. In: Presentation in Column Generation 2012 (2012)

    Google Scholar 

  56. Ropke, S., Cordeau, J.F.: Branch and cut and price for the pickup and delivery problem with time windows. Transp. Sci. 43(3), 267–286 (2009)

    Article  Google Scholar 

  57. Ryan, D.M., Foster, B.A.: An integer programming approach to scheduling. In: Wren, A. (ed.) Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling, pp. 269–280. North-Holland, Amsterdam (1981)

    Google Scholar 

  58. Sadykov, R., Uchoa, E., Pessoa, A.: A bucket graph based labeling algorithm with application to vehicle routing. Technical report L-2017-7, Cadernos do LOGIS-UFF, Niterói, Brazil, October 2017

    Google Scholar 

  59. Sadykov, R., Vanderbeck, F., Pessoa, A., Tahiri, I., Uchoa, E.: Primal heuristics for branch-and-price: the assets of diving methods. INFORMS J. Comput. (2018)

    Google Scholar 

  60. Schoenfield, J.E.: Fast, exact solution of open bin packing problems without linear programming. Technical report, US Army Space and Missile Defense Command (2002)

    Google Scholar 

  61. Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2), 254–265 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  62. Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Subramanian, A., Vidal, T.: New benchmark instances for the capacitated vehicle routing problem. Eur. J. Oper. Res. 257(3), 845–858 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  63. Vanderbeck, F., Sadykov, R., Tahiri, I.: BaPCod – a generic Branch-And-Price Code (2018). https://realopt.bordeaux.inria.fr/?page_id=2

  64. Vanderbeck, F., Wolsey, L.A.: Reformulation and decomposition of integer programs. In: Jünger, M., et al. (eds.) 50 Years of Integer Programming 1958–2008, pp. 431–502. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-540-68279-0_13

    Chapter  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Inria Bordeaux — Sud-Ouest, Talence, France

    Ruslan Sadykov & François Vanderbeck

  2. University of Bordeaux, Talence, France

    Ruslan Sadykov & François Vanderbeck

  3. Universidade Federal Fluminense, Niterói, Brazil

    Artur Pessoa & Eduardo Uchoa

Authors
  1. Artur Pessoa
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ruslan Sadykov
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Eduardo Uchoa
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. François Vanderbeck
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ruslan Sadykov .

Editor information

Editors and Affiliations

  1. École Polytechnique de Montréal, Montreal, QC, Canada

    Andrea Lodi

  2. University of Michigan, Ann Arbor, MI, USA

    Viswanath Nagarajan

Appendices

A Additional Information on the Experiments

We provide additional information about the experiments reported in Table 1, including relevant modeling decisions, datasets and remarks.

Note that the performance of exact algorithms is sensitive to the initial primal bound value given by the user before execution. We tried to be as fair as possible in this regard. Unless stated otherwise for the problems below we use the same bounds (usually took from the heuristic literature) as in previous works.

CVRP (Capacitated Vehicle Routing Problem): The model is defined over undirected edge variables and separates Rounded Capacity Cuts (RCCs) [40], using the procedure in CVRPSEP [42]. A packing set is defined for each customer and contains all incoming arcs to the corresponding node in the graph. Branching is done over edge variables. The considered E-M instances are the 12 hardest ones, those considered in [47]. The considered X instances are those with less than 400 customers.

VRPTW (Vehicle Routing Problem with Time Windows): The same model as CVRP except that only time is defined as a graph resource, capacity is enforced by RCCs. The considered Solomon instances (all with 100 customers) are the hardest ones according to [46].

HFVRP (Heterogeneous Fleet Vehicle Routing Problem): The model is defined over undirected edge variables. Each graph \(G^k\) (with capacity resource) corresponds to a vehicle type. Branching is on the number of paths in \(P^k\), assignment of packing sets to graphs, and on edge variables. Instances with 50, 75, and 100 customers are considered.

MDVRP (Multi-Depot Vehicle Routing problem): The model is defined over undirected edge variables. Each graph \(G^k\) corresponds to a depot. Branching is the same as for HFVRP. Only instances with one capacity resource are considered (without time constraints).

PDPTW: The model is precisely defined in Sect. 4.3.

TOP/CTOP (Team Orienteering Problem): The model contains binary variables y that are not mapped to any RCSP graph, so they appear directly in Formulation 2. Those variables indicate which customers will be visited. The problem is to maximize the total profit of visited customers. For TOP, one (time) resource is defined. In CTOP, an additional capacity resource is considered. Branching is on y and edge variables. No initial upper bound is defined. Instances of class 4, the most difficult one according to [13], are considered for TOP. Only basic instances from [2] are considered for CTOP, as well as open ones.

CPTP (Capacitated Profitable Tour Problem): Similar to CTOP, except that there is no time resource. The objective is the difference between the total profit and the transportation cost. Only open instances from [2] are considered.

VRPSL (VRP with Service Level constraints): Generalization of CVRP in which a service weight is defined for each customer. For each predefined group of customers, total service weight of visited customers should not be below a threshold. The model contains edge and y variables. For each group, a knapsack constraint over y variables is defined. Branching is both on y and edge variables.

GAP: The model is precisely defined in Sect. 4.1. Instances of the most difficult type D are considered. For OR-Library instances, we took best known solution values as initial upper bounds. We used Nauss instances with \(|T|=90,100\) and \(|K|=25,30\). Initial bounds for them were calculated by us using problem specific strong diving heuristic from [58]. Its time is included in the reported time.

BPP/VPP: The model is precisely defined in Sect. 4.2. The branching over the accumulated resource consumption showed to be effective so that Ryan and Foster branch rule was never needed. For VPP, we took only largest instances (200 items) with 2 resources of classes 1, 4, 5, and 9, the most difficult ones according to [37]. No initial bound is given for VPP. For BPP, we used the initial primal bound equal to the rounded up column generation dual bound plus one. Such solutions are easily obtainable by very simple heuristics.

CARP: The model is defined in Sect. 4.4. The branching is done on aggregation of x variables: (1) corresponding to node degrees in the original graph; (2) corresponding to whether required two edges are served immediately one after another by the same route or not. The Eglese dataset is used in all recent works on CARP.

B Open CVRP Instances Solved

According to CVRPLIB (http://vrp.atd-lab.inf.puc-rio.br) there were 52 open CVRP instances in the X set [62]. We started long runs of the generic solver on the most promising ones, using a specially calibrated parameterization. We could solve 5 instances to optimality for the first time, as indicated in Table 2. Improved best known solutions are underlined.

Table 2. Detailed results on the open instances solved.
Full size table

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Pessoa, A., Sadykov, R., Uchoa, E., Vanderbeck, F. (2019). A Generic Exact Solver for Vehicle Routing and Related Problems. In: Lodi, A., Nagarajan, V. (eds) Integer Programming and Combinatorial Optimization. IPCO 2019. Lecture Notes in Computer Science(), vol 11480. Springer, Cham. https://doi.org/10.1007/978-3-030-17953-3_27

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-17953-3_27

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-17952-6

  • Online ISBN: 978-3-030-17953-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation