EUVIMEDEUVIMED entdecken
Crossref

Reinforcement Learning for Solving Multiple Vehicle Routing Problem with Time Window

Zefang Zong, Xia Tong, Meng Zheng, Yong Li

ACM Transactions on Intelligent Systems and Technology · 30.04.2024 · 15 (2) · 1-19

DOI: 10.1145/3625232 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Intelligent Systems and Technology, online erschienen am 28.03.2024. Verfasst von Zefang Zong und 3 weiteren Autor:innen. Die Arbeit wurde bisher 52-mal zitiert (Crossref) und nennt 39 Literaturangaben. Gefördert von: The National Key Research and Development Program of China, National Nature Science Foundation of China, Beijing Natural Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Vehicle routing problem with time window (VRPTW) is of great importance for a wide spectrum of services and real-life applications, such as online take-out and car-hailing platforms. A promising method should generate high-qualified solutions within limited inference time, and there are three major challenges: (a) directly optimizing the goal with several practical constraints; (b) efficiently handling individual time-window limits; and (c) modeling the cooperation among the vehicle fleet. In this article, we present an end-to-end reinforcement learning framework to solve VRPTW. First, we propose an agent model that encodes constraints into features as the input and conducts harsh policy on the output when generating deterministic results. Second, we design a time penalty augmented reward to model the time-window limits during gradient propagation. Third, we design a task handler to enable the cooperation among different vehicles. We perform extensive experiments on two real-world datasets and one public benchmark dataset. Results demonstrate that our solution improves the performance by up to 11.7% compared to other RL baselines and could generate solutions for instances within seconds, while existing heuristic baselines take for minutes as well as maintain the quality of solutions. Moreover, our solution is thoroughly analyzed with meaningful implications due to the real-time response ability.

Förderung

  • The National Key Research and Development Program of China
  • National Nature Science Foundation of China
  • Beijing Natural Science Foundation
  • Beijing National Research Center for Information Science and Technology
  • Tsinghua University - Tencent Joint Laboratory for Internet Innovation Technology

Zitieren

APA

Zong, Z., Tong, X., Zheng, M., & Li, Y. (2024). Reinforcement Learning for Solving Multiple Vehicle Routing Problem with Time Window. ACM Transactions on Intelligent Systems and Technology, 15(2), 1-19. https://doi.org/10.1145/3625232

Vancouver

Zong Z, Tong X, Zheng M, Li Y. Reinforcement Learning for Solving Multiple Vehicle Routing Problem with Time Window. ACM Transactions on Intelligent Systems and Technology. 2024;15(2):1-19. doi:10.1145/3625232

BibTeX
@article{Zong2024,
  author = {Zong, Zefang and Tong, Xia and Zheng, Meng and Li, Yong},
  title = {Reinforcement Learning for Solving Multiple Vehicle Routing Problem with Time Window},
  journal = {ACM Transactions on Intelligent Systems and Technology},
  year = {2024},
  volume = {15},
  number = {2},
  pages = {1--19},
  doi = {10.1145/3625232}
}
Kostenlos starten →