Optimization of a Last Mile Delivery Model with a Truck and a Drone Using Mathematical Formulation and a VNS Algorithm

The use of drones in last-mile delivery services has attained significant interest due to the need for fast delivery. In addition, drones have the potential to reduce the cost associated with last-mile deliveries. However, restrictions such as payload capacity, range limits, and legal regulations have restricted the effective operational range of drones. To assist in alleviating these operational limitations, integrating a conventional delivery truck with drones to form a truck-drone delivery system, has received significant attention in the literature. This paper presents a scenario in which a single drone works in tandem with a single truck to serve customers. The drone can perform multiple deliveries in a single route, and the objective is to minimize the total traveling costs of both vehicles. An integer linear programming (ILP) model is developed and solved to optimality for small instances using the exact solution method. Considering the complexity of the ILP model, a variable neighborhood search (VNS) algorithm is introduced and assessed using small and large instances. In addition, a modified VNS algorithm involving a new neighborhood selection strategy is proposed and compared to the basic VNS. Both algorithms generate solutions in a short computational time for instances with up to 100 customer nodes.