An Exact Approach for Solving Pickup-and-Delivery Traveling Salesman Problems with Neighborhoods

References

• Agatz N, Bouman P, Schmidt M (2018) Optimization approaches for the traveling salesman problem with drone. Transportation Sci. 52(4):965–981.Link, Google Scholar
• Anily S, Mosheiov G (1994) The traveling salesman problem with delivery and backhauls. Oper. Res. Lett. 16(1):11–18.Crossref, Google Scholar
• Arkin EM, Hassin R (1994) Approximation algorithms for the geometric covering salesman problem. Discrete Appl. Math. 55(3):197–218.Crossref, 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., chapter 6 (Society for Industrial and Applied Mathematics, Philadelphia), 161–191.Crossref, Google Scholar
• Behdani B, Smith JC (2014) An integer-programming-based approach to the close-enough traveling salesman problem. INFORMS J. Comput. 26(3):415–432.Link, Google Scholar
• Belongia E (1988) The funcol program for primary healthcare, Colombia. Cultural Survival Quart. 12(1):19–25.Google Scholar
• Berbeglia G, Cordeau JF, Laporte G (2010) Dynamic pickup and delivery problems. Eur. J. Oper. Res. 202(1):8–15.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
• Carrabs F, Cerrone C, Cerulli R, Gaudioso M (2017) A novel discretization scheme for the close enough traveling salesman problem. Comput. Oper. Res. 78:163–171.Crossref, Google Scholar
• Christofides N (2022) Worst-case analysis of a new heuristic for the travelling salesman problem. Oper. Res. Forum 3:20.Google Scholar
• Cordeau JF, Dell’Amico M, Iori M (2010a) Branch-and-cut for the pickup and delivery traveling salesman problem with FIFO loading. Comput. Oper. Res. 37(5):970–980.Crossref, Google Scholar
• Cordeau JF, Iori M, Laporte G, Salazar González JJ (2010b) A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with LIFO loading. Networks 55(1):46–59.Crossref, Google Scholar
• Coutinho WP, do Nascimento RQ, Pessoa AA, Subramanian A (2016) A branch-and-bound algorithm for the close-enough traveling salesman problem. INFORMS J. Comput. 28(4):752–765.Link, Google Scholar
• Dell’Amico M, Montemanni R, Novellani S (2021) Drone-assisted deliveries: New formulations for the flying sidekick traveling salesman problem. Optim. Lett. 15(5):1617–1648.Crossref, Google Scholar
• Dumitrescu A, Mitchell JS (2003) Approximation algorithms for TSP with neighborhoods in the plane. J. Algorithms 48(1):135–159.Crossref, Google Scholar
• Dumitrescu I, Ropke S, Cordeau JF, Laporte G (2010) The traveling salesman problem with pickup and delivery: Polyhedral results and a branch-and-cut algorithm. Math. Programming 121(2):269–305.Crossref, Google Scholar
• Emami Y, Li K, Tovar E (2020) Buffer-aware scheduling for UAV relay networks with energy fairness. 2020 IEEE 91st Vehicular Tech. Conf. (VTC2020-Spring) (IEEE, Piscataway, NJ), 1–5.Google Scholar
• Gendreau M, Laporte G, Vigo D (1999) Heuristics for the traveling salesman problem with pickup and delivery. Comput. Oper. Res. 26(7):699–714.Crossref, Google Scholar
• Geoffrion AM (1972) Generalized Benders decomposition. J. Optim. Theory Appl. 10(4):237–260.Crossref, Google Scholar
• Gribkovskaia I, Halskau Ø Sr, Laporte G, Vlček M (2007) General solutions to the single vehicle routing problem with pickups and deliveries. Eur. J. Oper. Res. 180(2):568–584.Crossref, Google Scholar
• Gudmundsson J, Levcopoulos C (1999) A fast approximation algorithm for TSP with neighborhoods. Nordic J. Comput. 6(4):469–488.Google Scholar
• Gulczynski DJ, Heath JW, Price CC (2006) The close enough traveling salesman problem: A discussion of several heuristics. Alt FB, Fu MC, Golden BL, eds. Perspectives in Operations Research, Operations Research/Computer Science Interfaces Series, vol. 36 (Springer, Boston), 271–283.Crossref, Google Scholar
• Hernández-Pérez H, Salazar-González JJ (2004a) 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 (2004b) Heuristics for the one-commodity pickup-and-delivery traveling salesman problem. Transportation Sci. 38(2):245–255.Link, Google Scholar
• Hernández-Pérez H, Salazar-González JJ (2009) The multi-commodity one-to-one pickup-and-delivery traveling salesman problem. Eur. J. Oper. Res. 196(3):987–995.Crossref, Google Scholar
• Hernández-Pérez H, Rodríguez-Martín I, Salazar-González JJ (2009) A hybrid GRASP/VND heuristic for the one-commodity pickup-and-delivery traveling salesman problem. Comput. Oper. Res. 36(5):1639–1645.Crossref, Google Scholar
• Kalantari B, Hill AV, Arora SR (1985) An algorithm for the traveling salesman problem with pickup and delivery customers. Eur. J. Oper. Res. 22(3):377–386.Crossref, Google Scholar
• Li K, Ni W, Tovar E, Jamalipour A (2019) On-board deep Q-network for UAV-assisted online power transfer and data collection. IEEE Trans. Vehicular Technol. 68(12):12215–12226.Crossref, Google Scholar
• Mata CS, Mitchell JS 1995 Approximation algorithms for geometric tour and network design problems. Proc. 11th Annual Sympos. Comput. Geometry, 360–369.Google Scholar
• Mavalankar D (2016) Doctors for tribal areas: Issues and solutions. Indian J. Community Medicine 41(3):172–176.Crossref, Google Scholar
• Mennell WK (2009) Heuristics for Solving Three Routing Problems: Close-Enough Traveling Salesman Problem, Close-Enough Vehicle Routing Problem, and Sequence-Dependent Team Orienteering Problem (University of Maryland, College Park, MD).Google Scholar
• Mladenović N, Urošević D, Ilić A (2012) A general variable neighborhood search for the one-commodity pickup-and-delivery traveling salesman problem. Eur. J. Oper. Res. 220(1):270–285.Crossref, Google Scholar
• Mosheiov G (1994) The travelling salesman problem with pick-up and delivery. Eur. J. Oper. Res. 79(2):299–310.Crossref, Google Scholar
• Murray CC, Chu AG (2015) The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transp. Res., Part C Emerg. Technol. 54:86–109.Crossref, Google Scholar
• O’Neil RJ, Hoffman K (2017) Exact methods for solving traveling salesman problems with pickup and delivery in real time. Technical Report, George Mason University, Fairfax, VA.Google Scholar
• Ono F, Ochiai H, Miura R (2016) A wireless relay network based on unmanned aircraft system with rate optimization. IEEE Trans. Wirel. Commun. 15(11):7699–7708.Crossref, Google Scholar
• Parragh SN, Doerner KF, Hartl RF (2008) A survey on pickup and delivery problems. Journal für Betriebswirtschaft 58(2):81–117.Crossref, Google Scholar
• Psaraftis HN (1983) Analysis of an o(n2) heuristic for the single vehicle many-to-many Euclidean dial-a-ride problem. Transportation Res. Part B: Methodological 17(2):133–145.Crossref, 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
• Ramalingareddy K (2016) Improving health services for tribal populations. Internat. J. Res. Social Sci. 6(11):345–357.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. Transportation Sci. 40(4):455–472.Link, Google Scholar
• Savelsbergh MW, Sol M (1995) The general pickup and delivery problem. Transportation Sci. 29(1):17–29.Link, Google Scholar
• Toth P, Vigo D (2002) The Vehicle Routing Problem (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Veenstra M, Roodbergen KJ, Vis IF, Coelho LC (2017) The pickup and delivery traveling salesman problem with handling costs. Eur. J. Oper. Res. 257(1):118–132.Crossref, Google Scholar
• Wang X, Golden B, Wasil E (2019) A steiner zone variable neighborhood search heuristic for the close-enough traveling salesman problem. Comput. Oper. Res. 101:200–219.Crossref, Google Scholar
• Wei N, Walteros JL, Worden MR, Ortiz-Peña HJ (2021) A resiliency analysis of information distribution policies over mobile ad hoc networks. Optim. Lett. 15(4):1081–1103.Crossref, Google Scholar
• Xu H, Chen ZL, Rajagopal S, Arunapuram S (2003) Solving a practical pickup and delivery problem. Transportation Sci. 37(3):347–364.Link, Google Scholar
• Yuan B, Orlowska M, Sadiq S (2007) On the optimal robot routing problem in wireless sensor networks. IEEE Trans. Knowledge Data Engrg. 19(9):1252–1261.Crossref, Google Scholar
• Zhao F, Li S, Sun J, Mei D (2009) Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem. Comput. Ind. Eng. 56(4):1642–1648.Crossref, Google Scholar