Stronger multi-commodity flow formulations of the capacitated vehicle routing problem. (English) Zbl 1346.90615
Summary: The Capacitated Vehicle Routing Problem is a much-studied (and strongly \(\mathcal{N} P\)-hard) combinatorial optimization problem, for which many integer programming formulations have been proposed. We present two new multi-commodity flow (MCF) formulations, and show that they dominate all of the existing ones, in the sense that their continuous relaxations yield stronger lower bounds. Moreover, we show that the relaxations can be strengthened, in pseudo-polynomial time, in such a way that all of the so-called knapsack large multistar (KLM) inequalities are satisfied. The only other relaxation known to satisfy the KLM inequalities, based on set partitioning, is strongly \(\mathcal{N} P\)-hard to solve. Computational results demonstrate that the new MCF relaxations are significantly stronger than the previously known ones.
MSC:
| 90C10 | Integer programming |
| 90B06 | Transportation, logistics and supply chain management |
| 90B10 | Deterministic network models in operations research |
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] | Baldacci, R.; Christofides, N.; Mingozzi, A., An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts, Mathematical Programming, 115, 351-385 (2008) · Zbl 1279.90139 |
| [3] | Baldacci, R.; Hadjiconstantinou, E.; Mingozzi, A., An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation, Operation Research, 52, 723-738 (2004) · Zbl 1165.90353 |
| [4] | Balinski, M. L.; Quandt, R. E., On an integer program for a delivery problem, Operation Research, 12, 300-304 (1964) |
| [5] | (Ball, M.; Magnanti, T.; Monma, C.; Nemhauser, G., Handbooks in operations research and management science: Vol. 8. Network routing (1995), North Holland: North Holland Amsterdam) · Zbl 0829.00010 |
| [6] | (Bellman, R. E. (1957), Princeton University Press.: Princeton University Press. Princeton, NJ) · Zbl 0077.13605 |
| [7] | Dantzig, G. B.; Ramser, R. H., The truck dispatching problem, Management Science, 6, 80-91 (1959) · Zbl 0995.90560 |
| [8] | Desaulniers, G.; Desrosiers, J.; Erdmann, A.; Solomon, M. M.; Soumis, F., VRP with pickup and delivery, (Toth, P.; Vigo, D. (2001), SIAM.) · Zbl 1076.90544 |
| [9] | Foster, B. A.; Ryan, D. M., An integer programming approach to the vehicle scheduling problem, Operational Research Quarterly, 27, 367-384 (1976) · Zbl 0327.90030 |
| [10] | Fukasawa, R.; Lysgaard, J.; de Aragão, M. P.; Reis, M.; Uchoa, E.; Werneck, R. F., Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Mathematical Programming, 106, 491-511 (2006) · Zbl 1094.90050 |
| [11] | Garvin, W. W.; Crandall, H. W.; John, J. B.; Spellman, R. A., Applications of linear programming in the oil industry, Management Science, 3, 407-430 (1957) · Zbl 0995.90627 |
| [13] | Gavish, B.; Graves, S., The traveling salesman problem and related problems (1979), Graduate School of Management, University of Rochester: Graduate School of Management, University of Rochester New York, Working Paper |
| [14] | (Golden, B.; Raghavan, S.; Wasil, E., The vehicle routing problem: Latest advances and new challenges (2008), Springer: Springer New York) · Zbl 1142.90004 |
| [15] | Gouveia, L., A result on projection for the vehicle routing problem, European Journal of Operational Research, 85, 610-624 (1995) · Zbl 0912.90118 |
| [16] | Grötschel, M.; Lovász, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197 (1981) · Zbl 0492.90056 |
| [17] | Hernández-Pérez, H.; Salazar-González, J. J., The multi-commodity one-to-one pickup-and-delivery traveling salesman problem, European Journal of Operational Research, 196, 987-995 (2009) · Zbl 1176.90055 |
| [18] | Hoffman, A. J., Some recent applications of the theory of linear inequalities to extremal combinatorial analysis, (Bellman, R.; Hall, M. (1960), AMS: AMS Providence, RI) · Zbl 0096.00606 |
| [19] | Kara, I.; Kara, B. Y.; Yetis, M. K., Energy minimizing vehicle routing problem, (Dress, A.; Xu, Y.; Zhu, B. (2007), Springer: Springer Berlin-Heidelberg), 62-71 · Zbl 1175.90333 |
| [20] | Laporte, G.; Nobert, Y., A branch and bound algorithm for the capacitated vehicle routing problem, OR Spektrum, 5, 77-85 (1983) · Zbl 0523.90088 |
| [21] | Letchford, A. N.; Eglese, R. W.; Lysgaard, J., Multistars, partial multistars and the capacitated vehicle routing problem, Mathematical Programming, 94, 21-40 (2002) · Zbl 1023.90073 |
| [22] | Letchford, A. N.; Salazar-González, J. J., Projection results for vehicle routing, Mathematical Programming, 105, 251-274 (2006) · Zbl 1085.90032 |
| [23] | Lysgaard, J.; Letchford, A. N.; Eglese, R. W., A new branch-and-cut algorithm for the capacitated vehicle routing problem, Mathematical Programming, 100, 423-445 (2004) · Zbl 1073.90068 |
| [24] | Martinelli, R.; Pecin, D.; Poggi, M., Efficient elementary and restricted non-elementary route pricing, European Journal of Operational Research, 239, 102-111 (2014) · Zbl 1339.90061 |
| [25] | Naddef, D.; Rinaldi, G., Branch-and-cut algorithms for the capacitated VRP, (Toth, P.; Vigo, D. (2001), SIAM.) |
| [26] | Papernov, B. A., On existence of multicommodity flows (in Russian), (Fridman, A. A. (1976), Nauka.: Nauka. Moscow) |
| [27] | (Toth, P.; Vigo, D., The vehicle routing problem (2001), SIAM) · Zbl 0966.90009 |
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.
