A MILP and a genetic algorithm for the flying sidekick TSP with variable drone speeds

Thanks to technological advances, many last-mile delivery companies have launched projects that combine unmanned aerial vehicles, commonly known as drones, with classic ground vehicles to reduce delivery times and gas emissions and improve customer satisfaction. However, most drone-aided optimization problems in the literature assume a non-realistic scenario in which the drone speed is constant and the drone endurance is independent of its speed and payload. This work addresses this gap by considering a realistic non-linear non-convex drone power consumption model with variable drone speeds. We propose an exact and heuristic approach for the Flying Sidekick Traveling Salesman Problem with Variable Drone Speeds (FSTSP-VDS), an extension of the flying sidekick traveling salesman problem in which a truck is combined with a drone that can fly at variable speeds to deliver parcels to customers to minimize the makespan. If the drone energy-per-meter function is convex, the FSTSP-VDS can be formulated as a Mixed Integer Linear Programming (MILP) problem. We propose a MILP model that can solve to optimality instances with up to ten customers. We also show that, when a realistic drone energy model is used, fixing the drone speed can increase the average makespan by 32%. We also propose a genetic algorithm that outperforms the current state-of-the-art by 7% on average and finds optimal solutions for constant-speed instances with up to 99 customers.