GREAT-ESDD: Graph Edge Attention Network for Effectively Steered Delivery Decisions

Attila Lischka; Ze Zhou; Xuegang; Ban; Balázs Kulcsár

cs.AIOct 10, 2026

GREAT-ESDD: Graph Edge Attention Network for Effectively Steered Delivery Decisions

Authors: Attila Lischka, Ze Zhou, Xuegang, Ban, Balázs Kulcsár

Organizations: Jeff · Civil and Environmental Engineering, University of Washington, Seattle, USA · Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden

Abstract

Online, same-day delivery requires operators to constantly update their routes, and the routing cost for deliveries increases with the number of customers. Out-of-home (OOH) delivery options can help companies handle increasing customer numbers while keeping delivery costs low. We develop a dynamic pricing-and-routing framework for this online ordering scenario with home and OOH delivery options. First, we develop a neural solver for the capacitated vehicle routing problem (CVRP) based on the Graph-Edge-Attention-Network (GREAT). We train it to solve CVRP with varying instance sizes and starting conditions, allowing it to reoptimize partially executed routes under changing conditions. It is fast while achieving solution quality competitive with traditional baselines. Our solver processes several CVRP instances in parallel in batches and we use it to solve the candidate routing problems that arise from an incoming customer's choice of home or OOH delivery. This provides an estimate of the delivery cost increase per option, which we use to set dynamic prices. Further, it directly provides the updated route once the customer decides. We trade off delivery fees against routing costs and steer customers toward OOH delivery when home delivery would be costly. However, effective steering requires us to know the customer preferences. To learn those online, we use Thompson sampling with a Laplace-approximated posterior. We call the resulting framework GREAT-ESDD (GREAT for Effectively Steered Delivery Decisions). Compared to a traditional routing solver, it increases profit by around 11% under a similar pricing decision time budget. Moreover, we show that we can estimate customer preferences successfully, outperforming a static pricing strategy after only 5 days of simulated operations.

Figures & tables

Panel of Figure 1 — Figure 1: The pricing-and-routing loop of the GREAT-ESDD framework over one operating day. The vehicle follows a planned route. Any time a customer orders, the current routing state is used to compute a routing cost estimate of the delivery options and a price menu is chosen to maximize expected profit. The customer’s choice determines the updated route.

Figure 2: Given a current solution, our framework can react to stochastic changes in the environment. Case one (upper branch) occurs when a new customer dynamically enters the system. Case two (lower branch) occurs when a customer has a lower demand than expected. In both cases we construct a new graph representing the current state. It encodes all unserved customers, the depot, the current vehicle location and the current vehicle load. Our neural model processes this graph encoding and outputs a new solution.

Figure 3: Development of the customer arrival, pricing, customer selection and routing over one day with known customer parameters, shown after (a) 30, (b) 50, (c) 70 and (d) 100 customer requests. The black triangle shows the depot and the colored stars show the OOH locations in our considered Seattle setting. Customers are represented by dots that are either black (home delivery) or colored according to their OOH location; gray dots are customers who opted-out. We show the already executed tour along with the currently still remaining tour.

Instance Size	Generation Time
10	3s
20	3s
30	6s
40	11s
50	19s
60	31s

Table 1: Instance generation times by size

KPI	Definition
Profit per day	$\sum_{i}p_{i,j_{i}}-\theta C$ , see ( 6 )
Fees per day	$\sum_{i}p_{i,j_{i}}$
Routing cost per day	$\theta C$
OOH share	share of customers with $j_{i}\in\{OOH_{1},\dots,OOH_{K}\}$
Opt-out rate	share of customers with $j_{i}=\emptyset$
Price paid (mean, median)	$p_{i,j_{i}}$ for home, OOH and overall, customers with $j_{i}\neq\emptyset$

Table 2: Key performance indicators of the pricing experiments, averaged over the simulated days.

Figure 4: Pareto sets trading off performance (gap w.r.t. PyVRP without time limit) vs. runtime for different CVRP instance sizes.

Figure 5: Performance of different CVRP solvers w.r.t. PyVRP without time limit. Left: gap range 0–15 %; right: unconstrained range.

Figure 6: Runtime of different CVRP solvers (PyVRP with set time limit is omitted) to solve a batch of 5 CVRP instances in parallel. Left: linear scale, 0–2 s; right: logarithmic scale, unconstrained range.

			Mean per day ($)
Backend	Device / limit	$\omega$	Profit	$\Delta$ vs. PyVRP 0.5 s (95% CI)	$\Delta$ vs. flat (95% CI)	Fees	Routing cost
GREAT (non-aug)	GPU	0.40	636.18	+17.37 $\pm$ 10.77	-2.20 $\pm$ 8.92	1008.06	371.88
GREAT (aug)	GPU	0.30	652.35	+33.54 $\pm$ 10.01	+13.97 $\pm$ 9.51	1027.94	375.59
GREAT (non-aug)	CPU	0.40	637.08	+18.26 $\pm$ 10.66	-1.31 $\pm$ 8.73	1009.66	372.58
GREAT (aug)	CPU	0.30	651.95	+33.14 $\pm$ 9.79	+13.57 $\pm$ 8.97	1028.66	376.71
PyVRP	0.01 s	0.10	392.07	-226.75 $\pm$ 22.89	-246.32 $\pm$ 22.14	937.16	545.09

Table 3: Economic outcome of the pricing-and-routing operation, averaged over 25 simulated days. Each routing backend uses its best rectifier

\omega

. Profit is fees minus routing cost. Best value per column in bold.

\Delta

is the paired difference in mean profit against a baseline.

Backend	Device / limit	OOH share	Opt-out rate
GREAT (non-aug)	GPU	33.3%	24.54%
GREAT (aug)	GPU	29.2%	24.18%
GREAT (non-aug)	CPU	33.4%	24.44%
GREAT (aug)	CPU	29.3%	24.12%
PyVRP	0.01 s	36.8%	21.24%
PyVRP	0.1 s	34.8%	24.12%

Table 4: Service outcome from the customers’ perspective, averaged over 25 simulated days. Each routing backend uses its best rectifier

\omega

		Price paid ($)						Decision time (s)
		Home		OOH		Overall
Backend	Device / limit	Mean	Med.	Mean	Med.	Mean	Med.	Mean	Med.	p90	p99
GREAT (non-aug)	GPU	7.14	7.00	5.75	6.00	6.68	7.00	0.337	0.333	0.424	0.472
GREAT (aug)	GPU	7.07	7.00	6.07	6.00	6.78	7.00	0.472	0.443	0.676	0.797
GREAT (non-aug)	CPU	7.15	7.00	5.75	6.00	6.68	7.00	0.417	0.381	0.689	0.844
GREAT (aug)	CPU	7.07	7.00	6.07	6.00	6.78	7.00	1.604	1.336	3.395	4.967

Table 5: Realized prices paid by customers and the distribution of the price-decision time (marginal routing cost computation plus price selection), over 25 simulated days. Each routing backend uses its best rectifier

\omega

Figure 7: Marginal routing cost ablation, showing mean time to compute the routing cost increase for a pricing decision vs. the mean profit per operating day over 25 days

Panel of Figure 8 — Figure 8: Parameter estimation, price and regret developments of the deterministic learning to price setting.

Panel of Figure 9 — Figure 9: Parameter estimation, price and regret developments of the stochastic learning to price setting.

Panel of Figure 10 — Figure 10: Cumulative revenue, routing cost and profit over 100 days of operation, using the bandit-based pricing and the flat $7 pricing strategies in the deterministic and stochastic setting.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 11: Average profit achieved by different solvers for different rectifiers

\omega

Figure 12: Profit development of flat pricing options

Operations Research

See all 36 papers

A Deep Reinforcement Learning Algorithm for the Vehicle Routing Problem with Stochastic Demands and Outsourcing
Jul 18, 2026Mohsen Dastpak, Fausto Errico, Ola JabaliVehicle Routing RL for Combinatorial Optimization
aDepartment de génie de la construction, École de technologie supérieure, , Montréal, H3C 1K3, QC, Canada · bGERAD, , Montréal, H3T 1J4, QC, Canada · cCIRRELT, , Montréal, H3C 3J7, QC, Canada +1
Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints
Aug 14, 2026Andrew Soroka, German Mikhelson, Alexander Mescheryakov +1Vehicle Routing Metaheuristic Optimization
Moscow State University, Faculty of Computational Mathematics and Cybernetics, Moscow · Space Research Institute of RAS, Moscow
Neural Cluster First, Route Second: Capacitated Vehicle Routing via Differentiable Optimal Transport
May 10, 2026Samuel J. K. Chin, Maximilian SchifferVehicle Routing Neural Combinatorial Optimization
MIT · TUM

Jul 18, 2026J/K move · Enter open · S save

A Deep Reinforcement Learning Algorithm for the Vehicle Routing Problem with Stochastic Demands and Outsourcing

Mohsen Dastpak, Fausto Errico, Ola Jabali

aDepartment de génie de la construction, École de technologie supérieure, , Montréal, H3C 1K3, QC, Canada · bGERAD, , Montréal, H3T 1J4, QC, Canada · cCIRRELT, , Montréal, H3C 3J7, QC, Canada+1

Vehicle Routing RL for Combinatorial Optimization

Open paper AskPDF arXiv

We introduce the vehicle routing problem with stochastic demands and outsourcing options (VRP-SDO), in which a logistics service provider partitions customer requests into customers outsourced to a common carrier and customers committed to its fixed fleet. The latter induces a vehicle routing problem with stochastic demands (VRP-SD), solved dynamically. Demands are revealed upon visit; residual demand may be served by other vehicles or after restocking at the depot. Work beyond the regular shift incurs overtime costs, and the unit outsourcing cost decreases with the expected outsourced demand. The objective is to minimize expected travel, overtime, and outsourcing costs. We propose an iterative two-level methodology whose first level partitions customers into committed and outsourced subsets, while the second level estimates the expected VRP-SD routing cost. To avoid solving this problem from scratch at every iteration, we learn an offline routing policy that estimates costs almost instantly for any committed subset. An iterated local search establishes the first-level partitions. We formulate the second level as a Markov decision process and solve it with a deep Q-network whose state is represented by a graph attention network aggregating customer and vehicle information by relevance to the acting vehicle. Trained offline on instances with variable customer cardinality and locations, the policy applies to any daily customer realization; online fine-tuning improves the cost approximation. Experiments show that our policy reduces routing costs by 19.6% relative to a state-of-the-art method and by at least 29.6% over classical heuristics. Our overall algorithm saves 13.7% on average over the version without the attention-based representation and generates high-quality decisions within minutes, whereas benchmarks without an offline-trained estimator require over an hour.

Abstract

Operations Research

Explore similar work

A Deep Reinforcement Learning Algorithm for the Vehicle Routing Problem with Stochastic Demands and Outsourcing

Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints

Neural Cluster First, Route Second: Capacitated Vehicle Routing via Differentiable Optimal Transport