EUVIMEDEUVIMED entdecken
Crossref

Graph Transformer with Reinforcement Learning for Vehicle Routing Problem

Getu Fellek, Ahmed Farid, Goytom Gebreyesus, Shigeru Fujimura, Osamu Yoshie

IEEJ Transactions on Electrical and Electronic Engineering · 2023-05 · 18 (5) · 701-713

DOI: 10.1002/tee.23771 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEJ Transactions on Electrical and Electronic Engineering, online erschienen am 13.02.2023. Verfasst von Getu Fellek und 4 weiteren Autor:innen. Die Arbeit wurde bisher 25-mal zitiert (Crossref) und nennt 44 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Vehicle routing problem (VRP) is one of the classic combinatorial optimization problems where an optimal tour to visit customers is required with a minimum total cost in the presence of some constraints. Recently, VRP is being solved with the use of deep reinforcement learning (DRL), with node sets considered (represented) as a graph structure. Existing Transformer based DRL solutions for VRP rely only on node information ignoring the role of information on the edges between nodes in the graph structure. In this paper, we proposed an attention‐based end‐to‐end DRL model to solve VRP which embeds edge information between nodes for rich graph representation learning. We used Transformer based encoder‐decoder framework with an edge information embedded multi‐head attention (EEMHA) layer in the encoder. The EEMHA‐based encoder learns underlying structure of the graph and generates an expressive graph topology representation by merging node and edge information. We trained our model using proximal policy optimization (PPO) with some code‐level optimization techniques. We conducted an experiment on randomly generated instances and on a real‐world data generated from road networks to verify the performance of our proposed model. The result from all experiments show that our model performs better than the existing DRL methods and most of the conventional heuristics with good generalizability from random instance training to real‐world instance testing of different problem size. © 2023 Institute of Electrical Engineers of Japan. Published by Wiley Periodicals LLC.

Zitieren

APA

Fellek, G., Farid, A., Gebreyesus, G., Fujimura, S., & Yoshie, O. (2023). Graph Transformer with Reinforcement Learning for Vehicle Routing Problem. IEEJ Transactions on Electrical and Electronic Engineering, 18(5), 701-713. https://doi.org/10.1002/tee.23771

Vancouver

Fellek G, Farid A, Gebreyesus G, Fujimura S, Yoshie O. Graph Transformer with Reinforcement Learning for Vehicle Routing Problem. IEEJ Transactions on Electrical and Electronic Engineering. 2023;18(5):701-713. doi:10.1002/tee.23771

BibTeX
@article{Fellek2023,
  author = {Fellek, Getu and Farid, Ahmed and Gebreyesus, Goytom and Fujimura, Shigeru and Yoshie, Osamu},
  title = {Graph Transformer with Reinforcement Learning for Vehicle Routing Problem},
  journal = {IEEJ Transactions on Electrical and Electronic Engineering},
  year = {2023},
  volume = {18},
  number = {5},
  pages = {701--713},
  doi = {10.1002/tee.23771}
}
Kostenlos starten →