Reinforcement Learning for Solving Multiple Vehicle Routing Problem with Time Window
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.
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}
}
EUVIMED