AlphaRouter: Bridging the Gap Between Reinforcement Learning and Optimization for Vehicle Routing with Monte Carlo Tree Searches
Entropy · 27.02.2025 · 27 (3) · 251
DOI: 10.3390/e27030251 ↗Kurz gefasst
Fachartikel in der Zeitschrift Entropy, online erschienen am 27.02.2025. Verfasst von Won-Jun Kim und 3 weiteren Autor:innen. Beteiligte Einrichtung: Hyundai Glovis, Seoul 685-700, Republic of Korea. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 44 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: the Ministry of Education of the Republic of Korea, Ministry of Education of the Republic of Korea and the National Research Foundation of Korea.
Abstract (Originalsprache)
Deep reinforcement learning (DRL) as a routing problem solver has shown promising results in recent studies. However, an inherent gap exists between computationally driven DRL and optimization-based heuristics. While a DRL algorithm for a certain problem is able to solve several similar problem instances, traditional optimization algorithms focus on optimizing solutions to one specific problem instance. In this paper, we propose an approach, AlphaRouter, which solves routing problems while bridging the gap between reinforcement learning and optimization. Fitting to routing problems, our approach first proposes attention-enabled policy and value networks consisting of a policy network that produces a probability distribution over all possible nodes and a value network that produces the expected distance from any given state. We modify a Monte Carlo tree search (MCTS) for the routing problems, selectively combining it with the routing problems. Our experiments demonstrate that the combined approach is promising and yields better solutions compared to original reinforcement learning (RL) approaches without MCTS, with good performance comparable to classical heuristics.
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- Hyundai Glovis, Seoul 685-700, Republic of Korea.
- Department of Industrial Engineering, College of Engineering, Hanyang University, Seoul 133-791, Republic of Korea.
ORCID-Profile: Junho Jeong, Taeyeong Kim, Kichun Lee
Förderung
- the Ministry of Education of the Republic of Korea
- Ministry of Education of the Republic of Korea and the National Research Foundation of Korea
Zitieren
APA
Kim, W. J., Jeong, J., Kim, T., & Lee, K. (2025). AlphaRouter: Bridging the Gap Between Reinforcement Learning and Optimization for Vehicle Routing with Monte Carlo Tree Searches. Entropy, 27(3), 251. https://doi.org/10.3390/e27030251
Vancouver
Kim WJ, Jeong J, Kim T, Lee K. AlphaRouter: Bridging the Gap Between Reinforcement Learning and Optimization for Vehicle Routing with Monte Carlo Tree Searches. Entropy. 2025;27(3):251. doi:10.3390/e27030251
BibTeX
@article{Kim2025,
author = {Kim, Won-Jun and Jeong, Junho and Kim, Taeyeong and Lee, Kichun},
title = {AlphaRouter: Bridging the Gap Between Reinforcement Learning and Optimization for Vehicle Routing with Monte Carlo Tree Searches},
journal = {Entropy},
year = {2025},
volume = {27},
number = {3},
pages = {251},
doi = {10.3390/e27030251}
}
EUVIMED