Exponential-Size Neighborhoods for the Pickup-and-Delivery Traveling Salesman Problem

References

• Ahuja RK, Ergun Ö, Orlin JB, Punnen AP (2002) A survey of very large-scale neighborhood search techniques. Discrete Appl. Math. 123(1–3):75–102.Crossref, Google Scholar
• Applegate DL, Bixby RE, Chvátal V, Cook WJ (2006) The Traveling Salesman Problem: A Computational Study (Princeton University Press, Princeton, NJ).Google Scholar
• Applegate DL, Bixby RE, Chvatal V, Cook WJ, Espinoza D, Goycoolea M, Helsgaun K (2009) Certification of an optimal TSP tour through 85,900 cities. Oper. Res. Lett. 37(1):11–15.Crossref, Google Scholar
• Arnold F, Santana ÍG, Sörensen K, Vidal T (2021) PILS: Exploring high-order neighborhoods by pattern mining and injection. Pattern Recognit. 116:107957.Crossref, Google Scholar
• Balas E, Simonetti N (2001) Linear time dynamic-programming algorithms for new classes of restricted TSPs: A computational study. INFORMS J. Comput. 13(1):56–75.Link, Google Scholar
• Bentley JJ (1992) Fast algorithms for geometric traveling salesman problems. ORSA J. Comput. 4(4):387–411.Link, Google Scholar
• Capua R, Frota Y, Ochi LS, Vidal T (2018) A study on exponential-size neighborhoods for the bin packing problem with conflicts. J. Heuristics. 24(4):667–695.Crossref, Google Scholar
• Carrabs F, Cordeau J-F, Laporte G (2007) Variable neighborhood search for the pickup and delivery traveling salesman problem with LIFO loading. INFORMS J. Comput. 19(4):618–632.Link, Google Scholar
• Christiaens J, Vanden Berghe G (2020) Slack induction by string removals for vehicle routing problems. Transport. Sci. 54(2): 417–433.Link, Google Scholar
• Congram RK, Potts CN, van de Velde SL (2002) An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem. INFORMS J. Comput. 14(1):52–67.Link, Google Scholar
• Cordeau J-F, Iori M, Laporte G, Salazar-González J-J (2012) A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with LIFO loading. Networks. 55(1):46–59.Crossref, Google Scholar
• De Berg M, Buchin K, Jansen BMP, Woeginger G (2020) Fine-grained complexity analysis of two classic TSP variants. ACM Trans. Algorithms. 17(1):1–29.Crossref, Google Scholar
• De Franceschi R, Fischetti M, Toth P (2006) A new ILP-based refinement heuristic for vehicle routing problems. Math. Program. 105(2):471–499.Crossref, Google Scholar
• Deineko VG, Woeginger GJ (2000) A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem. Math. Program. 87(3):519–542.Crossref, Google Scholar
• Dumitrescu I, Ropke S, Cordeau J-F, Laporte G (2010) The traveling salesman problem with pickup and delivery: Polyhedral results and a branch-and-cut algorithm. Math. Program. 121(2):269–305.Crossref, Google Scholar
• Erdogan G, Cordeau J-F, Laporte G (2009) The pickup and delivery traveling salesman problem with first-in-first-out loading. Comput. Oper. Res. 36(6):1800–1808.Crossref, Google Scholar
• Falkenauer E, Bouffoix S (1991) A genetic algorithm for job shop. IEEE International Conference on Robotics and Automation (IEEE, Sacramento, CA), 824–829.Google Scholar
• Glover F (1996) Finding a best traveling salesman 4-Opt move in the same time as a best 2-Opt move. J. Heuristics. 2(2):169–179.Crossref, Google Scholar
• Glover F, Rego C (2006). Ejection chain and filter-and-fan methods in combinatorial optimization. 4OR 4(4):263–296.Crossref, Google Scholar
• Gschwind T, Drexl M (2019) Adaptive large neighborhood search with a constant-time feasibility test for the dial-a-ride problem. Transport. Sci. 53(2):480–491.Link, Google Scholar
• Hansen P, Mladenović N, Brimberg J, Pérez JAM (2019) Variable neighborhood search. Gendreau M, Potvin JY, eds. Handbook of Metaheuristics. International Series in Operations Research and Management Science (Springer, Cham, Switzerland), 57–97.Google Scholar
• Healy P, Moll R (1995) A new extension of local search applied to the dial-a-ride problem. Eur. J. Oper. Res. 83(1):83–104.Crossref, Google Scholar
• Helsgaun K (2000) An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1):106–130.Crossref, Google Scholar
• Helsgaun K (2009) General k-Opt submoves for the Lin-Kernighan TSP heuristic. Math. Program. Comput. 1(2–3):119–163.Crossref, Google Scholar
• Hintsch T, Irnich S (2018) Large multiple neighborhood search for the clustered vehicle-routing problem. Eur. J. Oper. Res. 270(1):118–131.Crossref, Google Scholar
• Irnich S (2008) Solution of real-world postman problems. Eur. J. Oper. Res. 190(1):52–67.Crossref, Google Scholar
• Johnson D, Mcgeoch L (1997) The traveling salesman problem: A case study in local optimization. Aarts E, Lenstra JK, eds. Local Search in Combinatorial Optim. (Princeton University Press, Princeton, NJ), 215–310.Google Scholar
• Karimi-Mamaghan M, Mohammadi M, Meyer P, Karimi-Mamaghan AM, Talbi E-G (2022) Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art. Eur. J. Oper. Res. 296(2):393–422.Google Scholar
• Lancia G, Dalpasso M (2019) Algorithmic strategies for a fast exploration of the TSP 4-OPT neighborhood. Paolucci M, Sciomachen A, Pierpaolo U, eds. Adv. Optim. Decision Sci. Soc., Services and Enterprises (Springer, Berlin Heidelberg), 457–470.Crossref, Google Scholar
• Laporte G, Ropke S, Vidal T (2014) Heuristics for the vehicle routing problem. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications, chap. 4. Society for Industrial and Applied Mathematics, 87–116.Crossref, Google Scholar
• Levandowsky M, Winter D (1971) Distance between sets. Nature 234:34–35.Crossref, Google Scholar
• Lin S, Kernighan BW (1973) An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21(2):498–516.Link, Google Scholar
• Nagata Y, Kobayashi S (2013) A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem. INFORMS J. Comput. 25(2):346–363.Link, Google Scholar
• O’Neil RJ 2018. Exact method for solving single-vehicle pickup and delivery problems in real time. PhD, George Mason University, Fairfax, VA.Google Scholar
• O’Neil RJ, Hoffman K (2019) Decision diagrams for solving traveling salesman problems with pickup and delivery in real time. Oper. Res. Lett. 47(3):197–201.Crossref, Google Scholar
• Or I 1976. Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. PhD thesis, Northwestern University, Evanston, IL.Google Scholar
• Parragh SN, Doerner KF, Hartl RF (2008a) A survey on pickup and delivery problems Part I: Transportation between customers and depot. Journal für Betriebswirtschaft. 58(1):21–51.Crossref, Google Scholar
• Parragh SN, Doerner KF, Hartl RF (2008b) A survey on pickup and delivery problems Part II: Transportation between pickup and delivery locations. Journal für Betriebswirtschaft. 58(2):81–117.Crossref, Google Scholar
• Pisinger D, Ropke S (2010) Large neighborhood search. Gendreau M, Potvin JY, eds. Handbook of Metaheuristics. International Series in Operations Research and Management Science (Springer, Cham, Switzerland), 399–419.Crossref, Google Scholar
• Pollaris H, Braekers K, Caris A, Janssens GK, Limbourg S (2015) Vehicle routing problems with loading constraints: State-of-the-art and future directions. OR Spectrum. 37(2):297–330.Crossref, Google Scholar
• Psaraftis HN (1983) k-Interchange procedures for local search in a precedence-constrained routing problem. Eur. J. Oper. Res. 13(4):391–402.Crossref, Google Scholar
• Reinelt G (1991) TSPLIB—A traveling salesman problem library. ORSA J. Comput. 3(4):376–384.Link, Google Scholar
• Renaud J, Boctor FF, Laporte G (2002) Perturbation heuristics for the pickup and delivery traveling salesman problem. Comput. Oper. Res. 29(9):1129–1141.Crossref, Google Scholar
• Renaud J, Boctor FF, Ouenniche J (2000) A heuristic for the pickup and delivery traveling salesman problem. Comput. Oper. Res. 27(9):905–916.Crossref, Google Scholar
• Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transport. Sci. 40(4):455–472.Link, Google Scholar
• Ruland KS (1994) Polyhedral solution to the pickup and delivery problem. PhD thesis, Sever Institute of Washington University, St. Louis, MO.Google Scholar
• Ruland KS, Rodin EY (1997) The pickup and delivery problem: Faces and branch-and-cut algorithm. Comput. Math. Appl. 33(12):1–13.Crossref, Google Scholar
• Savelsbergh MWP (1990) An efficient implementation of local search algorithms for constrained routing problems. Eur. J. Oper. Res. 47(1):75–85.Crossref, Google Scholar
• Subramanian A, Uchoa E, Ochi LS (2013) A hybrid algorithm for a class of vehicle routing problems. Comput. Oper. Res. 40(10):2519–2531.Crossref, Google Scholar
• Taillard ÉD, Helsgaun K (2019) POPMUSIC for the travelling salesman problem. Eur. J. Oper. Res. 272(2):420–429.Crossref, Google Scholar
• Toffolo TAM, Vidal T, Wauters T (2019) Heuristics for vehicle routing problems: Sequence or set optimization? Comput. Oper. Res. 105:118–131.Crossref, Google Scholar
• Toth P, Vigo D (2003) The granular tabu search and its application to the vehicle-routing problem. INFORMS J. Comput. 15(4):333–346.Link, Google Scholar
• Uchoa E, Pecin D, Pessoa A, Poggi M, Subramanian A, Vidal T (2017) New benchmark instances for the capacitated vehicle routing problem. Eur. J. Oper. Res. 257(3):845–858.Crossref, Google Scholar
• Veenstra M, Roodbergen KJ, Vis IFA, Coelho LC (2017) The pickup and delivery traveling salesman problem with handling costs. Eur. J. Oper. Res. 257(1):118–132.Crossref, Google Scholar
• Vidal T (2017) Node, edge, arc routing, and turn penalties: Multiple problems—One neighborhood extension. Oper. Res. 65(4):992–1010.Link, Google Scholar
• Vidal T (2022) Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Comput. Oper. Res. 140:105643.Crossref, Google Scholar
• Vidal T, Laporte G, Matl P (2020) A concise guide to existing and emerging vehicle routing problem variants. Eur. J. Oper. Res. 286:401–416.Crossref, Google Scholar
• Vidal T, Crainic TG, Gendreau M, Prins C (2013) Heuristics for multi-attribute vehicle routing problems: A survey and synthesis. Eur. J. Oper. Res. 231(1):1–21.Crossref, Google Scholar
• Vidal T, Crainic TG, Gendreau M, Prins C (2014) A unified solution framework for multi-attribute vehicle routing problems. Eur. J. Oper. Res. 234(3):658–673.Crossref, Google Scholar
• Vidal T, Maculan N, Ochi LS, Penna PHV (2016) Large neighborhoods with implicit customer selection for vehicle routing problems with profits. Transport. Sci. 50(2):720–734.Link, Google Scholar
• Vidal T, Crainic TG, Gendreau M, Lahrichi N, Rei W (2012) A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Oper. Res. 60(3):611–624.Link, Google Scholar
• Yildiz B, Savelsbergh M (2019) Provably high-quality solutions for the meal delivery routing problem. Transport. Sci. 53(5): 1372–1388.Link, Google Scholar