EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

AlphaRouter: Bridging the Gap Between Reinforcement Learning and Optimization for Vehicle Routing with Monte Carlo Tree Searches

Won-Jun Kim, Junho Jeong iD, Taeyeong Kim iD, Kichun Lee iD

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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

MCTSdeep reinforcement learningreinforcement learningvehicle routing problem

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}
}
Kostenlos starten →