The Robust Vehicle Routing Problem with Time Windows: Compact Formulation and Branch-Price-and-Cut Method

References

• Adulyasak Y, Jaillet P (2016) Models and algorithms for stochastic and robust vehicle routing with deadlines. Transportation Sci. 50(2):608–626.Link, Google Scholar
• Agra A, Christiansen M, Figueiredo R, Hvattum LM, Poss M, Requejo C (2012) Layered formulation for the robust vehicle routing problem with time windows. Ridha Mahjoub A, Markakis V, Milis I, Paschos VTh, eds. Combinatorial Optimization: Second International Symposium (ISCO 2012), Lecture Notes in Computer Science, vol. 7422 (Springer, Berlin), 249–260.Crossref, Google Scholar
• Agra A, Christiansen M, Figueiredo R, Hvattum LM, Poss M, Requejo C (2013) The robust vehicle routing problem with time windows. Comput. Oper. Res. 40(3):856–866.Crossref, Google Scholar
• Alem D, Morabito R (2012) Production planning in furniture settings via robust optimization. Comput. Oper. Res. 39(2):139–150.Crossref, Google Scholar
• Alem D, Curcio E, Amorim P, Almada-Lobo B (2018) A computational study of the general lot-sizing and scheduling model under demand uncertainty via robust and stochastic approaches. Comput. Oper. Res. 90(February):125–141.Crossref, Google Scholar
• Alvarez A, Munari P (2017) An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen. Comput. Oper. Res. 83(July):1–12.Crossref, Google Scholar
• Baldacci R, Bartolini E, Mingozzi A (2011) An exact algorithm for the pickup and delivery problem with time windows. Oper. Res. 59(2):414–426.Link, Google Scholar
• Ben AmorHMT, Desrosiers J, Frangioni A (2009) On the choice of explicit stabilizing terms in column generation. Discrete Appl. Math. 157(6):1167–1184.Crossref, Google Scholar
• Ben-Tal A, Nemirovski A (1999) Robust solutions of uncertain linear programming. Oper. Res. Lett. 25(1):1–13.Crossref, Google Scholar
• Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math. Programming 98(1):49–71.Crossref, Google Scholar
• Braekers K, Ramaekers K, Van Nieuwenhuyse I (2016) The vehicle routing problem: State of the art classification and review. Comput. Indust. Engrg. 99(September):300–313.Crossref, Google Scholar
• Briant O, Lemarechal C, Meurdesoif Ph, Michel S, Perrot N, Vanderbeck F (2008) Comparison of bundle and classical column generation. Math. Programming 113(2):299–344.Crossref, Google Scholar
• Chabrier A (2006) Vehicle routing problem with elementary shortest path based column generation. Comput. Oper. Res. 33(10):2972–2990.Crossref, Google Scholar
• Contardo C, Desaulniers G, Lessard F (2015) Reaching the elementary lower bound in the vehicle routing problem with time windows. Networks 65(1):88–99.Crossref, Google Scholar
• De La VegaJ, Munari P, Morabito R (2017) Robust optimization for the vehicle routing problem with multiple deliverymen. Central Eur. J. Oper. Res., ePub ahead of print December 16, https://doi.org/10.1007/s10100-017-0511-x.Crossref, Google Scholar
• Desaulniers G, Lessard F, Hadjar A (2008) Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows. Transportation Sci. 42(3):387–404.Link, Google Scholar
• Desaulniers G, Madsen OBG, Ropke S (2014) The vehicle routing problem with time windows. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications, 2nd ed., MOS-SIAM Series in Optimization (Society for Industrial and Applied Mathematics, Philadelphia), 119–159.Crossref, Google Scholar
• Desrosiers J, Lübbecke ME (2010) Branch-price-and-cut algorithms. Cochran JJ, Cox LA Jr, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia of Operations Research and Management Science (John Wiley & Sons, Hoboken, NJ), https://doi.org/10.1002/9780470400531.eorms0118.Google Scholar
• Errico F, Desaulniers G, Gendreau M, Rei W, Rousseau L-M (2016) A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times. Eur. J. Oper. Res. 249(1):55–66.Crossref, Google Scholar
• Feillet D, Dejax P, Gendreau M, Gueguen C (2004) An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks 44(3):216–229.Crossref, Google Scholar
• Furtado MGS, Munari P, Morabito R (2017) Pickup and delivery problem with time windows: A new compact two-index formulation. Oper. Res. Lett. 45(4):334–341.Crossref, Google Scholar
• Gondzio J (2012) Interior point methods 25 years later. Eur. J. Oper. Res. 218(3):587–601.Crossref, Google Scholar
• Gondzio J, Gonzalez-Brevis P, Munari P (2013) New developments in the primal-dual column generation technique. Eur. J. Oper. Res. 224(1):41–51.Crossref, Google Scholar
• Gondzio J, González-Brevis P, Munari P (2016) Large-scale optimization with the primal-dual column generation method. Math. Programming Comput. 8(1):47–82.Crossref, Google Scholar
• Gounaris CE, Wiesemann W, Floudas CA (2013) The robust capacitated vehicle routing problem under demand uncertainty. Oper. Res. 61(3):677–693.Link, Google Scholar
• Gounaris CE, Repoussis PP, Tarantilis CD, Wiesemann W, Floudas CA (2016) An adaptive memory programming framework for the robust capacitated vehicle routing problem. Transportation Sci. 50(4):1239–1260.Link, Google Scholar
• Irnich S., Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, New York), pp 33–65.Crossref, Google Scholar
• Irnich S, Toth P, Vigo D (2014) The family of vehicle routing problems. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications, 2nd ed., MOS-SIAM Series in Optimization (Society for Industrial and Applied Mathematics, Philadelphia), 1–33.Crossref, Google Scholar
• Jaillet P, Qi J, Sim M (2016) Routing optimization under uncertainty. Oper. Res. 64(1):186–200.Link, Google Scholar
• Jepsen M, Petersen B, Simon S, Pisinger D (2008) Subset-row inequalities applied to the vehicle routing problem with time windows. Oper. Res. 56(2):497–511.Link, Google Scholar
• Joncour C, Michel S, Sadykov R, Sverdlov D, Vanderbeck F (2010) Column generation based primal heuristics. Electronic Notes Discrete Math. 36(August):695–702.Crossref, Google Scholar
• Klamroth K, Köbis E, Schöbel A, Tammer C (2017) A unified approach to uncertain optimization. Eur. J. Oper. Res. 260(2):403–420.Crossref, Google Scholar
• Lee C., Lee K, Park S (2012) Robust vehicle routing problem with deadlines and travel time/demand uncertainty. J. Oper. Res. Soc. 63(9):1294–1306.Crossref, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Munari P, Gondzio J (2013) Using the primal-dual interior point algorithm within the branch-price-and-cut method. Comput. Oper. Res. 40(8):2026–2036.Crossref, Google Scholar
• Munari P, Gondzio J (2015) Column generation and branch-and-price with interior point methods. Proc. Ser. Brazilian Soc. Comput. Appl. Math. 3(1):010525-1–010525-7.Google Scholar
• Munari P, Morabito R (2018) A branch-price-and-cut for the vehicle routing problem with time windows and multiple deliverymen. TOP 26(3):437–464.Crossref, Google Scholar
• Ordóñez F (2010) Robust vehicle routing. Hasenbein JJ, ed. Risk and Optimization in an Uncertain World, TutORials in Operations Research (INFORMS, Hanover, MD), 153–178.Link, Google Scholar
• Oyola J, Arntzen H, Woodruff DL (2017) The stochastic vehicle routing problem, a literature review, part II: Solution methods. EURO J. Transportation Logist. 6(4):349–388.Crossref, Google Scholar
• Oyola J, Arntzen H, Woodruff DL (2018) The stochastic vehicle routing problem, a literature review, part I: Models. EURO J. Transportation Logist. 7(3):193–221.Crossref, Google Scholar
• Pecin D, Contardo C, Desaulniers G, Uchoa E (2017a) New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS J. Comput. 29(3):489–502.Link, Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E (2017b) Improved branch-cut-and-price for capacitated vehicle routing. Math. Programming Comput. 9(1):61–100.Crossref, Google Scholar
• Pessoa AA, Di Puglia Pugliese L, Guerriero F, Poss M (2015) Robust constrained shortest path problems under budgeted uncertainty. Networks 66(2):98–111.Crossref, Google Scholar
• Poggi M, Uchoa E (2014) New exact algorithms for the capacitated vehicle routing problem. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications, 2nd ed., MOS-SIAM Series in Optimization (Society for Industrial and Applied Mathematics, Philadelphia), 59–86.Crossref, Google Scholar
• Pugliese LDP, Guerriero F (2013) A survey of resource constrained shortest path problems: Exact solution approaches. Networks 62(3):183–200.Crossref, Google Scholar
• Pureza V, Morabito R, Reimann M (2012) Vehicle routing with multiple deliverymen: Modeling and heuristic approaches for the VRPTW. Eur. J. Oper. Res. 218(3):636–647.Crossref, Google Scholar
• Richter AT, Stiller S (2018) Robust strategic route planning in logistics. Transportation Sci. 52(1):38–58.Link, Google Scholar
• Righetto GM, Morabito R, Douglas A (2016) A robust optimization approach for cash flow management in stationery companies. Comput. Indust. Engrg. 99:137–152.Crossref, Google Scholar
• Righini G, Salani M (2008) New dynamic programming algorithms for the resource constrained elementary shortest path problem. Networks 51(3):155–170.Crossref, Google Scholar
• Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2):254–265.Link, Google Scholar
• Sungur I, Ordóñez F, Dessouky M (2008) A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. IIE Trans. 40(5):509–523.Crossref, Google Scholar
• Toth P, Vigo D, eds. (2014) Vehicle Routing: Problems, Methods and Applications, 2nd ed., MOS-SIAM Series in Optimization (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Vanderbeck F (2005) Implementing mixed integer column generation. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, New York), 331–358.Crossref, Google Scholar
• Vanderbeck F, Wolsey LA (2010) Reformulation and decomposition of integer programs. Jünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA, eds. 50 Years of Integer Programming 1958–2008 (Springer, Berlin), 431–502.Crossref, Google Scholar