[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

A branch-and-cut algorithm for vehicle routing problems

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

We present a branch-and-cut algorithm for the identical customer Vehicle Routing Problem. Transforming the problem into an equivalent Path-Partitioning Problem allows us to exploit its polyhedral structure and to generate strong cuts corresponding to facet-inducing inequalities. By using cuts defined by multistars, partial multistars and generalized subtour elimination constraints, we are able to consistently solve 60-city problems to proven optimality and are currently attempting to solve problems involving a hundred cities. We also present details of the computer implementation and our computational results.

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

Access this article

Subscribe and save

Springer+ Basic
£29.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

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. J.R. Araque G., Contributions to the polyhedral approach to vehicle routing, Ph.D. Dissertation, State University of New York at Stony Brook, Stony Brook, NY (1989).

    Google Scholar 

  2. J.R. Araque G., Solution of a 48-city vehicle routing problem by branch-and-cut, Working Paper, Department of Applied Mathematics and Statistics, SUNY at Stony Brook, Stony Brook, NY (1989).

    Google Scholar 

  3. J.R. Araque G., Lots of combs of different sizes for vehicle routing, Working Paper No. 9074, C.O.R.E., Université Catholique de Louvain, Louvain-la-Neuve, Belgium (1990).

    Google Scholar 

  4. J.R. Araque G., L. Hall and T.L. Magnanti, Capacitated trees, capacitated routing, and associated polyhedra, Working Paper No. 9061, C.O.R.E., Université Catholique de Louvain, Louvain-la-Neuve, Belgium (1990).

    Google Scholar 

  5. I. Barany, T.J. Van Roy and L.A. Wolsey, Strong formulations for multi-item capacitated lot sizing, Manag. Sci. 30(1984)1255–1261.

    Google Scholar 

  6. L. Bodin, B.L. Golden, A.A. Assad and M. Ball, Routing and scheduling of vehicles and crews: the state of the art, Comp. Oper. Res. 10(1983)62–212.

    Google Scholar 

  7. N. Christofides, The vehicle routing problem, RAIRO Recherche Opèrationelle 10 (1976) 55–70.

    Google Scholar 

  8. N. Christofides, Vehicle routing, in:The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, ed. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys (Wiley, New York, 1985) pp. 431–448.

    Google Scholar 

  9. N. Christofides, A. Mingozzi and P. Toth, Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxation, Math. Progr. 20(1981)255–282.

    Google Scholar 

  10. G. Clarke and J.W. Wright, Scheduling of vehicles from a central depot to a number of delivery points, Oper. Res. 12(1964)568–581.

    Google Scholar 

  11. G. Cornuéjols and F. Harche, Polyhedral study of the capacitated vehicle routing problem, Management Science Research Report #553, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA (1989).

    Google Scholar 

  12. H.P. Crowder and M.W. Padberg, Solving large-scale symmetric travelling salesman problems to optimality, Manag Sci. 26(1980)495–509.

    Google Scholar 

  13. G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, Solution of a large-scale traveling-salesman problem, Oper. Res. 2(1954)393–410.

    Google Scholar 

  14. G.B. Dantzig and J.H. Ramser, The truck dispatching problem, Manag. Sci. 6(1959)80–91.

    Google Scholar 

  15. M.L. Fisher, Optimal solution of vehicle routing problems using minimumK-trees, Working Paper 89-12-13, Department of Decision Sciences, The Wharton School, University of Pennsylvania, Philadelphia, PA (1990).

    Google Scholar 

  16. M.L. Fisher and R. Jaikumar, A generalized assignment heuristic for vehicle routing, Networks 11(1981)109–124

    Google Scholar 

  17. W.W. Garvin, H.W. Crandall, J.B. John and R.A. Spellman, Applications of linear programming in the oil industry, Manag. Sci. 3(1957)407–430.

    Google Scholar 

  18. T.J. Gaskell, Bases for vehicle fleet scheduling, Oper. Res. Quarterly 18(1967)281–295.

    Google Scholar 

  19. B.E. Gillet and L.R. Miller, A heuristic algorithm for the vehicle-dispatch problem, Oper. Res. 22(1974)340–349.

    Google Scholar 

  20. B.L. Golden, T.L. Magnanti and H.Q. Nguyen, Implementing vehicle routing algorithms, Networks 7(1977)113–148.

    Google Scholar 

  21. M. Grötschel and O. Holland, Solving matching problems with linear programming, Math. Progr. 33(1985)243–259.

    Google Scholar 

  22. M. Grötschel and O. Holland, Solution of large-scale symmetric travelling salesman problems, Report No. 73, Institut für Mathematik, Universität Augsburg, Augsburg, Germany (1988).

    Google Scholar 

  23. M. Grötschel, M. Jünger and G. Reinelt, A cutting plane algorithm for the linear ordering problem, Oper. Res. 32(1984)1195–1220.

    Google Scholar 

  24. M. Grötschel, M. Jünger and G. Reinelt, Facets of the linear ordering polytope, Math. Progr. 33(1985)43–60.

    Google Scholar 

  25. M. Grötschel and M.W. Padberg, Polyhedral theory, in:The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, ed. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys (Wiley, New York, 1985) pp. 251–302.

    Google Scholar 

  26. L. Hall, Two topics in discrete optimization: Polyhedral structure of capacitated trees and approximation algorithms for scheduling, Ph.D. Dissertation, M.I.T., Cambridge, MA (1989).

    Google Scholar 

  27. G. Laporte and Y. Nobert, Comb inequalities for the vehicle routing problem, Math. Oper. Res. 51(1984)271–276.

    Google Scholar 

  28. G. Laporte and Y, Nobert, Exact algorithms for the vehicle routing problem, Ann. Discr. Math. 31(1987)147–184.

    Google Scholar 

  29. G. Laporte, Y. Nobert and M. Desrochers, Optimal routing under capacity and distance restrictions, Oper. Res. 33(1985)1050–1073.

    Google Scholar 

  30. T.L. Magnanti, Combinatorial optimization and vehicle fleet planning: perspectives and prospects, Networks 11(1981)179–214.

    Google Scholar 

  31. D.L. Miller and J.F. Pekny, Exact solution of large asymmetric traveling salesman problems, Science 251(1991)754–761.

    Google Scholar 

  32. M.W. Padberg and M.R. Rao, The Russian method for linear inequalities III: Bounded integer programming, Report #81-39, Stern School of Business, New York University, New York, NY (1981).

    Google Scholar 

  33. M.W. Padberg and G. Rinaldi, An efficient algorithm for the minimum capacity cut problem, Math. Progr. 47(1990)19–36.

    Google Scholar 

  34. M.W. Padberg and G. Rinaldi, A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Rev. 33(1991)60–100.

    Google Scholar 

  35. J.F. Pekny and D.L. Miller, A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems, Math Progr. (1991), to appear.

  36. J.F. Pierce, Direct search algorithms for truck-dispatching problems, Part I, Trans. Res. 3(1969)1–42.

    Google Scholar 

  37. G. Rinaldi and L.A. Yarrow, Optimizing a 48-city traveling salesman problem: A case study in combinatorial problem solving, Report #85-42, Stern School of business, New York University, New York, NY (1985).

    Google Scholar 

  38. P.C. Yellow, A computational modification to the savings method of vehicle scheduling, Oper. Res. Quarterly 21(1970)281–283.

    Google Scholar 

  39. S. Eilon, C.D.T. Watson-Gandy and N. Christofides,Distribution Management: Mathematical Modeling and Practical Analysis (Griffin, London, 1971) pp. 197–200.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Araque G, J.R., Kudva, G., Morin, T.L. et al. A branch-and-cut algorithm for vehicle routing problems. Ann Oper Res 50, 37–59 (1994). https://doi.org/10.1007/BF02085634

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02085634

Keywords

Navigation