Multi-Agent Route Planning as a QUBO Problem
- URL: http://arxiv.org/abs/2602.07913v1
- Date: Sun, 08 Feb 2026 11:18:45 GMT
- Title: Multi-Agent Route Planning as a QUBO Problem
- Authors: Renáta Rusnáková, Martin Chovanec, Juraj Gazda,
- Abstract summary: This paper gives a formal problem definition, proves NP-hardness by reduction from the Weighted Set Packing problem, and derives a Quadratic Unconstrained Binary Optimization formulation.<n>A single penalty parameter controls the coverage-overlap trade-off.<n>Experiments on Barcelona instances with up to 10 000 vehicles reveal a clear coverage-overlap knee.
- Score: 0.39325957466009204
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-Agent Route Planning considers selecting vehicles, each associated with a single predefined route, such that the spatial coverage of a road network is increased while redundant overlaps are limited. This paper gives a formal problem definition, proves NP-hardness by reduction from the Weighted Set Packing problem, and derives a Quadratic Unconstrained Binary Optimization formulation whose coefficients directly encode unique coverage rewards and pairwise overlap penalties. A single penalty parameter controls the coverage-overlap trade-off. We distinguish between a soft regime, which supports multi-objective exploration, and a hard regime, in which the penalty is strong enough to effectively enforce near-disjoint routes. We describe a practical pipeline for generating city instances, constructing candidate routes, building the QUBO matrix, and solving it with an exact mixed-integer solver (Gurobi), simulated annealing, and D-Wave hybrid quantum annealing. Experiments on Barcelona instances with up to 10 000 vehicles reveal a clear coverage-overlap knee and show that Pareto-optimal solutions are mainly obtained under the hard-penalty regime, while D-Wave hybrid solvers and Gurobi achieve essentially identical objective values with only minor differences in runtime as problem size grows.
Related papers
- Assignment-Routing Optimization: Solvers for Problems Under Constraints [0.0]
We study the Joint Routing-Assignment (JRA) problem in which items must be assigned one-to-one to placeholders.<n>We develop a solver tailored for practical packaging-planning scenarios with richer constraints.<n>Results highlight the practical applicability of MIP-based JRA optimization for robotic packaging, motion planning, and complex logistics.
arXiv Detail & Related papers (2025-12-21T06:32:31Z) - QoS-Aware Hierarchical Reinforcement Learning for Joint Link Selection and Trajectory Optimization in SAGIN-Supported UAV Mobility Management [52.15690855486153]
A space-air-ground integrated network (SAGIN) has emerged as an essential architecture for enabling ubiquitous UAV connectivity.<n>This paper formulates UAV mobility management in SAGIN as a constrained multiobjective joint optimization problem.
arXiv Detail & Related papers (2025-12-17T06:22:46Z) - Rich Vehicle Routing Problem in Disaster Management enabling Temporally-causal Transhipments across Multi-Modal Transportation Network [1.1470070927586018]
A rich vehicle routing problem is considered, allowing multiple trips of heterogeneous vehicles stationed at geographically distributed vehicle depots having access to different modes of transportation.<n>The problem arises from the real-world requirement of optimizing the disaster response time by minimizing the makespan of vehicular routes.<n>The superiority of the proposed cascaded minimization approach is demonstrated through our developed Mixed-Integer Linear Programming formulation.
arXiv Detail & Related papers (2025-09-16T16:37:18Z) - Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning [56.240199425429445]
Multi-Robot Motion Planning (MPMP) involves generating trajectories for multiple robots operating in a shared continuous workspace.<n>While discrete multi-agent finding (MAPF) methods are broadly adopted due to their scalability, their coarse discretization trajectory quality.<n>This paper tackles limitations of two approaches by introducing discrete MAPF solvers with constrained generative diffusion models.
arXiv Detail & Related papers (2025-08-27T17:59:36Z) - Arc Routing Problems with Multiple Trucks and Drones: A Hybrid Genetic Algorithm [0.41292255339309664]
Rural Postman Problem (RPP) is a fundamental variant in which a subset of edges or arcs in a network must be traversed.<n>This paper investigates a generalized form of the RPP, called RPP-mTD, which involves a fleet of multiple trucks, each carrying multiple drones.<n>We propose a Hybrid Genetic Algorithm (HGA) that combines population-based exploration with targeted neighborhood searches.
arXiv Detail & Related papers (2025-08-25T15:10:46Z) - Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
We propose SEQUOIA, an RL algorithm that directly optimize for long-term reward over the feasible action space.<n>We empirically validate SEQUOIA on four novel restless bandit problems with constraints: multiple interventions, path constraints, bipartite matching, and capacity constraints.
arXiv Detail & Related papers (2025-03-01T21:25:21Z) - Joint Transmit and Pinching Beamforming for Pinching Antenna Systems (PASS): Optimization-Based or Learning-Based? [89.05848771674773]
A novel antenna system ()-enabled downlink multi-user multiple-input single-output (MISO) framework is proposed.<n>It consists of multiple waveguides, which equip numerous low-cost antennas, named (PAs)<n>The positions of PAs can be reconfigured to both spanning large-scale path and space.
arXiv Detail & Related papers (2025-02-12T18:54:10Z) - Multi-Agent Path Finding in Continuous Spaces with Projected Diffusion Models [57.45019514036948]
Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics.<n>This work proposes a novel approach that integrates constrained optimization with diffusion models for MAPF in continuous spaces.
arXiv Detail & Related papers (2024-12-23T21:27:19Z) - Multi-Tour Set Traveling Salesman Problem in Planning Power Transmission
Line Inspection [8.202492922523591]
The problem is formulated for an inspection vehicle with a limited travel budget.
The optimal solution of the problem is solved by the proposed Linear Programming (ILP) formulation.
The algorithms are demonstrated in a real-world scenario to inspect power line segments at the electrical substation.
arXiv Detail & Related papers (2023-02-02T15:59:46Z) - Multi-Agent Chance-Constrained Stochastic Shortest Path with Application
to Risk-Aware Intelligent Intersection [15.149982804527182]
A formidable challenge for existing automated intersections lies in detecting and reasoning about uncertainty from the operating environment and human-driven vehicles.
We propose a risk-aware intelligent intersection system for autonomous vehicles (AVs) as well as human-driven vehicles (HVs)
arXiv Detail & Related papers (2022-10-03T06:49:23Z) - Fidelity-Guarantee Entanglement Routing in Quantum Networks [64.49733801962198]
Entanglement routing establishes remote entanglement connection between two arbitrary nodes.
We propose purification-enabled entanglement routing designs to provide fidelity guarantee for multiple Source-Destination (SD) pairs in quantum networks.
arXiv Detail & Related papers (2021-11-15T14:07:22Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination.
We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
arXiv Detail & Related papers (2020-05-27T01:10:41Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.