×

The capacitated vehicle routing problem: stronger bounds in pseudo-polynomial time. (English) Zbl 1403.90578

Summary: The capacitated vehicle routing problem (CVRP) is a classic combinatorial optimization problem for which many heuristics, relaxations and exact algorithms have been proposed. Since the CVRP is \(\mathcal{NP}\)-hard in the strong sense, a natural research topic is relaxations that can be solved in pseudo-polynomial time. We consider several old and new relaxations of this kind, all of which are based on column generation. We also analyze the effect of adding some known inequalities. Computational experiments demonstrate that the best of our new relaxations yields extremely tight lower bounds.

MSC:

90C27 Combinatorial optimization
90B06 Transportation, logistics and supply chain management
90B10 Deterministic network models in operations research
90C10 Integer programming

Software:

CVRPSP; VRP
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] 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
[2] Balinski, M. L.; Quandt, R. E., On an integer program for a delivery problem, Operational Research, 12, 300-304, (1964)
[3] Bellman, R. E., Dynamic programming, (1957), Princeton University Press Princeton, NJ
[4] Dantzig, G. B.; Ramser, R. H., The truck dispatching problem, Management Science, 6, 80-91, (1959) · Zbl 0995.90560
[5] Dantzig, G. B.; Wolfe, P., Decomposition principle for linear programs, Operational Research, 8, 101-111, (1960) · Zbl 0093.32806
[6] Diarrassouba, I., On the complexity of the separation problem for rounded capacity inequalities, ISCR Optima, 25, 86-104, (2017) · Zbl 1387.90278
[7] Foster, B. A.; Ryan, D. M., An integer programming approach to the vehicle scheduling problem, Operation Research Quarterly, 27, 367-384, (1976) · Zbl 0327.90030
[8] 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
[9] Gauthier, J. B.; Desrosiers, J.; Lübbecke, M. E., Tools for primal degenerate linear programs: IPS, DCA, and PE, EURO Journal on Transportation and Logistics, 5, 161-204, (2016)
[10] Geoffrion, A. M., Lagrangean relaxation for integer programming, Mathematical Programming Studies, 2, 82-114, (1974) · Zbl 0395.90056
[11] Godinho, M. T.; Gouveia, L.; Magnanti, T. L., Combined route capacity and route length models for unit demand vehicle routing problems, Discrete Optimization, 5, 350-372, (2008) · Zbl 1168.90359
[12] (Golden, B. L.; Raghavan, S.; Wasil, E. A., The Vehicle Routing Problem: Latest Advances and New Challenges, (2008), Springer New York) · Zbl 1142.90004
[13] Gouveia, L., A result on projection for the vehicle routing problem, European Journal of Operational Research, 85, 610-624, (1995) · Zbl 0912.90118
[14] 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
[15] Guignard, M., Lagrangean relaxation, Trabajos de Operativa (TOP), 11, 151-228, (2003) · Zbl 1079.90087
[16] Kellerer, H.; Pferschy, U.; Pisinger, D., The multiple-choice knapsack problem, Chapter 11 in Knapsack problems, (2004), Springer Heidelberg
[17] Laporte, G., The vehicle routing problem: an overview of exact and approximate algorithms, European Journal of Operational Research, 59, 345-358, (1992) · Zbl 0761.90034
[18] Laporte, G., Fifty years of vehicle routing, Transportation Science, 43, 408-416, (2009)
[19] Laporte, G.; Nobert, Y., A branch and bound algorithm for the capacitated vehicle routing problem, OR Spektrum, 5, 77-85, (1983) · Zbl 0523.90088
[20] Leggieri, V.; Haouari, M., Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems, European Journal of Operational Research, 263, 755-767, (2017) · Zbl 1380.90050
[21] Lemaréchal, C., The omnipresence of Lagrange, Annals of Operational Research, 153, 9-27, (2007) · Zbl 1157.90509
[22] 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
[23] Letchford, A. N.; Salazar-González, J. J., Projection results for vehicle routing, Mathematical Programming, 105, 251-274, (2006) · Zbl 1085.90032
[24] Letchford, A. N.; Salazar-González, J. J., Stronger multi-commodity flow formulations of the capacitated vehicle routing problem, European Journal of Operational Research, 244, 730-738, (2015) · Zbl 1346.90615
[25] 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
[26] Martello, S.; Toth, P., A new algorithm for the 0-1 knapsack problem, Management Science, 34, 633-644, (1988) · Zbl 0645.90054
[27] 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
[28] Naddef, D.; Rinaldi, G., Branch-and-cut algorithms for the capacitated VRP, (Toth, P.; Vigo, D., The Vehicle Routing Problem, (2002), SIAM Philadelphia, PA) · Zbl 1076.90550
[29] Pecin, D.; Pessoa, A.; Poggi, M.; Uchoa, E., Improved branch-cut-and-price for capacitated vehicle routing, Mathematical Programming Computation, 9, 61-100, (2017) · Zbl 1368.90111
[30] Poggi, M.; Uchoa, E., New exact algorithms for the capacitated vehicle routing problem, Chapter 3 in Toth and Vigo, 59-86, (2014)
[31] Poggi, M.; Uchoa, E., Integer program reformulation for robust branch-and-cut-and-price algorithms, Proceedings of the mathematical programming in Rio: A conference in honour of Nelson Maculan, 56-61, (2003)
[32] Semet, F.; Toth, P.; Vigo, D., Classical exact algorithms for the capacitated vehicle routing problem, Chapter 2 in Toth and Vigo, 37-58, (2014)
[33] (Toth, P.; Vigo, D., Vehicle Routing: Problems, Methods and Applications, (2014), MOS-SIAM Philadelphia, PA) · Zbl 1305.90012
[34] Uchoa, E.; Pecin, D.; Pessoa, A.; Poggi, M.; Vidal, T.; Subramanian, A., New benchmark instances for the capacitated vehicle routing problem, European Journal of Operational Research, 257, 845-858, (2017) · Zbl 1394.90130
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.