The traveling salesman problem with release dates and drone resupply: A new formulation and a matheuristic approach

Drones are increasingly used in last-mile logistics to streamline the final, and often complex, delivery stage. While synchronized truck-and-drone systems have been widely studied, direct drone deliveries face regulatory and safety challenges. An emerging alternative is to use drones to resupply delivery trucks in transit, mitigating some regulatory and safety barriers and enhancing efficiency without direct-to-customer deployment. This new system reduces reliance on centralized depots, improves delivery speed, supports real-time order fulfillment, and enhances flexibility, cost-effectiveness, and sustainability. By delivering new packages to trucks on the road, drones can cut detours and fuel use, especially in rural areas, while better matching fluctuating demand. In this context, we tackle the Traveling Salesman Problem with Release Dates and Drone Resupply ( TSP-RD-DR ), which consists of determining the truck route and the drone resupply schedule to serve all customers in accordance with their release dates while minimizing the delivery completion time. We propose a novel formulation for the TSP-RD-DR and a matheuristic approach that exploits this formulation. The proposed methods are tested on benchmark instances and compared with the state of the art for the TSP-RD-DR . The proposed formulation can solve benchmark instances with up to 20 customers within a one-hour time limit. The matheuristic provides high-quality solutions in limited computational times and scales effectively to instances with up to 100 customers.