A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations. (September 2019)

• Record Type: Journal Article
• Authors: Schermer, Daniel; Moeini, Mahdi; Wendt, Oliver
• Is Part Of: Computers & operations research. Volume 109(2019)
• Page Start: 134
• Page End: 158
• Publication Date: 2019-09
• Subjects: Vehicle routing problem -- Drones -- Last-mile delivery -- Heuristics -- Metaheuristics -- Variable neighborhood search -- Valid inequalities -- Tabu search; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2019.04.021
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We study vehicle routing problem with drones and en route operations, formulate the problem as a MILP and introduce valid inequalities, show potentials and computational challenges of the problem, introduce an effective algorithm based on Variable Neighborhood Search, and report numerical results of our comprehensive computational experiments. Abstract: 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.