CS Paper Radar

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

Sofiene Lassoued, Devara Tertia, Stefan Lier, Andreas Schwung

cs.AI ·submitted 2026-10-20 09:44 UTC · v3

Abstract

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%.

Comment
12 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Size Generalization for Diffusion Routing Solvers

cs.AI ·2026-10-12 ·Barak Itzchak Davidovitch, Eli Meirom, Ethan Fetaya, Gal Chechik
similarity 0.72
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

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

cs.AI ·2026-10-10 ·Attila Lischka, Ze Zhou, Xuegang, Ban, Balázs Kulcsár
similarity 0.71
Abstract · 28 pages, 12 figures

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.

0.28

JAMPR+/L2D: scalable neural heuristic for constrained vehicle routing problems in dynamic environment

cs.LG ·2026-08-14 ·Andrew Soroka, Alex Meshcheryakov
published similarity 0.69
Abstract · Automation and Remote Control accepted

The vehicle routing problems with real-world constraints (we consider vehicles capacity limits, time windows constrains, pickup-and-delivery multi-depo --- CPDPTW) pose significant computational challenges. While classical exact and heuristic methods remain effective to solve problems of small/medium size ($N\lesssim100$), they often lack adaptability and scalability for larger logistics tasks. In this work, we show how JAMPR+/L2D RL deep learning model, proposed in to solve large CPDPTW problems can be adopted in the case of substantial changes of graph distance matrix. We test performance of JAMPR+/L2D model for medium-sized CVRP and VRPTW problems on CVRPLIB benchmarks: JAMPR+/L2D outperforms the state-of-the-art heuristic HGS in over 85\% of instances, achieving improvement in objective gap. We show that the JAMPR+/L2D model trained on CPDPTW problem, generalizes well for tasks with simpler constraints (CVRP, VRPTW), for different problem sizes and for moderate changes in distance matrixes. For more substantial changes in distance matrixes, we propose here to make fast finetuning of JAMPR+: on ORTEC data (for CPDPTW) the proposed strategy remarkably reduces the objective gap without full model retraining, what will give both accuracy and rapid inference of the model in the practical routing scenarios with distance matrix changes.

0.19

Deep Reinforcement Learning solution for pickup and delivery routing problems with time window and capacity constraints

cs.LG ·2026-08-14 ·Andrew Soroka, Alex Meshcheryakov, Sergey Gerasimov
publishedhighly cited similarity 0.67
Abstract

The task of constructing vehicles optimal routes for pickup and delivery of goods is one of most promising tasks in the context of global urban population growth. Although this kind of problems with small size can be solved by various classical approaches, a fast (or realtime) route optimizer under the constraints of the real world (such as capacity and time windows constraints) for medium-large size problems still remains a highly challenging task. In this work we, for the first time, successfully applied a deep Reinforcing Learning approach (modified JAMPR model) to solve Pickup and Delivery problem with Capacity and Time Window constraints (CPDPTW). We obtained a robust model that gives a fast optimal solution for problems of small and medium size, and gives fast suboptimal solution for problems of larger (> 200) size.

0.63

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

cs.LG ·2026-08-14 ·Andrew Soroka, German Mikhelson, Alexander Mescheryakov, Sergey Gerasimov
published similarity 0.67
Abstract

The problem of route optimization with realistic constraints is becoming extremely relevant in the face of global urban population growth. While we are aware of approaches that theoretically provide an exact optimal solution, their application becomes challenging as the problem size increases because of exponential complexity. We investigate the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and compare solutions obtaining by exact solver SCIP with heuristic algorithms such as LKH, 2-OPT, 3-OPT, the ORTools framework, and the deep learning model JAMPR. We demonstrate that for problem of size 50 deep learning and classical heuristic solutions became close to SCIP exact solution but requires less time. Additionally for problems with size 100, SCIP exact methods around 13 times slower that neural and classical heuristics with the same route cost and on around 50% worse for the first feasible solution on the same time. To conduct experiments, we developed the Smart Routes platform for solving route optimization problems, which includes exact, heuristic, and deep learning models, and facilitates convenient integration of custom algorithms and datasets.

0.22

HALO: Heterogeneous Allocation Via Localized Observations for the Vehicle Routing Problem

cs.RO cs.MA ·2026-09-30 ·Andrew Meighan, Hyungsub Kim, Or Dantsker
theory similarity 0.66
Abstract · 2026 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future me…

Scalable robotic fleets have become increasingly popular for various applications such as package delivery, warehouse management, and military operations. Prior fleet control algorithms solve centralized routing problems with up to $1{,}000$ tasks in controlled environments, yet they fail to consider realistic constraints such as limited observation and communication ranges typical of decentralized fleets. Thus, deploying existing fleet control algorithms into real-world settings is currently infeasible. To tackle this, we propose Heterogeneous Allocation via Localized Observations (HALO) to solve the Vehicle Routing Problem (VRP). HALO is a hybrid method that splits the VRP into allocation and routing portions to provide onboard, real-time solutions to robots in dynamic environments. During the allocation phase, HALO utilizes a heterogeneous graph neural network framework with unique message passing layers to explicitly separate the learning of spatial distributions and task-to-robot compatibility. Evaluation results on a partially observable, online variant of the VRP show HALO significantly outperforms the heuristic baseline while maintaining similar solution quality to an all-knowing offline variant of HALO. While HALO is explicitly designed for partially observable environments, it imposes no strict upper bound on the observation space allowing us to test HALO on the traditional static, single-depot VRP. Here, HALO outperforms state-of-the-art architectures strictly optimized for the static variant of the VRP by up to $14.06\%$. Throughout all testing, this framework maintains the quickest execution times which emphasizes its potential for large-scale, real-time deployment.

0.16

Improving Cross-Problem Vehicle Routing with Locally Augmented Preferences and Representation Disentanglement

cs.LG ·2026-08-25 ·Arthur Corrêa, Paulo Nascimento, Samuel Moniz
similarity 0.66
Abstract

Multi-task vehicle routing problem (VRP) solvers seek to handle multiple VRP variants within a single unified model, avoiding the need to train a separate model for every variant. In spite of recent progress, current approaches remain limited on two fronts. On the training side, reinforcement learning suffers from reward-scale disparities and shrinking advantage signals as policies improve, whereas preference optimization stagnates once sampled tours become near-identical and thus fundamentally limited by the quality of the policy's own generated solutions, leaving both paradigms with weak supervision as training progresses. On the architecture side, existing fully shared encoders entangle constraint-dependent representations across heterogeneous variants, which limits generalization. We address these gaps with two model-agnostic contributions. First, we propose Preference Optimization with Locally Augmented Refinement (POLAR), a novel training algorithm that applies a local search refinement pass to the best decoded tour before forming preference pairs, yielding much more informative pairwise margins. Second, a Progressive Layered Extraction (PLE) encoder routes each encoder layer through one shared expert and a set of task-specific experts via a gating mechanism, progressively separating common routing structure from constraint-specific encodings. Through extensive experiments on various VRP variants, we show that POLAR and PLE together elevate the current state-of-the-art among neural multi-task solvers. We reduce the average gap to reference solutions by 21.3% relative to the strongest published baseline on 16 in-distribution variants, and outperform prior neural methods on 27 out of 32 unseen variants. Ablation studies confirm the efficacy of each contribution, showing that both improve cross-problem generalization across multiple backbone model architectures.

0.17

Preserving Geometric Integrity in Graph Prompting via Measure-Constrained Optimal Transport

cs.LG ·2026-09-20 ·Xiangyu Wang, Shuo Wang, Ruiyi Fang, Zhao Kang
code/data similarity 0.66
Abstract · 28 pages, 4 figures

Graph prompt learning enables parameter-efficient adaptation of frozen Graph Neural Networks to downstream tasks through lightweight prompt parameters. As routing becomes increasingly node-adaptive, however, independently optimized local decisions can collectively concentrate assignment mass on a small subset of a finite shared prompt bank, even when individual node--prompt matches remain locally meaningful. We propose MINT (Measure-INtegrity Transport), an entropically regularized optimal transport framework that formulates node-to-prompt adaptation as a globally coupled allocation problem. The transport cost favors local geometric compatibility, while a prescribed prompt-side marginal explicitly controls graph-wide prompt utilization. We further derive an exact variance decomposition that separates prompt-side geometric variance into retained prompt-update variation and within-node barycentric dispersion, together with a conditional stability bound for the frozen-encoder forward map. Across standard citation networks and additional heterophilic graphs, MINT remains competitive in few-shot adaptation. Controlled and end-to-end experiments further distinguish the roles of routing and topology: fixed-marginal routing controls graph-wide prompt utilization and has measurable end-to-end effects on citation networks, while topology augmentation provides a complementary, graph-dependent mechanism for addressing structural mismatch. Code is available at https://github.com/Ga1axy0051/MINT.

0.32