Graph Transformer with Reinforcement Learning for Vehicle Routing Problem
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.
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}
}
EUVIMED