Hybrid truck-drone delivery system with multi-visits and multi-launch and retrieval locations: Mathematical model and adaptive variable neighborhood search with neighborhood categorization

Drones have recently been suggested as a means of performing last-mile deliveries, as they have several advantages compared to traditional delivery vehicles. A recent research avenue is to adopt a hybrid truck-drone delivery system that integrates drones with traditional delivery methods such as trucks. This paper deals with the problem of optimizing the delivery operation of a truck working in tandem with a drone capable of visiting multiple customers per dispatch. We also introduce practical attributes such as allowing the truck to launch and retrieve the drone from both customer and non-customer nodes as well as permitting cyclic and acyclic drone operations. An integer linear programming model is first formulated followed by the development of an effective variable neighborhood search (VNS)-based approach. The novelty of the latter is that it incorporates an effective categorisation of neighborhoods due to their large number that is needed while retaining their individual impact through an adaptive selection scheme. The performance of this powerful VNS-based heuristic is empirically assessed against three variants of the VNS. The VNS heuristic was also shown to be flexible and effective at handling the issue of synchronization. A sensitivity analysis, based on some of the critical parameters of the drone, is conducted alongside highlights of some interesting insights.