Exact Branch-Price-and-Cut Algorithms for Vehicle Routing

References

• Abdallah KS, Jang J (2014) An exact solution for vehicle routing problems with semi-hard resource constraints. Comput. Indust. Engrg. 76(October):366–377.Crossref, Google Scholar
• Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Upper Saddle River, NJ).Google Scholar
• Andelmin J, Bartolini E (2017) An exact algorithm for the green vehicle routing problem. Transportation Sci. 51(4):1288–1303.Link, Google Scholar
• Angelelli E, Mansini R (2002) The vehicle routing problem with time windows and simultaneous pick-up and delivery. Klose A, Speranza MG, Van Wassenhove LN, eds. Quantitative Approaches to Distribution Logistics and Supply Chain Management (Springer, Berlin), 249–267.Crossref, Google Scholar
• Archetti C, Speranza MG (2012) Vehicle routing problems with split deliveries. Internat. Trans. Oper. Res. 19(1/2):3–22.Crossref, Google Scholar
• Archetti C, Bianchessi N, Speranza MG (2011) A column generation approach for the split delivery vehicle routing problem. Networks 58(4):241–254.Crossref, Google Scholar
• Archetti C, Bianchessi N, Speranza MG (2013a) The capacitated team orienteering problem with incomplete service. Optim. Lett. 7(7):1405–1417.Crossref, Google Scholar
• Archetti C, Bianchessi N, Speranza MG (2013b) Optimal solutions for routing problems with profits. Discrete Appl. Math. 161(4–5):547–557.Crossref, Google Scholar
• Archetti C, Bianchessi N, Speranza MG (2014) The split delivery capacitated team orienteering problem. Networks 63(1):16–33.Crossref, Google Scholar
• Archetti C, Bianchessi N, Speranza MG (2015) A branch-price-and-cut algorithm for the commodity constrained split delivery vehicle routing problem. Comput. Oper. Res. 64(December):1–10.Crossref, Google Scholar
• Archetti C, Bouchard M, Desaulniers G (2011) Enhanced branch and price and cut for vehicle routing with split deliveries and time windows. Transportation Sci. 45(3):285–298.Link, Google Scholar
• Archetti C, Bianchessi N, Speranza MG, Hertz A (2014) Incomplete service and split deliveries in a routing problem with profits. Networks 63(2):135–145.Crossref, Google Scholar
• Archetti C, Feillet D, Hertz A, Speranza MG (2009) The capacitated team orientering and profitable tour problems. J. Oper. Res. Soc. 60(6):831–842.Crossref, Google Scholar
• Augerat P, Belenguer J, Benavent E, Coberan A, Naddef D, Rinaldi G (1998) Computational results with a branch-and-cut code for the capacitated vehicle routing problem. Technical report, Istituto di Analisi dei Sistemi ed Informatica, Rome.Google Scholar
• Azi N, Gendreau M, Potvin JY (2007) An exact algorithm for a single-vehicle routing problem with time windows and multiple routes. Eur. J. Oper. Res. 178(3):755–766.Crossref, Google Scholar
• Azi N, Gendreau M, Potvin JY (2010) An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles. Eur. J. Oper. Res. 202(3):756–763.Crossref, Google Scholar
• Balas E (1977) Some valid inequalities for the set partitioning problem. Ann. Discrete Math. 1:13–47.Crossref, Google Scholar
• Balas E, Padberg MW (1976) Set partitioning: A survey. SIAM Rev. 18(4):710–760.Crossref, Google Scholar
• Baldacci R, Mingozzi A (2009) A unified exact method for solving different classes of vehicle routing problems. Math. Programming 120(2):347–380.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
• Baldacci R, Christofides N, Mingozzi A (2008) An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming 115(2):351–385.Crossref, Google Scholar
• Baldacci R, Hadjiconstantinou E, Mingozzi A (2004) An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper. Res. 52(5):723–738.Link, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2012) Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. Eur. J. Oper. Res. 218(1):1–6.Crossref, Google Scholar
• Balinski ML, Quandt RE (1964) On an integer program for a delivery problem. Oper. Res. 12(2):300–304.Link, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Beasley JE, Christofides N (1989) An algorithm for the resource constrained shortest path problem. Networks 19(4):379–394.Crossref, Google Scholar
• Bektaş T, Laporte G (2011) The pollution-routing problem. Transportation Res. Part B: Methodol. 45(8):1232–1250.Crossref, Google Scholar
• Ben Amor HMT, 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, Ghaoui LE, Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Berbeglia G, Cordeau JF, Gribkovskaia I, Laporte G (2007) Static pickup and delivery problems: A classification scheme and survey. TOP 15(1):1–31.Crossref, Google Scholar
• Bertsimas D, Pachamanova D, Sim M (2004) Robust linear optimization under general norms. Oper. Res. Lett. 32(6):510–516.Crossref, Google Scholar
• Bettinelli A, Ceselli A, Righini G (2011) A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows. Transportation Res. Part C: Emerging Tech. 19(5):723–740.Crossref, Google Scholar
• Bettinelli A, Ceselli A, Righini G (2014) A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows. Math. Programming Comput. 6(2):171–197.Crossref, Google Scholar
• Boland N, Dethridge J, Dumitrescu I (2006) Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Oper. Res. Lett. 34(1):58–68.Crossref, Google Scholar
• Boschetti MA, Maniezzo V, Strappaveccia F (2017) Route relaxations on GPU for vehicle routing problems. Eur. J. Oper. Res. 258(2):456–466.Crossref, Google Scholar
• Boussier S, Feillet D, Gendreau M (2007) An exact algorithm for team orienteering problems. 4OR 5(3):211–230.Crossref, Google Scholar
• Braekers K, Ramaekers K, Nieuwenhuyse IV (2016) The vehicle routing problem: State of the art classification and review. Comput. Indust. Engrg. 99(September):300–313.Crossref, Google Scholar
• Bulhões T, Hà MH, Martinelli R, Vidal T (2018) The vehicle routing problem with service level constraints. Eur. J. Oper. Res. 265(2):544–558.Crossref, Google Scholar
• Bulhões T, Sadykov R, Uchoa E (2018) A branch-and-price algorithm for the minimum latency problem. Comput. Oper. Res. 93(May):66–78.Crossref, Google Scholar
• Butt SE, Ryan DM (1999) An optimal solution procedure for the multiple tour maximum collection problem using column generation. Comput. Oper. Res. 26(4):427–441.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
• Cherkesly M, Desaulniers G, Laporte G (2015) Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and last-in-first-out loading. Transportation Sci. 49(4):752–766.Link, Google Scholar
• Cherkesly M, Desaulniers G, Irnich S, Laporte G (2016) Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and multiple stacks. Eur. J. Oper. Res. 250(3):782–793.Crossref, Google Scholar
• Choi E, Tcha DW (2007) A column generation approach to the heterogeneous fleet vehicle routing problem. Comput. Oper. Res. 34(7):2080–2095.Crossref, Google Scholar
• Christiansen CH, Lysgaard J (2007) A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands. Oper. Res. Lett. 35(6):773–781.Crossref, Google Scholar
• Christofides N, Mingozzi A, Toth P (1981a) Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations. Math. Programming 20(1):255–282.Crossref, Google Scholar
• Christofides N, Mingozzi A, Toth P (1981b) State-space relaxation procedures for the computation of bounds to routing problems. Networks 11(2):145–164.Crossref, Google Scholar
• Contardo C, Martinelli R (2014) A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optim. 12(May):129–146.Crossref, Google Scholar
• Contardo C, Cordeau JF, Gendron B (2014) An exact algorithm based on cut-and-column generation for the capacitated location-routing problem. INFORMS J. Comput. 26(1):88–102.Link, 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
• Cordeau JF (2006) A branch-and-cut algorithm for the dial-a-ride problem. Oper. Res. 54(3):573–586.Link, Google Scholar
• Cordeau JF, Laporte G (2007) The dial-a-ride problem: Models and algorithms. Ann. Oper. Res. 153(1):29–46.Crossref, Google Scholar
• Côté JF, Archetti C, Speranza MG, Gendreau M, Potvin JY (2012) A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks. Networks 60(4):212–226.Crossref, Google Scholar
• Dabia S, Demir E, Van Woensel T (2017) An exact approach for a variant of the pollution-routing problem. Transportation Sci. 51(2):607–628.Link, Google Scholar
• Dabia S, Ropke S, Van Woensel T, de Kok T (2013) Branch and price for the time-dependent vehicle routing problem with time windows. Transportation Sci. 47(3):380–396.Link, Google Scholar
• Dantzig GB, Ramser JH (1959) The truck dispatching problem. Management Sci. 6(1):80–91.Link, Google Scholar
• Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale travelling-salesman problem. J. Oper. Res. Soc. Amer. 2(4):393–410.Link, Google Scholar
• Dell’Amico M, Righini G, Salani M (2006) A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection. Transportation Sci. 40(2):235–247.Link, Google Scholar
• Desaulniers G (2010) Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Oper. Res. 58(1):179–192.Link, Google Scholar
• Desaulniers G, Desrosiers J, Solomon MM, eds. (2005) Column Generation, 1st ed. (Springer, Boston).Crossref, Google Scholar
• Desaulniers G, Desrosiers J, Spoorendonk S (2011) Cutting planes for branch-and-price algorithms. Networks 58(4):301–310.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. (Society for Industrial and Applied Mathematics, Philadelphia), 119–159.Crossref, Google Scholar
• Desaulniers G, Pecin D, Contardo C (2017) Selective pricing in branch-price-and-cut algorithms for vehicle routing. EURO J. Transportation Logist. 8(2):147–168.Crossref, Google Scholar
• Desaulniers G, Errico F, Irnich S, Schneider M (2016) Exact algorithms for electric vehicle-routing problems with time windows. Oper. Res. 64(6):1388–1405.Link, Google Scholar
• Desaulniers G, Desrosiers J, Ioachim I, Solomon MM, Soumis F, Villeneuve D (1998) A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. Crainic TG, Laporte G, eds. Fleet Management and Logistics (Springer, Boston), 57–93.Crossref, Google Scholar
• Desrochers M, Soumis F (1988) A generalized permanent labeling algorithm for the shortest path problem with time windows. INFOR 26(3):191–212.Google Scholar
• Desrochers M, Desrosiers J, Solomon M (1992) A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. 40(2):342–354.Link, Google Scholar
• Desrosiers J, Soumis F, Desrochers M (1984) Routing with time windows by column generation. Networks 14(4):545–565.Crossref, Google Scholar
• Dinh T, Fukasawa R, Luedtke J (2018) Exact algorithms for the chance-constrained vehicle routing problem. Math. Programming 172(1–2):105–138.Crossref, Google Scholar
• Drexl M (2012) Synchronization in vehicle routing—A survey of VRPs with multiple synchronization constraints. Transportation Sci. 46(3):297–316.Link, Google Scholar
• Dror M (1994) Note on the complexity of the shortest path models for column generation in VRPTW. Oper. Res. 42(5):977–978.Link, Google Scholar
• Dumas Y, Desrosiers J, Soumis F (1991) The pickup and delivery problem with time windows. Eur. J. Oper. Res. 54(1):7–22.Crossref, Google Scholar
• Eksioglu B, Volkan A, Reisman A (2009) The vehicle routing problem: A taxonomic review. Comput. Indust. Engrg. 57(4):1472–1483.Crossref, Google Scholar
• Errico F, Desaulniers G, Gendreau M, Rei W, Rousseau LM (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
• Errico F, Desaulniers G, Gendreau G, Rei W, Roussau LM (2018) The vehicle routing problem with hard time windows and stochastic service times. EURO J. Transportation Logist. 7(3):223–251.Crossref, Google Scholar
• Feillet D (2010) A tutorial on column generation and branch-and-price for vehicle routing problems. 4OR 8(4):407–424.Crossref, Google Scholar
• Feillet D, Dejax P, Gendreau M (2005) The profitable arc tour problem: Solution with a branch-and-price algorithm. Transportation Sci. 39(4):539–552.Link, Google Scholar
• Feillet D, Gendreau M, Rousseau LM (2008) New refinements for the solution of vehicle routing problems with branch and price. INFOR 45(4):239–256.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
• Fukasawa R, He Q, Song Y (2016) A branch-cut-and-price algorithm for the energy minimization vehicle routing problem. Transportation Sci. 50(1):23–34.Link, Google Scholar
• Fukasawa R, Longo H, Lysgaard J, Poggi de Aragão M, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106(3):491–511.Crossref, Google Scholar
• Gauvin C, Desaulniers G, Gendreau M (2014) A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands. Comput. Oper. Res. 50(October):141–153.Crossref, Google Scholar
• Gélinas S, Desrochers M, Desrosiers J, Solomon MM (1995) A new branching strategy for time constrained routing problems with application to backhauling. Ann. Oper. Res. 61(1):91–109.Crossref, Google Scholar
• Gendreau M, Jabali O, Rei W (2014) Stochastic vehicle routing problems. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods and Applications, 2nd ed. (Society for Industrial and Applied Mathematics, Philadelphia), 213–239.Crossref, Google Scholar
• Gendreau M, Laporte G, Séguin R (1996) Stochastic vehicle routing. Eur. J. Oper. Res. 88(1):3–12.Crossref, Google Scholar
• Gendreau M, Dejax P, Feillet D, Gueguen C (2006) Vehicle routing with time windows and split deliveries. Technical Report 2006-851, Laboratoire Informatique d’Avignon, Avignon, France.Google Scholar
• Ghilas V, Cordeau JF, Demir E, Woensel TV (2018) Branch-and-price for the pickup and delivery problem with time windows and scheduled lines. Transportation Sci. 52(5):1191–1210.Link, Google Scholar
• Gschwind T (2015) A comparison of column-generation approaches to the synchronized pickup and delivery problem. Eur. J. Oper. Res. 247(1):60–71.Crossref, Google Scholar
• Gschwind T, Irnich S (2015) Effective handling of dynamic time windows and its application to solving the dial-a-ride problem. Transportation Sci. 49(2):335–354.Link, Google Scholar
• Gschwind T, Irnich S, Rothenbächer AK, Tilk C (2018) Bidirectional labeling in column-generation algorithms for pickup-and-delivery problems. Eur. J. Oper. Res. 266(1):521–530.Crossref, Google Scholar
• Gutiérrez-Jarpa G, Desaulniers G, Laporte G, Marianov V (2010) A branch-and-price algorithm for the vehicle routing problem with deliveries, selective pickups and time windows. Eur. J. Oper. Res. 206(2):341–349.Crossref, Google Scholar
• Hadjar A, Marcotte O, Soumis F (2006) A branch-and-cut algorithm for the multiple depot vehicle scheduling problem. Oper. Res. 54(1):130–149.Link, Google Scholar
• Hernandez F, Feillet D, Giroudeau R, Naud O (2014) A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration. 4OR 12(3):235–259.Crossref, Google Scholar
• Hernandez F, Feillet D, Giroudeau R, Naud O (2016) Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows. Eur. J. Oper. Res. 249(2):551–559.Crossref, Google Scholar
• Houck D, Picard J, Queyranne M, Vemuganti R (1980) The travelling salesman problem as a constrained shortest path problem: Theory and computational experience. OPSEARCH 17(2–3):93–109.Google Scholar
• Ichoua S, Gendreau M, Potvin JY (2003) Vehicle dispatching with time-dependent travel times. Eur. J. Oper. Res. 144(2):379–396.Crossref, Google Scholar
• Iori M, Riera-Ledesma J (2015) Exact algorithms for the double vehicle routing problem with multiple stacks. Comput. Oper. Res. 63(November):83–101.Crossref, Google Scholar
• Irnich S (2008) Resource extension functions: Properties, inversion and generalization to segments. OR Spectrum 30(1):113–148.Crossref, Google Scholar
• Irnich S (2010) A new branch-and-price algorithm for the traveling tournament problem. Eur. J. Oper. Res. 204(2):218–228.Crossref, Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation, 1st ed. (Springer, Boston), 33–65.Crossref, Google Scholar
• Irnich S, Villeneuve D (2006) The shortest path problem with resource constraints and k-cycle elimination for k\ge3. INFORMS J. Comput. 18(3):391–406.Link, 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. (Society for Industrial and Applied Mathematics, Philadelphia), 1–33.Crossref, Google Scholar
• 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.Link, Google Scholar
• Jepsen M, Petersen B, Spoorendonk 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
• Kara İ, Kara BY, Yetiş MK (2008) Cumulative vehicle routing problems. Caric T, Gold H, eds. Vehicle Routing Problem (I-Tech Education and Publishing KG, Vienna), 85–98.Crossref, Google Scholar
• Keshtkaran M, Ziarati K, Bettinelli A, Vigo D (2015) Enhanced exact solution methods for the team orienteering problem. Internat. J. Production Res. 54(2):591–601.Crossref, Google Scholar
• Kohl N, Desrosiers J, Madsen OBG, Solomon MM, Soumis F (1999) 2-Path cuts for the vehicle routing problem with time windows. Transportation Sci. 33(1):101–116.Link, Google Scholar
• Laporte G, Nobert Y, Desrochers M (1985) Optimal routing under capacity and distance restrictions. Oper. Res. 33(5):1050–1073.Link, 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
• Letchford AN, Salazar-González JJ (2006) Projection results for vehicle routing. Math. Programming 105(2):251–274.Crossref, Google Scholar
• Liberatore F, Righini G, Salani M (2011) A column generation algorithm for the vehicle routing problem with soft time windows. 4OR 9(1):49–82.Crossref, Google Scholar
• Lin C, Choy K, Ho G, Chung S, Lam H (2014) Survey of green vehicle routing problem: Past and future trends. Expert Systems Appl. 41(4):1118–1138.Crossref, Google Scholar
• Lozano L, Medaglia AL (2013) On an exact method for the constrained shortest path problem. Comput. Oper. Res. 40(1):378–384.Crossref, Google Scholar
• Lozano L, Duque D, Medaglia AL (2016) An exact algorithm for the elementary shortest path problem with resource constraints. Transportation Sci. 50(1):348–357.Link, Google Scholar
• Lübbecke ME (2005) Dual variable based fathoming in dynamic programs for column generation. Eur. J. Oper. Res. 162(1):122–125.Crossref, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Luo Z, Liu M, Lim A (2018) A two-phase branch-and-price-and-cut for a dial-a-ride problem in patient transportation. Transportation Sci. 53(1):113–130.Link, Google Scholar
• Luo Z, Qin H, Zhu W, Lim A (2017) Branch and price and cut for the split-delivery vehicle routing problem with time windows and linear weight-related cost. Transportation Sci. 51(2):668–687.Link, Google Scholar
• Lysgaard J (2003) CVRPSEP: A package of separation routines for the capacitated vehicle routing problem. Technical report, Aarhus School of Business, Aarhus, Denmark.Google Scholar
• Lysgaard J, Wøhlk S (2014) A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem. Eur. J. Oper. Res. 236(3):800–810.Crossref, Google Scholar
• Lysgaard J, Letchford AN, Eglese RW (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Programming 100(2):423–445.Crossref, Google Scholar
• Marsten RE, Hogan WW, Blankenship JW, 1975 The boxstep method for large-scale optimization. Oper. Res. 23(3):389–405.Link, Google Scholar
• Martinelli R, Pecin D, Poggi M (2014) Efficient elementary and restricted non-elementary route pricing. Eur. J. Oper. Res. 239(1):102–111.Crossref, Google Scholar
• Masson R, Ropke S, Lehuédé F, Péton O (2013) A branch-and-cut-and-price approach for the pickup and delivery problem with shuttle routes. Eur. J. Oper. Res. 236(3):849–862.Crossref, Google Scholar
• Mingozzi A, Roberti R, Toth P (2013) An exact algorithm for the multitrip vehicle routing problem. INFORMS J. Comput. 25(2):193–207.Link, Google Scholar
• Moreno L, Poggi de Aragão M, Uchoa E (2010) Improved lower bounds for the split delivery vehicle routing problem. Oper. Res. Lett. 38(4):302–306.Crossref, Google Scholar
• Muter I, Cordeau JF, Laporte G (2014) A branch-and-price algorithm for the multidepot vehicle routing problem with interdepot routes. Transportation Sci. 48(3):425–441.Link, Google Scholar
• Naddef D, Rinaldi G (2002) Branch-and-cut algorithms for the capacitated VRP. Toth P, Vigo D, eds. The Vehicle Routing Problem, 1st ed. (Society for Industrial and Applied Mathematics, Philadelphia), 53–84.Crossref, Google Scholar
• Neame PJ (1999) Nonsmooth dual methods in integer programming. Unpublished doctoral thesis, University of Melbourne, Parkville, VIC, Australia.Google Scholar
• Nemhauser GL, Wolsey LA (1988) Integer and Combinatorial Optimization (Wiley-Interscience, New York).Crossref, Google Scholar
• Noorizadegan M, Chen B (2018) Vehicle routing with probabilistic capacity constraints. Eur. J. Oper. Res. 270(2):544–555.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
• Parragh SN, Sousa JP, Almada-Lobo B (2015) The dial-a-ride problem with split requests and profits. Transportation Sci. 49(2):311–334.Link, Google Scholar
• Pecin DG (2014) Exact algorithms for the capacitated vehicle routing problem. Unpublished doctoral thesis, Pontifical Catholic University of Rio de Janeiro, Rio de Janeiro.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
• Pecin D, Pessoa A, Poggi M, Uchoa E, Santos H (2017c) Limited memory rank-1 cuts for vehicle routing problems. Oper. Res. Lett. 45(3):206–209.Crossref, Google Scholar
• Pelletier S, Jabali O, Laporte G (2016) 50th anniversary invited article—Goods distribution with electric vehicles: Review and research perspectives. Transportation Sci. 50(1):3–22.Link, Google Scholar
• Pessoa A, Poggi de Aragão M, Uchoa E (2008) Robust branch-cut-and-price algorithms for vehicle routing problems. Golden B, Raghavan S, Wasil E, eds. The Vehicle Routing Problem: Latest Advances and New Challenges (Springer, Boston), 297–325.Crossref, Google Scholar
• Pessoa A, Poggi de Aragão M, Uchoa E (2009) A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem. Networks 54(4):167–177.Crossref, Google Scholar
• Pessoa A, Sadykov R, Uchoa E (2018) Enhanced branch-cut-and-price algorithm for heterogeneous fleet vehicle routing problems. Eur. J. Oper. Res. 270(2):530–543.Crossref, Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2018) Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS J. Comput. 30(2):339–360.Link, Google Scholar
• Petersen B, Pisinger D, Spoorendonk S (2008) Chvátal-Gomory rank-1 cuts used in a Dantzig-Wolfe decomposition of the vehicle routing problem with time windows. Golden B, Raghavan S, Wasil E, eds. The Vehicle Routing Problem: Latest Advances and New Challenges (Springer, Boston), 397–419.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. (Society for Industrial and Applied Mathematics, Philadelphia), 59–86.Crossref, Google Scholar
• Poggi de Aragão M, Uchoa E (2003) Integer program reformulation for robust branch-and-cut-and-price algorithms. Wolsey LA, ed. Proc. Conf. Math. Programming: Conf. Honour Nelson Maculan, Buzios, Brazil, 56–61.Google Scholar
• Qu Y, Bard JF (2015) A branch-and-price-and-cut algorithm for heterogeneous pickup and delivery problems with configurable vehicle capacity. Transportation Sci. 49(2):254–270.Link, Google Scholar
• Righini G, Salani M (2006) Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optim. 3(3):255–273.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
• Ropke S (2005) Heuristic and exact algorithms for vehicle routing problems. Unpublished doctoral dissertation, University of Copenhagen, Copenhagen.Google Scholar
• Ropke S, Cordeau JF (2009) Branch and cut and price for the pickup and delivery problem with time windows. Transportation Sci. 43(3):267–286.Link, Google Scholar
• Ropke S, Cordeau JF, Laporte G (2007) Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks 49(4):258–272.Crossref, Google Scholar
• Rousseau LM, Gendreau M, Feillet D (2007) Interior point stabilization for column generation. Oper. Res. Lett. 35(5):660–668.Crossref, Google Scholar
• Rousseau LM, Gendreau M, Pesant G (2004) Solving VRPTWs with constraint programming based column generation. Ann. Oper. Res. 130(1–4):199–216.Crossref, Google Scholar
• Ryan DM, Foster BA (1981) An integer programming approach to scheduling. Wren A, ed. Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling (North-Holland, Amsterdam), 269–280.Google Scholar
• Salani M, Vacca I (2011) Branch and price for the vehicle routing problem with discrete split deliveries and time windows. Eur. J. Oper. Res. 213(3):470–477.Crossref, Google Scholar
• Savelsbergh M, Sol M (1998) Drive: Dynamic routing of independent vehicles. Oper. Res. 46(4):474–490.Link, Google Scholar
• Souyris S, Cortés CE, Ordóñez F, Weintraub A (2013) A robust optimization approach to dispatching technicians under stochastic service times. Optim. Lett. 7(7):1549–1568.Crossref, Google Scholar
• Spoorendonk S, Desaulniers G (2010) Clique inequalities applied to the vehicle routing problem with time windows branch-cut-and-price. INFOR 48(1):53–67.Google Scholar
• Subramanian A, Uchoa E, Pessoa AA, Ochi LS (2013) Branch-cut-and-price for the vehicle routing problem with simultaneous pickup and delivery. Optim. Lett. 7(7):1569–1581.Crossref, Google Scholar
• Taş D, Gendreau M, Dellaert N, Van Woensel T, de Kok AG (2014) Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach. Eur. J. Oper. Res. 236(3):789–799.Crossref, Google Scholar
• Tilk C, Rothenbächer AK, Gschwind T, Irnich S (2017) Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster. Eur. J. Oper. Res. 261(2):530–539.Crossref, Google Scholar
• Vanderbeck F (2000) On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Oper. Res. 48(1):111–128.Link, Google Scholar
• Veenstra M, Cherkesly M, Desaulniers G, Laporte G (2017) The pickup and delivery problem with time windows and handling operations. Comput. Oper. Res. 77(January):127–140.Crossref, Google Scholar
• Villeneuve D, Desaulniers G (2005) The shortest path problem with forbidden paths. Eur. J. Oper. Res. 53(4):97–107.Crossref, Google Scholar
• Walker WE (1969) A method for obtaining the optimal dual solution to a linear program using the Dantzig-Wolfe decomposition. Oper. Res. 17(2):368–370.Link, Google Scholar
• Wentges P (1997) Weighted Dantzig-Wolfe decomposition for linear mixed-integer programming. Internat. Trans. Oper. Res. 4(2):151–162.Crossref, Google Scholar