Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 109, Issue -, Pages 134-158Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2019.04.021
Keywords
Vehicle routing problem; Drones; Last-mile delivery; Heuristics; Metaheuristics; Variable neighborhood search; Valid inequalities; Tabu search
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available