A Branch-and-Price-and-Cut Algorithm for Resource-Constrained Pickup and Delivery Problems

References

• 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
• Barnhart C, Hane CA, Vance PH (2000) Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Oper. Res. 48(2):318–326.Link, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MW, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Battarra M, Cordeau JF, Iori M (2014) Pickup-and-delivery problems for goods transportation. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications, 2nd ed. (SIAM, Philadelphia), 161–191.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):45–47.Crossref, Google Scholar
• Chen X, Thomas BW, Hewitt M (2016) The technician routing problem with experience-based service times. Omega 61:49–61.Crossref, Google Scholar
• Chen X, Thomas BW, Hewitt M (2017) Multi-period technician scheduling with experience-based service times and stochastic customers. Comput. Oper. Res. 82:1–14.Crossref, Google Scholar
• Dai L, Stålhane M, Utne IB (2015) Routing and scheduling of maintenance fleet for offshore wind farms. Wind Engrg. 39(1):15–30.Crossref, Google Scholar
• Desrochers M (1987) La fabrication d’horaires de travail pour les conducteurs d’autobus par une méthode de génération de colonnes. Unpublished doctoral dissertation, University of Montreal, Montreal.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
• 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
• 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
• Feillet D, Gendreau M, Medaglia AL, Walteros JL (2010) A note on branch-and-cut-and-price. Oper. Res. Lett. 38(5):346–353.Crossref, Google Scholar
• Gamrath G, Fischer T, Gally T, Gleixner AM, Hendel G, Koch T, Maher SJ, et al. (2016) The scip optimization suite 3.2. Technical Report 15-60, Zuse Institute Berlin, Berlin.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(2):521–530.Crossref, Google Scholar
• Gu Z, Nemhauser GL, Savelsbergh MW (1998) Lifted cover inequalities for 0-1 integer programs: Computation. INFORMS J. Comput. 10(4):427–437.Link, Google Scholar
• Gu Z, Nemhauser GL, Savelsbergh MW (1999) Lifted cover inequalities for 0-1 integer programs: Complexity. INFORMS J. Comput. 11(1):117–123.Link, Google Scholar
• Hernández-Pérez H, Salazar-González JJ (2004) A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. Discrete Appl. Math. 145(1):126–139.Crossref, Google Scholar
• Hernández-Pérez H, Salazar-González JJ (2014) The multi-commodity pickup-and-delivery traveling salesman problem. Networks 63(1):46–59.Crossref, Google Scholar
• Irawan CA, Ouelhadj D, Jones D, Stålhane M, Sperstad IB, (2017) Optimisation of maintenance routing and scheduling for offshore wind farms. Eur. J. Oper. Res. 256(1):76–89.Crossref, 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), 33–65.Crossref, 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
• Kerkhove LP, Vanhoucke M (2017) Optimised scheduling for weather sensitive offshore construction projects. Omega 66:58–78.Crossref, Google Scholar
• López-Santana E, Akhavan-Tabatabaei R, Dieulle L, Labadie N, Medaglia AL (2016) On the combined maintenance and routing optimization problem. Reliability Engrg System Safety 145:199–214.Crossref, Google Scholar
• Lozano L, Duque D, Medaglia AL (2015) An exact algorithm for the elementary shortest path problem with resource constraints. Transportation Sci. 50(1):348–357.Link, Google Scholar
• Maher SJ (2015) Solving the integrated airline recovery problem using column-and-row generation. Transportation Sci. 50(1):216–239.Link, Google Scholar
• Muter I, Birbil Şİ, Bülbül K (2013) Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows. Math. Program. 142(1–2):47–82.Crossref, Google Scholar
• Naddef D, Rinaldi G (2001) Branch-and-cut algorithms for the capacitated VRP. Toth P, Vigo D, eds. The Vehicle Routing Problem (SIAM, Philadelphia), 53–84.Google Scholar
• Parragh SN, Doerner KF, Hartl RF (2008) A survey on pickup and delivery problems. J. Betriebswirtschaft 58(1):21–51.Crossref, Google Scholar
• Pillac et al., 2013Crossref, Google Scholar Pillac V, Guéret C, Medaglia AL (2013) A parallel matheuristic for the technician routing and scheduling problem. Optim. Lett. 7(7):1525–1535.Crossref, Google Scholar
• Pillac et al., 2018Crossref, Google Scholar Pillac V, Guéret C, Medaglia AL (2018) A fast reoptimization approach for the dynamic technician routing and scheduling problem. Amodeo L, Talbi El-G, Yalaoui F, eds. Recent Developments in Metaheuristics (Springer, New York), 347–367.Crossref, Google Scholar
• Polat O, Kalayci CB, Kulak O, Günther HO (2015) A perturbation based variable neighborhood search heuristic for solving the vehicle routing problem with simultaneous pickup and delivery with time limit. Eur. J. Oper. Res. 242(2):369–382.Crossref, 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
• Savelsbergh M (1997) A branch-and-price algorithm for the generalized assignment problem. Oper. Res. 45(6):831–841.Link, Google Scholar
• Savelsbergh MWP, Sol M (1995) The general pickup and delivery problem. Transportation Sci. 29(1):17–29.Link, Google Scholar
• Schrotenboer AH, Uit het Broek MAJ, Jargalsaikhan B, Roodbergen KJ (2018) Coordinating technician allocation and maintenance routing for offshore wind farms. Comput. Oper. Res. 98:185–197.Crossref, Google Scholar
• Stålhane M, Hvattum LM, Skaar V (2015) Optimization of routing and scheduling of vessels to perform maintenance at offshore wind farms. Energy Procedia 80:92–99.Crossref, Google Scholar
• Subramanian A, Cabral LdAF, (2008) An ILS based heuristic for the vehicle routing problem with simultaneous pickup and delivery and time limit. van Hemert J, Cotta C, eds. Eur. Conf. Evolutionary Comput. Combinatorial Optim. (Springer, New York), 135–146.Crossref, Google Scholar
• Tarantilis CD, Paraskevopoulos DC, Laporte G, Repoussis PP (2017) Resource constrained routing and scheduling: Review and research prospects. Eur. J. Oper. Res. 263(3):737–754.Crossref, Google Scholar
• Willis D, Niezrecki C, Kuchma D, Hines E, Arwade S, Barthelmie R, DiPaola M, et al.. (2018) Wind energy research: State-of-the-art and future research directions. Renewable Energy 125:133–154.Crossref, Google Scholar
• Zamorano E, Stolletz R (2016) Branch-and-price approaches for the multiperiod technician routing and scheduling problem. Eur. J. Oper. Res. 257(1):55–68.Crossref, Google Scholar