EUVIMEDEUVIMED entdecken
Crossref

An exact algorithm for the two-echelon vehicle routing problem with drones

Hang Zhou, Hu Qin, Chun Cheng, Louis-Martin Rousseau

Transportation Research Part B: Methodological · 2023-02 · 168 · 124-150

DOI: 10.1016/j.trb.2023.01.002 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Transportation Research Part B: Methodological, 2023-02. Verfasst von Hang Zhou und 3 weiteren Autor:innen. Die Arbeit wurde bisher 159-mal zitiert (Crossref) und nennt 57 Literaturangaben. Gefördert von: National Natural Science Foundation of China, National Key Research and Development Program of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • National Natural Science Foundation of China
  • National Key Research and Development Program of China

Zitieren

APA

Zhou, H., Qin, H., Cheng, C., & Rousseau, L. (2023). An exact algorithm for the two-echelon vehicle routing problem with drones. Transportation Research Part B: Methodological, 168, 124-150. https://doi.org/10.1016/j.trb.2023.01.002

Vancouver

Zhou H, Qin H, Cheng C, Rousseau L. An exact algorithm for the two-echelon vehicle routing problem with drones. Transportation Research Part B: Methodological. 2023;168:124-150. doi:10.1016/j.trb.2023.01.002

BibTeX
@article{Zhou2023,
  author = {Zhou, Hang and Qin, Hu and Cheng, Chun and Rousseau, Louis-Martin},
  title = {An exact algorithm for the two-echelon vehicle routing problem with drones},
  journal = {Transportation Research Part B: Methodological},
  year = {2023},
  volume = {168},
  pages = {124--150},
  doi = {10.1016/j.trb.2023.01.002}
}
Kostenlos starten →