The Traveling Salesman Problem with Release Dates and Drone Resupply

Abstract This paper introduces the Traveling Salesman Problem with Release Dates and Drone Resupply, which consists of finding a minimum time route for a single truck that can receive newly available orders en route via a drone sent from the depot. We assume that each order’s release date is known at the time of delivery planning. This context is common for many applications, notably last-mile logistics. We develop a Mixed-Integer Linear Program and a solution approach for larger instances based on decomposing the problem into the truck-routing and the drone-resupply decisions. Numerical experiments show that using drones for resupply can reduce the total delivery time by up to 20%. Additionally, experiments show that the decomposition can rapidly obtain high-quality solutions. For instances of 10 and 15 customers, the decomposition solved the majority to optimality, with a trivial gap. For larger instances, this approach provided lower delivery times than a traditional parcel delivery system using a truck only. Investigations on the effects of drone speed, drone capacity, depot location, constraint addition, and allowing the truck to return to the depot are studied. We consider instances up to 50 customers.