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

Attila Lischka; Filip Rydin; Jiaming Wu; Morteza Haghir Chehreghani; Balázs Kulcsár

cs.LGAug 29, 2024

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

Authors: Attila Lischka, Filip Rydin, Jiaming Wu, Morteza Haghir Chehreghani, Balázs Kulcsár

Organizations: Chalmers University of Technology · University of Gothenburg

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.

Figures & tables

Abbreviation	Definition
EVRP	Electric Vehicle Routing Problem
CVRP	Capacitated Vehicle Routing Problem
TSP	Traveling Salesman Problem
OP	Orienteering Problem
EV	Electric Vehicle
SoC	State of Charge

Table 1: List of Abbreviations

Figure 1: MDP transition diagram for the EVRP. At each step we select a feasible next node by masking out invalid options. The three possible node types (customer, charger, depot) result in distinct transitions for load

q

, SoC

\sigma

, and unvisited set

\mathcal{U}

. The MDP terminates when all customers are served and the vehicle has returned to the depot. Reward equals the negative energy cost of each traversed edge adjusted for possible battery limits.

Panel of Figure 2 — Figure 2: Example instances of the three auxiliary routing benchmarks in the Euclidean setting.

Panel of Figure 3 — Figure 3: Comparison of aggregation mechanisms.

Panel of Figure 4 — Figure 4: Overview of the two steps of GREAT (node-based)

Panel of Figure 5 — Figure 5: A GREAT layer with sublayers and normalizations

Panel of Figure 6 — Figure 6: The GREAT-based RL framework. The input edge feature matrix is encoded by GREAT into edge embeddings, transformed into node embeddings, and decoded into a solution tour.

Panel of Figure 7 — Figure 7: Heatmaps of cosine similarities and Euclidean distances between GREAT node encodings. Red borders indicate edges present in the optimal TSP solution. High cosine similarity and low Euclidean distance between node encodings correlate strongly with solution edges.

Model	Epoch	Val	Total	Params
GREAT NB	$\simeq$ 7.5 min	$\simeq$ 60 s	$\simeq$ 60 h	1.42M
GREAT NF	$\simeq$ 6.9 min	$\simeq$ 50 s	$\simeq$ 55 h	1.29M
Pointerformer	$\simeq$ 2.1 min	$\simeq$ 12 s	$\simeq$ 19 h	1.09M
MatNet	$\simeq$ 3.4 min	$\simeq$ 22 s	$\simeq$ 29 h	1.42M

Table 2: Training times and model sizes (CVRP, 100 nodes)

Panel of Figure 8 — Figure 8: EVRP instances with 100 customers, 5 chargers, and 1 depot across three cities. Node placement reflects population density.

		Customer Demand [1, 9]			Customer Demand [11, 19]			Customer Demand [21, 29]
Battery (kWh)	Method	kWh	opt. gap	time	kWh	opt. gap	time	kWh	opt. gap	time
15	Baseline (HGS)	26.66	–	8.6 min	65.32	–	10.4 min	110.53	–	6.2 min
	ALNS (1s)	31.92	20.10	11.7 s	72.79	11.61	7.8 s	112.43	1.82	8.2 s
	ALNS (5s)	27.57	3.61	35.6 s	69.33	6.16	35.5 s	106.84	-3.29	35.6 s
	ALNS (60s)	26.53	-0.39	7.0 min	63.65	-2.57	7.0 min	102.66	-7.06	7.0 min
	ALNS HGS-init (1s)	25.53	-4.13	8.8 min	63.78	-2.35	10.6 min	107.54	-2.70	6.3 min

Table 3: EVRP results for San Francisco (training city). Gaps are reported relative to the HGS baseline; negative values indicate better performance than HGS. Results over 100 test instances.

		Customer Demand [1, 9]			Customer Demand [11, 19]			Customer Demand [21, 29]
Battery (kWh)	Method	kWh	opt. gap	time	kWh	opt. gap	time	kWh	opt. gap	time
15	Baseline (HGS)	46.17	–	7.0 min	90.25	–	7.1 min	142.45	–	5.7 min
	ALNS (1s)	54.41	18.77	15.1 s	99.75	10.87	8.3 s	151.71	6.75	8.7 s
	ALNS (5s)	47.79	3.99	36.7 s	95.73	6.27	35.9 s	142.19	-0.08	35.7 s
	ALNS (60s)	44.38	-3.68	7.0 min	88.09	-2.25	7.0 min	137.44	-3.39	7.0 min
	ALNS HGS-init (1s)	43.90	-4.72	7.1 min	87.95	-2.48	7.3 min	139.88	-1.71	5.9 min

Table 4: EVRP results for Gothenburg (unseen city, no retraining). Gaps are reported relative to the HGS baseline; negative values indicate better performance than HGS. Results over 100 test instances.

		Customer Demand [1, 9]			Customer Demand [11, 19]			Customer Demand [21, 29]
Battery (kWh)	Method	kWh	opt. gap	time	kWh	opt. gap	time	kWh	opt. gap	time
15	Baseline (HGS)	37.73	–	8.0 min	79.72	–	7.5 min	127.24	–	5.8 min
	ALNS (1s)	44.84	19.33	14.1 s	87.40	10.19	8.4 s	134.71	6.16	8.9 s
	ALNS (5s)	39.84	6.00	36.4 s	84.15	5.74	35.7 s	126.24	-0.64	36.1 s
	ALNS (60s)	37.13	-1.58	7.0 min	77.59	-2.60	7.0 min	121.91	-4.04	7.0 min
	ALNS HGS-init (1s)	36.23	-3.86	8.1 min	77.78	-2.39	7.6 min	124.77	-1.87	5.9 min

Table 5: EVRP results for Vienna (unseen city, no retraining). Gaps are reported relative to the HGS baseline; negative values indicate better performance than HGS. Results over 100 test instances.

Method	OSM3	OSM5	OSM10	POP5
Battery 15 kWh, demand $\{1,\ldots,9\}$
Baseline (HGS)	28.43	27.61	27.19	27.47
ALNS (1 s)	33.67	33.26	32.63	32.91
ALNS (5 s)	29.40	29.17	28.73	29.02
ALNS (60 s)	26.58	26.47	26.37	26.43
ALNS HGS-init (1 s)	26.71	26.32	26.17	26.25

Table 6: Robustness of the EVRP results to the location and the number of charging stations, on San Francisco data. OSM

k

chooses

k

charging stations drawn from OpenStreetMap data. POP5 is the population-density sampling used in the main experiments. Average energy consumption in kWh over 100 instances.

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Instance size

n

Model

Mode

B

100

200

300

400

500

600

700

800

900

1000

Pointerformer

Train

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\times

\checkmark

\checkmark

\checkmark

\checkmark

\times

–

\checkmark

\checkmark

\times

–

Infer

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

\checkmark

Appendix

Table 7: Result of each test across models, batch sizes

B

and instance sizes

n

, during training and inference. All models use hidden dim. 128 and run on a single GPU (NVIDIA A40) with 48GB of memory.

Method	opt. gap (%)	time GPU	time CPU (seq.)
GREAT NB $\times 9$ , POMO 100	-1.13	5.2 s	3.4 min
GREAT NB $\times 9$ , POMO 100 + 2opt	-2.10	6.2 s	3.5 min
GREAT $\times 1$ , POMO 100	-0.50	1.0 s	25.0 s
GREAT $\times 1$ , POMO 100 + 2opt	-1.61	2.0 s	26.0 s
GREAT $\times 1$ , POMO 5	0.74	0.9 s	14.1 s
GREAT $\times 1$ , POMO 5 + 2opt	-0.59	2.0 s	15.2 s

Appendix

Table 8: Average performance of GREAT NB

\times 9

and GREAT NB

\times 1

, with and without 2-opt post-processing against HGS baseline, averaged over all 36 city/battery/demand configurations (100 instances per configuration). GPU solves batches of EVRP instances; CPU runs the same model sequentially, one instance at a time. CPU and GPU achieve the same gaps (same model, same resulting tours), while runtime depends on the hardware. Runtime is the average wall-clock time for solving the 100 instances of one configuration.

	Inference augmentation
Grouping	$\times 1$	$\times 9$
By battery capacity (kWh)
15	-0.49	-0.44
20	-0.26	-0.20
30	-0.13	-0.07
40	-0.06	-0.02

Appendix

Table 9: Effect of augmentation during training on EVRP performance. The entries show the mean per-instance relative difference (%) between the model trained without augmentation and the model trained with augmentation. Positive values would indicate that training-time augmentation helped. We consider 100 test instance per configuration and each block pools over the remaining two factors.

Model	Edge input	$d_{\mathrm{in}}$	$\times 1$	$\times 9$	$\times 33$
MatNet	$c_{ij}$ only	1	7.54	5.28	4.40
GREAT NB	$c_{ij}$ + 4 engineered	5	1.52	1.07	1.03
GREAT NB (ablation)	$c_{ij}$ only	1	1.78	1.19	1.12

Appendix

Table 10: Encoder ablation on TSP with TMAT distribution. Optimality gaps (%) are w.r.t. to Gurobi over 10,000 test instances. “

c_{ij}

only” denotes the raw edge costs, and

d_{\mathrm{in}}

is input dimension per edge.

		Customer Demand [1, 9]			Customer Demand [11, 19]			Customer Demand [21, 29]
City	Battery (kWh)	gap	95% CI	win	gap	95% CI	win	gap	95% CI	win
San Francisco	15	0.11	[-0.57, 0.80]	52	-5.64	[-6.34, -4.94]	96	-8.78	[-9.54, -8.02]	100
	20	1.31	[0.61, 2.02]	30	-4.61	[-5.32, -3.89]	90	-7.56	[-8.33, -6.78]	100
	30	1.96	[1.46, 2.45]	20	-3.33	[-3.94, -2.73]	86	-6.51	[-7.25, -5.77]	99
	40	3.63	[3.14, 4.11]	10	-2.68	[-3.24, -2.12]	80	-5.97	[-6.70, -5.23]	99
Gothenburg	15	-3.15	[-3.93, -2.37]	83	-2.89	[-3.40, -2.38]	86	-3.84	[-4.26, -3.42]	98

Appendix

Table 11: Comparison of GREAT NB

\times 9

+ 2opt against the HGS baseline. Table shows mean gap (negative means GREAT consumes less energy), 95% CI of the mean gap, and win the number of instances (out of 100) on which GREAT strictly beats HGS.

		Customer Demand [1, 9]				Customer Demand [21, 29]
Battery (kWh)	Method	depot	charger	mean SoC	min SoC	depot	charger	mean SoC	min SoC
15	Baseline (HGS)	10.52	2.49	0.50	0.01	54.53	12.76	0.45	0.01
	ALNS (60 s)	11.06	2.91	0.56	0.04	55.20	20.70	0.60	0.03
	GREAT NB $\times 9$ + 2opt	10.81	3.68	0.62	0.13	54.73	27.10	0.68	0.12
40	Baseline (HGS)	10.52	0.55	0.54	0.04	54.53	4.05	0.50	0.01
	ALNS (60 s)	11.12	0.87	0.57	0.06	55.10	11.34	0.67	0.06

Appendix

Table 12: Operational diagnostics for San Francisco. depot is the number of depot visits, charger the number of charging stops, and the two SoC columns are the mean and the minimum state of charge on arrival at a charger.

Figure 9: Validation performance over 400 training epochs. The y-axis shows the average amount of battery charge that was consumed on the 1,000 validation instances.

Panel of Figure 10 — Figure 10: Validation performance over the 400 training epochs, for TSP (top row), CVRP (middle row) and OP (bottom row) under the Euclidean (left), TMAT (middle) and XASY (right) distributions. TSP and CVRP show average tour length (lower is better) and OP show average collected prize (higher is better). Pointerformer is shown for the Euclidean distributions only, as it requires node coordinates.

		EUC100		TMAT100		XASY100
		opt. gap	time	opt. gap	time	opt. gap	time
TSP	Baseline - Gurobi	-	-	-	-	-	-
	LKH	0.0%	442s	0.0%	936s	0.01%	1006s
	Nearest Neighbor	24.86%	1.3s	36.04%	1.2s	185.26%	1.2s
	Nearest Insertion	21.8%	27s	31.8%	28s	301.65%	28s
	Farthest Insertion	7.66%	32s	23.92%	33s	310.98%	33s

Appendix

Table 13: Benchmarking GREAT against neural methods and traditional baselines on TSP and CVRP with 100 nodes. Optimality gaps relative to Gurobi (TSP) and HGS (CVRP). Bold = best, underline = second-best.

		EUC100		TMAT100		XASY100
		opt. gap	time	opt. gap	time	opt. gap	time
	Baseline - Greedy	-	7.9s	-	6.9s	-	340s
OP	EA4OP	-23.64%	5609s	NA	NA	NA	NA
	Pointerformer x1	-19.61%	12s	NA	NA	NA	NA
	Pointerformer x8	-21.31%	74s	NA	NA	NA	NA
	MatNet x1	-15.54%	21s	-24.13%	21s	54.98%	17s

Appendix

Table 14: Benchmarking GREAT against neural methods and traditional baselines on OP with 100 nodes. Optimality gaps relative to greedy heuristic. Bold = best, underline = second-best.

		EUC		TMAT		XASY
		opt. gap	time	opt. gap	time	opt. gap	time
TSP200	Baseline - LKH	-	23s	-	40s	-	36s
	Nearest Neighbor	25.5%	0.1s	36.71 %	0.1s	224.93 %	0.1s
	Nearest Insertion	23.39%	3.8s	37.95 %	3.9s	465.76%	4.1s
	Farthest Insertion	9.04%	2.9s	29.41 %	2.9s	481.4%	3.0s
	BQ-NCO bs16*	0.09%*	3min*	1.41%*	1min*	UNK	UNK

Appendix

Table 15: Generalization on 128 synthetic test instances of larger TSP sizes

	TMAT150		TMAT250		TMAT1000
	opt. gap	time	opt. gap	time	opt. gap	time
LKH	-	6s	-	15s	-	231s
BQ-NCO bs16	UNK	UNK	UNK	UNK	$8.26\%^{*}$	$7\text{m}^{*}$
GLOP	$19.28\%^{\text{\textdagger}}_{\diamond}$	$8.2s^{\text{\textdagger}}$	$29.67\%^{\text{\textdagger}}_{\diamond}$	$9.3s^{\text{\textdagger}}$	$44.27\%^{\text{\textdagger}}_{\diamond}$	$15s^{\text{\textdagger}}$
GREAT NF ZS x1	4.47%	3s	11.98%	6s	85.54%	54s
GREAT NF ZS x9	3.42%	19s	7.81%	17s	52.07%	455s

Appendix

Table 16: Generalization results on large TMAT instances (30 instances, from Ye et al. (2024) )

		Dist.	Mean	Q10	Q25	Median	Q75	Q90
TSPLIB $n=12$	Baseline - LKH	-	-	-	-	-	-	-
	GREAT NB x9	EUC	2.38%	0.66%	1.32%	2.16%	3.44%	3.65%
	GREAT NF x9	EUC	20.45%	0.72%	1.9%	3.56%	7.17%	57.38%
	GREAT NB x9	MIX	2.25%	1.45%	1.85%	2.28%	2.59%	2.82%
	GREAT NF x9	MIX	5.6%	1.61%	2.69%	4.64%	7.76%	10.68%
	MatNet x9	EUC	2.82%	1.08%	1.43%	3.08%	3.55%	3.97%

Appendix

Table 17: Generalization to real-world routing libraries (

\leq 100

nodes)

		Dist.	Mean	Q10	Q25	Median	Q75	Q90
TSPLIB $n=17$	Baseline - LKH	-	-	-	-	-	-	-
	GREAT NB x9	EUC	5.97%	1.68%	2.2%	3.94%	6.89%	10.76%
	GREAT NF x9	EUC	9.27%	1.55%	3.44%	7.07%	14.26%	22.3%
	GREAT NB x9	MIX	6.28%	2.42%	3.11%	4.35%	7.03%	8.56%
	GREAT NF x9	MIX	14.26%	3.81%	5.81%	13.87%	20.91%	23.64%
	Pointerformer x8	EUC	3.9%	0.93%	1.63%	2.18%	5.3%	6.88%

Appendix

Table 18: Generalization to real-world routing libraries (101–200 nodes)

Explore similar work

Mar 3, 2026

SynthCharge: An Electric Vehicle Routing Instance Generator with Feasibility Screening to Enable Learning-Based Optimization and Benchmarking

The electric vehicle routing problem with time windows (EVRPTW) extends the classical VRPTW by introducing battery capacity constraints and charging station decisions. Existing benchmark datasets are often static and lack verifiable feasibility, which restricts reproducible evaluation of learning-based routing models. We introduce SynthCharge, a parametric generator that produces diverse, feasibility-screened EVRPTW instances across varying spatiotemporal configurations and scalable customer counts. While SynthCharge can currently generate large-scale instances of up to 500 customers, we focus our experiments on sizes ranging from 5 to 100 customers. Unlike static benchmark suites, SynthCharge integrates instance geometry with adaptive energy capacity scaling and range-aware charging station placement. To guarantee structural validity, the generator systematically filters out unsolvable instances through a fast feasibility screening process. Ultimately, SynthCharge provides the dynamic benchmarking infrastructure needed to systematically evaluate the robustness of emerging neural routing and data-driven approaches.

Mertcan Daysalilar, Fuat Uyguroglu, Gabriel Nicolosi +1

Industrial and Systems Engineering, University of Miami, Coral Gables, FL, USA · Faculty of Engineering, Cyprus International University 99258 Nicosia, North Cyprus, via Mersin 10, Turkey · Engineering Management and Systems Engineering, Missouri University of Science and Technology, Rolla, MO, USA

Synthetic Benchmark Generation Vehicle Routing Electric Vehicle Charging

Ask PDF

May 6, 2026

Two-Stage Learned Decomposition for Scalable Routing on Multigraphs

Most neural methods for Vehicle Routing Problems (VRPs) are limited to Euclidean settings or simple graphs. In this work, we instead consider multigraphs, where parallel edges represent distinct travel options with varying trade-offs (e.g., distance vs. time). Multigraphs are highly relevant in practice, yet few neural methods are designed for them, and those that do exist face major scalability issues. We address these scalability issues with Node-Edge Policy Factorization (NEPF), which splits the routing policy into a node permutation stage and an edge selection stage. To enable the decomposition, we introduce a pre-encoding edge aggregation scheme and a non-autoregressive architecture for the edge stage, as well as a hierarchical reinforcement learning method to train the stages jointly. Our experiments across six VRP variants demonstrate that NEPF trains and runs up to orders of magnitude faster than prior neural multigraph methods and scales to considerably larger instances, while matching or improving on their solution quality.

Filip Rydin, Morteza Haghir Chehreghani, Balázs Kulcsár

Chalmers University of Technology · University of Gothenburg

Vehicle Routing Neural Combinatorial Optimization

Ask PDF

Jun 1, 2026

Graph Edit Distance Formulation for the Vehicle Routing Problem: Theory and Analysis

We show that the Vehicle Routing Problem (VRP) can be reformulated as a Graph Edit Distance (GED) maximization problem. Under a simple edge-deletion cost model, minimizing total route cost is equivalent to maximizing the total weight of edges deleted from the complete instance graph. This formulation models VRP at the edge level, where solutions are defined by selected edges rather than route sequences, enabling structural analyses that are difficult in classical formulations: per-edge attribution of solution quality, decomposition of the optimality gap, characterization of solution sparsity, and identification of edges that are hard to reach by greedy construction. Theoretically, we establish a merge-decomposition theorem showing that Clarke-Wright savings equal per-merge GED increments, and an approximation-transfer theorem that turns GED approximation ratios into VRP cost bounds. Using this reformulation, we analyze 90 CVRP benchmark instances with known optimal solutions. We find that optimal routing graphs use only 5.5% of available edges, that approximately 3.0% of optimal edges are consistently not found by Clarke-Wright heuristics under repeated restarts, and that the cost gap decomposes into missed optimal edges and substituted non-optimal edges of comparable total weight. The edge-additive objective provides a natural per-edge supervision signal for future graph neural network approaches to edge prediction, suggesting a potential connection to graph neural network approaches that we leave for follow-up work.

Adel Dabah

Jülich Supercomputing Centre Forschungszentrum Jülich Jülich, Germany

Vehicle Routing

Ask PDF