×

Robust vehicle routing under uncertainty via branch-price-and-cut. (English) Zbl 1508.90086

Summary: This paper contemplates how branch-price-and-cut solvers can be employed along with the robust optimization paradigm to address parametric uncertainty in the context of vehicle routing problems. In this setting, given postulated uncertainty sets for customer demands and vehicle travel times, one aims to identify a set of cost-effective routes for vehicles to traverse, such that the vehicle capacities and customer time window constraints are respected under any anticipated demand and travel time realization, respectively. To tackle such problems, we propose a novel approach that combines cutting-plane techniques with an advanced branch-price-and-cut algorithm. Specifically, we use deterministic pricing procedures to generate “partially robust” vehicle routes and then utilize robust versions of rounded capacity inequalities and infeasible path elimination constraints to guarantee complete robust feasibility of routing designs against demand and travel time uncertainty. In contrast to recent approaches that modify the pricing algorithm, our approach is both modular and versatile. It permits the use of advanced branch-price-and-cut technologies without significant modification, while it can admit a variety of uncertainty sets that are commonly used in robust optimization but could not be previously employed in a branch-price-and-cut setting.

MSC:

90C27 Combinatorial optimization
90C17 Robustness in mathematical programming
90B06 Transportation, logistics and supply chain management

Software:

VRP; VRPSolver

References:

[1] Agostinho, A.; Marielle, C.; Rosa, F.; Hvattum, LM; Michael, P.; Cristina, R., The robust vehicle routing problem with time windows, Comput Oper Res, 40, 3, 856-866 (2013) · Zbl 1349.90152 · doi:10.1016/j.cor.2012.10.002
[2] Agra, A.; Christiansen, M.; Lars, MH; Rodrigues, F., Robust optimization for a maritime inventory routing problem, Transp Sci, 52, 3, 509-525 (2018) · doi:10.1287/trsc.2017.0814
[3] Agra A, Christiansen M, Figueiredo R, Hvattum LM, Poss M, Requejo C (2012) Layered formulation for the robust vehicle routing problem with time windows. In: International symposium on combinatorial optimization. pp 249-260. Springer · Zbl 1370.90019
[4] Alves-Pessoa, A.; Puglia, LD; Guerriero, PF; Michael, P., Robust constrained shortest path problems under budgeted uncertainty, Networks, 66, 2, 98-111 (2015) · Zbl 1387.90255 · doi:10.1002/net.21615
[5] Ascheuer, N.; Fischetti, M.; Grötschel, M., Solving the asymmetric travelling salesman problem with time windows by branch-and-cut, Math Progr, 90, 3, 475-506 (2001) · Zbl 1039.90056 · doi:10.1007/PL00011432
[6] Augerat Ph, Manuel BJ, Benavent E, Corberán A, Naddef D, Rinaldi G (1995) Computational results with a branch and cut code for the capacitated vehicle routing problem. IMAG
[7] Baldacci, R.; Christofides, N.; Mingozzi, A., An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts, Math Progr, 115, 2, 351-385 (2008) · Zbl 1279.90139 · doi:10.1007/s10107-007-0178-5
[8] Baldacci, R.; Mingozzi, A.; Roberti, R., New route relaxation and pricing strategies for the vehicle routing problem, Oper Res, 59, 5, 1269-1283 (2011) · Zbl 1233.90059 · doi:10.1287/opre.1110.0975
[9] Ben-Tal, A.; El Ghaoui, L.; Nemirovski, A., Robust optimization (2009), Princeton: Princeton University Press, Princeton · Zbl 1221.90001 · doi:10.1515/9781400831050
[10] Ben-Tal A, Nemirovski A (2001) Lectures on modern convex optimization: analysis, algorithms, and engineering applications. 2. SIAM · Zbl 0986.90032
[11] Bertsimas , Gupta S, Tay J (2016) Scalable robust and adaptive inventory routing. Technical report. Available on Optimization Online: www.optimization-online.org/DB_FILE/2016/06/5497.pdf
[12] Bertsimas, D.; Sim, M., The price of robustness, Oper Res, 52, 1, 35-53 (2004) · Zbl 1165.90565 · doi:10.1287/opre.1030.0065
[13] Birge, JR; Francois, L., Introduction to stochastic programming (2011), Berlin: Springer, Berlin · Zbl 1223.90001 · doi:10.1007/978-1-4614-0237-4
[14] Contardo, C.; Martinelli, R., A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints, Discret Optim, 12, 129-146 (2014) · Zbl 1308.90144 · doi:10.1016/j.disopt.2014.03.001
[15] Costa, L.; Contardo, C.; Desaulniers, G., Exact branch-price-and-cut algorithms for vehicle routing, Transp Sci, 53, 4, 946-985 (2019) · doi:10.1287/trsc.2018.0878
[16] Desaulniers, G.; Rakke, JG; Coelho, LC, A branch-price-and-cut algorithm for the inventory-routing problem, Transp Sci, 50, 3, 1060-1076 (2016) · doi:10.1287/trsc.2015.0635
[17] Desrochers, M.; Desrosiers, J.; Solomon, M., A new optimization algorithm for the vehicle routing problem with time windows, Oper Res, 40, 2, 342-354 (1992) · Zbl 0749.90025 · doi:10.1287/opre.40.2.342
[18] Dinh, T.; Fukasawa, R.; Luedtke, J., Exact algorithms for the chance-constrained vehicle routing problem, Math Progr, 172, 1-2, 105-138 (2018) · Zbl 1406.90079 · doi:10.1007/s10107-017-1151-6
[19] Dominique Feillet (2010) A tutorial on column generation and branch-and-price for vehicle routing problems. 4OR 8(4):407-424 · Zbl 1208.90016
[20] Dror, M., Note on the complexity of the shortest path models for column generation in vrptw, Oper Res, 42, 5, 977-978 (1994) · Zbl 0815.90064 · doi:10.1287/opre.42.5.977
[21] Eufinger, L.; Kurtz, J.; Buchheim, C.; Clausen, U., A robust approach to the capacitated vehicle routing problem with uncertain costs, INFORMS J Optim, 2, 2, 79-95 (2020) · doi:10.1287/ijoo.2019.0021
[22] Fukasawa, R.; Longo, H.; Lysgaard, J.; de Aragão, MP; Reis, M.; Uchoa, E.; Werneck, RF, Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Math Progr, 106, 3, 491-511 (2006) · Zbl 1094.90050 · doi:10.1007/s10107-005-0644-x
[23] Gendreau M, Jabali O, Rei W (2014) Chapter 8: stochastic vehicle routing problems. In: Vehicle routing: problems, methods, and applications, Second Edition. pp 213-239. SIAM
[24] Ghosal, S.; Wiesemann, W., The distributionally robust chance-constrained vehicle routing problem, Oper Res, 68, 3, 716-732 (2020) · Zbl 1445.90009 · doi:10.1287/opre.2019.1924
[25] Gounaris Chrysanthos, E.; Wiesemann, Wolfram; Floudas Christodoulos, A., The robust capacitated vehicle routing problem under demand uncertainty, Oper Res, 61, 3, 677-693 (2013) · Zbl 1273.90026 · doi:10.1287/opre.1120.1136
[26] Gounaris Chrysanthos, E.; Repoussis Panagiotis, P.; Tarantilis Christos, D.; Wiesemann, Wolfram; Floudas Christodoulos, A., An adaptive memory programming framework for the robust capacitated vehicle routing problem, Transp Sci, 50, 4, 1239-1260 (2014) · doi:10.1287/trsc.2014.0559
[27] Hojny, C.; Gally, T.; Habeck, O.; Lüthen, H.; Matter, F.; MaE, Pfetsch; Schmitt, A., Knapsack polytopes: a survey, Ann Oper Res, 292, 469-517 (2020) · Zbl 1456.90133 · doi:10.1007/s10479-019-03380-2
[28] Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. In: Column generation. pages 33-65. Springer · Zbl 1130.90315
[29] Irnich S, Desaulniers G, Desrosiers J, Hadjar A (2010) Path-reduced costs for eliminating arcs in routing and scheduling. INFORMS J Comput 22(2):297-313 · Zbl 1243.90064
[30] Jepsen, M.; Petersen, B.; Spoorendonk, S.; Pisinger, D., Subset-row inequalities applied to the vehicle-routing problem with time windows, Oper Res, 56, 2, 497-511 (2008) · Zbl 1167.90413 · doi:10.1287/opre.1070.0449
[31] Kallehauge, B.; Boland, N.; Madsen, OBG, Path inequalities for the vehicle routing problem with time windows, Netw Int J, 49, 4, 273-293 (2007) · Zbl 1141.90338
[32] Laporte, G.; Nobert, Y., A branch and bound algorithm for the capacitated vehicle routing problem, Oper Res Spektrum, 5, 2, 77-85 (1983) · Zbl 0523.90088 · doi:10.1007/BF01720015
[33] Lee, C.; Lee, K.; Park, S., Robust vehicle routing problem with deadlines and travel time/demand uncertainty, J Oper Res Soc, 63, 9, 1294-1306 (2012) · doi:10.1057/jors.2011.136
[34] Lee T, Kwon C (2014) A short note on the robust combinatorial optimization problems with cardinality constrained uncertainty. 4OR 12(4):373-378 · Zbl 1308.90111
[35] Lu, D.; Gzara, F., The robust vehicle routing problem with time windows: solution by branch and price and cut, Eur J Oper Res, 275, 3, 925-938 (2019) · Zbl 1430.90104 · doi:10.1016/j.ejor.2018.12.019
[36] Lübbecke, ME; Desrosiers, J., Selected topics in column generation, Oper Res, 53, 6, 1007-1023 (2005) · Zbl 1165.90578 · doi:10.1287/opre.1050.0234
[37] Munari, P.; Moreno, A.; Vega, LD; Douglas, JA; Gondzio, J.; Morabito, R., The robust vehicle routing problem with time windows: compact formulation and branch-price-and-cut method, Transp Sci, 53, 4, 1043-1066 (2019) · doi:10.1287/trsc.2018.0886
[38] Pecin, D.; Contardo, C.; Desaulniers, G.; Uchoa, E., New enhancements for the exact solution of the vehicle routing problem with time windows, INFORMS J Comput, 29, 3, 489-502 (2017) · Zbl 1378.90027 · doi:10.1287/ijoc.2016.0744
[39] Pecin, D.; Pessoa, A.; Poggi, M.; Uchoa, E., Improved branch-cut-and-price for capacitated vehicle routing, Math Progr Comput, 9, 1, 61-100 (2017) · Zbl 1368.90111 · doi:10.1007/s12532-016-0108-8
[40] Pessoa, A.; Sadykov, R.; Uchoa, E.; Vanderbeck, F., Automation and combination of linear-programming based stabilization techniques in column generation, INFORMS J Comput, 30, 2, 339-360 (2018) · Zbl 1528.90164 · doi:10.1287/ijoc.2017.0784
[41] Pessoa, A.; Sadykov, R.; Uchoa, E.; Vanderbeck, F., A generic exact solver for vehicle routing and related problems, Math Progr, 183, 1, 483-523 (2020) · Zbl 1450.90017 · doi:10.1007/s10107-020-01523-z
[42] Pessoa, AA; Poss, M.; Sadykov, R.; Vanderbeck, F., Branch-cut-and-price for the robust capacitated vehicle routing problem with knapsack uncertainty, Oper Res, 69, 3, 739-754 (2021) · Zbl 1472.90079 · doi:10.1287/opre.2020.2035
[43] Puglia, LD; Francesca, GP, A survey of resource constrained shortest path problems: exact solution approaches, Networks, 62, 3, 183-200 (2013) · Zbl 1338.90432 · doi:10.1002/net.21511
[44] Righini, G.; Salani, M., Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints, Discret Optim, 3, 3, 255-273 (2006) · Zbl 1149.90167 · doi:10.1016/j.disopt.2006.05.007
[45] Roberti, R.; Mingozzi, A., Dynamic ng-path relaxation for the delivery man problem, Transp Sci, 48, 3, 413-424 (2014) · doi:10.1287/trsc.2013.0474
[46] Røpke S (2012) Branching decisions in branch-and-cut-and-price algorithms for vehicle routing problems. Presentation in Column Generation
[47] Sadykov, R.; Vanderbeck, F.; Pessoa, A.; Tahiri, I.; Uchoa, E., Primal heuristics for branch and price: the assets of diving methods, INFORMS J Comput, 31, 2, 251-267 (2019) · Zbl 07281710 · doi:10.1287/ijoc.2018.0822
[48] Sadykov, R.; Uchoa, E.; Pessoa, A., A bucket graph-based labeling algorithm with application to vehicle routing, Transp Sci, 55, 1, 4-28 (2021) · doi:10.1287/trsc.2020.0985
[49] Solano-Charris, E.; Prins, C.; Andréa, CS, Local search based metaheuristics for the robust vehicle routing problem with discrete scenarios, Appl Soft Comput, 32, 518-531 (2015) · doi:10.1016/j.asoc.2015.03.058
[50] Solomon, MM, Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper Res, 35, 2, 254-265 (1987) · Zbl 0625.90047 · doi:10.1287/opre.35.2.254
[51] Subramanyam, A.; Wang, A.; Gounaris, CE, A scenario decomposition algorithm for strategic time window assignment vehicle routing problems, Transp Res Part B Methodol, 117, 296-317 (2018) · doi:10.1016/j.trb.2018.09.008
[52] Subramanyam, A.; Repoussis, PP; Gounaris, CE, Robust optimization of a broad class of heterogeneous vehicle routing problems under demand uncertainty, INFORMS J Comput, 32, 3, 661-681 (2020) · Zbl 1451.90021 · doi:10.1287/ijoc.2019.0923
[53] Subramanyam, A.; Mufalli, F.; Laínez-Aguirre, JJM; Pinto, JM; Gounaris, CE, Robust multiperiod vehicle routing under customer order uncertainty, Oper Res, 69, 1, 30-60 (2021) · Zbl 1466.90013 · doi:10.1287/opre.2020.2009
[54] Sungur, I.; Ordónez, F.; Dessouky, M., A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty, IIE Trans, 40, 5, 509-523 (2008) · doi:10.1080/07408170701745378
[55] Toth P, Vigo D (2014) Vehicle routing: problems, methods, and applications. SIAM · Zbl 1305.90012
[56] Zeng, B.; Zhao, L., Solving two-stage robust optimization problems using a column-and-constraint generation method, Oper Res Lett, 41, 5, 457-461 (2013) · Zbl 1286.90143 · doi:10.1016/j.orl.2013.05.003
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.