An exact algorithm for the two-echelon vehicle routing problem with drones. (February 2023)

• Record Type: Journal Article
• Authors: Zhou, Hang; Qin, Hu; Cheng, Chun; Rousseau, Louis-Martin
• Is Part Of: Transportation research. Volume 168(2023)
• Page Start: 124
• Page End: 150
• Publication Date: 2023-02
• Subjects: Truck–drone system -- Two-echelon vehicle routing with drones -- Branch-and-price; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2023.01.002
• Languages: English
• ISSNs: 0191-2615

Abstract

Abstract: This paper studies a new variant of the vehicle routing problem with drones, i.e., the two-echelon vehicle routing problem with drones, where multiple vehicles and drones work collaboratively to serve customers. Drones can perform multiple back-and-forth trips when their paired vehicle stops at a customer node, forming a two-echelon network. Several practical constraints such as customers' delivery deadlines and drones' energy capacity are considered. Different from existing studies, we treat the number of drones taken by each vehicle as a decision variable instead of a given parameter, which provides more flexibility for planning vehicle and drone routes. We first formulate this problem as a mixed-integer linear programming model, which is solvable by off-the-shelf commercial solvers. To tackle instances more efficiently, we next construct a set-partitioning model. To solve it, an exact branch-and-price algorithm is proposed, where a bidirectional labeling algorithm is used to solve the pricing problem. To speed up the algorithm, a tabu search algorithm is first applied before the exact labeling algorithm for finding desired columns in each iteration of the column generation process. Extensive numerical tests show that our algorithm can solve most instances within 25 customers to optimality in a short time frame and some instances of 35 customers to optimality within a three-hour time limit. Results also demonstrate that the allocation decisions of drones can help save the duration of all routes by 3.44% on average for 25-customer instances, compared to the case of fixing the number of paired drones on each vehicle. In addition, sensitivity analyses show that multiple strategies, e.g., adopting batteries of a higher energy density and developing faster drones, can be applied to further improve the delivery efficiency of a truck–drone system. Highlights: A two-echelon vehicle routing problem with drones is studied. The allocation decisions of drones to vehicles are considered. An MILP model and a set-partitioning model are provided. A branch-and-price algorithm is developed. Results show the effectiveness of the algorithm and provide managerial insights.