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.
Similar content being viewed by others
References
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).
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).
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).
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).
I. Barany, T.J. Van Roy and L.A. Wolsey, Strong formulations for multi-item capacitated lot sizing, Manag. Sci. 30(1984)1255–1261.
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.
N. Christofides, The vehicle routing problem, RAIRO Recherche Opèrationelle 10 (1976) 55–70.
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.
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.
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.
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).
H.P. Crowder and M.W. Padberg, Solving large-scale symmetric travelling salesman problems to optimality, Manag Sci. 26(1980)495–509.
G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, Solution of a large-scale traveling-salesman problem, Oper. Res. 2(1954)393–410.
G.B. Dantzig and J.H. Ramser, The truck dispatching problem, Manag. Sci. 6(1959)80–91.
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).
M.L. Fisher and R. Jaikumar, A generalized assignment heuristic for vehicle routing, Networks 11(1981)109–124
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.
T.J. Gaskell, Bases for vehicle fleet scheduling, Oper. Res. Quarterly 18(1967)281–295.
B.E. Gillet and L.R. Miller, A heuristic algorithm for the vehicle-dispatch problem, Oper. Res. 22(1974)340–349.
B.L. Golden, T.L. Magnanti and H.Q. Nguyen, Implementing vehicle routing algorithms, Networks 7(1977)113–148.
M. Grötschel and O. Holland, Solving matching problems with linear programming, Math. Progr. 33(1985)243–259.
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).
M. Grötschel, M. Jünger and G. Reinelt, A cutting plane algorithm for the linear ordering problem, Oper. Res. 32(1984)1195–1220.
M. Grötschel, M. Jünger and G. Reinelt, Facets of the linear ordering polytope, Math. Progr. 33(1985)43–60.
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.
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).
G. Laporte and Y. Nobert, Comb inequalities for the vehicle routing problem, Math. Oper. Res. 51(1984)271–276.
G. Laporte and Y, Nobert, Exact algorithms for the vehicle routing problem, Ann. Discr. Math. 31(1987)147–184.
G. Laporte, Y. Nobert and M. Desrochers, Optimal routing under capacity and distance restrictions, Oper. Res. 33(1985)1050–1073.
T.L. Magnanti, Combinatorial optimization and vehicle fleet planning: perspectives and prospects, Networks 11(1981)179–214.
D.L. Miller and J.F. Pekny, Exact solution of large asymmetric traveling salesman problems, Science 251(1991)754–761.
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).
M.W. Padberg and G. Rinaldi, An efficient algorithm for the minimum capacity cut problem, Math. Progr. 47(1990)19–36.
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.
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.
J.F. Pierce, Direct search algorithms for truck-dispatching problems, Part I, Trans. Res. 3(1969)1–42.
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).
P.C. Yellow, A computational modification to the savings method of vehicle scheduling, Oper. Res. Quarterly 21(1970)281–283.
S. Eilon, C.D.T. Watson-Gandy and N. Christofides,Distribution Management: Mathematical Modeling and Practical Analysis (Griffin, London, 1971) pp. 197–200.
Author information
Authors and Affiliations
Rights 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
Issue Date:
DOI: https://doi.org/10.1007/BF02085634