New saving-based formulae for the truck–drone routing problem

Abstract Accepted by: M. Zied Babai This study investigates the hybrid truck–drone routing problem with an emphasis on last-mile delivery. To address this challenge, novel savings rules are developed by extending the classical Clarke and Wright savings formula, and these are incorporated into an adapted savings-based heuristic. In contrast to the traditional Clarke and Wright algorithm, the drone launch and retrieval points are not predetermined but instead depend on the truck’s route, resulting in greater complexity and flexibility. Consequently, nine distinct configurations are identified, each associated with a specific savings formulation. These contribute to the development of an enhanced Clarke and Wright-based heuristic, further augmented with a computational acceleration mechanism. For comparative evaluation, a sweep-based algorithm is also implemented to handle larger problem instances. The proposed savings-based heuristic (MSH) demonstrates superior performance over the sweep-based method, effectively capturing the operational structure of a moving depot. While the new savings equations remain relatively simple, they offer analytically rigorous and computationally efficient solutions that can serve as a strong foundation for future hybrid or metaheuristic approaches.