Fast Heuristics for Traveling Salesman Problems with Multiple Flying Sidekicks

Speedy delivery of products is important for customers and the optimization of the last mile has particular challenges. In recent years drone-supported delivery has become increasingly feasible and therefore a topic of intense research. In this paper we address a traveling salesman problem where a truck has to serve customers and can use drones as flying sidekicks for the delivery of parcels. The goal is to assign customers to be either served by the truck or by some drone and schedule all events in order to minimize the total completion time of whole operation. We propose a heuristic for this problem, and introduce several novel components, including a multi-armed bandit selection for partitioning customers, an efficient matching-based heuristic for assigning drones to customers, local searches to improve solutions, and a fast greedy scheduler to estimate solution quality. In computational experiments we show that the combined approach finds better solutions than current methods, in less time.