A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations

With the goal of integrating drones in last-mile delivery, the Vehicle Routing Problem with Drones (VRPD) uses a fleet of vehicles, each of them equipped with a set of drones, for serving a set of customers with minimal makespan. In this paper, we propose an extension of the VRPD that we call the Vehicle Routing Problem with Drones and En Route Operations (VRPDERO). Here, in contrast to the VRPD, drones may not only be launched and retrieved at vertices but also on some discrete points that are located on each arc. We formulate the problem as a Mixed Integer Linear Program (MILP) and introduce some valid inequalities that enhance the performance of the MILP solvers. Furthermore, due to limited performance of the solvers in addressing large-scale instances, we propose an algorithm based on the concepts of Variable Neighborhood Search (VNS) and Tabu Search (TS). In order to evaluate the performance of the introduced algorithm as well as the solver in solving the VRPDERO instances, we carried out extensive computational experiments. According to the numerical results, the proposed valid inequalities and the heuristic have a significant contribution in solving the VRPDERO effectively. In addition, the consideration of en route operations can increase the utilization of drones and lead to an improved makespan. (C) 2019 Elsevier Ltd. All rights reserved.