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

• OOH delivery can consolidate parcels for multiple customers into one stop, while prices can steer customers toward options that are cheaper to serve.Source: §1 · p. 1
• Dynamic orders require routing decisions for each delivery option at checkout, too quickly for classical exact or metaheuristic solvers.The relevant cost is the marginal routing-cost increase from inserting a stop given the vehicle’s current position and planned tour.Source: §1 · p. 2
• GREAT-ESDD uses a GREAT-based neural CVRP solver for mixed-size instances and arbitrary starting states, including partially executed routes.It serves as both a routing-cost estimator during pricing and a route generator after state changes, with GPU batching for parallel option problems.Source: §1 · p. 2
• 11% higher profit than a traditional routing solver under similar decision-time budgets is reported for GREAT-ESDD.The framework solves candidate routing problems for delivery options in parallel, uses their cost increases to price options, and provides the chosen option’s updated route.Source: §1 · p. 2
• Online Thompson sampling with an MNL choice model approximately recovers customer preferences and beats the best flat pricing strategy within five simulated operating days.Source: §1 · p. 2

2.1. Machine learning for static routing problems

• 2.1. Machine learning for static routing problems: GREAT trains across instance sizes and arbitrary start nodes and vehicle loads, unlike the common fixed-size, depot-start setup.This supports re-solving partially completed routes as active customer counts change.Source: §2.1 · p. 3

2.2. Machine learning for dynamic routing problems

• 2.2. Machine learning for dynamic routing problems: GREAT-ESDD models dynamic arrivals through iterative re-optimization rather than training a dynamic model that anticipates future arrivals.This makes training cheaper and supports transfer between inference distributions, but sacrifices anticipation of future arrivals.Source: §2.2 · pp. 3–4

2.3. Pricing and routing

• 2.3. Pricing and routing: Unlike opportunity-cost models, value functions, or learned cost predictors, GREAT-ESDD solves each candidate routing problem to estimate marginal service cost and directly update the route.A fast batched solver makes this approach practical within sub-second decision budgets, but its estimate is myopic.Source: §2.3 · p. 4

3.1. Operational setting

• 3.1. Operational setting: A single vehicle serves sequentially arriving customers from one depot, offering home delivery, one of K fixed OOH locations, or opt-out at dynamic prices.The operator maximizes expected daily profit, defined as collected prices minus the route cost, by steering customers toward cheaper-to-serve options.Source: §3.1 · pp. 4–5

3.2. Customer choice model

• 3.2. Customer choice model: An MNL model assigns choice probabilities from option utilities, with OOH utility depending on price and distance and home utility depending on price.The model defines five preference parameters: home and OOH base utilities, their price sensitivities, and OOH distance sensitivity.Source: §3.2 · p. 5

3.3. The dynamic pricing-and-routing problem

• 3.3. The dynamic pricing-and-routing problem: At each arrival, the operator offers a price menu, observes the selected option, and updates the route from the vehicle’s current position and load.The objective depends on future customers, prices must be set while customers wait, and choice probabilities depend on preference parameters that are typically unknown.Source: §3.3 · p. 6

4. Solution approach

• Across an operating day, the framework prices options using the current routing state and adopts the route already computed for the customer’s accepted option.It also reoptimizes when realized demand is below ordered demand; after orders stop, the vehicle completes its route and returns to the depot.Source: §4 · p. 6, Figure 1 · p. 7

4.1. A neural solver for CVRP of mixed sizes and arbitrary start states

• Training across customer counts and starting states lets the GREAT solver reoptimize residual CVRPs as new customers arrive or realized demand changes.Deterministic training reduces training resource requirements, but does not teach the model patterns of stochastic arrivals that could improve inference performance.Source: §4.1 · pp. 8–9

4.2. Making profitable pricing and routing decisions

• For each arriving customer, GREAT estimates each delivery option’s marginal routing cost and the framework selects the price menu maximizing expected immediate profit.Because the price grid is discrete and routing-cost estimates do not depend on prices, the framework enumerates price menus after computing each option’s cost estimate once.Source: §4.2 · p. 9

4.3. Rectifying the marginal cost estimate

• A rectifier ω adjusts the estimated marginal routing cost in expected-profit calculations because future customer arrivals can make early cost estimates too high.A customer arriving in an otherwise empty neighborhood may later share a delivery with customers who order before delivery.Source: §4.3 · p. 10

4.4. Learning unknown customer preferences online

• Thompson sampling with a Laplace-approximated posterior learns shared MNL preference parameters from observed customer choices, balancing exploration and exploitation.The posterior is refit after each choice; the distance vector enters the choice likelihood, while marginal routing costs affect which price menu is optimal.Source: §4.4 · pp. 10–11

5.1. Road network and instance generation

• The Seattle road-network graph has 19,241 nodes, population-weighted customer sampling, travel-time distances, and four fixed OOH locations.Nodes are split into training, validation, and test sets; the travel-time metric is asymmetric because of one-way streets.Source: §5.1 · p. 11

5.2. Training the GREAT model

• GREAT is trained for 400 epochs on CVRP instances of sizes 10–100, with varied starting nodes and vehicle loads to represent partially served routes.Training uses 5,000 instances per size per epoch, with validation after each epoch and the best-performing model retained.Source: §5.2 · p. 12

5.3. Routing baselines

• Routing backends include GREAT variants, PyVRP with different time limits, and a fast insertion heuristic; PyVRP’s five candidate CVRPs can run in parallel on five CPU cores.GREAT is tested with and without ×9 instance augmentation and on GPU and CPU; PyVRP is run with time limits up to 1 second in the pricing-and-routing setting.Source: §5.3 · pp. 12–14

5.4. Pricing simulation setup

• Pricing experiments simulate 25 operating days with known preferences and 100 days with unknown preferences, comparing dynamic pricing with a $7 flat-price baseline.The unknown-preference experiments track parameter convergence and profit regret, under both deterministic and stochastic demand; in the stochastic setting, 30% of customers have demand reduced to 1.Source: §5.4 · pp. 14–15

6.2. Pricing with known customer preferences

• At a similar decision-time budget, GREAT-ESDD earned approximately $65, or 11.3%, more profit per day than PyVRP with a 0.1s limit.The mean runtime of GREAT-ESDD without augmentation coincided with PyVRP’s 0.1s limit.Source: §6.2 · p. 16

6.1. GREAT-based CVRP solver

• Across instance sizes from 5 to 150 customers, GREAT’s gap stayed within approximately 1–5%, while PyVRP’s gap under a fixed 1s limit grew steadily, reaching approximately 20% at 150 customers.Source: §6.1 · p. 16

6.2. Pricing with known customer preferences

• Dynamic pricing steered more customers to OOH delivery and lowered prices paid while slightly increasing company profit relative to flat pricing.Flat pricing collected more fees, but its lower OOH share led to higher routing costs.Source: §6.2 · p. 18

6.1. GREAT-based CVRP solver

• On GPUs, GREAT solved a batch of five instances in under 1s even at 150 customers.Skipping augmentation also allowed CPU runtimes below 2s at 150 customers.Source: §6.1 · p. 16, Figure 6 · p. 19

6.3. Learning to price

• Customer-preference parameters were approximately recovered and seemed to converge after around 50 simulated days.In the stochastic setting, α_h, β_h, and γ were recovered almost perfectly, while α_OOH and β_OOH were slightly overestimated.Source: §6.3 · p. 19
• Learned dynamic pricing broke even with flat pricing after 3–5 days and outperformed it within five simulated days.The estimated cumulative-profit difference was on the order of $1000 after 100 simulated days.Source: §6.3 · p. 21

Myopic ΔC estimate

• Because the routing solver cannot anticipate future arrivals, early or isolated orders tend to be overpriced, distorting customer steering.A distribution-aware model could potentially improve performance for a fixed city and customer distribution, but would require modeling arrivals during training.Source: §7 · p. 21

Heuristic marginal cost

• The marginal routing cost is a difference between approximate route costs, not an optimal increment, and the estimation error is not quantified directly.The authors report that backends with smaller solution gaps generally achieve higher profits.Source: §7 · p. 21

Static rectifier ω

• The fixed rectifier ω is tuned offline and may not transfer across cities, demand patterns, or operating horizons without retuning.Its values were selected using a 10-day search susceptible to noise, and a coarse grid may miss better values.Source: §7 · p. 21, Figure 8 · p. 22, Figure 9 · p. 23

Routing and goods assumptions

• The framework assumes one vehicle and interchangeable goods; serving multiple vehicles in parallel requires a different modeling approach, while customer volume is limited with one vehicle.Interchangeable goods fit pickup operations such as parcel returns, but typical parcel delivery requires specific goods and depot reloading; the decoder could mask new customers until the next depot visit.Source: §7 · p. 22

Simulation and model specification

• Customer choices are simulated from the same MNL family learned by the bandit, favoring parameter recovery; heterogeneous or misspecified behavior may slow learning, and sparse-area pricing raises unaddressed fairness questions.The authors call for real customer-choice data for a more realistic evaluation.Source: §7 · pp. 22–23

Conclusion

• The framework solves candidate home and OOH routing problems in parallel at checkout, uses their cost increases to select prices, and reuses the chosen solution as the vehicle’s route.It also learns unknown customer preferences online with Thompson sampling and a Laplace-approximated posterior.Source: §8 · p. 23
• Approximately 11% higher daily profit than a PyVRP-based framework with the same decision time was achieved by GREAT-ESDD.The neural solver outperformed PyVRP under a similar time budget, especially for larger instances.Source: §8 · p. 23
• Against flat pricing, GREAT-ESDD raises OOH share from 18.6% to 29.2%, reduces routing cost by approximately 6%, lowers average price paid by 3.2%, and increases profit by approximately $14 per day.Figure 10 presents cumulative revenue, routing cost, and profit over 100 days for bandit-based and flat $7 pricing in deterministic and stochastic settings.Source: §8 · p. 24, Figure 10 · p. 24
• GREAT-ESDD’s cost estimates are myopic and heuristic, its rectifier is static, and its evaluation assumes one vehicle, interchangeable goods, and simulated customer behavior.Future work includes adaptive rectifier tuning, multiple vehicles, non-interchangeable goods, anticipatory cost estimates, and validation with real customer-choice data.Source: §8 · p. 24

B. Optimal price for flat pricing

• $7 led to the highest company profit among flat prices from $5 to $8 in a 10-day simulation using GREAT without augmentation.The tested prices were $5, $5.5, $6, …, and $8.Source: B. Optimal price for flat pricing · p. 27

C. Local search postprocessing

• Subtour-wise 2-opt and Or-opt alternate for up to 10 passes or until no improvement, keeping subtour endpoints fixed and preserving capacity feasibility.The method targets local inefficiencies rather than global route patterns; subtours usually contain about 10 nodes.Source: C. Local search postprocessing · p. 28