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

Andrew Meighan; Hyungsub Kim; Or Dantsker

cs.ROSep 30, 2026

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

Authors: Andrew Meighan, Hyungsub Kim, Or Dantsker

Organizations: Department of Intelligent Systems Engineering, Indiana University Bloomington · Department of Computer Science, Indiana University Bloomington

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.

Figures & tables

Panel of Figure 1 — Fig. 1: Comparison of fleet routing strategies in partially observable wildfire monitoring scenario. Black flames denote fires known a priori, while red flames indicate fires discovered during flight. (a) Traditional offline solvers require a costly second deployment (red dashed line) to visit new observations. (b) HALO enables dynamic, decentralized rerouting which dramatically improves coverage speed.

Fig. 2: Overview of HALO’s work flow and architecture consisting of three different components: ( 1 ) Heterogeneous Graph Construction, ( 2 ) Hybrid GNN Allocation, and ( 3 ) Heuristic Routing Execution.

	# Tasks
Method	50		100		600		800		1000
	$L(\Sigma)$	T(s)	$L(\Sigma)$	T(s)	$L(\Sigma)$	T(s)	$L(\Sigma)$	T(s)	$L(\Sigma)$	T(s)
Google OR-Tools (1s)	2.42	1.0	4.37	1.0	$\times$	$\times$	$\times$	$\times$	$\times$	$\times$
Google OR-Tools (2s)	2.12	2.0	3.79	2.0	$\times$	$\times$	$\times$	$\times$	$\times$	$\times$
Google OR-Tools (1800s) [ 12 ]	2.03	3.60	2.27	36.128	9.64	1800	12.34	1800	14.84	1800
ScheduleNet (g.) [ 18 ]	1.98	–	2.07	–	–	–	–	–	–	–

TABLE I: Performance comparison on the offline, single-depot VRP at small-scale (

50

100

tasks) and large-scale (

600

800

1{,}000

tasks).

L(\Sigma)

is the average makespan and

T(s)

is the average time to output a solution. The symbols (–), (

\times

), and (*) denote unreported results, solution failures, and our proposed method, respectively.

		# Robots, # Tasks
Method	Hidden %	10, 100		10, 500		10, 1000		50, 1000		100, 1000
		$L(\Sigma)$	T(s)	$L(\Sigma)$	T(s)	$L(\Sigma)$	T(s)	$L(\Sigma)$	T(s)	$L(\Sigma)$	T(s)
OR-Tools (RH)	0%	6.20	1.00	9.95	1.00	14.32	1.00	$\times$	$\times$	$\times$	$\times$
	25%	6.30	1.00	8.12	1.00	12.25	1.00	$\times$	$\times$	$\times$	$\times$
	50%	7.07	1.00	8.01	1.00	13.339	1.00	$\times$	$\times$	$\times$	$\times$
HALO (Online)*	0%	2.74	0.011	4.17	0.104	5.11	0.105	2.56	0.105	2.05	0.105

TABLE II: Performance comparison on the online, multi-depot VRP across varying percentages of hidden tasks and problem sizes.

L(\Sigma)

indicates the average makespan. Here,

T(s)

represents the average replanning time. The symbols (

\times

), and (*) represent solution failures, and our proposed method.

Explore similar work

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 Problem Unmanned Aerial Vehicle Trajectories Metaheuristics Heuristics

Ask PDF

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

Vehicle Routing Problem Multi-Agent Path Finding Neural Solvers

Ask PDF

May 5, 2026cs.MA

ARMATA: Auto-Regressive Multi-Agent Task Assignment

Coordinating multi-agent systems over spatially distributed areas requires solving a complex hierarchical problem: first distributing areas among agents (allocation) and subsequently determining the optimal visitation order (routing). Existing methods typically decouple these stages ignoring inter-stage dependencies or rely on decentralized heuristics that lack global context. In this work, we propose a centralized, fully end-to-end auto-regressive framework that jointly generates allocation decisions and routing sequences. The core contribution of our approach is a multi-stage decoding mechanism that unifies high-level allocation and low-level routing in a single autoregressive pass while maintaining a centralized global state. This enables the model to implicitly balance workload distribution with routing efficiency, avoiding local optima common in decentralized methods. Extensive experiments demonstrate that our method significantly outperforms diverse baselines, achieving up to a 20% improvement in solution quality over industrial solvers such as Google OR-Tools, IBM CPLEX, and LKH-3, while reducing computation time from hours to seconds.

Yazan Youssef, Aboelmagd Noureldin, Sidney Givigi

Department of Electrical and Computer Engineering, Queen’s University, Kingston, ON, Canada · Department of Electrical and Computer Engineering at the Royal Military College of Canada, and the Department of Electrical and Computer Engineering at Queen’s University, both in Kingston, Canada · School of Computing, Queen’s University, Kingston, ON, Canada

Repair-Assignment Problem Autoregressive Model

Ask PDF