A variable neighborhood search for parcel delivery by vehicle with drone cycles

Abstract

In spite of the growing literature on and relevance of vehicle-drone parcel delivery, the logistical impact of cyclic drone flights, in which a drone launches and lands at the same node (as opposed to distinct sites) while delivering to a customer in between, remains unclear. To assess the pertinence and logistical impact of drone cycles, we propose a variable neighborhood search (VNS) heuristic for the Traveling Salesman Problem with Drone (TSP-D), whereby a vehicle and its companion aerial drone are synchronously routed to deliver customer orders with the objective of minimizing the return time of both carriers to the depot. The key to the success of the proposed VNS is a two-phase intensification scheme. In the first phase, the VNS broadly explores the feasible space by temporarily limiting the scope of drone flights and rendezvous locations. In the second phase, two features are introduced to ensure a deeper exploration of the feasible space: (i) intervening visits to customers are allowed for the vehicle between the drone rendezvous (launch and re-collect) nodes and (ii) drone operations may include no cycles, single cycles, or multiple cycles. The VNS is powered by optimization models that may accommodate the diverse operational settings proposed in the TSP-D literature. Over a set of benchmark instances, the VNS improves upon the best-known results for 113/120 instances having up to 100 nodes with comparable computational effort to existing approaches. The VNS also reveals improvements of up to 1%–8% in delivery times when drone multi-cycles are permitted, over a test-bed of diverse customer topographies and instance sizes.