Multi-Agent Route Planning as a QUBO Problem

Juraj Gazda; Martin Chovanec; Ren\'ata Rusn\'akov\'a

REVIEW 2 major objections 6 minor 24 references

The paper claims that the fleet-selection problem in multi-agent route planning is NP-hard, and that it can be solved exactly as a QUBO whose diagonal entries are coverage rewards and off-diagonal entries are λ-scaled overlap penalties; hyb

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 03:26 UTC pith:ZYMFNNXZ

load-bearing objection Useful QUBO benchmark, but the objective doesn't maximize union coverage and the NP-hardness proof is invalid under the paper's own u_i definition. the 2 major comments →

arxiv 2602.07913 v2 pith:ZYMFNNXZ submitted 2026-02-08 cs.RO quant-ph

Multi-Agent Route Planning as a QUBO Problem

Ren\'ata Rusn\'akov\'a , Martin Chovanec , Juraj Gazda This is my paper

classification cs.RO quant-ph

keywords multi-agent route planningQUBONP-hardnessweighted set packingquantum annealinghybrid solvercoverage–overlap trade-offurban fleet planning

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper is trying to establish that the core decision in multi-agent route planning — which predefined routes to deploy so that road-network coverage is maximized while redundant overlaps are limited — can be cast exactly as a Quadratic Unconstrained Binary Optimization (QUBO) problem. It proves the problem NP-hard by a reduction from Weighted Set Packing, then defines a QUBO matrix where each diagonal entry is a route's exclusive coverage reward and each off-diagonal entry is λ times the shared-element count between two routes. A single penalty parameter λ controls the coverage–overlap trade-off, with a soft regime for multi-objective exploration and a hard regime that effectively enforces disjoint routes. On Barcelona instances up to 10,000 vehicles, the paper reports that D-Wave's hybrid quantum annealer finds objective values identical to those of the exact solver Gurobi, with runtime scaling comparably as the problem grows.

Core claim

Central claim: the MaRP problem (1) is NP-hard, and its optimal solutions are exactly the minimizers of the QUBO f(x) = -∑ u_i x_i + λ ∑ c_ij x_i x_j with Q_ii = -u_i and Q_ij = λ c_ij. The coefficients are interpretable: diagonals are exclusive-coverage counts, off-diagonals are λ times shared-element counts. Under λ_hard = 1 + ∑ u_i, overlapping routes are never optimal, so the QUBO reduces to weighted set packing. On Barcelona instances the paper observes a clear coverage–overlap knee, with nearly all Pareto-optimal solutions coming from the hard-penalty regime, and reports that hybrid quantum annealing matches Gurobi's objective values from 100 to 10,000 vehicles.

What carries the argument

The load-bearing construction is the QUBO matrix Q together with the penalty parameter λ. Every candidate route is a binary variable; the diagonal Q_ii = -u_i encodes the coverage reward of selecting the route, and the off-diagonal Q_ij = λ c_ij for i<j encodes the pairwise overlap penalty. λ has two regimes: a soft value λ_soft = median_i(∑_{j≠i} c_ij) / max(1, median_i u_i), meant to balance the objectives, and a hard value λ_hard = 1 + ∑_i u_i, which makes overlap effectively a hard constraint. The NP-hardness proof works by reducing Weighted Set Packing to MaRP and setting λ = λ_hard so that any optimal solution must be disjoint, thereby reducing the QUBO objective to the set-packing obj

Load-bearing premise

The formulation assumes that rewarding each selected route by its precomputed unique-element count u_i — independent of which other routes are chosen — correctly prices a route's contribution to network coverage; since real marginal coverage depends on the selected set, a soft-penalty solution may maximize the written objective without maximizing true covered area.

What would settle it

Take any small instance with three routes where route A overlaps both B and C while B and C are disjoint. Enumerate all subsets, compute the QUBO objective (5) and the true union coverage for each. If, for some soft λ, the QUBO-minimizing subset has lower union coverage than another feasible subset with higher QUBO energy, the additive reward misprices coverage. The same test can be run on a Barcelona instance by comparing the QUBO solution's Pct_cov with that of a greedy marginal-coverage heuristic.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

Since MaRP is NP-hard, no polynomial-time exact algorithm is expected; the QUBO formulation hands the problem to a large existing ecosystem of QUBO/Ising solvers, both classical and quantum.
Setting λ to its hard value turns the same QUBO into a weighted set-packing solver, so the implementation can be reused for other set-packing tasks.
The reproducible coverage–overlap knee (coverage grows rapidly to 75–85% before overlap starts climbing) gives planners a quantitative curve for deciding how many vehicles can be deployed at a given redundancy budget.
If hybrid quantum annealing matches Gurobi's objective values at these scales, fleet operators can obtain high-quality route selections without relying on a commercial exact solver, using cloud quantum-classical services.
The distinction between soft and hard regimes means one formulation supports both exploratory multi-objective analysis (sweeping λ) and near-disjoint selections (λ_hard), so the same codebase serves both planning questions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The static rewards u_i are precomputed against the full set of candidate routes; for a chosen subset, a route's true marginal coverage depends on which other routes are selected. A street shared by a selected and an unselected route still counts as coverage on the ground but contributes to no u_i, so in the soft regime the additive objective can diverge from the union coverage reported as Pct_cov.
The reported equivalence between hybrid quantum annealing and Gurobi is for objective (energy) values; a stronger test would compare the actual selected route sets and the resulting Pct_cov/Pct_ov metrics, since identical energies can correspond to different deployments with different operational consequences.
The hard-penalty regime dominating the Pareto frontier suggests the soft regime is mostly a search device; a follow-up could design a λ schedule that crosses the knee to find the minimal overlap cost for each coverage target, which is what an operator would actually want.
Because the model intentionally ignores time and capacity, an immediate extension preserving the QUBO form would be adding per-node capacity constraints as quadratic penalty terms; the paper's pipeline already computes the node usage statistics needed to calibrate those penalties.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Useful QUBO benchmark, but the objective doesn't maximize union coverage and the NP-hardness proof is invalid under the paper's own u_i definition.

read the letter

This paper is a useful empirical benchmark with a load-bearing modeling flaw. The QUBO encoding is a direct rewrite of objective (1), and the Barcelona study with up to 10k vehicles gives real evidence that D-Wave hybrid can match Gurobi on these instances. The coverage-overlap knee and runtime scaling are plausible and worth reporting.

The flaw starts in Section 2. They define u_i as the number of elements unique to vehicle i among the entire fleet. That means the linear term rewards only elements that appear in exactly one route. Any element shared by two or more routes never contributes to u_i, so the objective is not the union coverage they report as Pct_cov. The thing they optimize is different from the thing they measure. This is fixable: redefine u_i as an arbitrary weight with a proper marginal-coverage interpretation or explicitly frame the linear term as a heuristic surrogate.

That same definition invalidates Theorem 3.1. The reduction from WSP sets u_i := w_i for arbitrary weights, but MaRP forces u_i to be an exclusive count. A two-set counterexample shows the reduction cannot preserve optimality (e.g., S1={a}, S2={a,b}, w1=100, w2=1 forces u=(0,1), not (100,1)). So NP-hardness is proven only for a generalized MaRP, not the problem defined in Section 2. The real problem might still be NP-hard, but this proof doesn't show it.

The empirical details need work: the code is only 'available upon request', there are no error bars or per-instance values, and the D-Wave and Gurobi numbers are close but not identical on the largest cases. These are minor and fixable.

The modeling inconsistency and broken reduction are major flaws, but the empirical pipeline and the QUBO formulation are salvageable. I'd send this to review with the expectation of heavy revision, because the benchmark itself has value.

To summarize: read this for the Barcelona experiments and the direct QUBO construction, not for the theory. If the authors fix the objective definition and release the code, it becomes citable.

Referee Report

2 major / 6 minor

Summary. The paper formalizes Multi-Agent Route Planning (MaRP) as selecting a subset of vehicles with precomputed routes to maximize a linear coverage reward minus a quadratic overlap penalty, encoded as a QUBO. It claims NP-hardness via a reduction from Weighted Set Packing, derives Q_ii = -u_i and Q_ij = λ c_ij, distinguishes soft and hard penalty regimes, and reports experiments on Barcelona networks comparing Gurobi, simulated annealing, and D-Wave hybrid quantum annealing. The main empirical claim is that D-Wave hybrid matches Gurobi's objective values with comparable runtime on instances up to 10,000 vehicles.

Significance. The paper addresses a relevant practical problem and the QUBO encoding itself is clean and interpretable; the soft/hard penalty taxonomy and the real-world OSM/Valhalla pipeline are useful engineering contributions. The comparison of an exact solver, SA, and a quantum hybrid on large QUBOs is a valuable benchmark. However, the formal results are not currently established: the stated definition of u_i makes the objective inconsistent with the reported coverage metric, and the hardness proof as written treats u_i as an arbitrary input rather than as a derived quantity. If these definitional issues are corrected, the paper could be a useful contribution to the QUBO route-selection literature.

major comments (2)

[Section 2, Eq. (1) and Section 5.3, Eq. (14)] Section 2 defines u_i = |{e∈S_i : e∉S_j for all j≠i}|, i.e., the number of elements of route i that are unique within the full candidate fleet. With this definition, Eq. (1) does not maximize the coverage measure later reported as Pct_cov in Eq. (14). An element e that lies in a selected route i and in an unselected route j is covered by the selected route and counted in |N_selected|, but it contributes to no u_k and therefore receives no reward in (1). For instance, if S_1={a,b} and S_2={a}, then u_1=1, u_2=0; selecting vehicle 1 gives objective value 1 while covering two elements. The QUBO (4)-(5) thus optimizes a fleet-relative 'exclusivity' reward, not the union coverage that the paper claims to maximize and measures. All coverage-overlap Pareto statements in Section 6 are therefore not consequences of the solved optimization problem.
[Section 3, Theorem 3.1] The proof sets u_i := w_i for arbitrary WSP weights w_i, but under the Section 2 definition u_i is not an independent input; it is the exclusive element count of the constructed route. For the WSP instance U={a,b}, S_1={a}, S_2={a,b}, w_1=100, w_2=1, the described construction (routes equal to S_i) forces u=(0,1). With λ=1+101=102, the MaRP optimum is x=(0,1) with objective 1, whereas the WSP optimum is x=(1,0) with weight 100. Thus the reduction does not preserve optimality. A valid reduction would need to pad each route with w_i artificial unique elements (or redefine u_i as an independent input); the paper does neither. As written, Theorem 3.1 establishes hardness only for a generalized MaRP with arbitrary linear route rewards, not for the problem defined in Section 2.

minor comments (6)

[Section 4.1, Eq. (3)-(4)] The text states that Q is a symmetric matrix, but then defines Q_ij only for i<j and uses f(x)=Σ_i Q_ii x_i + Σ_{i<j} Q_ij x_i x_j. For a symmetric matrix, x^T Q x would double the off-diagonal coefficient. Clarify the QUBO convention (upper-triangular vs. symmetric) and ensure the implementation matches it; otherwise the effective λ in the experiments is ambiguous.
[Section 5.3, Eq. (14)] Define N_pre-optimization explicitly. If it is the union of nodes of all candidate routes, Pct_cov measures coverage relative to the candidate pool, not to the road network. If it is a pre-selected baseline, that baseline should be specified.
[Section 4.2, Eq. (7)] The λ_soft heuristic is data-driven but not derived from any optimization principle. Since median_i u_i can be zero, the denominator max{1, median_i u_i} introduces a discontinuity. A brief justification or a sensitivity check would help.
[Table 1] The table caption says values are averaged over all runs and penalty parameters. Because the QUBO energy scale depends on λ, averaging energies across different λ values is not meaningful. Report per-λ results or clarify what the average represents.
[Section 3, Remark 3.1] The remark claims that the restriction to simple road-network paths 'preserves the pairwise conflict structure' and hence remains intractable. This requires a proof or citation; not every set system can be realized as paths in a road network.
[Section 5.2] Typo: 'nealli' should presumably be 'neal' (D-Wave's simulated annealing library).

Circularity Check

0 steps flagged

No significant circularity: the QUBO is a direct algebraic rewrite of objective (1), the NP-hardness argument is an external reduction, and no fitted parameter is relabeled as a prediction.

full rationale

The derivation chain is self-contained and not circular. Section 4's QUBO is obtained by substituting Q_ii = -u_i and Q_ij = λc_ij into f(x) = x^T Q x, yielding f(x) = -Σu_i x_i + λΣc_ij x_i x_j, which is exactly the negative of objective (1); this is an algebraic reformulation, not a prediction drawn from the model. Theorem 3.1's hardness proof is an external reduction from Weighted Set Packing, not an import of the paper's own conclusions, and the referenced NP-hardness is standard (Karp, Garey–Johnson). λ_soft is a stated data-dependent heuristic and λ_hard is a defined regime; neither is fitted to the reported solver comparison and then relabeled as a prediction. The comparison of hybrid QA with Gurobi is an empirical benchmark, not a circular validation. A possible concern is that the fixed definition u_i = |{e ∈ S_i : e ∉ S_j for all j ≠ i}| restricts the reduction's freedom to set u_i := w_i, and that the additive reward may not equal union coverage; however, these are correctness or soundness issues rather than instances of the model deriving its conclusions from its own inputs. No load-bearing self-citation appears.

Axiom & Free-Parameter Ledger

1 free parameters · 4 axioms · 0 invented entities

The central claim rests on the objective's reward definition being a valid coverage measure and on the WSP reduction. The u_i additivity assumption is the main load-bearing premise and is questionable. No new physical or mathematical entities are introduced.

free parameters (1)

λ (coverage-overlap penalty weight) = λ_soft = median_i s_i / max(1, median_i u_i); λ_hard = 1 + Σ_i u_i
λ is the single knob controlling the trade-off. λ_soft is estimated from instance statistics, and λ_hard is set from the sum of rewards to force disjointness; both are chosen by the authors rather than derived from first principles.

axioms (4)

standard math Weighted Set Packing is NP-hard
Relied upon in Theorem 3.1 via references [10, 11].
domain assumption u_i, the number of elements unique to route i among all vehicles, can be used as an additive coverage reward in objective (1)
Section 2, Eq. (1). This additive-reward assumption is false when a selected route and an unselected route share elements; it is the paper's weakest premise.
domain assumption Pairwise overlap penalties c_ij are a sufficient proxy for congestion/overlap
Section 2; overlaps beyond pairwise (triples, etc.) are not modeled, and the paper acknowledges temporal/capacity details are ignored.
domain assumption The practical restriction to simple paths preserves the pairwise conflict structure and hence NP-hardness
Remark 3.1; asserted without proof that path-realizable set systems preserve hardness.

pith-pipeline@v1.3.0-alltime-deepseek · 10385 in / 20337 out tokens · 202895 ms · 2026-08-03T03:26:33.797367+00:00 · methodology

0 comments

read the original abstract

Multi-Agent Route Planning considers selecting vehicles, each associated with a single predefined route, such that route-level coverage utility is maximized while redundant spatial 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 route utility rewards and pairwise overlap penalties. A single penalty parameter $\lambda$ 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 a binary quadratic programming baseline (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 very similar objective values on matching configurations with only minor runtime differences as problem size grows.

discussion (0)

Reference graph

Works this paper leans on

24 extracted references · 1 canonical work pages

[1]

Approximation algorithms for the set covering and vertex cover problems,

D. S. Hochbaum, “Approximation algorithms for the set covering and vertex cover problems,”SIAM Jour- nal on Computing, vol. 11, no. 3, pp. 555–556, 1982. [Online]. Available: https://doi.org/10.1137/0211045

doi:10.1137/0211045 1982
[2]

Hoffman and M

K. Hoffman and M. Padberg,Set Covering, Packing, and Partitioning Problems. Cham: Springer Nature Switzerland, 2025, pp. 1–7. [Online]. Available: https://doi.org/10.1007/978-3-030-54621-2_599-1

work page doi:10.1007/978-3-030-54621-2_599-1 2025
[3]

Conflict-based search for optimal multi-agent pathfinding,

G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, “Conflict-based search for optimal multi-agent pathfinding,”Artificial Intelligence, vol. 219, pp. 40–66, 2015. [Online]. Available: https://doi.org/10.1016/j.artint.2014.11.006

doi:10.1016/j.artint.2014.11.006 2015
[4]

Multi-agent pathfinding: Definitions, variants, and benchmarks,

R. Stern, N. R. Sturtevant, A. Felner, S. Koenig, H. Ma, T. Walker, J. Li, D. Atzmon, L. Cohen, T. K. S. Kumar, E. Boyarski, and R. Bartak, “Multi-agent pathfinding: Definitions, variants, and benchmarks,” Artificial Intelligence, 2019, arXiv:1906.08291. [On- line]. Available: https://arxiv.org/abs/1906.08291

Pith/arXiv arXiv 2019
[5]

A survey on coverage path planning for robotics,

E. Galceran and M. Carreras, “A survey on coverage path planning for robotics,”Robotics and Autonomous Systems, vol. 61, no. 12, pp. 1258–1276, 2013. [Online]. Available: https: //doi.org/10.1016/j.robot.2013.09.004

doi:10.1016/j.robot.2013.09.004 2013
[6]

A quantum approach for cov- erage path planning in multi-vehicle deployments,

P. U. Rao and B. Sodhi, “A quantum approach for cov- erage path planning in multi-vehicle deployments,” in Proceedings of the IEEE International Conference on Quantum Computing and Engineering (QCE), 2022, pp. 729–732

2022
[7]

Ising formulations of many np problems,

A. Lucas, “Ising formulations of many np problems,” Frontiers in Physics, vol. 2, p. 5, 2014

2014
[8]

Quantum bridge analytics i: A tutorial on formulating and us- ing qubo models,

F. Glover, G. Kochenberger, and Y . Du, “Quantum bridge analytics i: A tutorial on formulating and us- ing qubo models,”4OR, vol. 17, pp. 1–20, December 2019

2019
[9]

Quantum annealing in the transverse ising model,

T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse ising model,”Physical Review E, vol. 58, no. 5, pp. 5355–5363, 1998

1998
[10]

R. M. Karp,Reducibility Among Combinato- rial Problems. Boston, MA: Springer US, 1972, pp. 85–103. [Online]. Available: https: //doi.org/10.1007/978-1-4684-2001-2_9

doi:10.1007/978-1-4684-2001-2_9 1972
[11]

M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP- Completeness, 1st ed. San Francisco, CA: W. H. Freeman, 1979

1979
[12]

A. P. Punnen, Ed.,The Quadratic Unconstrained Bi- nary Optimization Problem. Cham: Springer Nature Switzerland, 2022

2022
[13]

Quadratic unconstrained binary optimization problem preprocessing: Theory and empirical analysis,

M. Lewis and F. Glover, “Quadratic unconstrained binary optimization problem preprocessing: Theory and empirical analysis,” 2017. [Online]. Available: https://arxiv.org/abs/1705.09844

Pith/arXiv arXiv 2017
[14]

Ehrgott,Multicriteria Optimization, 2nd ed., ser

M. Ehrgott,Multicriteria Optimization, 2nd ed., ser. Lecture Notes in Economics and Mathematical Sys- tems. Berlin, Heidelberg: Springer, 2005, vol. 491

2005
[15]

Osmnx: New methods for acquiring, con- structing, analyzing, and visualizing complex street networks,

G. Boeing, “Osmnx: New methods for acquiring, con- structing, analyzing, and visualizing complex street networks,”Computers, Environment and Urban Sys- tems, vol. 65, pp. 126–139, 2017

2017
[16]

Valhalla: Open source routing engine,

Mapbox, “Valhalla: Open source routing engine,” https://valhalla.readthedocs.io, 2026, accessed: 2026- 02-02

2026
[17]

Gurobi optimizer ref- erence manual,

Gurobi Optimization, LLC, “Gurobi optimizer ref- erence manual,” https://docs.gurobi.com/projects/ optimizer/en/current/index.html, 2024, accessed 2026-01-30

2024
[18]

Op- timization by simulated annealing,

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Op- timization by simulated annealing,”Science, vol. 220, no. 4598, pp. 671–680, 1983

1983
[19]

Hybrid solvers for quadratic optimization,

D-Wave Systems Inc., “Hybrid solvers for quadratic optimization,” D-Wave Systems, Tech. Rep., 2023, https://www.dwavequantum.com/media/soxph512/ hybrid-solvers-for-quadratic-optimization.pdf (Ac- cessed: 2026-02-02)

2023
[20]

Advantage2 4400q quantum computer: Technology overview,

——, “Advantage2 4400q quantum computer: Technology overview,” https://www.dwavequantum. com/media/wakjcpsf/adv2_4400q_whitepaper-1.pdf, 2025, whitepaper, Accessed: 2026-02-02

2025
[21]

Minor-embedding in adiabatic quantum computation: I. the parameter setting problem,

V . Choi, “Minor-embedding in adiabatic quantum computation: I. the parameter setting problem,” Quantum Inf. Process., vol. 7, pp. 193–209, 2008

2008
[22]

A mathematical theory of communi- cation,

C. E. Shannon, “A mathematical theory of communi- cation,”Bell System Technical Journal, vol. 27, no. 3, pp. 379–423, 1948

1948
[23]

Herfindahl–hirschman index level of concentration values modification and analysis of their change,

I. Brezina, J. Pekár, Z. ˇCiˇcková, and M. Reiff, “Herfindahl–hirschman index level of concentration values modification and analysis of their change,” Central European Journal of Operations Research, vol. 24, no. 1, pp. 49–72, 2016

2016
[24]

Multi-objective optimization for pareto frontier sen- sitivity analysis in power systems,

S. Giannelos, X. Zhang, T. Zhang, and G. Strbac, “Multi-objective optimization for pareto frontier sen- sitivity analysis in power systems,”Sustainability, vol. 16, no. 14, p. 5854, 2024. [Online]. Available: https://www.mdpi.com/2071-1050/16/14/5854 ISSN 1335-8243 (print) ISSN 1338-3957 (online), www.aei.tuke.sk

2024

[1] [1]

Approximation algorithms for the set covering and vertex cover problems,

D. S. Hochbaum, “Approximation algorithms for the set covering and vertex cover problems,”SIAM Jour- nal on Computing, vol. 11, no. 3, pp. 555–556, 1982. [Online]. Available: https://doi.org/10.1137/0211045

doi:10.1137/0211045 1982

[2] [2]

Hoffman and M

K. Hoffman and M. Padberg,Set Covering, Packing, and Partitioning Problems. Cham: Springer Nature Switzerland, 2025, pp. 1–7. [Online]. Available: https://doi.org/10.1007/978-3-030-54621-2_599-1

work page doi:10.1007/978-3-030-54621-2_599-1 2025

[3] [3]

Conflict-based search for optimal multi-agent pathfinding,

G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, “Conflict-based search for optimal multi-agent pathfinding,”Artificial Intelligence, vol. 219, pp. 40–66, 2015. [Online]. Available: https://doi.org/10.1016/j.artint.2014.11.006

doi:10.1016/j.artint.2014.11.006 2015

[4] [4]

Multi-agent pathfinding: Definitions, variants, and benchmarks,

R. Stern, N. R. Sturtevant, A. Felner, S. Koenig, H. Ma, T. Walker, J. Li, D. Atzmon, L. Cohen, T. K. S. Kumar, E. Boyarski, and R. Bartak, “Multi-agent pathfinding: Definitions, variants, and benchmarks,” Artificial Intelligence, 2019, arXiv:1906.08291. [On- line]. Available: https://arxiv.org/abs/1906.08291

Pith/arXiv arXiv 2019

[5] [5]

A survey on coverage path planning for robotics,

E. Galceran and M. Carreras, “A survey on coverage path planning for robotics,”Robotics and Autonomous Systems, vol. 61, no. 12, pp. 1258–1276, 2013. [Online]. Available: https: //doi.org/10.1016/j.robot.2013.09.004

doi:10.1016/j.robot.2013.09.004 2013

[6] [6]

A quantum approach for cov- erage path planning in multi-vehicle deployments,

P. U. Rao and B. Sodhi, “A quantum approach for cov- erage path planning in multi-vehicle deployments,” in Proceedings of the IEEE International Conference on Quantum Computing and Engineering (QCE), 2022, pp. 729–732

2022

[7] [7]

Ising formulations of many np problems,

A. Lucas, “Ising formulations of many np problems,” Frontiers in Physics, vol. 2, p. 5, 2014

2014

[8] [8]

Quantum bridge analytics i: A tutorial on formulating and us- ing qubo models,

F. Glover, G. Kochenberger, and Y . Du, “Quantum bridge analytics i: A tutorial on formulating and us- ing qubo models,”4OR, vol. 17, pp. 1–20, December 2019

2019

[9] [9]

Quantum annealing in the transverse ising model,

T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse ising model,”Physical Review E, vol. 58, no. 5, pp. 5355–5363, 1998

1998

[10] [10]

R. M. Karp,Reducibility Among Combinato- rial Problems. Boston, MA: Springer US, 1972, pp. 85–103. [Online]. Available: https: //doi.org/10.1007/978-1-4684-2001-2_9

doi:10.1007/978-1-4684-2001-2_9 1972

[11] [11]

M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP- Completeness, 1st ed. San Francisco, CA: W. H. Freeman, 1979

1979

[12] [12]

A. P. Punnen, Ed.,The Quadratic Unconstrained Bi- nary Optimization Problem. Cham: Springer Nature Switzerland, 2022

2022

[13] [13]

Quadratic unconstrained binary optimization problem preprocessing: Theory and empirical analysis,

M. Lewis and F. Glover, “Quadratic unconstrained binary optimization problem preprocessing: Theory and empirical analysis,” 2017. [Online]. Available: https://arxiv.org/abs/1705.09844

Pith/arXiv arXiv 2017

[14] [14]

Ehrgott,Multicriteria Optimization, 2nd ed., ser

M. Ehrgott,Multicriteria Optimization, 2nd ed., ser. Lecture Notes in Economics and Mathematical Sys- tems. Berlin, Heidelberg: Springer, 2005, vol. 491

2005

[15] [15]

Osmnx: New methods for acquiring, con- structing, analyzing, and visualizing complex street networks,

G. Boeing, “Osmnx: New methods for acquiring, con- structing, analyzing, and visualizing complex street networks,”Computers, Environment and Urban Sys- tems, vol. 65, pp. 126–139, 2017

2017

[16] [16]

Valhalla: Open source routing engine,

Mapbox, “Valhalla: Open source routing engine,” https://valhalla.readthedocs.io, 2026, accessed: 2026- 02-02

2026

[17] [17]

Gurobi optimizer ref- erence manual,

Gurobi Optimization, LLC, “Gurobi optimizer ref- erence manual,” https://docs.gurobi.com/projects/ optimizer/en/current/index.html, 2024, accessed 2026-01-30

2024

[18] [18]

Op- timization by simulated annealing,

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Op- timization by simulated annealing,”Science, vol. 220, no. 4598, pp. 671–680, 1983

1983

[19] [19]

Hybrid solvers for quadratic optimization,

D-Wave Systems Inc., “Hybrid solvers for quadratic optimization,” D-Wave Systems, Tech. Rep., 2023, https://www.dwavequantum.com/media/soxph512/ hybrid-solvers-for-quadratic-optimization.pdf (Ac- cessed: 2026-02-02)

2023

[20] [20]

Advantage2 4400q quantum computer: Technology overview,

——, “Advantage2 4400q quantum computer: Technology overview,” https://www.dwavequantum. com/media/wakjcpsf/adv2_4400q_whitepaper-1.pdf, 2025, whitepaper, Accessed: 2026-02-02

2025

[21] [21]

Minor-embedding in adiabatic quantum computation: I. the parameter setting problem,

V . Choi, “Minor-embedding in adiabatic quantum computation: I. the parameter setting problem,” Quantum Inf. Process., vol. 7, pp. 193–209, 2008

2008

[22] [22]

A mathematical theory of communi- cation,

C. E. Shannon, “A mathematical theory of communi- cation,”Bell System Technical Journal, vol. 27, no. 3, pp. 379–423, 1948

1948

[23] [23]

Herfindahl–hirschman index level of concentration values modification and analysis of their change,

I. Brezina, J. Pekár, Z. ˇCiˇcková, and M. Reiff, “Herfindahl–hirschman index level of concentration values modification and analysis of their change,” Central European Journal of Operations Research, vol. 24, no. 1, pp. 49–72, 2016

2016

[24] [24]

Multi-objective optimization for pareto frontier sen- sitivity analysis in power systems,

S. Giannelos, X. Zhang, T. Zhang, and G. Strbac, “Multi-objective optimization for pareto frontier sen- sitivity analysis in power systems,”Sustainability, vol. 16, no. 14, p. 5854, 2024. [Online]. Available: https://www.mdpi.com/2071-1050/16/14/5854 ISSN 1335-8243 (print) ISSN 1338-3957 (online), www.aei.tuke.sk

2024