Vehicle Routing

Follow this topic Ask about this topic

Momentum

7 papers in the last four weeks, down 22% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 77

May 9, 2026cs.AI

Value-Decomposed Reinforcement Learning Framework for Taxiway Routing with Hierarchical Conflict-Aware Observations

Taxiway routing and on-surface conflict avoidance are coupled safety-critical decision problems in airport surface operations. Existing planning and optimization methods are often limited by online computational cost, while reinforcement learning methods may struggle to represent downstream traffic conflicts and balance multiple objectives. This paper presents Conflict-aware Taxiway Routing (CaTR), a reinforcement learning framework for real-time multi-aircraft taxiway routing. CaTR constructs a grid-based airport surface environment with action masking, introduces a hierarchical foresight traffic representation to encode current and downstream conflict-related traffic conditions, and adopts a value-decomposed reinforcement learning strategy to prioritize sparse but safety-critical objectives. Experiments are conducted on a realistic environment based on Changsha Huanghua International Airport under multiple traffic density levels. Results show that CaTR achieves better safety--efficiency trade-offs than representative planning, optimization, and reinforcement learning baselines while maintaining practical runtime.

Shizhong Zhou, Haifeng Liu, Zheng Zhang +3

National Key Laboratory of Fundamental Science on Synthetic Vision, Sichuan University, Chengdu 610000, China · College of Computer Science, Sichuan University, Chengdu 610000, China

Collision Avoidance Vehicle Routing Multi-Agent Planning

May 7, 2026cs.LG

LINC: Decoupling Local Consequence Scoring from Hidden Matching in Constructive Neural Routing

Constructive neural routing solvers usually score the next action by matching a decoder context to candidate embeddings, leaving deterministic one-step consequences such as travel, waiting, slack, and capacity changes implicit. We propose LINC, a decoder-side candidate decision architecture that computes these consequences explicitly. LINC uses them according to their decision role: candidate-level consequences are scored by a state-conditioned shared linear comparator, while feasible-set summaries modulate the decoder context. This preserves standard global matching while reducing the burden on the hidden state to reconstruct transition arithmetic. The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) serves as the main constrained-routing testbed, and the same interface extends to the Capacitated Vehicle Routing Problem (CVRP) and Traveling Salesman Problem (TSP). Across external benchmarks and no-retraining scale-transfer settings, LINC consistently improves strong neural baselines, with the advantage becoming more pronounced as test size moves further beyond the training scale, especially on constrained routing problems.

Shaofeng Qin, Li Wang

Beijing University of Posts and Telecommunications

Vehicle Routing Neural Combinatorial Optimization

May 6, 2026cs.LG

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

May 5, 2026cs.AI

Automated Large-scale CVRP Solver Design via LLM-assisted Flexible MCTS

Solving large-scale CVRP (LSCVRP) with hundreds to thousands of nodes remains difficult for even state-of-the-art solvers. Divide-and-conquer can scale by decomposing the instance into size-reduced subproblems, but designing decomposition logic and configuring sub-solvers is highly expertise- and labor-intensive. Large Language Models (LLMs) have emerged as promising tools for automated algorithm design. However, existing LLM-driven approaches struggle with LSCVRP primarily due to the difficulty in generating sophisticated search strategies within a limited context window. To bridge this gap, we propose the LLM-assisted Flexible Monte Carlo Tree Search (LaF-MCTS), a novel framework that automates the design of high-performance LSCVRP solvers. We develop a three-tier decision hierarchy to enable incremental design of decomposition policies and sub-solvers for LSCVRP. To enable efficient search within the algorithmic hypothesis space, we introduce semantic pruning to eliminate semantically and structurally redundant codes, and branch regrowth to regenerate codes and preserve diversity. Extensive experiments on CVRPLib demonstrate that LaF-MCTS autonomously composes and optimizes decomposition-enhanced solvers that surpasses various state-of-the-art CVRP solvers.

Tong Guo, Caishun Chen, Yew Soon Ong

College of Computing and Data Science, Nanyang Technological University, Singapore

Automated Algorithm Discovery Large Language Model-Guided Optimization Combinatorial Optimization Monte Carlo Tree Search Vehicle Routing

May 4, 2026stat.ML

Middle-mile logistics through the lens of goal-conditioned reinforcement learning

Middle-mile logistics describes the problem of routing parcels through a network of hubs linked by trucks with finite capacity. We rephrase this as a multi-object goal-conditioned MDP. Our method combines graph neural networks with model-free RL, extracting small feature graphs from the environment state.

Onno Eberhard, Thibaut Cuvelier, Michal Valko +1

Max Planck Institute for Intelligent Systems, Tübingen, Germany · University of Tübingen · Google Research +1

Vehicle Routing Goal-Conditioned RL

May 2, 2026cs.LG

Hybrid Quantum Reinforcement Learning with QAOA for Improved Vehicle Routing Optimization

Vehicle Routing Problem (VRP) is one of the most complex NP-hard combinatorial optimization problem in transportation and logistics that requires a dynamic solution approach. In this paper we present a new hybrid approach that combines the Quantum Approximate Optimization Algorithm (QAOA) into the QRL policy network, instead of the usual variational layers, QAOA mixing and cost Hamiltonian layers. This enhancement enables the agent to exploit problem specific particular quantum correlations when learning policies, and so richer exploration of the routing solution space. The QAOA-augmented QRL framework shows quicker convergence in training and can tackle larger VRP instances that are beyond the reach of Grover's Adaptive Search (GAS) and Quantum Reinforcement Learning (QRL) approaches. Experiments on standard VRP instances demonstrate better solutions, fewer episodes to converge and good memory usage on near term quantum hardware simulators. These findings demonstrate QAOA- integrated QRL as a viable approach to scalable, high quality quantum-assisted combinatorial optimization.

T. Satyanarayana Murthy, B. Swathi Sowmya, Santhosh Voruganti +3

Chaitanya Bharathi Institute of Technology Hyderabad, India

Quantum Machine Learning Combinatorial Optimization Hybrid Quantum-Classical ML Vehicle Routing Quantum Approximate Optimization Algorithm Quantum RL

May 1, 2026cs.AI

Instance-Aware Parameter Configuration in Bilevel Late Acceptance Hill Climbing for the Electric Capacitated Vehicle Routing Problem

Algorithm performance in combinatorial optimization is highly sensitive to parameter settings, while a single globally tuned configuration often fails to exploit the heterogeneity of instances. This limitation is particularly evident in the Electric Capacitated Vehicle Routing Problem, where instances differ in structure, demand patterns, and energy constraints. This paper investigates instance-aware parameter configuration for Bilevel Late Acceptance Hill Climbing, a state-of-the-art metaheuristic for the Electric Capacitated Vehicle Routing Problem. An offline tuning procedure is used to obtain instance-specific parameter labels, which are then mapped from instance features via a regression model to enable parameter prediction for unseen instances prior to execution. Experimental results on the IEEE WCCI 2020 benchmark and its extensions show that the proposed approach achieves an average objective value reduction of

0.28\%

across eight held-out test instances relative to a globally tuned configuration. This corresponds to a significant cost reduction in multimillion-dollar transportation operations.

Yinghao Qin, Xinwei Wang, Mosab Bazargani +1

Centre for Intelligent Transport Queen Mary, University of London London, UK · School of Computer Science and Engineering Bangor University Bangor, UK

Metaheuristic Optimization Vehicle Routing Hyperparameter Optimization

Apr 30, 2026cs.AI

Agentic AI for Trip Planning Optimization Application

Trip planning for intelligent vehicles increasingly requires selecting optimal routes rather than merely producing feasible itineraries, as interacting factors such as travel time, energy consumption, and traffic conditions directly affect plan quality. Yet existing systems are largely designed for feasibility-oriented planning, and current benchmarks provide only reference answers without ground truth, preventing objective evaluation of optimization performance. In our paper, we address these limitations with an agentic AI framework that enables dynamic refinement through an orchestration agent coordinating specialized agents for traffic, charging, and points of interest, and with the Trip-planning Optimization Problems Dataset, which supplies definitive optimal solutions and category-level task structure for fine-grained analysis. Experiments show that our system achieves 77.4% accuracy on the TOP Benchmark, significantly outperforming single-agent and workflow-based multi-agent baselines, demonstrating the importance of orchestrated agentic reasoning for robust trip planning optimization.

Tiejin Chen, Ahmadreza Moradipari, Kyungtae Han +2

Toyota Motor North America R&D, InfoTech Labs, USA. · Arizona State University

Multi-Agent Orchestration Intelligent Transportation Systems Vehicle Routing Multi-Agent Planning

Apr 30, 2026cs.LG

FiLMMeD: Feature-wise Linear Modulation for Cross-Problem Multi-Depot Vehicle Routing

Solving practical multi-depot vehicle routing problems (MDVRP) is a challenging optimization task central to modern logistics, increasingly driven by e-commerce. To address the MDVRP's computational complexity, neural-based combinatorial optimization methods offer a promising scalable alternative to traditional approaches. However, neural-based methods typically rely on rigid architectures and input encodings tailored to specific problem formulations. In real-world settings, heterogeneous constraints create multiple MDVRP variants, limiting the applicability of such models. While multi-task learning (MTL) has begun to accelerate the development of unified neural-based solvers, prior works focus almost exclusively on single-depot VRPs, leaving the MDVRP unaddressed. To bridge this gap, we propose Feature-wise Linear Modulation for Cross-Problem Multi-Depot Vehicle Routing (FiLMMeD), a novel unified neural-based model for 24 different MDVRP variants. We introduce three main contributions: (1) to improve the model's generalization, we augment the standard Transformer encoder with Feature-wise Linear Modulation (FiLM), which dynamically conditions learned internal representations based on the active set of constraints; (2) we provide an initial demonstration of Preference Optimization in the MTL setting, establishing it as a superior alternative to Reinforcement Learning for future MTL works; (3) to mitigate the generalization gap caused by the introduction of multi-depot constraints, we introduce a targeted curriculum learning strategy that progressively exposes the model to increasingly more complex constraint interactions. Extensive experiments on 24 MDVRP variants (including 8 novel formulations) and 16 single-depot VRPs confirm the effectiveness of FiLMMeD, which consistently outperforms state-of-the-art baselines. Our code is available at: https://github.com/AJ-Correa/FiLMMeD/tree/main

Arthur Corrêa, Paulo Nascimento, Samuel Moniz

University of Coimbra, CEMMPRE, ARISE, Department of Mechanical Engineering, Coimbra, 3030-788, Portugal

Multi-Task Learning Vehicle Routing Neural Combinatorial Optimization

Apr 29, 2026eess.SY

Learning to Route Electric Trucks Under Operational Uncertainty

Electric truck operations require routing decisions that remain feasible under limited battery range, long charging times, travel and energy consumption, and competition for shared charging infrastructure. These features make electric truck routing a coupled logistics and energy problem, limiting the practicality of heuristics-based methods and rendering them computationally infeasible at scale. This paper proposes a learning-based framework for the stochastic electric truck routing under charging constraints and operational uncertainty. The problem, solved by Reinforcement Learning, is formulated as an event-driven semi-Markov decision process with shared charging resources, stochastic travel and energy requirements, and realistic nonlinear fast-charging behavior. To support learning in this setting, a graph-based representation of system state and feasible decisions is introduced, together with a rule-based action mask that restricts policies to operationally admissible actions; thus, improving training efficiency. Building on this formulation, an event-driven simulation environment is developed that supports both Reinforcement Learning and benchmarking against heuristic and mathematical programming baselines. Computational experiments across a range of fleet sizes show that the proposed learning-based algorithm consistently outperforms baselines and attains performance close to optimization benchmarks in many settings, while preserving high success rates under charging congestion and uncertainty.

Stavros Orfanoudakis, Ziyan Li, Ruixiao Yang +4

Delft University of Technology, Intelligent Electrical Power Grids, Delft, The Netherlands · Massachusetts Institute of Technology, Center of Transportation and Logistics, Cambridge, MA, United States of America · Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, Cambridge, MA, United States of America

Sequential Decision Making Electric Vehicle Charging Constrained RL Vehicle Routing

Apr 17, 2026cs.LG

NCO4CVRP: Neural Combinatorial Optimization for the Capacitated Vehicle Routing Problem

Neural Combinatorial Optimization (NCO) has emerged as a powerful framework for solving combinatorial optimization problems by integrating deep learning-based models. This work focuses on improving existing inference techniques to enhance solution quality and generalization. Specifically, we modify the Random Re-Construct (RRC) approach of the Light Encoder Heavy Decoder (LEHD) model by incorporating Simulated Annealing (SA). Unlike the conventional RRC, which greedily replaces suboptimal segments, our SA-based modification introduces a probabilistic acceptance mechanism that allows the model to escape local optima and explore a more diverse solution space. Additionally, we enhance the Policy Optimization with Multiple Optima (POMO) approach by integrating Beam Search, enabling systematic exploration of multiple promising solutions while maintaining diversity in the search space. We further investigate different inference strategies, including Softmax Sampling, Greedy, Gumbel-Softmax, and Epsilon-Greedy, analyzing their impact on solution quality. Furthermore, we explore instance augmentation techniques, such as horizontal and vertical flipping and rotation-based augmentations, to improve model generalization across different CVRP instances. Our extensive experiments demonstrate that these modifications significantly reduce the optimality gap across various Capacitated Vehicle Routing Problem (CVRP) benchmarks, with Beam Search and SA-based RRC consistently yielding superior performance. By refining inference techniques and leveraging enhanced search strategies, our work contributes to the broader applicability of NCO models in real-world combinatorial optimization tasks.

Mahir Labib Dihan, Md. Ashrafur Rahman Khan, Wasif Jalal +2

Department of Computer Science and Engineering Bangladesh University of Engineering and Technology

Inference-Time Search Metaheuristic Optimization Vehicle Routing Neural Combinatorial Optimization

Apr 17, 2026cs.HC

Driving Assistance System for Ambulances to Minimise the Vibrations in Patient Cabin

The ambulance service is the main transport for diseased or injured people which suffers the same acceleration forces as regular vehicles. These accelerations, caused by the movement of the vehicle, impact the performance of tasks executed by sanitary personnel, which can affect patient survival or recovery time. In this paper, we have trained, validated, and tested a system to assess driving in ambulance services. The proposed system is composed of a sensor node which measures the vehicle vibrations using an accelerometer. It also includes a GPS sensor, a battery, a display, and a speaker. When two possible routes reach the same destination point, the system compares the two routes based on previously classified data and calculates an index and a score. Thus, the index balances the possible routes in terms of time to reach the destination and the vibrations suffered in the patient cabin to recommend the route that minimises those vibrations. Three datasets are used to train, validate, and test the system. Based on an Artificial Neural network (ANN), the classification model is trained with tagged data classified as low, medium, and high vibrations, and 97% accuracy is achieved. Then, the obtained model is validated using data from three routes of another region. Finally, the system is tested in two new scenarios with two possible routes to reach the destination. The results indicate that the route with less vibration is preferred when there are low time differences (less than 6%) between the two possible routes. Nonetheless, with the current weighting factors, the shortest route is preferred when time differences between routes are higher than 20%, regardless of the higher vibrations in the shortest route.

Abdulaziz Aldegheishem, Nabil Alrajeh, Lorena Parra +2

Vehicle Routing

Nov 7, 2025cs.MA

Policy Stability for Measuring Operational Performance in Task Assignment with Time-Windows Under Internal Adversarial Influence

We study autonomous pickup-and-delivery routing problems in which internal adversarial agents spoof their locations to attract request assignments and then intentionally leave those requests unserviced. Such attacks disrupt the centralized scheduler, causing delays, cancellations, and routing instability. A routing policy is stable if its cost remains uniformly bounded over time. Existing policy-cost formulations typically characterize cost through the work required to service outstanding requests. Such a formulation requires analyzing agent-specific route execution and is therefore not well suited to adversarial settings, where non-cooperative agents may arbitrarily deviate from assigned routes or fail to service requests altogether. We introduce a new policy-cost formulation based only on observable system signals, namely the numbers of outstanding and canceled requests. Under bounded arrivals and finite request time windows, we show that stability under this formulation is equivalent to keeping the expected cumulative number of canceled requests uniformly bounded over time, an important operational metric in both cooperative and adversarial settings. We also extend cooperative fleet-sizing guarantees to finite time-window settings and highlight that request time windows are not merely a modeling detail, but are essential for ruling out \emph{degenerate stability}, a regime in which policies are certified as stable despite undesirable large request backlogs.

Roee M. Francos, Daniel Garces, Orhan Eren Akgün +1

School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138 USA

Vehicle Routing Multi-Robot Task Allocation

Oct 10, 2025cs.AI

Sequence Variables: A Constraint Programming Computational Domain for Routing and Sequencing

Constraint Programming (CP) offers an intuitive, declarative framework for modeling Vehicle Routing Problems (VRP). While classical successor-based CP models can be adapted to handle optional visits or insertion-based heuristics, sequence variables provide a significantly more natural and elegant formulation for these requirements. Building upon our prior work that introduced the initial concept, the main contribution of this article is the complete semantic and operational formalization of sequence variables as a computational domain. Specifically, we formally define the sequence domain and its update operations, and detail the implementation and data structures required to integrate sequence variables into trail-based CP solvers. Furthermore, we introduce consistency levels for associated constraints on this domain alongside specialized global constraints tailored for routing problems. Finally, we demonstrate that sequence variables simplify problem modeling while achieving competitive computational performance on Pickup and Delivery Problems with and without Time Windows, the Dial-a-Ride Problem, and a Prize-Collecting Scheduling Problem.

Augustin Delecluse, Pierre Schaus, Pascal Van Hentenryck

KU Leuven · UCLouvain · GATECH

Vehicle Routing Constraint Programming

Mar 13, 2025cs.LG

Learning Constraints-Based Adaptive Hypergraph Neural Networks for Solving Vehicle Routing Problems

The application of learning based methods to vehicle routing problems has emerged as a pivotal area of research in combinatorial optimization. These problems are characterized by vast solution spaces and intricate constraints, making traditional approaches such as exact mathematical models or heuristic methods prone to high computational overhead or reliant on the design of complex heuristic operators to achieve optimal or near optimal solutions. Meanwhile, although some recent learning-based methods can produce good performance for VRP with straightforward constraint scenarios, they often fail to effectively handle hard constraints that are common in practice. This study introduces a novel end-to-end framework that combines constraint-oriented hypergraphs with reinforcement learning to address vehicle routing problems. A central innovation of this work is the development of a constraint-oriented dynamic hyperedge reconstruction strategy within an encoder, which significantly enhances hypergraph representation learning. Additionally, the decoder leverages a double-pointer attention mechanism to iteratively generate solutions. The proposed model is trained by incorporating asynchronous parameter updates informed by hypergraph constraints and optimizing a dual loss function comprising constraint loss and policy gradient loss. The experiment results on benchmark datasets demonstrate that the proposed approach not only eliminates the need for sophisticated heuristic operators but also achieves substantial improvements in solution quality.

Zhenwei Wang, Tiehua Zhang, Jing Liu +3

University of Nottingham Ningbo China, 199 East Taikang Road, Ningbo, 315100, Zhejiang, China · Tongji University, 1239,Siping Road, Shanghai, 200092, Shanghai, China · State Key Laboratory for Novel Software Technology, Nanjing University, 163,Xianlin Road, Nanjing, 210023, Jiangsu, China +1

Constrained RL Vehicle Routing Hypergraph Neural Networks Neural Combinatorial Optimization

May 3, 2024cs.AI

Instance-Conditioned Adaptation for Large-scale Generalization of Neural Routing Solver

In modern intelligent transportation systems (ITS), particularly in freight transportation and logistics, real-time route planning is crucial. It presents unique challenges driven by high uncertainty in service requests, where the number of service customers can vary drastically, ranging from hundreds to thousands. Existing neural methods struggle to maintain performance under such significant variations, which severely limits their practical applicability. To address this crucial shortcoming, this work proposes a novel Instance-Conditioned Adaptation Model (ICAM) designed for better large-scale generalization. In particular, we design a simple yet efficient instance-conditioned adaptation function that adjusts the policy based on the specific geometry and density of the current traffic scenario to improve model adaptability with minimal computational overhead. Furthermore, we propose a powerful yet low-complexity instance-conditioned adaptation module to generate better solutions for instances across various scales. Extensive experiments on synthetic, benchmark, and real-world instances demonstrate that ICAM can consistently achieve promising generalization performance across four widely studied large-scale route planning scenarios. Notably, our proposed method delivers high-quality solutions with remarkably fast inference speed, providing a scalable and efficient solution for real-time intelligent transportation operations. Our code is available at https://github.com/CIAM-Group/ICAM.

Changliang Zhou, Xi Lin, Zhenkun Wang +3

Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and Technology, School of Automation and Intelligent Manufacturing, Southern University of Science and Technology, Shenzhen 518055, China · School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an 710049, China · Huawei Noah’s Ark Lab, Hong Kong SAR, China +1

Neural Network Generalization Intelligent Transportation Systems Vehicle Routing Neural Combinatorial Optimization

Date pendingcs.RO

Optimal Solutions for the Moving Target Vehicle Routing Problem with Obstacles via Lazy Branch-and-Price

The Moving Target Vehicle Routing Problem with Obstacles (MT-VRP-O) seeks trajectories for several agents that collectively intercept a set of moving targets. Each target has one or more time windows where it can be visited, and the agents must avoid static obstacles and satisfy speed and capacity constraints. Previously studied VRPs are often addressed using a framework called branch-and-price. This framework requires computing the cost for a single agent to visit a given sequence of target-time window pairings, for several candidate sequences. These sequences are called tours. Computing tour costs is more expensive in the MT-VRP-O than in previously studied VRPs due to the presence of both moving targets and static obstacles. Thus, we introduce a new exact algorithm, Lazy Branch-and-Price with Relaxed Continuity (Lazy BPRC), for the MT-VRP-O. The key idea in Lazy BPRC is to use cheap-to-compute lower bounds on tour costs where costs are traditionally used, and lazily update lower bounds to true costs. When computing a tour's true cost is needed, we do so by searching for a shortest path on a graph of convex sets, and we introduce a new heuristic to accelerate the search. We demonstrate that Lazy BPRC runs up to an order of magnitude faster than two ablations.

Anoop Bhat, Geordan Gutow, David Neiman +4

Robotics Institute at Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15213 · Mechanical and Aerospace Engineering at Michigan Technological University, Houghton, MI 49931 · Robotics and AI Institute, Cambridge, MA 02142 +2

Vehicle Routing Motion Planning