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

Jul 8, 2026cs.LG

Latency-Aware Bid Acceptance under Operational Feasibility: A Public Benchmark with Hindsight Ceilings

Online truckload bid acceptance is a closed-loop stochastic decision problem in which a carrier or broker must, in real time, accept or reject a tendered load subject to operational feasibility, fleet repositioning costs, and opportunity cost against future demand. Public, reproducible benchmarks for this problem are scarce: existing routing benchmarks are static, while dynamic-fleet studies typically rely on private operator data. We introduce FreightBidBench, a public-calibrated, dependency-free, closed-loop benchmark in which feasibility (pickup reach, appointment windows, simplified hours-of-service, stochastic yard delays) and economics (service-failure penalty, terminal fleet value, daily price-premium window) are explicit, versioned, and reproducible from public Freight Analysis Framework and U.S. Department of Agriculture truck rate data. We develop two full-horizon hindsight ceilings: a simple LP style relaxation and a tighter Lagrangian-per-truck information relaxation that retains per-truck hours-of-service and sequencing structure and is 20.7% tighter than the LP relaxation on a tight-capacity scenario and 39.3% tighter on a scarce-capacity scenario. We introduce a parametric surrogate-rollout cascade with boundary-band and scarcity-pressure escalation triggers. On ten-seed tight and scarce scenarios, the best simple policy retains 91.0% and 86.5% of rollout profit and the standard-library surrogate 94.2% and 89.3%; a cascade at a single escalation band recovers roughly 98% on both at 40-56% of rollout's mean decision latency, and on the tight scenario is statistically indistinguishable from the rollout teacher (paired-bootstrap 95% CI on the profit delta spans zero).

Aswin Chandrasekaran

Bubba AI

Benchmark Design Vehicle Routing Supply Chain Management Online Resource Allocation Real-Time Bidding

Jul 7, 2026cs.RO

Towards Reliable Aerial Ground Vehicle Collaboration: An Integrated Planning and Autonomy Framework for Field Deployment

Limited flight endurance significantly restricts the operational range of unmanned aerial vehicles (UAVs) in long duration missions such as surveillance and inspection, where multiple spatially distributed Areas of Interest (AOIs) must be visited. These tasks require efficient routing determining the sequence of visits which directly impacts mission time, energy consumption, and overall feasibility. Pairing UAVs with unmanned ground vehicles (UGVs) for mobile recharging offers a promising solution, but introduces a tightly coupled cooperative routing problem involving UAV route planning, UGV road constrained movement, energy management, and rendezvous scheduling under uncertainty. In this work, we present an integrated planning and autonomy framework for reliable field deployment. We formulate the problem as an energy constrained cooperative routing task and solve it using a Deep Reinforcement Learning (DRL) based planner that jointly optimizes the UAV visitation sequence and rendezvous locations with the UGV, outperforming baseline heuristics in minimizing total mission time. To bridge the gap between planning and execution, we introduce a standardized two layer YAML based mission API that captures environment states and structures lightweight, synchronized action sequences. This framework is supported by a complete autonomy stack using PX4/MAVSDK for UAV control and ROS 2/Nav2 for UGV navigation. Furthermore, we propose a lightweight Rendezvous Aware Replanner (RARP) that operates online to handle environmental uncertainties, reducing energy margin violations from 83.33% to 20.00%. The full system is validated through outdoor field experiments, demonstrating robust cooperative navigation and adaptability in dynamic tasks, including a search and rescue scenario with vision language model (VLM) based hazard detection

Md Safwan Mondal, Luca Russo, James D. Humann +2

Department of Mechanical and Industrial Engineering, University of Illinois Chicago, IL, 60607 USA · DEVCOM Army Research Laboratory, Minneapolis, Minnesota, USA · DEVCOM Army Research Laboratory, Aberdeen Proving Grounds, Aberdeen, MD 21005 USA

Vehicle Routing Multi-Robot Coordination

Jul 7, 2026cs.AI

Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency

The Vehicle Routing Problem (VRP) and its variants represent some of the most practically consequential optimization challenges in modern logistics and urban mobility. In this study, we address a dynamic, online variant combining elements of the VRP and the Orienteering Problem (OP), in which a fleet of vehicles must maximise cumulative reward collected within a fixed time horizon while continuously replanning as new tasks arrive. We propose and evaluate a reward-density heuristic for dynamic multi-vehicle assignment, referred to as the Efficiency heuristic. We evaluate this formulation across two application domains: autonomous drone task allocation and urban taxi dispatch, across multiple fleet sizes and task scales. The proposed method is compared with four classical construction heuristics and three metaheuristic algorithms (Adaptive Large Neighbourhood Search, Genetic Algorithm, and Simulated Annealing), all evaluated under identical conditions. Across all tested configurations, the Efficiency heuristic matches the solution quality of the best metaheuristic algorithms while requiring two to three orders of magnitude less planning time, establishing Pareto dominance over all competing methods on the reward-versus-compute frontier. These findings suggest a practical design principle for real-time allocation and dispatch systems: in dynamic, time-constrained routing environments, carefully designed greedy heuristics can match the output of sophisticated search procedures at a fraction of the computational cost, making them preferable for online deployment.

Manish Kolachalam, Rani Malhotra

Autonomous Machines Applied Research Center Infosys Center for Imaging Technologies, Infosys Bengaluru, India

Vehicle Routing

Jul 5, 2026cs.LG

Two Black Boxes, One Solver: Encoder Probing and Decoder Attribution for Neural Multi-Attribute VRP under Hard-Mask and Recourse Decoders

Neural autoregressive solvers for the Multi-Attribute Vehicle Routing Problem (MAVRP) reach competitive cost but offer no per-step justification, a problem when dispatchers must validate, accept, or compare them. We open two complementary black boxes in one protocol. On the encoder side, linear probes, spontaneous-organization metrics, rank-based richness measures, and discovered-direction analyses with intervention validation characterize how the latent represents constraint families at the graph, node, and edge level. On the decoder side, three attribution methods (gradient, integrated gradients, DeepLIFT) feed three reading angles: abductive, contrastive against the best feasible alternative, and counterfactual (smallest input change that switches the action or restores feasibility). Explanations are scored on fidelity, concentration, stability, sanity, and actionability. Across six variants combining three encoders (Attention baseline, Unimp, UnimpMoe) with two decoders (Hard-Mask, Recourse), we find that graph inductive bias improves both representational predictability and decoder sanity, that the Mixture-of-Experts encoder represents constraints in a distributed rather than axis-aligned way, and that the Recourse training regime, not merely its softer mask, produces policies that represent infeasibility usefully, exposing make-feasible counterfactuals that Hard-Mask policies fail to produce even when fed infeasible alternatives externally.

Sohaib Afifi

Univ. Artois, UR 3926, Laboratoire de G´enie Informatique et d’Automatique de l’Artois (LGI2A), F-62400 B´ethune, France

Gradient-Based Attribution Counterfactual Explanations Vehicle Routing Neural Network Interpretability Representation Probing Neural Combinatorial Optimization

Jul 4, 2026cs.AI

Robust Feasible Route Construction through Collaborative Partition Optimization

Large-scale Capacitated Vehicle Routing Problems (CVRPs) are commonly solved by partitioning customers into smaller routing problems that can be optimized independently. While this substantially reduces computational complexity, independently constructed routing solutions may leave some customer demand unserved even when sufficient resources exist elsewhere in the fleet. We present Collaborative Routing Constructors (CoRC), a routing framework that enables independently solved subproblems to exchange customers and vehicles during optimization rather than relying solely on a fixed partition or a subsequent global re-optimization stage. Computational experiments on AGS benchmark instances and synthetic instances containing up to 200,000 customers compare CoRC against independent routing, post-routing global re-optimization, and state-of-the-art, end-to-end routing frameworks. Across all evaluated partitioning strategies, CoRC consistently constructs feasible routing solutions where competing partition-based methods do not. Furthermore, it remains effective on problem instances for which the evaluated end-to-end routing frameworks did not produce solutions under the same computational budget. These results demonstrate that collaboration between routing subproblems provides a robust and scalable approach for feasible large-scale route construction.

Oguzhan Karaahmetoglu, Hyong Kim

Department of Electrical and Computer Engineering, Carnegie Mellon University

Vehicle Routing

Jun 30, 2026cs.AI

Adaptive Cluster-First Route-Second Decomposition for Industrial-Scale Vehicle Routing

Large-scale capacitated vehicle routing problems (CVRPs) are commonly addressed using cluster-first route-second (CFRS) approaches that split a routing instance into smaller, computationally tractable subproblems. Existing splitting methods typically rely on fixed partitioning rules, predefined optimization objectives, or learned policies, which may perform inconsistently across instances exhibiting different spatial, demand, and operational characteristics. In this work, we propose an adaptive CFRS system that formulates a decomposition procedure as an iterative decision-making process. Motivated by the recent success of large language models (LLMs) in reasoning and tool selection, the system employs an LLM as a high-level decision maker that analyzes the evolving decomposition state and selectively applies further clustering, balancing, and refinement operators. The proposed algorithm jointly partitions customers and vehicles, enabling capacity-aware clustering while adapting partitioning decisions to the characteristics of each problem. We evaluate the approach on synthetic and benchmark-derived CVRP instances containing up to 500,000 customers. Experimental results demonstrate competitive performance on benchmark-scale instances while exhibiting improved scalability and robust routing quality on substantially larger problems. These results highlight the potential of adaptive, LLM-guided decision support as a practical approach for industrial-scale vehicle routing and large-scale logistics planning.

Oguzhan Karaahmetoglu, Hyong Kim

Carnegie Mellon University · Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, 15213 USA

Large Language Model-Guided Optimization Combinatorial Optimization Vehicle Routing

Jun 29, 2026cs.LG

Optimizing Nursing Care Taxi Dispatch Leveraging Integer Linear Programming Solvers and Machine Learning

In this paper, we formulate a new vehicle dispatch optimization problem, called Nursing Care Taxi Dispatch, as a variant of the Vehicle Routing Problem, considering constraints related to wheelchair use, user compatibility, pick-up and drop-off times, and vehicle limitations. Previous neural-based methods for Vehicle Routing Problems have typically addressed a few simple constraints, while our new problem involves multiple complex constraints, resulting in having fewer destinations to select. This complexity makes it more difficult to obtain solutions that allow all nodes to be visited with a limited number of vehicles. To balance low violation rate, computational efficiency, and solution quality, we propose a supervised machine learning approach based on the Transformer architecture. We first obtain a set of high-quality solutions using an integer linear programming solver for given inputs and then train our learning model through supervised learning. Additionally, we introduce the post-processing of the paths generated by the learning model, ensuring that all constraints are satisfied. We compared each instance's objective function value (operating time), execution time, and constraint violation rate across different methods: our proposed method and some existing methods including integer linear programming and machine learning-based methods, using real-world facility data. Our method successfully produced balanced solutions regarding operating time, execution time, and constraint violation rate. Notably, we observed a decrease in the operating time for all problem sizes and regions, while keeping constraint violations to a minimum compared to existing methods. Especially, the decrease reached up to 8% for problem sizes with fewer than 30 users.

Riku Nakao, Akihito Hiromori, Hamada Rizk +1

The University of Osaka, Japan · RIKEN R-CCS, Japan · Tanta University, Egypt

Vehicle Routing Neural Combinatorial Optimization

Jun 26, 2026cs.RO

Locker-based Truck-Drone Routing with Integrated Considerations of Pickups, Deliveries, and No-Fly Zones

Truck-drone delivery is an emerging last-mile logistics mode combining the long-haul capacity of trucks with the flexible service capability of drones. In locker-based operations, smart lockers serve not only as temporary parcel storage facilities but also as automated drone docking and service nodes. These automated nodes support drone takeoff, landing, parcel handover, and battery replacement, thereby significantly extending the service range and operational flexibility of drone-assisted delivery networks. However, practical locker-based delivery systems face complex real-world challenges, requiring the integrated coordination of not only parcel delivery, return pickup, battery-constrained and load-dependent drone flights, but also necessary detours around restricted airspace. To address this practical and multifaceted challenge, this paper introduces a locker-based truck-drone routing problem with integrated considerations of pickups, deliveries, and no-fly zones (LTDRP-PDNF), with the objective of minimizing the total operational cost of a fleet of drone-equipped trucks. We formulate the route construction process as a Markov Decision Process and develop a two-stage deep reinforcement learning-based neural heuristic. The first stage utilizes an attention-based encoder and a Bidirectional Gated Recurrent Unit decoder to solve the truck-only routing problem, formulated as a capacitated vehicle routing problem. The second stage combines a policy-transfer strategy with a hybrid dispatch assignment heuristic to construct fully coordinated truck and drone routes for LTDRP-PDNF. Experiments on instances of different scales demonstrate that the proposed method outperforms metaheuristic and neural heuristic baselines in most cases while maintaining exceptionally short computation times, offering an effective, scalable solution framework under practical operational constraints.

Xuanyu Liu, Hui Hu, Jiao Zhao +2

College of Transportation Engineering, Chang’an University, China · Faculty of Science and Technology, University of Nottingham Ningbo China

Combinatorial Optimization Vehicle Routing RL for Combinatorial Optimization

Jun 9, 2026cs.CV

Vision-Assisted Foundation Model for Solving Multi-Task Vehicle Routing Problems

Multi-task vehicle routing problems play a critical role in enhancing efficiency across various industries and service sectors. These problems consist of multiple variants that optimize routing costs while meeting diverse customer constraints. Existing multi-task VRP solvers solely utilize a graph-based modality, limiting their ability to address variants with multiple constraints. As a format to represent complex semantics, vision modality shows great potential for encoding diverse VRP constraints. This motivates us to learn patch-level semantics from the vision images, and then integrate them into a graph-based model to solve various VRP variants simultaneously. However, directly applying this approach to multi-task VRPs presents three challenges: 1) existing VRP images lack constraint representations, which are essential for multi-task VRPs, 2) the fixed receptive field of individual patches cannot effectively accommodate varying requirements across tasks, and 3) imbalanced pixel distribution among constraints may cause the model to overlook constraints with fewer pixels. In this paper, we propose a vision-assisted foundation model (VaFM) to address these challenges. In the vision modality, input images tailored to all constraints are encoded by a convolutional neural network. The obtained patch embeddings are fused with graph-based nodes to generate solutions, with an auxiliary task designed to address the pixel-imbalanced issue. The performance of VaFM is evaluated across 16 different VRP variants. The experimental results demonstrate the superiority of VaFM over state-of-the-art methods, especially for variants with complex constraints.

Shuangchun Gui, Zhiguang Cao, Wen Song +1

College of Computing and Data Science, Nanyang Technological University, Singapore, and the Centre for Frontier AI Research, Institute of High Performance Computing, Agency for Science, Technology and Research, Singapore

Multi-Task Learning Vehicle Routing Multimodal Fusion Neural Combinatorial Optimization

Jun 9, 2026cs.LG

Baseline-Free Policy Optimization for Neural Combinatorial Optimization

Neural combinatorial optimization (NCO) trains autoregressive policies to solve routing problems. The standard training algorithm, REINFORCE with a rollout baseline, requires maintaining and periodically updating a frozen copy of the policy for variance reduction. This baseline introduces a structural vulnerability: on harder instances, a poor baseline produces noisy gradient estimates that can destabilize training. We evaluate Group Relative Policy Optimization (GRPO), an algorithm from large language model alignment that eliminates the baseline entirely by normalizing advantages within groups of sampled trajectories. In a controlled comparison of five RL algorithms on TSP and CVRP benchmarks within the RL4CO framework, we find that: (i) GRPO avoids the training collapse observed with REINFORCE on TSP-100, where performance degrades from cost 9.8 to 52.1 immediately after the warmup phase and does not recover under extended training; (ii) at matched gradient updates, GRPO achieves solution quality within 2% of POMO, a strong AM-based multi-start baseline, while requiring no external baseline; and (iii) P3O, a pairwise preference algorithm also from the alignment literature, is competitive on TSP but shows higher variability on CVRP. These results identify GRPO as a promising baseline-free alternative for NCO, particularly in settings where baseline-dependent training becomes fragile.

Carlos S. Sepúlveda, Gonzalo A. Ruz

Traveling Salesperson Problem Group Relative Policy Optimization Combinatorial Optimization Vehicle Routing RL for Combinatorial Optimization Neural Combinatorial Optimization

Jun 7, 2026cs.NI

Systems-Level Planning and Coordination of Truck-Drone Collaborative Delivery Networks

Urban last-mile parcel delivery increasingly relies on heterogeneous fleets whose performance depends on timely coordination, reliable communication, and scalable control. Truck-drone collaboration has emerged as a networked cyber-physical delivery paradigm that combines the payload capacity and range efficiency of trucks with the agility of drones in congested or access-limited urban environments. This paper proposes a layered planning and coordination framework that structures truck-drone collaborative delivery (TDCD) from a systems and control perspective. The framework consists of five interrelated layers: spatial-demand alignment, collaborative delivery configuration, resource and workflow orchestration, performance evaluation, and scalability analysis, providing a unified view of coordination, control, and system-level performance in networked delivery operations. The proposed framework is evaluated using a realistic urban last-mile delivery scenario derived from the 2021 Amazon Last Mile Routing Research Challenge dataset. The case study demonstrates how coordinated truck-drone operation, enabled by structured task orchestration and inter-agent synchronization, improves end-to-end system efficiency under operational constraints. Results show a 42.4% reduction in total delivery time and a 44.2% reduction in energy consumption compared to a conventional truck-only delivery model. The scalability analysis further highlights how coordination gains persist as system size increases, and shows the importance of efficient control and communication in heterogeneous delivery networks.

Didem Cicek, Burak Kantarci

School of Electrical Engineering and Computer Science at the University of Ottawa, Ottawa, ON, K1N 6N5, Canada

Vehicle Routing Multi-Robot Coordination

Jun 4, 2026cs.MA

A Swarm Approach to Public Transit Using On-demand Routing in a Slime-Mold-Inspired Framework

Demand-responsive transit (DRT) is a flexible alternative to traditional, fixed-route mass-transit networks. Although DRT can function well in low-density communities, high operating costs and low reliability are common issues. We propose that these issues can be mitigated by moving from a centralized, manually-scheduled scheme to a distributed system capable of dynamically routing multiple vehicles using a slime-mold-inspired routing algorithm to maximize network effectiveness. We additionally introduce the method of dynamic transfers to further optimize transit network efficiency. All passenger allocation and dynamic transfers are handled via a continual cooperative bidding process by the buses. In this paper, we present simulated results for a swarm-driven transit network in suburban, urban, and semi-rural scenarios, using map networks pulled from OpenStreetMap. We show that our approach increases passenger delivery rates relative to a fixed-network approach by 28%, 49%, and 101%, respectively, and results in over 75% reduction in walking time in all cases.

Lindsay Burke, Maxfield Comstock, Jason Graham +3

Department of Computer Science, New Jersey Institute of Technology · Federated Department of Biological Sciences, New Jersey Institute of Technology · Department of Mathematics, University of Scranton +1

Intelligent Transportation Systems Vehicle Routing Demand Response

Jun 3, 2026cs.AI

Beyond Objective Equivalence: Constraint Injection for LLM-Based Optimization Modeling on Vehicle Routing Problems

Large language models (LLMs) can generate executable solver code from natural-language descriptions of optimization problems. However, existing verification signals focus on whether the generated formulation produces the correct objective value. Such signals can overlook constraint-level errors: incorrect formulations may still produce the same optimum when extra or missing constraints do not affect the tested instance. We propose constraint injection, a verification method that directly tests whether the generated code implements the intended constraints. We use feasible solutions to detect incorrectly added constraints and one-constraint-violating solutions to detect omissions. Together with the optimal value check, these tests verify both the objective and the constraint set. We evaluate this approach on vehicle routing problems (VRPs), which provide a challenging testbed with diverse, tightly coupled operational constraints. We develop VRPCoder, an 8B model for generating Gurobi code from natural-language VRP descriptions, and VRPBench, an expert-verified benchmark spanning 21 VRP variants across four subsets. The verifier serves as a rejection-sampling criterion for synthetic data construction and as a rollout-level reward for reinforcement learning (RL). On VRPBench, VRPCoder-RL reaches 93% overall Pass@1, outperforms Gemini-3.1-Pro Preview on three subsets, exceeds Claude-Sonnet-4.5 by 28 percentage points, and exceeds the strongest prior OR-LLM by 78 percentage points.

Xizi Luo, Changhong He, Dongdong Geng +2

Beihang University, Beijing, China · Baidu Inc., Beijing, China

Vehicle Routing Natural Language to Optimization Modeling

Jun 1, 2026cs.LG

Edge-aware Decoding for Neural Asymmetric Routing

Neural asymmetric routing models increasingly encode directionality through matrix representations and asymmetry-aware attention. The final routing action, however, is not a node in isolation but a directed transition chosen under the current partial route. This creates a representation--decision mismatch: pairwise cost information may be encoded upstream while the final candidate logit is still largely parameterized as context--node compatibility. We propose a decoder-design principle for neural asymmetric routing: the final score should explicitly expose transition-level quantities suggested by the problem's cost-to-go structure. We instantiate this principle with an edge-aware decoder that adds candidate-specific terms for the current directed edge, return-to-start closure, and static lightweight lookahead, while keeping the representation backbone fixed. On a controlled SVD/Sinkhorn asymmetric backbone, the decoder improves over the RADAR reference when trained on ATSP-100 and evaluated zero-shot on ATSP-100/200/500/1000, reducing the ATSP-1000 gap from

4.13\%

to

2.73\%

. On ACVRP, the same score-level modification shows the same qualitative trend under a richer routing state. ATSP ablations and directed-transition diagnostics sharpen the mechanism: the strongest evidence concerns sensitivity to the current directed edge, while closure and static lookahead act as heuristic continuation cues. The results support a mechanism study: a key decoder-side signal in neural asymmetric routing is decision-time exposure of transition-level edge information.

Li Liang, Jinbiao Chen, Zizhen Zhang

Sun Yat-Sen University · Department of Industrial Systems Engineering and Management, National University of Singapore

Combinatorial Optimization Vehicle Routing Neural Combinatorial Optimization

Jun 1, 2026cs.DM

Graph Edit Distance Formulation for the Vehicle Routing Problem: Theory and Analysis

We show that the Vehicle Routing Problem (VRP) can be reformulated as a Graph Edit Distance (GED) maximization problem. Under a simple edge-deletion cost model, minimizing total route cost is equivalent to maximizing the total weight of edges deleted from the complete instance graph. This formulation models VRP at the edge level, where solutions are defined by selected edges rather than route sequences, enabling structural analyses that are difficult in classical formulations: per-edge attribution of solution quality, decomposition of the optimality gap, characterization of solution sparsity, and identification of edges that are hard to reach by greedy construction. Theoretically, we establish a merge-decomposition theorem showing that Clarke-Wright savings equal per-merge GED increments, and an approximation-transfer theorem that turns GED approximation ratios into VRP cost bounds. Using this reformulation, we analyze 90 CVRP benchmark instances with known optimal solutions. We find that optimal routing graphs use only 5.5% of available edges, that approximately 3.0% of optimal edges are consistently not found by Clarke-Wright heuristics under repeated restarts, and that the cost gap decomposes into missed optimal edges and substituted non-optimal edges of comparable total weight. The edge-additive objective provides a natural per-edge supervision signal for future graph neural network approaches to edge prediction, suggesting a potential connection to graph neural network approaches that we leave for follow-up work.

Adel Dabah

Jülich Supercomputing Centre Forschungszentrum Jülich Jülich, Germany

Vehicle Routing

May 31, 2026cs.LG

MViewRouter: Internalizing Geometric Equivariance via Multi-view Alternating Attention for Combinatorial Routing

Combinatorial routing problems such as the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP) are fundamental NP-hard problems with broad real-world applications. While recent deep reinforcement learning methods have shown promising performance, they typically handle geometric symmetries only through data augmentation, resulting in inconsistent decisions and limited generalization. To address this issue, we propose MViewRouter, a multi-view framework that internalizes geometric equivariance as a structural inductive bias to achieve invariant decision-making across routing problem variants. Our approach introduces a Multi-view Alternating Attention (MAA) mechanism that enables parallel processing over the

D_4

symmetry group, alternating between intra-view relational modeling and inter-view feature alignment. Furthermore, we optimize the policy via Collective Policy Gradient Aggregation (CPGA), leveraging consensus gradients from multiple symmetric views to stabilize training and accelerate convergence. Experiments on TSP and CVRP benchmarks, as well as real-world TSPLIB instances, demonstrate that MViewRouter achieves competitive solution quality and strong zero-shot generalization.

Shiyan Liu, Bohan Tan, Yaoxin Wu +1

Huazhong University of Science and Technology · Eindhoven University of Technology

Traveling Salesperson Problem Multi-View Learning Equivariant Neural Networks Combinatorial Optimization Vehicle Routing Neural Combinatorial Optimization

May 27, 2026cs.RO

Integrated Exploration-Aware UAV Route Optimization and Path Planning

Uncrewed aerial vehicles (UAVs) are increasingly used for exploration-driven monitoring in hazardous environments such as disaster zones, contaminated sites, wildfire areas, and damaged infrastructure, where limited flight endurance must be allocated between visiting reported locations and gathering new information. In these settings, prior information regarding hazards is often incomplete, spatially imprecise, and subject to change during execution. For example, initial reports may identify a region where a hazard is likely to exist, but the actual hazard may be displaced, partially observed, or entirely unreported. We present an integrated exploration-aware UAV route optimization and path planning framework for hazard monitoring under uncertain and evolving prior information. The environment is represented as a spatial risk map, where each location has an associated belief of hazardous conditions. Reported hazards are modeled as uncertain regions of interest (ROIs) rather than confirmed target locations, requiring the UAV to inspect reported areas while also using its limited flight endurance to explore informative regions. The proposed method solves a vehicle routing problem over reported ROIs, augments the route with auxiliary pseudo-nodes to improve spatial coverage, allocates the remaining flight distance budget across route segments, and optimizes dynamically feasible B-spline trajectories for local exploration. During execution, UAV measurements update a grid-based belief map, and the remaining trajectory is replanned when new information and the remaining budget justify adaptation. Across 48 scenario configurations, online replanning improves average KL reduction by 15.9% over the offline optimized planner and 48.6% over straight-line traversal.

Jimin Choi, Grant Stagg, Cameron K. Peterson +1

Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109, USA · Department of Electrical Engineering, Brigham Young University, Provo, UT 84602, USA · Department of Aerospace Engineering, Department of Civil and Environmental Engineering, and Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI 48109, USA

Belief-Space Planning Trajectory Optimization Informative Path Planning UAV Navigation Vehicle Routing UAV Trajectory Optimization+1

May 26, 2026cs.LG

Towards Generalization-Oriented Models for Vehicle Routing Problems with Mixture-of-Experts

In recent years, Deep Reinforcement Learning (DRL) has achieved substantial progress on Vehicle Routing Problems (VRPs). However, existing DRL-based methods are typically trained on instances generated from a uniform distribution, which limits their performance under real-world distribution shifts. In this paper, we aim to develop a generalization-oriented model that partitions the policy network into multiple modules and adaptively recombines modules to form specific policies during inference. Specifically, we propose Residual Refined Experts with Instance-level Gating (R2E-IG) to improve cross-distribution generalization. Our contributions are threefold: (1) We introduce a Residual Refined Expert (R2E) architecture that enhance expert expressiveness via residual refinement; (2) We design an instance-level gating mechanism that learns distribution-aware instance representations and routes inputs to suitable modules; (3) We propose a mixed-distribution training mechanism equipped with Dynamic Weight Adaption (DWA), which dynamically reweights training data from different distributions to emphasize more informative ones. Extensive experiments show that R2E-IG achieves competitive performance against state-of-the-art baselines on both in-distribution and out-of-distribution instances across synthetic and benchmark datasets. Moreover, R2E-IG is generic and can be easily integrated into existing DRL-based methods to further improve performance.

Changhao Miao, Yuntian Zhang, Tongyu Wu +2

State Key Laboratory of Autonomous Intelligent Unmanned Systems, Beijing Institute of Technology, Beijing 100081, China · Department of Computer, Control and Management Engineering “Antonio Ruberti”, Sapienza University of Rome, Rome, 00185, Italy · School of AI, Beijing Institute of Technology, Beijing 100081, China

Reinforcement Learning Adaptive Model Routing Vehicle Routing Cross-Domain Generalization Mixture-of-Experts Models RL for Combinatorial Optimization

May 23, 2026cs.AI

SPACE: Unifying Symmetric and Asymmetric Routing Problems for Generalist Neural Solver

Generalist neural routing solvers have shown great potential in solving diverse vehicle routing problems (VRPs) with a unified model. However, existing solvers are typically limited to symmetric settings or degrade in performance when switching to asymmetric settings due to input inconsistencies or inherent structural differences, substantially limiting their practicality in real-world scenarios that encompass both scenarios. To address this limitation, we define the spatial position of each node based on the relative distances to a specific set of pivots and further propose a Spatial Pivot-Aligned Coordinate-free Embedding (SPACE) framework that unifies node representation and solution generation across symmetric and asymmetric VRPs. Specifically, we construct a bidirectional Frechet representation using a novel furthest pivot sampling strategy to enable invariant node representations across distinct problem settings. Furthermore, we introduce a weight-decomposed adaptive decoding mechanism that decouples geometric perception from problem representations, mitigating the overfitting of constraint decisions to a specific geometry setting. Extensive experiments on 110 VRP variants, comprising 55 symmetric problems and their asymmetric counterparts, demonstrate that SPACE achieves promising zero-shot generalization in both symmetric and asymmetric VRPs.

Rongsheng Chen, Changliang Zhou, Canhong Yu +4

School of Automation and Intelligent Manufacturing, Southern University of Science and Technology, Shenzhen, China · Pengcheng Laboratory, Shenzhen, China · Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and Technology, Southern University of Science and Technology, Shenzhen, China +1

Vehicle Routing Invariant Representation Learning Neural Combinatorial Optimization

May 20, 2026cs.AI

COAgents: Multi-Agent Framework to Learn and Navigate Routing Problems Search Space

Although Vehicle Routing Problems (VRP) are essential to many real-world systems, they remain computationally intractable at scale due to their combinatorial complexity. Traditional heuristics rely on handcrafted rules for local improvements and occasional \textit{jumps} to escape local minima, but often struggle to generalize across diverse instances. We introduce \textbf{COAgents}, a cooperative multi-agent framework that models the search process as a graph: nodes represent solutions, and edges correspond to either local refinements or large perturbations for diversification (i.e., jumps). A \textit{Partial Search Graph} (PSG) is dynamically constructed during search, enabling COAgents to train a Node Selection Agent and a Move Selection Agent to guide intensification, and a Jump Agent to trigger well-timed explorations of new regions. Unlike end-to-end learning approaches, COAgents cleanly separates problem-agnostic search control from compact domain-specific encoding, facilitating adaptability across tasks. Extensive experiments on the CVRP and VRPTW benchmarks show that COAgents remains competitive with several learn-to-search baselines on CVRP and sets a new state of the art among learning-based methods on the more challenging VRPTW instances, reducing the gap to the best-known solutions by 14% at

N\!=\!100

and 44% at

N\!=\!50

relative to the strongest neural solver (POMO), and by 21% and 40% respectively relative to ALNS. Code is available at https://github.com/mahdims/COAgents.

Oleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed +4

Huawei Technologies Canada, 4321 Still Creek Dr, Burnaby, BC, Canada V5C 6S7 · Huawei Technologies, China

Multi-Agent System Optimization Vehicle Routing Cooperative MARL Neural Combinatorial Optimization

May 19, 2026cs.LG

Learning with Foresight: Enhancing Neural Routing Policy via Multi-Node Lookahead Prediction

Neural policies have shown promise in solving vehicle routing problems due to their reduced reliance on handcrafted heuristics. However, current training paradigms suffer from a fundamental limitation: they primarily focus on next-node prediction for solution construction, resulting in myopic decision-making that undermines long-horizon planning capacity. To this end, we introduce Multi-node Lookahead Prediction (MnLP), a novel training strategy that extends the supervised learning paradigm to predict multiple future nodes simultaneously. We incorporate causal and discardable MnLP modules that operate exclusively during training, facilitating models to anticipate multi-step decisions while preserving inference-time efficiency. By incorporating multi-depth auxiliary supervision into the loss function, MnLP equips neural policies with the ability of long-range contextual understanding. Experimentally, MnLP outperforms existing training methods, improving the generalization capability of neural policies across various problem sizes, distributions, and real-world benchmarks. Moreover, MnLP can be seamlessly integrated into diverse neural architectures without introducing additional inference overhead.

Xia Jiang, Yaoxin Wu, Yew-Soon Ong +1

Eindhoven University of Technology · Nanyang Technological University · Agency for Science, Technology and Research (A*STAR)

Vehicle Routing Neural Combinatorial Optimization

May 16, 2026cs.MA

Dynamic Deployment of Mobile Charging Trucks During Natural Disaster Evacuation: An Offline-to-Online Framework

During large-scale evacuations, concentrated electric vehicle (EV) charging demand can overload fixed charging stations (FCSs), leading to prolonged waiting time and increased risk exposure. To address this challenge, this study proposes dynamically deploying mobile charging trucks (MCTs) to complement FCSs, and develops an Adaptive Risk-aware MCT Deployment (ARMD) framework for real-time operation. It divides the MCT deployment into two problems: risk-aware allocation of MCTs among FCSs and dynamic routing of MCTs to the assigned FCSs, and solves them under an offline-to-online paradigm. The resource allocation problem is formulated as a decentralized partially observable Markov decision process, and a multi-agent proximal policy optimization (MAPPO)-based policy is developed to coordinate multiple MCTs under decentralized observations. The policy is pre-trained offline in an evacuation simulator and adaptively refined online according to current evacuation context. For routing, a spatio-temporal travel time predictor is developed to support rolling-horizon route updates. The proposed framework is evaluated in a simulated hurricane evacuation environment built using real-world data from Hillsborough County, Florida. Experiments show that ARMD consistently outperforms offline optimization, online heuristic dispatch, and rolling-horizon optimization in reducing risk exposure. For demand perturbation scenarios, ARMD reduces average risk exposure by up to 71.1%, relative to the baseline without MCTs. In the case of fixed e-vehicle charging infrastructure or road link failures, ARMD achieves 39.3% to 60.5% reduction in average risk exposure, with its advantages becoming more pronounced as the severity of disruption increases. These results demonstrate the effectiveness and robustness of ARMD in enhancing mobile charging operations for realistic scenarios of uncertain evacuation conditions.

Rui Ma, Zilin Bian, Kaan Ozbay

New York University · Rochester Institute of Technology

Electric Vehicle Charging Vehicle Routing Decision-Making under Uncertainty

May 15, 2026cs.CG

Optimizing Line Segment Inspection with Limited-Range Drones

Optimization problems with drones are widely studied in a variety of civilian tasks, mainly due to their ability to traverse rough terrains and to carry cameras and other sensors for surveillance tasks. The limited battery life of these aerial robots poses challenges in operational research. In this paper, we address the following optimization problem. We are given a set of line segments (e.g. tubes in a solar plant) to inspect by drones. The objective is to detect broken pipes using artificial intelligence and path planning must be carried out efficiently. On the one hand, the limited capacity of the batteries necessitates periodic visits (tours) to a fixed base station. However, it is desirable to allocate a set of tours for each drone to ensure that the segments are covered as quickly as possible, aiming to minimize the makespan, which is the maximum time spent by any drone. We are able to prove that this optimization problem is strongly NP-hard even when the segments are positioned on a line and the scenario involves only two drones. Then, approximation algorithms are proposed. Our computational experiments demonstrate that the proposed algorithm achieves near-optimal performance across diverse operational scenarios.

José-Miguel Díaz-Báñez, José-Manuel Higes, Alina Kasiuk +1

Department of Applied Mathematics, University of Seville, Spain

Aerial Robotics Combinatorial Optimization Vehicle Routing Multi-Robot Task Allocation Approximation Algorithms

May 14, 2026math.OC

Scalable Solution of the Stochastic Multi-path Traveling Salesman Problem via Neural Networks

The multi-path Traveling Salesman Problem with stochastic travel costs arises in hybrid vehicle routing applications designed for Smart City and City Logistics, where multiple paths exist between each pair of locations. Travel times along these paths are typically affected by real-time traffic conditions and therefore modeled as stochastic. The objective of the problem is to determine a Hamiltonian tour that minimizes the expected total travel cost under uncertainty. In this work, we adopt a two-stage stochastic programming formulation. In the first stage, a predefined route specifying the sequence of locations to be visited is determined, while taking into consideration a second-stage recourse problem that selects the optimal path from the feasible set of alternative paths for each pair of locations, once real-time traffic conditions are realized. To reduce the computational burden imposed by the large number of scenarios required to capture travel time uncertainty, the innovation of this work is the integration of neural network-based surrogate models to approximate the expected value of the second-stage recourse problem. Different architectures and training strategies for the neural networks are proposed and analyzed, with performance evaluated in terms of computation time, solution quality, and generalization capability. Preliminary findings demonstrate the enhanced scalability and practical applicability of the approach for complex vehicle routing problems under uncertainty.

Xiaochen Chou, Ludovica Di Marco, Enza Messina

Department of Informatics, Systems and Communication, University of Milano-Bicocca, Viale Sarca 336, Milan, 20125, Italy.

Neural Surrogate Modeling Stochastic Optimization Traveling Salesperson Problem Combinatorial Optimization Vehicle Routing

May 14, 2026eess.SY

Fully Dynamic Rebalancing in Dockless Bike-Sharing Systems via Deep Reinforcement Learning

This paper proposes a fully dynamic Deep Reinforcement Learning (DRL) method for rebalancing dockless bike-sharing systems, overcoming the limitations of periodic, system-wide interventions. We model the service through a graph-based simulator and cast rebalancing as a Markov decision process. A DRL agent routes a single truck in real time, executing localized pick-up, drop-off, and charging actions guided by spatiotemporal criticality scores. Experiments on real-world data show significant reductions in availability failures with a minimal fleet size, while limiting spatial inequality and mobility deserts. Our approach demonstrates the value of learning-based rebalancing for efficient and reliable shared micromobility.

Edoardo Scarpel, Alberto Pettena, Matteo Cederle +3

University of Padua, via Gradenigo 6/B, 35131, Padua, Italy

RL Control Reinforcement Learning Intelligent Transportation Systems Vehicle Routing

May 14, 2026cs.AI

A Unified Knowledge Embedded Reinforcement Learning-based Framework for Generalized Capacitated Vehicle Routing Problems

The Capacitated Vehicle Routing Problem (CVRP) is a fundamental NP-hard problem with broad applications in logistics and transportation. Real-world CVRPs often involve diverse objectives and complex constraints, such as time windows or backhaul requirements, motivating the development of a unified solution framework. Recent reinforcement learning (RL) approaches have shown promise in combinatorial optimization, yet they rely on end-to-end learning and lack explicit problem-solving knowledge, limiting solution quality. In this paper, we propose a knowledge-embedded framework inspired by the Route-First Cluster-Second heuristics. It incorporates knowledge at two levels: (1) decomposing CVRPs into the route-first and cluster-second subproblems, and (2) leveraging dynamic programming to solve the second subproblem, whose results guide the RL-based constructive solver to solve the first problem. To mitigate partial observability caused by problem decomposition, we introduce a unified history-enhanced context processing module. Extensive experiments show that this framework achieves superior solution quality compared with state-of-the-art learning-based methods, with a smaller gap to classical heuristics, demonstrating strong generalization across diverse CVRP variants.

Wen Wang, Xiangchen Wu, Liang Wang +2

Nanjing University

Reinforcement Learning Vehicle Routing RL for Combinatorial Optimization Neural Combinatorial Optimization

May 13, 2026cs.AI

An Agentic AI Framework with Large Language Models and Chain-of-Thought for UAV-Assisted Logistics Scheduling with Mobile Edge Computing

In cloud manufacturing, unmanned aerial vehicles (UAVs) can support both product collection and mobile edge computing (MEC). This joint operation forms a hybrid scheduling problem, where physical logistics decisions are coupled with computational task scheduling. In this paper, UAVs collect finished products from manufacturing stations and transport them back to a central depot. Meanwhile, computational tasks generated by industrial sensor devices at these stations are processed locally, at UAVs, or offloaded via UAVs to the cloud. This coupling makes the problem challenging. A UAV can provide MEC services only during its service window at a station, so routing decisions directly determine when UAV-assisted offloading is available. Routing decisions also affect the UAV energy budget and the availability of onboard computing and communication resources for computational task execution under task deadline constraints. To address this, we propose an agentic-AI-assisted optimization framework with two components. First, we develop an agentic AI that combines large language models, retrieval-augmented generation, and chain-of-thought reasoning to translate user input into an interpretable mathematical formulation for the hybrid scheduling problem. Second, we design a hierarchical deep reinforcement learning approach based on proximal policy optimization (PPO), where the upper layer learns UAV routing and the lower layer optimizes per-slot task execution and resource allocation. Simulation results show that the proposed framework yields more consistent formulations, while the hierarchical PPO achieves full product collection in 99.6% of the last 500 episodes and maintains a 100% deadline satisfaction rate, with more stable performance than the advantage actor-critic approach.

Hanwen Zhang, Dusit Niyato, Wei Zhang +2

College of Computing and Data Science, Nanyang Technological University, Singapore, 639798, Singapore · Information and Communications Technology Cluster, Singapore Institute of Technology, Singapore, 828608, Singapore

Large Language Model-Guided Optimization Edge Computing Vehicle Routing Edge-Cloud Computing

May 12, 2026cs.AI

Rethinking Positional Encoding for Neural Vehicle Routing

Transformer-based models have become the dominant paradigm for neural combinatorial optimization (NCO) of vehicle routing problems (VRPs), yet the role of positional encoding (PE) in these architectures remains largely unexplored. Unlike natural language, where tokens are uniformly spaced on a line, routing solutions exhibit several properties that render standard NLP positional encodings inadequate. In this work, we formalize three such structural properties that a routing-aware PE should respect, namely anisometric node distances, cyclic and direction-aware topology, and hierarchical depot-anchored global multi-route structure, combining them with a unifying design principle of geometric grounding. Guided by these criteria, we analyze and compare PE methods spanning NLP, graph-transformer, and routing-specific families, and propose a hierarchical anisometric PE that combines a distance-indexed, circularly consistent in-route encoding with a depot-anchored angular cross-route encoding. Extensive experiments across diverse VRP variants demonstrate that geometry-grounded PE consistently outperforms index-based alternatives, with gains that transfer across problem variants, model architectures, and distribution shifts.

Chuanbo Hua, Federico Berto, Andre Hottung +8

KAIST · Radical Numerics · Bielefeld University +3

Vehicle Routing Positional Encoding Neural Combinatorial Optimization

May 11, 2026cs.AI

Rethinking Constraint Awareness for Efficient State Embedding of Neural Routing Solver

Heavy-Encoder-Light-Decoder (HELD) neural routing solvers have emerged as a promising paradigm due to their broad applicability across multiple vehicle routing problems (VRPs). However, they typically struggle with VRP variants with complex constraints. To address this limitation, this paper systematically revisits existing neural solvers from the perspective of the generation mechanism for state embeddings (i.e., query vector prior to compatibility calculation) during decoding. We identify that current mechanisms restrict the observation space during attention computation, introducing a key bottleneck to achieving high-quality solutions. Through detailed empirical analysis, we demonstrate the necessity of preserving a global observation space. To overcome the constraint-agnostic drawback inherent to global observation spaces, we propose a simple yet powerful Constraint-Aware Residual Modulation (CARM) module. By adaptively modulating the context embedding with constraint-relevant variables, CARM effectively enhances constraint awareness, enabling the neural solver to fully leverage the global observation space and generate an efficient state embedding. Extensive experimental results across two single-task and five multi-task neural routing solvers confirm that the CARM module consistently boosts baseline performance. Notably, solvers equipped with our CARM achieve substantial improvements in scaling to large-scale instances and in generalizing to unseen VRP variants. These findings provide valuable insights for the architectural design of neural routing solvers.

Canhong Yu, Changliang Zhou, Rongsheng Chen +2

College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, China · School of Automation and Intelligent Manufacturing, Southern University of Science and Technology, Shenzhen, China · Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and Technology, Southern University of Science and Technology, Shenzhen, China +1

Neural Network Optimization Combinatorial Optimization Vehicle Routing Neural Combinatorial Optimization

May 10, 2026cs.LG

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

The Capacitated Vehicle Routing Problem (CVRP) underpins modern last-mile logistics, where routing decisions recur over the same fixed service area, like a city. In this setting, routing problems share a fixed set of potential customer locations, while active customers and demands vary between instances. We study how this spatial support can be exploited through reusable learned representations and design our method around three symmetries of the symmetric Euclidean CVRP:

E(2)

transformations, vehicle-route permutations, and tour reversal. We introduce Neural Cluster-First--Route-Second (CFRS), a neural extension of the Fisher--Jaikumar framework that predicts seed-selection scores and customer-to-cluster assignment costs non-autoregressively and respects the three symmetries. A differentiable entropic optimal transport layer provides capacity-aware supervision and guides discrete capacitated assignment, followed by independent traveling salesman subproblems for route recovery. Component ablations show consistent benefits from learned seed selection, while learned assignment costs perform best near the training size and classical FJ costs perform better at larger sizes under exact decoding. On the fixed-support distribution with constant capacity, a model trained on

N=100

achieves a

3.77\%

routing gap relative to HGS at

N=1000

without retraining. A shallow variant with one attention layer in each transformer achieves a

5.08\%

gap at this scale, with spatial embeddings consistently improving routing quality over raw coordinates. Embedding interpolation further accommodates entirely unseen customer locations without retraining. On standard CVRP benchmarks, a separately trained model achieves a

2.73\%

routing gap relative to LKH-3 at

N=100

.

Samuel J. K. Chin, Maximilian Schiffer

MIT · TUM

Vehicle Routing Neural Combinatorial Optimization