The multivisit drone routing problem with edge launches: An iterative approach with discrete and continuous improvements

In recent years, the usage of drones in last-mile logistics has stirred great interest in the operations research community. Many papers have considered schemes of hybrid truck-and-drone delivery. In this paper, we focus on the Multivisit Drone Routing Problem with Edge Launches (MVDRP-EL) which assumes: a heterogenous set of packages, a drone capable of carrying multiple packages at a time and that can be launched and retrieved along an edge, a flexible launch/retrieval site set, and a user-defined energy depletion function. We believe this paper is the first to exploit edge launch ability through a global continuous approach. In this context, we propose an original formulation based on the Covering Salesman Problem to compute a valid lower bound for the problem and an iterative solution method to determine a MVDRP-EL solution with quality launch/retrieval sites along the road network edges. Each iteration of the solution method consists of two phases. In the first phase, the road network edges are discretized to obtain launch/retrieval sites, and a first solution is determined. In the second phase, the truck route is set and we reduce the completion time by carefully synchronizing truck and drone routes by solving an original Mixed Integer Second Order Cone Program. The lower bound formulation and the proposed method have been tested on several instances and results indicate the effectiveness of the proposed method and the potential value of launching along an edge, respectively.