arXiv：cs.AI· Attila Lischka, Filip Rydin, Jiaming Wu, Morteza Haghir Chehreghani, Bal\'azs Kulcs\'ar·· 5 小时前
GREAT：面向非对称成本电动汽车路径问题的图边注意力网络
GREAT: A Graph Edge Attention Network for the Electric Vehicle Routing Problem with Asymmetric Costs
AI 导读
研究提出图边注意力网络（GREAT），完全在边空间而非节点坐标上运算，天然适配电动汽车路径问题（EVRP）中由路网拓扑导致的非对称能耗成本。基于旧金山真实能耗数据训练后，GREAT 在 15-40 kWh 电池容量等测试设置下相比 HGS 启发式最高降低 8.78% 能耗，运行时缩短 60 倍。
正文
Abstract:Due to the ongoing electrification of transportation systems, energy-based routing problems such as the Electric Vehicle Routing Problem (EVRP) are becoming increasingly important. Unlike Euclidean routing problems, the EVRP involves asymmetric energy costs caused by road topology. Existing learning-based routing approaches are based on graph neural networks (GNNs) or transformer architectures operating on Euclidean node coordinates, making them poorly suited for asymmetric, non-Euclidean edge-based metrics such as energy consumption. To address this, we propose the Graph Edge Attention Network (GREAT), a novel GNN-related architecture that operates purely in edge space rather than on node coordinates, making it naturally compatible with asymmetric routing costs. Integrated into an end-to-end reinforcement learning framework, GREAT jointly optimizes routing and charging decisions for the EVRP. We train the model using real-world energy consumption data from San Francisco, derived from physical road networks enriched with topological features, and evaluate generalization on datasets from San Francisco, Vienna, and Gothenburg. Across diverse battery sizes (15-40 kWh) and customer demand distributions, GREAT outperforms a strong HGS-based EVRP heuristic in most tested settings, achieving energy reductions of up to 8.78% while reducing runtime by a factor of 60. Moreover, we benchmark against a custom adaptive large neighborhood search (ALNS) that jointly optimizes routing and charging. GREAT achieves competitive performance at a faster runtime, and we show that the ALNS can profit from a warm start with the GREAT solution. We further evaluate GREAT on standard (asymmetric) routing problems, including Traveling Salesman Problem, Capacitated Vehicle Routing Problem, and Orienteering Problem, where it achieves state-of-the-art performance among neural methods for non-Euclidean settings.
| Comments: | 40 pages, 10 figures |
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2408.16717 [cs.LG] |
| (or arXiv:2408.16717v4 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2408.16717 arXiv-issued DOI via DataCite |
Submission history
From: Attila Lischka [view email]
[v1]
Thu, 29 Aug 2024 17:07:43 UTC (1,864 KB)
[v2]
Thu, 26 Jun 2025 13:54:56 UTC (1,244 KB)
[v3]
Mon, 29 Sep 2025 15:30:46 UTC (1,797 KB)
[v4]
Sat, 10 Oct 2026 09:24:45 UTC (8,256 KB)
来源：arXiv：cs.AI · arxiv.org