×

Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems. (English) Zbl 1380.90050

Summary: We propose compact formulations for the symmetric and asymmetric capacitated vehicle routing problems. These formulations are obtained by lifting, using the reformulation-linearization technique, a novel polynomial size ordered path-based formulation. We show that the strongest proposed formulation is equivalent to the strongest multi-commodity flow formulation presented so far. In addition, we propose polynomial size valid inequalities that aim at further tightening the proposed formulations. Also, the tightest formulation is extended to model the fleet size and mix vehicle routing problem with fixed costs. We show that the new derived model is not comparable with a state-of-the-art polynomial length formulation. We present the results of computational experiments that demonstrate the tightness of the proposed formulations and the impact of the valid inequalities.

MSC:

90B06 Transportation, logistics and supply chain management
90C11 Mixed integer programming

Software:

VRP; CVRPSP
Full Text: DOI

References:

[1] Achuthan, N.; Caccetta, L.; Hill, S. P., An improved branch-and-cut algorithm for the capacitated vehicle routing problem, Transportation Science, 37, 2, 153-169 (2003)
[2] Baldacci, R.; Battarra, M.; Vigo, D., Routing a heterogeneous fleet of vehicles, (Golden, I. B.; Raghavan, S.; Wasil, E., The vehicle routing problem: Latest advances and new challenges of operations research/computer science interfaces, vol.43 (2008), Springer: Springer US), 3-27 · Zbl 1187.90038
[3] Baldacci, R.; Hadjiconstantinou, E.; Mingozzi, A., An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation, Operations Research, 52, 5, 723-738 (2004) · Zbl 1165.90353
[4] Baldacci, R.; Mingozzi, A., A unified exact method for solving different classes of vehicle routing problems, Mathematical Programming, 120, 2, 347-380 (2008) · Zbl 1180.90260
[5] Baldacci, R.; Mingozzi, A.; Roberti, R., Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints, European Journal of Operational Research, 218, 1, 1-6 (2012) · Zbl 1244.90001
[6] Balinski, R.; Quandt, R., On an integer program for a delivery problem, Operations Research, 12, 300-3004 (1964)
[7] Carlier, J.; Clautiaux, F.; Moukrim, A., New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation, Computers & Operations Research, 34, 8, 2223-2250 (2007) · Zbl 1144.90465
[8] Choi, E.; Tcha, D. W., A column generation approach to the heterogeneous fleet vehicle routing problem, Computers & Operations Research, 34, 7, 2080-2095 (2007) · Zbl 1187.90094
[9] Christofides, N.; Mingozzi, A.; Toth, P., The vehicle routing problem, (Christofides, N.; Mingozzi, A.; Toth, P.; Sandi, C., Combinatorial optimization (1979), Wiley, Chichester: Wiley, Chichester UK), 315-338 · Zbl 0413.90075
[10] Clautiaux, F.; Alves, C.; Val, J.; de Carvalho, e., A survey of dual-feasible and superadditive functions, Annals of Operations Research, 179, 1, 317-342 (2010) · Zbl 1229.90155
[11] Cornuéjols, G.; Harche, F., Polyhedral study of the capacitated vehicle routing problem, Mathematical Programming, 60, 1, 21-52 (1993) · Zbl 0790.90029
[12] Dantzig, G. B.; Ramser, R. H., The truck dispatching problem, Management Science, 6, 1, 80-91 (1959) · Zbl 0995.90560
[13] Desrochers, M.; Desrosiers, J.; Solomon, M., A new optimization algorithm for the vehicle-routing problem with time windows, Operations Research, 40, 2, 342-354 (1992) · Zbl 0749.90025
[14] Desrochers, M.; Laporte, G., Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints, Operations Research Letters, 10, 1, 27-36 (1991) · Zbl 0723.90081
[15] Fischetti, M.; Toth, P.; Vigo, D., A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs, Operations Research, 42, 5, 846-859 (1994) · Zbl 0815.90065
[16] Fukasawa, R.; Longo, H.; 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, 3, 491-511 (2006) · Zbl 1094.90050
[17] Gavish, B., The delivery problem: New cutting planes procedures, Proceedings of the 1984 TIMS XXVI conference (1984), Copenhagen
[18] Gavish, B.; Graves, S., The traveling salesman problem and related problems, Technical report (1979), Graduate School of Management, University of Rochester
[19] Godinho, M. T.; Gouveia, L.; Magnanti, T. L., Combined route capacity and route length models for unit demand vehicle routing problems, Discrete Optimization, 5, 2, 350-372 (2008) · Zbl 1168.90359
[20] Golden, B.; Assad, A.; Levy, L.; Gheysens, F., The fleet size and mix vehicle routing problem, Computers & Operations Research, 11, 1, 49-66 (1984) · Zbl 0607.90043
[21] Golden, B.; Raghavan, S.; Wasil, E., The vehicle routing problem: latest advances and new challenges, Operations research computer science interfaces series, 43 (2008), Springer: Springer US · Zbl 1142.90004
[22] Gouveia, L., A result on projection for the vehicle routing problem, European Journal of Operational Research, 85, 3, 610-624 (1995) · Zbl 0912.90118
[23] Gouveia, L.; Pires, J. M., The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints, European Journal of Operational Research, 112, 1, 134-146 (1999) · Zbl 0971.90099
[24] Gouveia, L.; Pires, J. M., The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints, Discrete Applied Mathematics, 112, 1-3, 129-145 (2001) · Zbl 1054.90059
[25] Johnson, D. S., Near-optimal bin packing algorithms, Technical report, Doctoral Thesis (1973), Department of Mathematics MITss, Cambridge, MA
[26] Kara, I.; Laporte, G.; Bektas, T., A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for the capacitated vehicle routing problem, European Journal of Operational Research, 158, 3, 793-795 (2004) · Zbl 1061.90020
[27] Koç, C.; Bektas, T.; Jabali, O.; Laporte, G., Thirty years of heterogeneous vehicle routing, European Journal of Operational Research, 249, 1, 1-21 (2016) · Zbl 1346.90140
[28] Laporte, G.; Nobert, Y., Exact algorithms for the vehicle routing problem, Annals of Discrete Mathematics, 31, 147-184 (1987) · Zbl 0611.90055
[29] Laporte, G.; Nobert, Y.; Desrochers, M., Optimal routing under capacity and distance restrictions, Operations Research, 33, 5, 1050-1073 (1985) · Zbl 0575.90039
[30] 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, 3, 730-738 (2015) · Zbl 1346.90615
[31] Letchford, A. N.; Salazar-González, J. J., Projection results for vehicle routing, Mathematical Programming, 105, 2-3, 251-274 (2006) · Zbl 1085.90032
[32] Lysgaard, J.; Letchford, A. N.; Eglese, R. W., A new branch-and-cut algorithm for the capacitated vehicle routing problem, Mathematical Programming, 100, 2, 423-445 (2004) · Zbl 1073.90068
[33] Miller, C. E.; Tucker, A. W.; Zemlin, R. A., Integer programming formulation of traveling salesman problems, Journal of the ACM, 7, 4, 326-329 (1960) · Zbl 0100.15101
[34] Pessoa, A.; de Aragão, M. P.; Uchoa, E., A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem, (Demetrescu, C., Proceedings of the sixth international workshop on experimental algorithms (WEA) (2007), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 150-160 · Zbl 1203.90136
[35] Pessoa, A.; de Aragão, M. P.; Uchoa, E., Robust branch-cut-and-price algorithms for vehicle routing problems, (Golden, B.; Raghavan, S.; Wasil, E., The vehicle routing problem: Latest advances and new challenges, of operations research/computer science interfaces, 43 (2008), Springer: Springer US), 297-325 · Zbl 1190.90283
[36] Ralphs, T. K.; Kopman, L.; Pulleyblank, W. R., On the capacitated vehicle routing problem, Mathematical Programming, 94, 2, 343-359 (2003) · Zbl 1030.90131
[37] Sarin, S. C.; Sherali, H. D.; Bhootra, A., New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints, Operations Research Letters, 33, 1, 62-70 (2005) · Zbl 1076.90062
[38] Sherali, H. D.; Adams, W. P., A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM Journal on Discrete Mathematics, 3, 3, 411-430 (1990) · Zbl 0712.90050
[39] Sherali, H. D.; Adams, W. P., A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems, Discrete Applied Mathematics, 52, 1, 83-106 (1994) · Zbl 0819.90064
[40] Sherali, H. D.; Sarin, S. C.; Tsai, P.-F., A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints, Discrete Optimization, 3, 1, 20-32 (2006) · Zbl 1109.90075
[41] Toth, P.; Vigo, D., Vehicle routing: problems, methods, and applications, SIAM - Society for Industrial and Applied Mathematics (2014), Philadelphia · Zbl 1305.90012
[42] Toth, P.; Vigo, D., An overview of vehicle routing problems, The vehicle routing problem, 1-26 (2001), SIAM-Society for Industrial and Applied Mathematics: SIAM-Society for Industrial and Applied Mathematics Philadelphia · Zbl 1076.90553
[43] Yaman, H., Formulations and valid inequalities for the heterogeneous vehicle routing problem, Mathematical Programming, 106, 2, 365-390 (2006) · Zbl 1134.90527
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.