Multiple traveling salesman problem with drones: Mathematical model and heuristic approach

E-commerce and retail companies are seeking ways to cut delivery times and costs by exploring opportunities to use drones for making last mile delivery deliveries. This paper addresses the delivery concept of a truck-drone combination along with the idea of allowing autonomous drones to fly from delivery trucks, make deliveries, and fly to any available delivery truck nearby. We present a mixed integer programming (MIP) formulation that captures this scenario with the objective of minimizing the arrival time of both trucks and drones at the depot after completing the deliveries. A new algorithm based on insertion heuristics is also developed to solve large sized problems containing up to a hundred locations. Experiments are conducted to compare the MIP solutions with those obtained from different models with single truck, multiple truck and a single truck and drone system, as well as test the performance of the proposed algorithm. The numerical results demonstrate the potential operational gain when implementing the proposed drone delivery system compared to the conventional truck alone or single truck/drone delivery system.