CS Paper Radar

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

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

cs.AI ·submitted 2026-10-10 10:29 UTC · v1

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.

Comment
28 pages, 12 figures

Closest papers

Nearest neighbours by meaning across the whole index.

From Comparison to Selection: Enhancing Cross-Scale Generalization of Pointer Networks Trained with Reinforcement Learning for Capacitated Vehicle Routing Problem

cs.AI ·2026-10-20 ·Sofiene Lassoued, Devara Tertia, Stefan Lier, Andreas Schwung
similarity 0.71
Abstract · 12 pages

Vehicle routing in delivery and logistics remains challenging as the number of clients varies. Classical approaches based on mixed-integer programming and heuristics can scale poorly or require problem-specific design, motivating learning-based alternatives. Reinforcement learning is particularly promising, provided a single policy can generalise across problem sizes without retraining. Although attention-based Pointer Networks are inherently size-agnostic, their solution quality degrades under both upscaling and downscaling. Using the Capacitated Vehicle Routing Problem (CVRP) as a controlled proxy, we investigate this degradation and identify three contributing factors: shifts in node density, attention dispersion, and dilution of the mean-pooled graph context. We systematically compare architecture-wide, encoder-side, and decoder-side modifications to address these limitations and propose a learned, permutation-invariant graph-context aggregation mechanism, implemented as a weighted average and as Set2Set. Results reveal distinct requirements for transfer in each direction: entropy-based attention scaling reduces the CVRP20-to-CVRP100 performance gap by 1.41 percentage points, while the proposed aggregation methods achieve the largest improvement on the more challenging CVRP100-to-CVRP20 transfer, approximately 0.9 percentage points. Exploiting this complementarity, we introduce an approach selector that chooses the best model for each training-target size pair. The selector reduces cost relative to the reference model across all nine seen train-test pairs and eight of nine pairs involving unseen sizes (CVRP35, CVRP75, and CVRP200), achieving improvements of up to 3.2%.

0.15

Just Initialize: A Training-Free Initialization Component for Large-Scale Routing Optimization

cs.AI ·2026-09-28 ·Jiale Zhao, Sirui Mao, Zimu Chen, Wentao Yang, Zihan Wang +3 more
similarity 0.67
Abstract · 31 pages, 5 figures

Large-scale routing problems are difficult to solve efficiently as their search spaces grow rapidly with problem size. Existing approaches primarily improve the optimization procedure itself, often at increasing computational cost. We instead shift the focus to a useful initialization that can be refined into a high-quality solution with limited downstream refinement. We propose Just Initialize, a training-free and solver-agnostic initialization component for large-scale routing optimization. Just Initialize compresses a large routing instance into a compact surrogate space, optimizes its global routing structure, and recovers the resulting solution as an optimization-friendly starting point in the original space. Extensive experiments on Traveling Salesman Problems (TSPs), Capacitated Vehicle Routing Problems (CVRPs), Vehicle Routing Problems with Time Windows (VRPTWs), and Prize-Collecting Traveling Salesman Problems (PCTSPs) demonstrate that Just Initialize achieves high-quality solutions comparable to or better than state-of-the-art methods while substantially reducing computational cost across instances ranging from 1K to 100K nodes, including an average speedup of approximately 70$\times$, sub-second runtimes on 10K-node instances, and runtimes within tens of seconds on 100K-node instances.

0.19

Size Generalization for Diffusion Routing Solvers

cs.AI ·2026-10-12 ·Barak Itzchak Davidovitch, Eli Meirom, Ethan Fetaya, Gal Chechik
similarity 0.64
Abstract

Routing problems, like the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP), are NP-hard and slow to solve for large instances. Diffusion-based solvers can be trained in a supervised way using sets of optimal solutions, and then quickly solve new test instances. However, for large instances, optimal solutions are hard to find, and diffusion models fail to generalize to instance sizes outside their training distribution. Here we describe ResizeCO, a label free size-generalization approach that addresses both the change in statistical properties of larger instances, and the computational challenge of solving them quickly. It uses reinforcement learning on large-scale instances to adapt a diffusion model trained on small instances. Specifically, we adapt GRPO to this problem, using route length as the training signal. ResizeCO also formulates k-opt as a tree search, solved by a beam search on the GPU. In size-generalization experiments on TSP and CVRP instances with up to 10000 nodes, ResizeCO achieves a Pareto front over route quality and time that dominates learned solvers, and also outperforms other solvers at short run times, setting a new state of the art.

0.10

Customizable and Jointly Optimized Route Planning: A Deep Architecture Enabling Differentiable Shortest-Path Search

cs.AI ·2026-09-17 ·Rui Zhao, Chao Chen, Longfei Xu, Chenguang Ji, Hengbin Cui +2 more
similarity 0.63
Abstract

With the widespread use of online navigation and ride-hailing services, achieving optimal route planning for diverse user preferences has recently attracted increasing attention. Classic graph algorithms for pathfinding use heuristic cost functions to define edge weight, thus providing no optimality guarantee of route quality. Prior data-driven approaches equating ground truth of the optimal route with user trajectory, which is however moderately influenced by the navigation service, suffers from the feedback loop problem. To address these issues, we propose a deep architecture that is able to jointly optimize cost functions and route-ranking model towards any route preference. First, we run a multi-objective Dijkstra algorithm offline to collect the set of Pareto optimal routes, deeming it as the complete candidate set. Exploiting the property of such a set, we design a neural network structure that emulates shortest-path search and route ranking in an end-to-end differentiable manner. Second, we define route preference as a task of constrained optimization of route attributes, and propose a novel loss function that optimizes a single-objective variable, with other variables strictly under constraints. We conduct extensive experiments on real-world datasets. The results show that our architecture significantly outperforms state-of-the-art methods in route quality and customizability.

0.28

SCOPE-Router: Cost-Aware Open-Set VLM Routing for Execution-Oriented Tasks

cs.CV ·2026-08-12 ·Tao Yu, Yifei Qu, Zhiqing Cui, Pengfei Zhou, Zhongtian Luo +12 more
benchmark similarity 0.63
Abstract

Model routing aims to select the most suitable model from a candidate pool for each query, balancing quality and cost. Existing VLM routing research is limited to traditional VQA evaluation, lacks systematic calibration optimization for open-set scenarios, and employs training objectives that dilute multi-positive signals via softmax normalization without incorporating cost. We address these limitations with three contributions: (1)VLM-ExecRouterBench, the first execution-oriented VLM routing benchmark covering Code, Agentic, and Search domains with 11 candidate models spanning nearly two orders of magnitude in pricing; (2)SCOPE-Router, a dual-tower router that matches queries to model behavior profiles constructed via hybrid calibration (random/diagnostic/diversity sampling), enabling new models to join routing without retraining; (3)CRM+RCCR, an architecture-agnostic cost-aware objective that encodes cost preference into continuous relevance targets through per-pair independent scoring, eliminating multi-positive dilution while regularizing queries with similar routing preferences to be closer in the routing space. Empirically, SCOPE-Router achieves the best Rank Score on all three benchmarks, surpassing the runner-up by 1.84 points under OOD settings and by 6.75 points under doubly OOD open-set evaluation. When applied to four diverse routers, CRM+RCCR improves Rank Score by 1.25--6.21 points.

0.40

Improved Approximation for Unsplittable CVRP via a Greedy Approach

cs.DS math.CO ·2026-09-15 ·Daniel Ebert, Leonard Weismantel
similarity 0.62
Abstract · 26 pages, 1 figure

We devise a polynomial-time $3.159$-approximation algorithm for the metric unsplittable Capacitated Vehicle Routing Problem. We build on the Relative Greedy Algorithm suggested by Traub (2025), which can be considered as a variant of the LP rounding algorithm of Friggstad, Mousavi, Rahgoshay, and Salavatipour (2025). Our main ingredient is the Average Greedy Algorithm, a new algorithm that controls both tour costs and the coverage of clients with high demand. This additional control enables a sharper averaging argument for the cost of subsequent greedy choices. Similarly to Zhao and Xiao (2026), combining the Average Greedy with variants of tour partitioning and a matching algorithm yields the final approximation guarantee.

0.55

Trajectory-Initialized Neural Double Q-Routing for Large-Scale Overhead Hoist Transport Systems

cs.LG cs.AImath.OC ·2026-08-31 ·Cheng Gu, Qiusheng Zhao, Anbang Liu, Shaochong Lin, Max Z. J. Shen
similarity 0.62
Abstract

Large-scale industrial robot fleets share constrained physical infrastructure, making vehicle travel times dependent on safety separation, intersection access, downstream blocking, and station contention. We study this problem in overhead hoist transport (OHT) systems, a representative ceiling-mounted material-handling system used in semiconductor fabs. Static shortest-path routing cannot account for these time-varying traffic costs, whereas tabular Q-routing adapts online but learns each destination--node--action value independently, limiting information sharing across sparsely visited routing contexts and making startup behavior sensitive to inaccurate value estimates. We propose Neural Double Q-routing, which replaces destination-indexed tables with a shared state--action value network. The network is warm-started through return-to-go regression on mixed simulator-generated routing trajectories and then refined online using Double-Q updates, local congestion correction, and event-stratified structured replay. Across nine matched fleet-size--arrival-rate settings with 100, 150, and 200 OHTs, the proposed framework reduces mean completion time relative to tabular Double Q-routing by $0.8\%$--$8.8\%$. It achieves the lowest mean completion time among all compared methods in the six 150- and 200-OHT settings, whereas Dijkstra remains best in the three 100-OHT settings. Completed-task counts remain within $1\%$ of tabular Double Q-routing in eight of nine settings, and 95th-percentile completion time decreases in eight settings. In two matched startup scenarios, offline initialization increases the number of completed tasks by up to $23\%$ and reduces tail completion time by up to $15\%$.

0.28

Imperfect Is Perfect: Learned Column Prefilling for Branch-Price-and-Cut

cs.LG ·2026-10-14 ·Haoran Liu, Yu Yang
benchmark similarity 0.62
Abstract · 27 pages, 3 figures

Column generation folklore warns that initial columns hurt: a warm start may bias the dual and slow the root of branch-price-and-cut. We show the opposite once the columns are imperfect in the right way. Preloading the support of the optimal root LP, the best columns one could know in advance, fails to finish on half of our hardest instances; a pool of ordinary routes that need not belong to any optimal solution, held outside the master and priced at the current smoothed dual, speeds the root up. Because the columns need not be optimal, producing them becomes a learning task: a neural edge scorer guides a constructive generator that builds the pool in seconds. A second network predicts the initial center of Wentges smoothing from the instance file, and with it the direction of the smoothed pricing queries; the solver's own updates run unchanged. With prefill and center in place, exact pricing dominates root pricing time, so we rebuild bucket-graph labeling around its dominance test for the GPU and certify on the CPU. Inside RouteOpt, the state-of-the-art exact solver for capacitated vehicle routing, the pipeline reaches the same certified root bound in 13.2% of vanilla RouteOpt's root pricing time over 95 instances with 300 to 1000 customers, prefill alone in 26.1%, and 17.5 times faster in the best case. In an exact branch-price-and-cut solver for unrelated parallel machine scheduling, prefill with smoothing and the learned center certifies all 25 benchmark instances, 12 times faster than the solver's own column generation, which certifies 20 of them.

0.51