CS Paper Radar

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

Andrew Meighan, Hyungsub Kim, Or Dantsker

cs.RO cs.MA ·submitted 2026-09-30 01:44 UTC · v1
theory

Abstract

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.

Comment
2026 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works

Closest papers

Nearest neighbours by meaning across the whole index.

HiRAD: A Flexible Large-Scale AGV Routing System

cs.RO cs.AI ·2026-09-09 ·Yunjie Huang, Ruizhong Wu, Mengxuan Zhang, Frodo Kin Sun Chan, Yan Nei Law +1 more
similarity 0.67
Abstract

Automatic Guided Vehicles (AGVs) substantially boost warehouse throughput, but routing large-scale AGV fleets remains challenging. Classical Multi-Agent Pathfinding solvers suffer from exploding combinatorial complexity and super-quadratic runtime, while relying on idealized grid or piecewise-linear motion models that mismatch real-world kinematics. Recent Reinforcement Learning (RL) solutions improve flexibility via decentralized agent policies but depend on discretized spatiotemporal representations, require millions of episodes to converge, and incur full-map observation at every step, which leads to large models, slow convergence, and high inference latency that violates real-time industrial control constraints. To address these bottlenecks, we propose HiRAD, a hierarchical RL framework for continuous-space AGV routing with real-time guarantees: (1) a step-level spatiotemporal representation that translates continuous motion into a differentiable RL problem, (2) a hierarchical strategy that splits heading choice from velocity control to reduce the action space, and (3) an asynchronous event-driven decision pipeline that lowers inference complexity from O(n^2) to O(n) and cuts per-step latency by as much as 71 percent. Across random graphs and two warehouse maps, HiRAD reduces makespan by 45 percent to 63 percent and shortens end-to-end runtime.

0.12

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

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

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

0.15

Synergizing Drone Delivery Order Pooling and Road Network Monitoring through Monitoring-Task Orderization

cs.MA cs.LG ·2026-10-04 ·Yulong Hu, Meng Xu, Sen Li, Nikolas Geroliminis
similarity 0.64
Abstract

This paper investigates the real-time dispatch of a shared drone fleet for on-demand food delivery and urban road network monitoring. We consider a courier-drone collaborative setting in which couriers transport orders to launchpads and drones complete the final delivery leg to kiosks. Drones may consolidate multiple origin-destination orders within one flight and make monitoring-aware route adjustments to collect real-time traffic information subject to delivery-time constraints. This yields a joint decision problem coupling dynamic order-to-drone matching, multi-order pooling, routing, and time-varying monitoring under fleet-level competition and uncertainty. We propose monitoring-task orderization, which periodically converts road-network nodes with high congestion and stale information into virtual monitoring orders. Pooling these virtual tasks with food-delivery orders creates a unified heterogeneous task set and transforms the coupled matching-and-routing problem into an order-level decision process. Building on this abstraction, we formulate a decentralized graph-interdependent Multi-Agent Markov Decision Process and develop Graph Multi-Agent Q-Learning (Graph-MAQL), which captures localized inter-agent dependencies through bipartite match coordination graphs. Agent-task value estimates are then used as edge weights in a dynamic heterogeneous bipartite matching program for globally feasible execution. Experiments using real-world data reveal strong operational synergy between delivery and monitoring. Monitoring-task orderization improves monitoring performance by 25.1% with less than a 1% reduction in delivery performance, while Graph-MAQL improves the aggregate objective by up to 20.8%, reduces deadline violations by over 40%, and transfers zero-shot to higher demand intensity without retraining.

0.18

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

PACT: Plan-Augmented Coordination via Trace-Graphs for Dynamic Multi-Agent Combinatorial Optimization

cs.LG ·2026-10-19 ·Xiao Zhou, Alex Schutz, Victor-Alexandru Darvariu, Nick Hawes
similarity 0.64
Abstract

Multi-agent approaches have been investigated recently as a means of improving the scalability of reinforcement learning for neural combinatorial optimization. Existing methods assume that all problem instance information is known upfront. However, real-world problems are often dynamic: relevant information is progressively revealed as the agents take actions (e.g., arriving at an edge in a routing problem only to discover it is untraversable). In such cases, existing methods fail to coordinate agents to explore and exploit the progressively revealed information. To address the arising coordination challenge, we introduce PACT (Plan-Augmented Coordination via Trace-graphs). PACT augments the environment graph with auxiliary nodes representing the plans of agents, which are connected to the resource nodes to indicate future dependencies. The proposed message-passing scheme over the augmented graph grounds inter-agent coordination in the environment and enables proactive, rather than reactive, conflict resolution. We show that PACT improves solution quality in dynamic problems relative to baselines and exhibits the best transfer to larger instances on which, remarkably, it outperforms centralized oracles with privileged access to instance uncertainty.

0.20

Route Anything: A Study of Model and Policy Routing for General-Purpose AI Systems

cs.CV ·2026-11-03 ·Pengfei Zhou, Yixing Ma, Hexin Wang, Weidong Tang, Zhenglin Wan +2 more
community pick similarity 0.64
Abstract

Artificial general intelligence (AGI) requires a method that can understand, generate, reason, and act across diverse domains and modalities. Rather than relying on a single model to master every capability, a promising path toward AGI now is to orchestrate a heterogeneous ecosystem of specialized models, tools, and policies (candidates) into a unified AI system. At the heart of this vision lies a fundamental question: how can an AI system dynamically select and coordinate the most capable candidate for each task while balancing performance and computational cost? In this work, we present Route Anything, a unified framework for studying model and policy routing across general-purpose AI systems. We develop a unified theoretical foundation that characterizes optimal routing under quality--cost trade-offs and establishes how the information available to a router determines its attainable performance. To systematically investigate routing across diverse capabilities, we first construct an omni-modal trajectory matrix spanning 25 benchmarks across language understanding, image, video, and speech generation, coding and workplace agents, and robotic manipulation, comprising 374,401 scored runs from 452 candidate configurations. Building on this framework, we train and test different routers to investigate the potential of omni-modal model routing, the capabilities of learned routers, and the conditions under which routing improves efficiency. Our results reveal substantial opportunities for capability orchestration: per-input oracle routing outperforms the best fixed candidate by 5.4 points, and learned routers outperform it by 0.3 points across 16 benchmarks, by 2.1 points on video generation, and by 1.1 points on robot manipulation while using 24% less policy time. More importantly, routing raises efficiency by 8.82x on average compared with the reference model.

0.25

Reinforcement Learning Based Heterogeneous Task Allocation Under Spatio-Temporal Environmental Uncertainty for Multi-Robot Teams

cs.RO ·2026-10-11 ·Xi Lin, Yaxuan Li, Paul Szenher, Brendan Englot
similarity 0.64
Abstract · The 2026 IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR 2026)

Autonomous Surface Vehicles (ASVs) have been increasingly deployed to perform different kinds of maritime tasks in recent years, which motivates the need for a reliable task allocation policy that can adapt to heterogeneous tasks and maritime disturbances. In this work, we formulate a multi-robot task allocation problem in which a team of ASVs with heterogeneous capabilities needs to complete tasks of different types and appearance times under unknown stochastic spatio-temporal uncertainties from maritime disturbances. We propose a decentralized Reinforcement Learning (RL) based policy network that is trained to be robust towards uncertainty-induced observation deviations, and is able to perform individual decision making that leads to efficient execution behaviors toward heterogeneous task requirements. We evaluate the proposed policy and four baseline methods in simulated experiments with varied proportions of different tasks types, numbers of tasks, robot species and robots per species. Experiment results show that our proposed policy achieves the lowest makespan and can be deployed to address scenarios with 100 robots and 400 tasks.

0.23

Agentic AI Enabling Autonomous, Self-Organizing, and Evolving UAV Networks

eess.SY ·2026-09-21 ·Zhaoyang Li, Xingzhi Jin, Zijiu Yang, Qianqian Yang, Zhiguo Shi
similarity 0.63
Abstract

As low-altitude applications expand across emergency response, intelligent transportation, and autonomous operations, they demand communication networks that can deliver flexible, resilient, and rapidly deployable connectivity. Heterogeneous UAV networks are a promising solution, as they can dynamically provide sensing, access, relay, and backhaul functions. Yet, most existing approaches assume predefined missions, prior knowledge of user distributions, and manually configured infrastructure, making them ill suited to dynamic and initially unknown environments. Addressing this limitation requires a shift from mission-oriented UAV deployment to autonomous network formation, in which UAVs continuously perceive their surroundings, infer evolving service demands, and self-organize network resources. Agentic AI, empowered by large language models (LLMs), offers a new foundation for this shift by integrating closed-loop perception, reasoning, planning, and execution across heterogeneous information sources. Unlike conventional optimization and learning methods designed for individual networking tasks, agentic AI can coordinate these capabilities to support sustained, network-level autonomy. In this article, we explore agentic AI for autonomous and self-organizing heterogeneous UAV networks in low-altitude environments. Our key contribution is an LLM-assisted architecture in which a base-station-hosted agent conducts global network reasoning and autonomously reconfigures access and backhaul infrastructure. The proposed system explores unknown environments, discovers users, and deploys UAVs on demand to provide access and establish end-to-end backhaul connectivity. A case study illustrates how this agentic-AI-driven approach can transform UAVs from task-specific platforms into a continuously evolving communication network.

0.04