×

Models, relaxations and exact approaches for the capacitated vehicle routing problem. (English) Zbl 1060.90065

The authors review exact algorithms based on branch-and-bound for the solution of the vehicle routing problem, in which only the vehicle capacity constraints are considered. The contents of this paper (for the asymmetric and symmetric case, respectively) can be resumed by the following key-words: the assignment lower bound, bounds based on arborescences, the disjunctive lower bound, the lower bound based on min-cost flow, branch-and-bound algorithms; the lower bound based on trees, on matching, the Lagrangian lower bounds, bounds based on a set partitioning formulation, branching schemes and overall algorithms.
The authors present computational results and conclude with future directions of research.

MSC:

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
90B20 Traffic problems in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90B06 Transportation, logistics and supply chain management

Software:

VRPLIB; VRP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarwal, Y.; Mathur, K.; Salkin, H. M., A set-partitioning-based exact algorithm for the vehicle routing problem, Networks, 19, 731-749 (1989) · Zbl 0682.90050
[2] Balinski, M.; Quandt, R., On an integer program for a delivery problem, Oper. Res., 12, 300-304 (1964)
[3] Bellmore, M.; Malone, J. C., Pathology of travelling salesman subtour-elimination algorithms, Oper. Res., 19, 278-307 (1971) · Zbl 0219.90032
[4] Bodin, L.; Golden, B. L.; Assad, A. A.; Ball, M. O., Routing and scheduling of vehicles and crews, the state of the art, Comput. Oper. Res., 10, 2, 63-212 (1983)
[5] Bramel, J.; Simchi-Levi, D., On the effectiveness of the set partitioning formulation for the vehicle routing problem, Oper. Res., 45, 295-301 (1997) · Zbl 0890.90054
[6] P. Toth, G. Carpaneto, Some new branching and bounding criteria for the asymmetric traveling salesman problem, Manage. Sci., 26, 736-743 (1980) · Zbl 0445.90089
[7] Christofides, N., Vehicle routing, (Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., The Traveling Salesman Problem (1985), Wiley: Wiley Chichester), 431-448 · Zbl 0571.90059
[8] Christofides, N.; Eilon, S., An algorithm for the vehicle dispatching problem, Oper. Res. Quart., 20, 309-318 (1969)
[9] Christofides, N.; Mingozzi, A., Vehicle routing: practical and algorithmic aspects, (van Rijn, C. F.H., Logistics: Where Ends Have to Meet (1989), Pergamon Press: Pergamon Press Oxford), 30-48
[10] Christofides, N.; Mingozzi, A.; Toth, P., The vehicle routing problem, (Christofides, N.; Mingozzi, A.; Toth, P.; Sandi, C., Combinatorial Optimization (1979), Wiley: Wiley Chichester), 315-338
[11] Christofides, N.; Mingozzi, A.; Toth, P., Exact algorithms for the vehicle routing problem based on the spanning tree and shortest path relaxations, Math. Programming, 20, 255-282 (1981) · Zbl 0461.90067
[12] Cornuéjols, G.; Harche, F., Polyhedral study of the capacitated vehicle routing problem, Math. Programming, 60, 1, 21-52 (1993) · Zbl 0790.90029
[13] Desrochers, M.; Laporte, G., Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints, Oper. Res. Lett., 10, 27-36 (1991) · Zbl 0723.90081
[14] J. Desrosiers, Y. Dumas, M.M. Solomon, F. Soumis, Time constrained routing and scheduling, in: M.O. Ball, T.L. Magnanti, C.L. Monma, G.L. Nemhauser, (Eds.), Network Routing, Handbooks in Operations Research and Management Science, North-Holland, Amsterdam, 1995, pp. 35-139.; J. Desrosiers, Y. Dumas, M.M. Solomon, F. Soumis, Time constrained routing and scheduling, in: M.O. Ball, T.L. Magnanti, C.L. Monma, G.L. Nemhauser, (Eds.), Network Routing, Handbooks in Operations Research and Management Science, North-Holland, Amsterdam, 1995, pp. 35-139. · Zbl 0861.90052
[15] J.J. Dongarra, Performance of various computers using standard linear equations software, Technical Report CS-89-85, University of Tennessee, Knoxville, 1996.; J.J. Dongarra, Performance of various computers using standard linear equations software, Technical Report CS-89-85, University of Tennessee, Knoxville, 1996.
[16] Fischetti, M.; Toth, P., An additive bounding procedure for combinatorial optimization problems, Oper. Res., 37, 319-328 (1989) · Zbl 0676.90049
[17] Fischetti, M.; Toth, P., An additive bounding procedure for the asymmetric travelling salesman problem, Math. Programming, 53, 173-197 (1992) · Zbl 0773.90082
[18] Fischetti, M.; Toth, P.; Vigo, D., A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs, Oper. Res., 42, 5, 846-859 (1994) · Zbl 0815.90065
[19] Fisher, M. L., An application oriented guide to Lagrangian relaxation, Interfaces, 15, 10-21 (1985)
[20] Fisher, M. L., Optimal solution of vehicle routing problems using minimum \(k\)-trees, Oper. Res., 42, 626-642 (1994) · Zbl 0815.90066
[21] Fisher, M. L., A polynomial algorithm for the degree constrained \(k\)-tree problem, Oper. Res., 42, 4, 776-780 (1994)
[22] M.L. Fisher, Vehicle routing, in: M.O. Ball, T.L. Magnanti, C.L. Monma, G.L. Nemhauser (Eds.), Network Routing, Handbooks in Operations Research and Management Science, North-Holland, Amsterdam, 1995, pp. 1-33.; M.L. Fisher, Vehicle routing, in: M.O. Ball, T.L. Magnanti, C.L. Monma, G.L. Nemhauser (Eds.), Network Routing, Handbooks in Operations Research and Management Science, North-Holland, Amsterdam, 1995, pp. 1-33. · Zbl 0870.90058
[23] Gabow, H. N.; Tarjan, R. E., Efficient algorithms for a family of matroid intersection problems, J. Algorithms, 5, 80-131 (1984) · Zbl 0545.05029
[24] Golden, B. L.; Assad, A. A., Vehicle Routing: Methods and Studies (1988), North-Holland: North-Holland Amsterdam · Zbl 0638.00043
[25] Golden, B. L.; Wasil, E. A.; Kelly, J. P.; Chao, I., The impact of metaheuristics on solving the vehicle routing problem: algorithms, problem sets, and computational results, (Crainic, T. G.; Laporte, G., Fleet Management and Logistic (1998), Kluwer Academic Publisher: Kluwer Academic Publisher Boston (MA)), 33-56 · Zbl 0997.90021
[26] Hadjiconstantinou, E.; Christofides, N.; Mingozzi, A., A new exact algorithm for the vehicle routing problem based on \(q\)-Paths and \(k\)-Shortest paths relaxations, Ann. Oper. Res., 61, 21-43 (1995) · Zbl 0839.90031
[27] Held, M.; Karp, R. M., The traveling salesman problem and minimum spanning tress: Part II, Math. Programming, 1, 6-25 (1971) · Zbl 0232.90038
[28] Kulkarni, R. V.; Bhave, P. V., Integer programming formulations of vehicle routing problems, European J. Oper. Res., 20, 58-67 (1985)
[29] Laporte, G., The vehicle routing problem: An overview of exact and approximate algorithms, European J. Oper. Res., 59, 345-358 (1992) · Zbl 0761.90034
[30] Laporte, G., Vehicle routing, (Dell’Amico, M.; Maffioli, F.; Martello, S., Annotated Bibliographies in Combinatorial Optimization (1997), Wiley: Wiley Chichester) · Zbl 1068.90516
[31] Laporte, G.; Mercure, H.; Nobert, Y., An exact algorithm for the asymmetrical capacitated vehicle routing problem, Networks, 16, 33-46 (1986) · Zbl 0643.90034
[32] Laporte, G.; Nobert, Y., Exact algorithms for the vehicle routing problem, Ann. Discrete Math., 31, 147-184 (1987)
[33] Laporte, G.; Nobert, Y.; Desrochers, M., Optimal routing under capacity and distance restrictions, Oper. Res., 33, 1050-1073 (1985) · Zbl 0575.90039
[34] Laporte, G.; Osman, I. H., Routing problems: a bibliography, Ann. Oper. Res., 61, 227-262 (1995) · Zbl 0839.90032
[35] Lenstra, J. K.; Rinnooy Kan, A. H.G., Some simple applications of the traveling salesman problem, Oper. Res. Quart., 26, 717-734 (1975) · Zbl 0308.90044
[36] Lin, S.; Kernighan, B. W., An effective heuristic algorithm for the travelling salesman problem, Oper. Res., 21, 498-516 (1973) · Zbl 0256.90038
[37] Magnanti, T. L., Combinatorial optimization and vehicle fleet planning: Perspectives and prospects, Networks, 11, 179-214 (1981)
[38] Martello, S.; Toth, P., Knapsack Problems: Algorithms and Computer Implementations (1990), Wiley: Wiley Chichester · Zbl 0708.68002
[39] Miller, C. E.; Tucker, A. W.; Zemlin, R. A., Integer programming formulations and traveling salesman problems, ACM, 7, 326-329 (1960) · Zbl 0100.15101
[40] Miller, D. L., A matching based exact algorithm for capacitated vehicle routing problems, ORSA J. Comput., 7, 1, 1-9 (1995) · Zbl 0822.90057
[41] Miller, D. L.; Pekny, J. F., A staged primal-dual algorithm for perfect b-matching with edge capacities, ORSA J. Comput., 7, 298-320 (1995) · Zbl 0859.90116
[42] Pekny, J. F.; Miller, D. L., A staged primal-dual algorithm for finding a minimum cost perfect two-matching in an undirected graph, ORSA J. Comput., 6, 68-81 (1994) · Zbl 0798.90128
[43] Toth, P.; Vigo, D., An exact algorithm for the capacitated shortest spanning arborescence, Ann. Oper. Res., 61, 121-142 (1995) · Zbl 0844.90104
[44] Toth, P.; Vigo, D., An exact algorithm for the vehicle routing problem with backhauls, Transport. Sci., 31, 372-385 (1997) · Zbl 0919.90057
[45] Toth, P.; Vigo, D., Exact solution of the vehicle routing problem, (Crainic, T. G.; Laporte, G., Fleet Management and Logistic (1998), Kluwer Academic Publisher: Kluwer Academic Publisher Boston (MA)), 1-31 · Zbl 0966.90009
[46] P. Toth, D. Vigo, The granular tabu search (and its application to the vehicle routing problem). Technical Report OR/98/9, D.E.I.S. - Università di Bologna, 1998.; P. Toth, D. Vigo, The granular tabu search (and its application to the vehicle routing problem). Technical Report OR/98/9, D.E.I.S. - Università di Bologna, 1998. · Zbl 1238.90141
[47] Vigo, D., A heuristic algorithm for the asymmetric capacitated vehicle routing problem, European J. Oper. Res., 89, 108-126 (1996) · Zbl 0908.90115
[48] D. Vigo, VRPLIB: a vehicle routing problem library, Technical Report OR/99/9, D.E.I.S., Universitá di Bologna, 1999.; D. Vigo, VRPLIB: a vehicle routing problem library, Technical Report OR/99/9, D.E.I.S., Universitá di Bologna, 1999.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.