Enabling the multi-LR ability of drones in the multi-visit truck-drone routing problem with pickup and delivery

The use of drones alongside trucks for parcel delivery has received considerable research attention, further stimulated by advancements in drone capacity and range that enhance operational viability relative to traditional methods. In this paper, we address a variant of the combined truck-drone routing problem, entailing multiple trucks collaborating with drones to meet the pickup and delivery demands of customers. In the proposed problem, drone energy consumption depends on the carried load; drones may serve multiple customers per flight, and each truck can launch and retrieve its drone multiple times at each customer node (multi-LR) to enhance overall utilization. We propose a mixed-integer linear programming model to minimize total cost, enhanced with problem-specific cuts, which are demonstrated through extensive computational experiments to effectively reduce runtime. The model includes flexible features that allow it to handle diverse operational constraints, such as restrictions on the number of flights performed and high-traffic areas. Given the complexity of the model, we develop an adapted algorithm from the literature, incorporating significant modifications along with a new acceleration strategy. The approach combines a maximum payload method in the first stage with an improved simulated annealing algorithm using problem-specific neighborhood operators in the second stage. Although our findings show that the multi-LR feature increases the number of flights performed, both the model and the adapted algorithm demonstrate its cost efficiency, achieving average transportation cost reductions of 14.51% compared to the system without multi-LR and 45.62% compared to the traditional truck-only system.