An efficient routing heuristic for a drone-assisted delivery problem

Source abstract

Abstract In this paper, we present a routing heuristic for the Flying Sidekick Traveling Salesman Problem. This problem combines a single truck with a single drone. The drone may be launched from the truck from a customer location and can make a single package delivery before being recovered by the truck. While the drone is in flight, the truck can deliver packages independently. The problem is one of simultaneously assigning the customers to each vehicle and determining the synchronized routes for both vehicles to satisfy all customer demands in the shortest time possible. The problem is NP-hard. Our main contribution lies in developing a novel split algorithm that utilizes a shortest path approach for determining the optimal routing solution to a given order of customer locations. This split algorithm has polynomial complexity. We develop a heuristic solution to the problem by combining the split algorithm with local search techniques. This overall heuristic is shown to be accurate and computationally scalable to large, realistically sized problems applicable in last-mile logistics.