GREAT: A Graph Edge Attention Network for the Electric Vehicle Routing Problem with Asymmetric Costs

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.

Machine Learning (cs.LG); Artificial Intelligence (cs.AI)

arXiv:2408.16717 [cs.LG]

(or arXiv:2408.16717v4 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2408.16717 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.