An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. (May 2019)

• Record Type: Journal Article
• Authors: Sacramento, David; Pisinger, David; Ropke, Stefan
• Is Part Of: Transportation research. Volume 102(2019)
• Page Start: 289
• Page End: 315
• Publication Date: 2019-05
• Subjects: Delivery operations -- Vehicle Routing Problems with Drones -- UAVs -- ALNS; Transportation -- Periodicals; Transportation -- Technological innovations -- Periodicals; 388.011
• DOI: 10.1016/j.trc.2019.02.018
• Languages: English
• ISSNs: 0968-090X

Abstract

Highlights: New optimization problem for delivery activities using drones in collaboration with trucks. Fleet of delivery trucks, each of them equipped with a single drone. Focus on cost-minimization objective function with maximum duration time for all routes. Noteworthy cost-savings with respect to the case of only using trucks. Efficient metaheuristic is proposed to solve this problem. Abstract: Unmanned Aerial Vehicles, commonly known as drones, have attained considerable interest in recent years due to the potential of revolutionizing transport and logistics. Amazon were among the first to introduce the idea of using drones to deliver goods, followed by several other distribution companies working on similar services. The Traveling Salesman Problem, frequently used for planning last-mile delivery operations, can easily be modified to incorporate drones, resulting in a routing problem involving both the truck and aircraft. Introduced byMurray and Chu (2015), the Flying Sidekick Traveling Salesman Problem considers a drone and truck collaborating. The drone can be launched and recovered at certain visits on the truck route, making it possible for both vehicles to deliver goods to customers in parallel. This generalization considerably decreases the operational cost of the routes, by reducing the total fuel consumption for the truck, as customers on the routes can be serviced by drones without covering additional miles for the trucks, and hence increase productivity. In this paper a mathematical model is formulated, defining a problem similar to the Flying Sidekick Traveling Salesman Problem, but for the capacitated multiple-truck case with time limit constraints and minimizing cost as objective function. The corresponding problem is denoted the Vehicle Routing Problem with Drones . Due to the difficulty of solving large instances to optimality, an Adaptive Large Neighborhood Search metaheuristic is proposed. Finally, extensive computational experiments are carried out. The tests investigate, among other things, how beneficial the inclusion of the drone-delivery option is compared to delivering all items using exclusively trucks. Moreover, a detailed sensitivity analysis is performed on several drone-parameters of interest.