A hierarchical solution evaluation method and a hybrid algorithm for the vehicle routing problem with drones and multiple visits. (August 2022)

• Record Type: Journal Article
• Authors: Gu, Ruixue; Poon, Mark; Luo, Zhihao; Liu, Yang; Liu, Zhong
• Is Part Of: Transportation research. Volume 141(2022)
• Publication Date: 2022-08
• Subjects: Drone delivery -- Last-mile delivery -- Multi-visits -- Integer programming -- Heuristics -- Vehicle routing problems; Transportation -- Periodicals; Transportation -- Technological innovations -- Periodicals; 388.011
• DOI: 10.1016/j.trc.2022.103733
• Languages: English
• ISSNs: 0968-090X

Abstract

Abstract: Vehicle routing problem with drones (VRPD) has recently gained much traction among the research community due to its potential to improve efficiency and reduce costs for delivery. However, limited research investigates feasibility evaluation methods for the VRPD due to complex synchronization requirements between truck routes and drone trips. This paper proposes an efficient hierarchical solution evaluation method for a general VRPD problem with multiple visits (VRPD-MV), in which each vehicle is equipped with a single drone capable of serving multiple customers per trip. The endurance model is based on both the payload and flight time of the drone. The solution evaluation method decomposes a combined truck–drone route into its constituent truck segment and drone segment, which are collectively recognized as a route segment. Thereafter, efficient processing methods are developed for each segment type. We hybridize an iterative local search heuristic with a variable neighborhood descent procedure (ILS-VND) to solve the VRPD-MV. The algorithm obtains promising computational results in reasonable times for the VRPD-MV. Specifically, the proposed evaluation method is shown to accelerate the feasibility evaluation of a solution and reduce the time complexity to O ( 1 ) independent of the length of the route. The computational results also show a positive impact of powerful drones on reducing solution costs. Lastly, the ILS-VND outperforms a state-of-the-art algorithm on the multi-visit traveling salesman problem with multi-drones in terms of both solution qualities and computational times required. Highlights: A vehicle routing problem with drones and multiple visits per drone trip. An MIP model solvable by commercial solvers. A hierarchical solution evaluation method with constant run time. A hybrid iterated local search and variable neighborhood search algorithm to solve this problem. New benchmark test instances and comprehensive experiments.