The truck–drone routing optimization problem: mathematical model and a VNS approach

A combined Truck–drone system that delivers packages from a warehouse to multiple customers is investigated. The truck movements are restricted to the potential stops from which the drone with limited capacity takes off or lands. The aim is to determine both the best or ‘optimal’ sequence of the drone delivery trips and the best or ‘optimal’ trucks stops that will minimize the total combined truck drone delivery cost. This is an innovative delivery process which also falls under the umbrella of last mile delivery which is known to be one of the most challenging activities within logistics. The problem is first formulated as a 0–1 Linear programming model. A Variable Neighborhood Search (VNS) algorithm is then designed. The proposed metaheuristic is assessed on test problems from the online TSP library. A sensitivity analysis which examines the effect of a neighborhood removal, and the neighborhood sequencing is carried out. The metaheuristic has also shown to be reliable when tested against our mathematical model using the commercial optimizer CPLEX. Interesting overall results are discovered which demonstrate the robustness of the proposed VNS.