Optimization Approaches for the Traveling Salesman Problem with Drone

References

• Applegate DL, Bixby RE, Chvátal V, Cook WJ (2001) TSP cuts which do not conform to the template paradigm. Jünger M, Naddef D, eds. Computational Combinatorial Optimization, Lecture Notes Comput. Sci., Vol. 2241 (Springer, Berlin Heidelberg), 261–303.Crossref, Google Scholar
• Applegate DL, Bixby RE, Chvátal V, Cook WJ (2011) The Traveling Salesman Problem: A Computational Study (Princeton University Press, Princeton, NJ).Google Scholar
• Beasley JE (1983) Route first–cluster second methods for vehicle routing. Omega 11(4):403–408.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
• Belenguer JM, Benavent E, Martínez A, Prins C, Prodhon C, Villegas JG (2016) A branch-and-cut algorithm for the single truck and trailer routing problem with satellite depots. Transportation Sci. 50(2):735–749.Link, Google Scholar
• Bouman P (2018) pcbouman-eur/drones-TSP: Traveling salesman with drone (Java code) v1.0.0. https://doi.org/10.5281/zenodo.1204697.Google Scholar
• Bouman P, Agatz N, Schmidt M (2018) Instances for the TSP with drone (and some solutions). https://doi.org/10.5281/zenodo.1204676.Google Scholar
• Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Defense Technical Information Center, Fort Belvoir, VA.Google Scholar
• Current JR, Schilling DA (1989) The covering salesman problem. Transportation Sci. 23(3):208–213.Link, Google Scholar
• Drexl M (2011) Branch-and-price and heuristic column generation for the generalized truck-and-trailer routing problem. Revista de Métodos Cuantitativos para la Economía y la Empresa 12:5–38.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
• Drexl M (2014) Branch-and-cut algorithms for the vehicle routing problem with trailers and transshipments. Networks 63(1):119–133.Crossref, Google Scholar
• Evers L, Dollevoet T, Barros AI, Monsuur H (2014) Robust UAV mission planning. Ann. Oper. Res. 222(1):293–315.Crossref, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to NP-Completeness (WH Freeman, New York).Google Scholar
• Golden B, Naji-Azimi Z, Raghavan S, Salari M, Toth P (2012) The generalized covering salesman problem. INFORMS J. Comput. 24(4):534–553.Link, 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, Oper. Res./Comput. Sci. Interfaces Series, Vol. 36 (Springer, Boston), 271–283.Crossref, Google Scholar
• Hern A (2014) DHL launches first commercial drone “Parcelcopter” delivery service. Guardian (September 24), https://www.theguardian.com/technology/2014/sep/25/german-dhl-launches-first-commercial-drone-delivery-service.Google Scholar
• Karp RM (1972) Reducibility among combinatorial problems. Miller RE, Thatcher JW, Bohlinger JD, eds. Complexity of Computer Computations, IBM Res. Sympos. Series (Springer, Boston), 85–103.Crossref, Google Scholar
• Kim MH, Baik H, Lee S (2014) Response threshold model based UAV search planning and task allocation. J. Intelligent Robotic Systems 75(3–4):625–640.Crossref, Google Scholar
• Kruskal JB (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc. 7(1):48–50.Google Scholar
• Laporte G (1992) The traveling salesman problem: An overview of exact and approximate algorithms. Eur. J. Oper. Res. 59(2):231–247.Crossref, Google Scholar
• Lin SW, Vincent FY, Chou SY (2009) Solving the truck and trailer routing problem based on a simulated annealing heuristic. Comput. Oper. Res. 36(5):1683–1692.Crossref, Google Scholar
• Murray CC, Chu AG (2015) The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Res. Part C: Emerging Tech. 54:86–109.Crossref, Google Scholar
• Nicas J, Bensinger G (2015) Delivery drones hit bumps on path to doorstep. Wall Street Journal (March 20), https://www.wsj.com/articles/technical-hurdles-delay-drone-deliveries-1426867441.Google Scholar
• Popper B (2013) UPS researching delivery drones that could compete with Amazon’s Prime Air. Verge (December 3), https://www.theverge.com/2013/12/3/5169878/ups-is-researching-its-own-delivery-drones-to-compete-with-amazons.Google Scholar
• Rosenkrantz DJ, Stearns RE, Lewis PM II (1977) An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6(3):563–581.Crossref, Google Scholar
• Scheuerer S (2006) A tabu search heuristic for the truck and trailer routing problem. Comput. Oper. Res. 33(4):894–909.Crossref, Google Scholar
• Shamos MI (1978) Computational geometry. Unpublished doctoral thesis, Yale University, New Haven, CT.Google Scholar
• Shuttleworth R, Golden BL, Smith S, Wasil E (2008) Advances in meter reading: Heuristic solution of the close enough traveling salesman problem over a street network. Golden B, Raghavan S, Wasil E, eds. The Vehicle Routing Problem: Latest Advances and New Challenges, Oper. Res./Comput. Sci. Interfaces, Vol. 43 (Springer, Boston), 487–501.Crossref, Google Scholar
• Valavanis KP, Vachtsevanos GJ (2015) UAV applications: Introduction. Valavanis K, Vachtsevanos GJ, eds. Handbook of Unmanned Aerial Vehicles (Springer, Dordrecht, Netherlands), 2639–2641.Crossref, Google Scholar
• Villegas JG, Prins C, Prodhon C, Medaglia AL, Velasco N (2011) A grasp with evolutionary path relinking for the truck and trailer routing problem. Comput. Oper. Res. 38(9):1319–1334.Crossref, Google Scholar
• Wang X, Poikonen S, Golden B (2017) The vehicle routing problem with drones: Several worst-case results. Optim. Lett. 11(4):679–697.Crossref, Google Scholar
• Wohlsen M (2014) The next big thing you missed: Amazon’s delivery drones could work. They just need trucks. Wired (June 10), https://www.wired.com/2014/06/the-next-big-thing-you-missed-delivery-drones-launched-from-trucks-are-the-future-of-shipping/.Google Scholar