Intelligent Parcel Delivery Scheduling Using Truck-Drones to Cut down Time and Cost

Abstract

In the evolving landscape of logistics, drone technology presents a solution to the challenges posed by traditional ground-based deliveries, such as traffic congestion and unforeseen road closures. This research addresses the Truck–Drone Delivery Problem (TDDP), wherein a truck collaborates with a drone, acting as a mobile charging and storage unit. Although the Traveling Salesman Problem (TSP) can represent the TDDP, it becomes computationally burdensome when nodes are dynamically altered. Motivated by this limitation, our study’s primary objective is to devise a model that ensures swift execution without compromising the solution quality. We introduce two meta-heuristics: the Strawberry Plant, which refines the initial truck schedule, and Genetic Algorithms, which optimize the combined truck–drone schedule. Using “Dataset 1” and comparing with the Multi-Start Tabu Search (MSTS) algorithm, our model targeted costs to remain within 10% of the optimum and aimed for a 73% reduction in the execution time. Of the 45 evaluations, 37 met these cost parameters, with our model surpassing MSTS in eight scenarios. In contrast, using “Dataset 2” against the CPLEX solver, our model optimally addressed all 810 experiments, while CPLEX managed only 90 within the prescribed time. For 20-customer scenarios and more, CPLEX encountered memory limitations. Notably, when both methods achieved optimal outcomes, our model’s computational efficiency exceeded CPLEX by a significant margin. As the customer count increased, so did computational challenges, indicating the importance of refining our model’s strategies. Overall, these findings underscore our model’s superiority over established solvers like CPLEX and the economic advantages of drone-assisted delivery systems.

Keywords

• traveling salesman
• drone
• heuristics
• parcel delivery
• mixed-integer programming