×

The robust vehicle routing problem with time windows: solution by branch and price and cut. (English) Zbl 1430.90104

Summary: We study the vehicle routing problem with time windows under demand uncertainty. Such a problem arises in fuel delivery to gas stations, to farms, or to production plants. We suggest a robust formulation where uncertain demand has support defined by cardinality constrained sets. The model ensures the feasibility of each route when demand values on the route change in predefined set. The range is customer specific, does not assume any probability distribution of demand, and may be estimated using historical demand data. We develop a branch-and-price-and-cut algorithm where the pricing problem is a robust resource constrained shortest path problem. We extend the rounded capacity inequalities to the robust case and suggest a separation procedure that solves a robust bin packing problem. The bound is further strengthened using 2-path and subset row inequalities and the full algorithm is tested on an extension of the benchmark Solomon instances. The robust schedules are simulated and compared to schedules obtained by solving the deterministic problem under varying levels and distributions of uncertainty. Simulation results show that the robust model provides superior protection against demand uncertainty. Over all scenarios, only 0.57% of the robust solutions turn out to be infeasible compared to 41.62% of the deterministic ones. Such protection against infeasibility comes with an 11.22% increase in routing costs on average.

MSC:

90B06 Transportation, logistics and supply chain management
90C10 Integer programming
90C35 Programming involving graphs or networks

Software:

VRP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agra, A.; Christiansen, M.; Figueiredo, R.; Hvattum, L.; Poss, M.; Requejo, C., The robust vehicle routing problem with time windows, Computers & Operations Research, 40, 3, 856-866 (2013) · Zbl 1349.90152
[2] Álvarez Miranda, E.; Ljubić, I.; Toth, P., A note on the bertsimas & sim algorithm for robust combinatorial optimization problems, 4OR, 11, 4, 349-360 (2013), ISSN 1619-4500 · Zbl 1302.90136
[3] Bektaùs, T.; Repoussis, P. P.; Tarantilis, C. D., Chapter 11: Dynamic vehicle routing problems, 299-347 (2014)
[4] Berhan, E.; Beshah, B.; Kitaw, D.; Abraham, A., Stochastic vehicle routing problem: A literature survey, Journal of Information & Knowledge Management, 13, 3 (2014)
[5] Bertsimas, D.; Sim, M., Robust discrete optimization and network flows, Mathematical Programming, 98, 1-3, 49-71 (2003) · Zbl 1082.90067
[6] Cordeau, J.-F.; Desaulniers, G.; Desrosiers, J.; Solomon, M.; Soumis, F., VRP with time windows, (Toth, P.; Vigo, D., The vehicle routing problem. The vehicle routing problem, SIAM e-books (2001), Society for Industrial and Applied Mathematics)
[7] Desaulniers, G.; Lessard, F.; Hadjar, A., Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows, Transportation Science, 42, 3, 387-404 (2008)
[8] 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
[9] Desrochers, M.; Laporte, G., Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints., Operations Research Letters, 10, 1 (1991) · Zbl 0723.90081
[10] Feillet, D., A tutorial on column generation and branch-and-price for vehicle routing problems, 4OR, 8, 4, 407-424 (2010) · Zbl 1208.90016
[11] Gendreau, M.; Jabali, O.; Rei, W., Chapter 8: Stochastic vehicle routing problems, 213-239 (2014)
[12] Goetzmann, K.-S.; Stiller, S.; Telha, C., Optimization over integers with robustness in cost and few constraints, (Solis-Oba, R.; Persiano, G., Approximation and online algorithms. Approximation and online algorithms, Lecture Notes in Computer Science, 7164 (2012)), 89-101 · Zbl 1242.90110
[13] Gounaris, C. E.; Repoussis, P. P.; Tarantilis, C. D.; Wiesemann, W.; Floudas, C. A., An Adaptive Memory Programming Framework for the Robust Capacitated Vehicle Routing Problem, Transportation Science, 50, 4, 1239-1260 (2016)
[14] Gounaris, C. E.; Wiesemann, W.; Floudas, C. A., The robust capacitated vehicle routing problem under demand uncertainty., Operations Research, 61, 3, 677-693 (2013) · Zbl 1273.90026
[15] Jepsen, M.; Petersen, B.; Spoorendonk, S.; Pisinger, D., Subset-row inequalities applied to the vehicle-routing problem with time windows, Operations Research, 56, 2, 497-511 (2008) · Zbl 1167.90413
[16] Kallehauge, B.; Larsen, J.; Madsen, O. B.; Solomon, M. M., Vehicle routing problem with time windows, Column generation, 67-98 (2005), Springer U.S. · Zbl 1130.90316
[17] Kohl, N.; Desrosiers, J.; Madsen, O. B.G.; Solomon, M. M.; Soumis, F., 2-path cuts for the vehicle routing problem with time windows, Transportation Science, 33, 1, 101-116 (1999) · Zbl 1004.90015
[18] Laporte, G., Fifty years of vehicle routing., Transportation Science, 43, 4, 408-416 (2009)
[19] Lu, D.; Gzara, F., Models and algorithms for the robust resource constrained shortest path problem, submitted to INFORMS Journal on Computing (2014)
[20] Ordóñez, F., Robust vehicle routing, In Risk and optimization in an uncertain world, 153-178 (2010)
[21] Oyola, J.; Arntzen, H.; Woodruff, D. L., The stochastic vehicle routing problem, a literature review, part i: models, EURO Journal on Transportation and Logistics, 1-29 (2016)
[22] Oyola, J.; Arntzen, H.; Woodruff, D. L., The stochastic vehicle routing problem, a literature review, part ii: solution methods, EURO Journal on Transportation and Logistics, 6, 4, 349-388 (2017)
[23] Pessoa, A. A.; Di Puglia Pugliese, L.; Guerriero, F.; Poss, M., Robust constrained shortest path problems under budgeted uncertainty, Networks, 66, 2, 98-111 (2015) · Zbl 1387.90255
[24] Pillac, V.; Gendreau, M.; Guéret, C.; Medaglia, A. L., A review of dynamic vehicle routing problems, European Journal of Operational Research, 225, 1, 1-11 (2013) · Zbl 1292.90203
[25] Shen, Z.; Dessouky, M. M.; Ordóñez, F., A two-stage vehicle routing model for large-scale bioterrorism emergencies, Networks, 54, 4 (2009) · Zbl 1203.90051
[26] Shen, Z.; Ordóñez, F.; Dessouky, M., The stochastic vehicle routing problem for minimum unmet demand, (Chaovalitwongse, W.; Furman, K. C.; Pardalos, P. M., Optimization and logistics challenges in the enterprise. Optimization and logistics challenges in the enterprise, Springer Optimization and Its Applications, 30 (2009), Springer US), 349-371 · Zbl 1172.90342
[27] Sungur, I.; Ordóñez, F.; Dessouky, M., A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty., IIE Transactions, 40, 5, 509-523 (2008)
[28] Sungur, I.; Ren, Y.; Ordóñez, F.; Dessouky, M.; Zhong, H., A model and algorithm for the courier delivery problem with uncertainty., Transportation Science, 44, 2, 193-205 (2010)
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.