×

Exact algorithms for routing problems under vehicle capacity constraints. (English) Zbl 1185.90033

Summary: The solution of a vehicle routing problem calls for the determination of a set of routes, each performed by a single vehicle which starts and ends at its own depot, such that all the requirements of the customers are fulfilled and the global transportation cost is minimized. The routes have to satisfy several operational constraints which depend on the nature of the transported goods, on the quality of the service level, and on the characteristics of the customers and of the vehicles. One of the most common operational constraint addressed in the scientific literature is that the vehicle fleet is capacitated and the total load transported by a vehicle cannot exceed its capacity.

MSC:

90B20 Traffic problems in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2006). The traveling salesman problem: A computational study. Princeton: Princeton University Press. · Zbl 1130.90036
[2] Araque, J. R., Hall, L., & Magnanti, T. (1990). Capacitated trees, capacitated routing and associated polyhedra (Technical Report Discussion Paper 9061). CORE, Louvain La Nueve.
[3] Augerat, P. (1995). Approche polyèdrale du problème de tournées de véhicules. PhD thesis, Institut National Polytechnique de Grenoble.
[4] Augerat, P., Belenguer, J. M., Benavent, E., Corberán, A., Naddef, D., & Rinaldi, G. (1995). Computational results with a branch and cut code for the capacitated vehicle routing problem (Technical Report 1 RR949-M). ARTEMIS-IMAG, Grenoble, France.
[5] Augerat, P., Belenguer, J. M., Benavent, E., Corberán, A., & Naddef, D. (1998). Separating capacity constraints in the CVRP using tabu search. European Journal of Operational Research, 106, 546–557. · Zbl 0991.90028 · doi:10.1016/S0377-2217(97)00290-7
[6] Baldacci, R., & Mingozzi, A. (2009). A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming, 120(2), 347–380. · Zbl 1180.90260 · doi:10.1007/s10107-008-0218-9
[7] Baldacci, R., Hadjiconstantinou, E., & Mingozzi, A. (2004). An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Operations Research, 52(5), 723–738. · Zbl 1165.90353 · doi:10.1287/opre.1040.0111
[8] Baldacci, R., Bodin, L., & Mingozzi, A. (2006). The multiple disposal facilities and multiple inventory locations rollon-rolloff vehicle routing problem. Computers and Operations Research, 33(9), 2667–2702. · Zbl 1086.90002 · doi:10.1016/j.cor.2005.02.023
[9] Baldacci, R., Toth, P., & Vigo, D. (2007). Recent advances in vehicle routing exact algorithms. 4OR: A Quarterly Journal of Operations Research, 5(4), 269–298. · Zbl 1160.90312 · doi:10.1007/s10288-007-0063-3
[10] Baldacci, R., Battarra, M., & Vigo, D. (2008a). Routing a heterogeneous fleet of vehicles. In B. L. Golden, S. Raghavan, & E. Wasil (Eds.), The vehicle routing problem: latest advances and new challenges (Vol. 43, pp. 3–27). Berlin: Springer. · Zbl 1187.90038
[11] Baldacci, R., Christofides, N., & Mingozzi, A. (2008b). An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Mathematical Programming Ser. A, 115(2), 351–385. · Zbl 1279.90139 · doi:10.1007/s10107-007-0178-5
[12] Baldacci, R., Battarra, M., & Vigo, D. (2009, to appear). Valid inequalities for the fleet size and mix vehicle routing problem with fixed costs. Networks. DOI: 10.1002/net.20331 · Zbl 1203.90043
[13] Balinski, M., & Quandt, R. (1964). On an integer program for a delivery problem. Operations Research, 12, 300–304. · doi:10.1287/opre.12.2.300
[14] Bramel, J., & Simchi-Levi, D. (2002). Set-covering-based algorithms for the capacitated VRP. In P. Toth & D. Vigo (Eds.), SIAM monographs on discrete mathematics and applications : Vol. 9. The vehicle routing problem (pp. 85–108). Philadelphia: SIAM. · Zbl 1076.90541
[15] Choi, E., & Tcha, D. W. (2007). A column generation approach to the heterogeneous fleet vehicle routing problem. Computers and Operations Research, 34, 2080–2095. · Zbl 1187.90094 · doi:10.1016/j.cor.2005.08.002
[16] Christofides, N., & Eilon, S. (1969). An algorithm for the vehicle dispatching problem. Operational Research Quarterly, 20, 309–318. · doi:10.1057/jors.1969.75
[17] Christofides, N., Mingozzi, A., & Toth, P. (1979). The vehicle routing problem. In N. Christofides, A. Mingozzi, P. Toth, & C. Sandi (Eds.), Combinatorial optimization (pp. 315–338). New York: Wiley. Chap. 11. · Zbl 0413.90075
[18] Christofides, N., Mingozzi, A., & Toth, P. (1981). Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxation. Mathematical Programming, 10, 255–280. · Zbl 0461.90067 · doi:10.1007/BF01589353
[19] Chvátal, V. (1973). Edmonds polytopes and weakly Hamiltonian graphs. Mathematical Programming, 5, 29–40. · Zbl 0267.05118 · doi:10.1007/BF01580109
[20] Cordeau, J. F., Gendreau, M., & Laporte, G. (1997). A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks, 30, 105–119. · Zbl 0885.90037 · doi:10.1002/(SICI)1097-0037(199709)30:2<105::AID-NET5>3.0.CO;2-G
[21] Cordeau, J. F., Laporte, G., Savelsbergh, M. W. P., & Vigo, D. (2007). Vehicle routing. In C. Barnhart & G. Laporte (Eds.), Transportation, handbooks in operations research and management science (Vol. 14, pp. 367–428). Amsterdam: North-Holland.
[22] Cornuéjols, G., & Harche, F. (1993). Polyhedral study of the capacitated vehicle routing. Mathematical Programming, 60, 21–52. · Zbl 0790.90029 · doi:10.1007/BF01580599
[23] CPLEX. (2006). ILOG CPLEX 9.0 callable library. ILOG.
[24] Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80–91. · Zbl 0995.90560 · doi:10.1287/mnsc.6.1.80
[25] Finke, G., Claus, A., & Gunn, E. (1984). A two-commodity network flow approach to the traveling salesman problem. Congressus Numerantium, 41, 167–178. · Zbl 0697.90056
[26] Fischetti, M., & Toth, P. (1989). An additive bounding procedure for combinatorial optimization problems. Operational Research, 37(2), 319–328. · Zbl 0676.90049
[27] Fischetti, M., Toth, P., & Vigo, D. (1994). A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs. Operational Research, 42, 846–859. · Zbl 0815.90065
[28] Fischetti, M., Salazar González, J. J., & Toth, P. (1995). Experiments with a multi-commodity formulation for the symmetric capacitated vehicle routing problem. In 3rd meeting of the EURO working group on transportation Barcelona (pp. 169–173).
[29] Fisher, M. L. (1994). Optimal solution of vehicle routing problems using minimum K-trees. Operational Research, 42, 626–642. · Zbl 0815.90066
[30] Fukasawa, R., Longo, H., Lysgaard, J., de Aragão, M.P., Reis, M., Uchoa, E., & Werneck, R.F. (2006). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical Programming (A), 106, 491–511. · Zbl 1094.90050 · doi:10.1007/s10107-005-0644-x
[31] Garey, M. R., & Johnson, D. S. (1990). Computers and intractability; A guide to the theory of NP-completeness. New York: Freeman. · Zbl 0411.68039
[32] Gendreau, M., Laporte, G., & Potvin, J.-Y. (2002). Metaheuristics for the capacitated VRP. In P. Toth & D. Vigo (Eds.), SIAM monographs on discrete mathematics and applications : Vol. 9. The vehicle routing problem (pp. 129–154). Philadelphia: SIAM. · Zbl 1076.90545
[33] Golden, B. L., Magnanti, T. L., & Nguyen, H. Q. (1977). Implementing vehicle routing algorithms. Networks, 7, 113–148. · Zbl 0359.90054 · doi:10.1002/net.3230070203
[34] Gouveia, L. (1995). A result on projection for the vehicle routing problem. European Journal of Operational Research, 85, 610–624. · Zbl 0912.90118 · doi:10.1016/0377-2217(94)00025-8
[35] Grötschel, M., & Padberg, M. W. (1979). On the symmetric traveling salesman problem: I and II. Mathematical Programming, 16, 265–280. · Zbl 0413.90048 · doi:10.1007/BF01582116
[36] Grötschel, M., & Padberg, M. W. (1985). Polyhedral theory. In E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, & D. B. Shmoys (Eds.), The traveling salesman problem: A guided tour of combinatorial optimization (pp. 231–305). Chichester: Wiley.
[37] Laporte, G., & Nobert, Y. (1984). Comb inequalities for the vehicle routing problem. Methods of Operations Research, 51, 271–276. · Zbl 0559.90091
[38] Laporte, G., & Nobert, Y. (1987). Exact algorithms for the vehicle routing problem. Annals of Discrete Mathematics, 31, 147–184. · Zbl 0611.90055
[39] Laporte, G., & Semet, F. (2002). Classical heuristics for the capacitated VRP. In P. Toth & D. Vigo (Eds.), SIAM monographs on discrete mathematics and applications : Vol. 9. The vehicle routing problem (pp. 109–128). Philadelphia: SIAM. · Zbl 1076.90549
[40] Laporte, G., Nobert, Y., & Desrochers, M. (1985). Optimal routing under capacity and distance restrictions. Operational Research, 33, 1058–1073. · Zbl 0575.90039
[41] Letchford, A. N., & Salazar González J. J. (2006). Projection results for vehicle routing. Mathematical Programming, 105(2–3), 251–274. · Zbl 1085.90032 · doi:10.1007/s10107-005-0652-x
[42] Letchford, A. N., Eglese, R. W., & Lysgaard, J. (2002). Multistars, partial multistars and the capacitated vehicle routing problem. Mathematical Programming, 94, 21–40. · Zbl 1023.90073 · doi:10.1007/s10107-002-0336-8
[43] Lysgaard, J. (2003). CVRPSEP: A package of separation routines for the capacitated vehicle routing problem (Technical Report). Dept. of Mgt. Science and Logistics, Aarhus School of Business.
[44] Lysgaard, J., Letchford, A. N., & Eglese, R. W. (2004). A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical Programming, 100(2), 423–445. · Zbl 1073.90068 · doi:10.1007/s10107-003-0481-8
[45] Naddef, D., & Rinaldi, G. (2002). Branch-and-cut algorithms for the capacitated VRP. In P. Toth & D. Vigo (Eds.), SIAM monographs on discrete mathematics and applications : Vol. 9. The vehicle routing problem (pp. 53–81). Philadelphia: SIAM. · Zbl 1076.90550
[46] Niskanen, S., & Östergård, P. R. J. (2003). Cliquer user’s guide (Technical Report 48). Helsinki University of Technology Communications Laboratory.
[47] Östergård, P. R. J. (2002). A fast algorithm for the maximum clique problem. Discrete Applied Mathematics, 120(1–3), 197–207. · Zbl 1019.05054 · doi:10.1016/S0166-218X(01)00290-6
[48] Pessoa, A., de Aragão, M. P., & Uchoa, E. (2008). Robust branch-cut-and-price algorithms for vehicle routing problems. In B. L. Golden, S. Raghavan, & E. Wasil (Eds.), The vehicle routing problem: Latest advances and new challenges (Vol. 43, pp. 297–325). Berlin: Springer. · Zbl 1190.90283
[49] Pessoa, A., & Uchoa, E. de Aragão, M.P. (2009, to appear). A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem. Networks. DOI: 10.1002/net.20330 · Zbl 1205.90081
[50] Ralphs, T. K., Kopman, L., Pulleyblank, W. R., & Trotter, L. E. (2003). On the capacitated vehicle routing problem. Mathematical Programming (B), 94, 343–359. · Zbl 1030.90131 · doi:10.1007/s10107-002-0323-0
[51] Toth, P., & Vigo, D. (2002). SIAM monographs on discrete mathematics and applications: Vol. 9. The vehicle routing problem. Philadelphia: SIAM. · Zbl 1060.90065
[52] Yaman, H. D. (2006). Formulations and valid inequalities for the heterogeneous vehicle routing problem. Mathematical Programming Ser. A, 106, 365–390. · Zbl 1134.90527 · doi:10.1007/s10107-005-0611-6
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.