Optimization Approaches for the Traveling Salesman Problem with Drone
- 1 January 2015
- preprint
- Published by Elsevier BV in SSRN Electronic Journal
Abstract
The fast and cost-effcient home delivery of goods ordered online is logistically challenging. Many companies are looking for new ways to cross the last-mile to their customers. One technology-enabled opportunity that recently has received much attention is the use of a drone to support deliveries. An innovative last-mile delivery concept in which a truck collaborates with a drone to make deliveries gives rise to a new variant of the traveling salesman problem (TSP) that we call the TSP with drone. In this paper, we formulate this problem as an MIP model and develop several fast route first-cluster second heuristics based on local search and dynamic programming. We prove worst-case approximation ratios for the heuristics and test their performance by comparing the solutions to the optimal solutions for small instances. In addition, we apply our heuristics to several artificial instances with different characteristics and sizes. Our numerical analysis shows that substantial savings are possible with this concept in comparison to truck-only delivery.This publication has 19 references indexed in Scilit:
- Instances For The Tsp With Drone2015
- An Integer-Programming-Based Approach to the Close-Enough Traveling Salesman ProblemINFORMS Journal on Computing, 2014
- Branch‐and‐cut algorithms for the vehicle routing problem with trailers and transshipmentsNetworks, 2013
- Robust UAV mission planningAnnals of Operations Research, 2012
- The Generalized Covering Salesman ProblemINFORMS Journal on Computing, 2012
- Synchronization in Vehicle Routing—A Survey of VRPs with Multiple Synchronization ConstraintsTransportation Science, 2012
- TSP Cuts Which Do Not Conform to the Template ParadigmPublished by Springer Science and Business Media LLC ,2001
- The Covering Salesman ProblemTransportation Science, 1989
- Route first—Cluster second methods for vehicle routingOmega, 1983
- Reducibility among Combinatorial ProblemsPublished by Springer Science and Business Media LLC ,1972