Quantum and classical approaches to the optimization of highway platooning: the two-vehicle matching problem

Chinonso Onah, Agneev Guin, Carsten Othmer, J. A. Montaez-Barrera, Kristel Michielsen · 2026

Read Quantum and classical approaches to the optimization of highway platooning: the two-vehicle matching problem by Chinonso Onah, Agneev Guin, Carsten Othmer, J. A. Montaez-Barrera, Kristel Michielsen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-18919.txt.

Introduction

Onah and co-authors compare ways to match pairs of highway vehicles so one can shelter the other from wind. Pairing cuts drag, but wide use is blocked by tech and legal hurdles. They frame the two-vehicle matching task as a binary math problem that many solvers can share. Classical search methods, quantum annealing, and quantum approximation methods all tackle the same form. Heuristic solvers give no proof of the best answer. Hybrid flows with classical cleanup can return only valid plans.

Catalog record

CREATORChinonso Onah, Agneev Guin, Carsten Othmer, J. A. Montaez-Barrera, Kristel Michielsen
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65055
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.18919

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum and classical approaches to the optimization of highway platooning: the two-vehicle matching problem Chinonso Onah, Agneev Guin, Carsten Othmer, J. A. Montaez-Barrera, Kristel Michielsen Abstract Aerodynamic drag reduction on highways through vehicle platooning is a well-known concept that has not seen systematic uptake so far. Arguably because of high technological and legislative obstacles. As a low-tech entry solution to real multi-vehicle platooning, “Windbreaking-as-a-Service” (WaaS) was introduced in [ 20 ] . Here we leverage the QUBO formulation to explore classical meta-heuristics such as simulated annealing, tabu search, and emergent quantum heuristics including quantum annealing and variants of the Quantum Approximate Optimization Algorithm (QAOA). These heuristic solvers do not guarantee optimality, yet they traverse the same high-order landscape in polynomial memory. They can be parallelized aggressively, and efficient classical processing can be employed to return only valid schedules in certain hybrid workflows. The present paper therefore positions QUBO as the lingua franca that allows heterogeneous classical, quantum and hybrid solvers to attack the optimization of highway platooning. Keywords: quantum optimization; QUBO; aerodynamics; platooning; CO 2 mitigation 1 Problem Formulation 1.1 Matching Problem Statement We study the two-vehicle matching problem on a single road segment formulated in [ 20 ] . A surfer is a vehicle that seeks to follow (or be assigned to) a compatible lead vehicle, a breaker for cooperative driving. The breaker can accept at most one surfer for such an assignment. The overall objective is to compute a one-to-one (or capacity-respecting) matching between surfers and breakers that minimizes a weighted cost capturing aerodynamic efficiency and timing/velocity compatibility. The a mathematical statement is the following: Let the set of surfers be \mathcal{S}=\{1,\dots,S\} and the set of breakers be \mathcal{B}=\{1,\dots,B\} . We form a bipartite graph G(\mathcal{S}\cup\mathcal{B},\mathcal{E}) where each edge (s,b)\in\mathcal{E} indicates that surfer s\in\mathcal{S} can potentially be matched to breaker b\in\mathcal{B} . For each possible edge (s,b)\in\mathcal{E} , we define a binary variable x_{s,b}\in\{0,1\} such that: x_{s,b}=\begin{cases}1,&\text{if surfer $s$ is assigned to breaker $b$,}\\ 0&\text{otherwise.}\end{cases} The edge carries a weight w_{s,b} reflecting the aerodynamic efficiency and timing compatibility of the pairing. It is defined as: w_{s,b}\;=\;c_{s}\,V_{b}^{2}\,\bigl[\,1-f(C_{b}-c_{s})\bigr]\;+\;\lambda_{1}\,\Delta_{s,b}^{T}\;+\;\lambda_{2}\,\Delta_{s,b}^{V}, (1) where \lambda_{1},\lambda_{2}\geq 0 are scaling factors, and \Delta_{s,b}^{T} and \Delta_{s,b}^{V} capture time and velocity preferences of surfer s for breaker b as follows: \displaystyle\Delta_{s,b}^{T} \displaystyle= \displaystyle\begin{cases}|t_{s}-T_{b}|&\text{if }|t_{s}-T_{b}|>\delta t_{s}/2,\\ 0&\text{otherwise,}\end{cases} (2) and similarly for \Delta_{s,b}^{V} , with \delta t_{s} and \delta v_{s} being surfer-individual flexibility intervals for departure time and preferred travel speed, respectively. The matching problem is therefore formalized in [ 20 ] as: \min_{x_{s,b}\in\{0,1\}}\sum_{s\in S}\sum_{b\in B}w_{s,b}\,x_{s,b} (3) subject to constraints: \displaystyle\sum_{b\in B}x_{s,b} \displaystyle=1,\quad\forall s\in S\quad(\text{each surfer matched exactly once}) (4) \displaystyle\sum_{s\in S}x_{s,b} \displaystyle=1,\quad\forall b\in B\quad(\text{each breaker matched at most once})\; i.e. we require each surfer s\in\mathcal{S} to be matched to exactly one breaker, and each breaker b\in\mathcal{B} to accept exactly one surfer. We further assume B=S in the rest of the paper. 1.2 QUBO Form To exploit quantum and quantum-inspired solvers, we need to transform the problem into a QUBO problem. To that end, we add squared-penalty terms with a hyperparameter \lambda_{3} to quadratize the constraints and obtain the following unconstrained version: \lambda_{3}\sum_{s\in\mathcal{S}}\Bigl(1-\sum_{b\in\mathcal{B}}x_{s,b}\Bigr)^{2}\;+\;\lambda_{3}\sum_{b\in\mathcal{B}}\Bigl(1-\sum_{s\in\mathcal{S}}x_{s,b}\Bigr)^{2}. (5) This is added to Eq. ( 3 ) to yield the QUBO problem. Namely: \min_{\{x_{s,b}\}}(\sum_{(s,b)\in\mathcal{E}}w_{s,b}\,x_{s,b}+\,\lambda_{3}\sum_{s\in\mathcal{S}}\Bigl(1-\sum_{b\in\mathcal{B}}x_{s,b}\Bigr)^{2}+\,\lambda_{3}\sum_{b\in\mathcal{B}}\Bigl(1-\sum_{s\in\mathcal{S}}x_{s,b}\Bigr)^{2}). With n:=S(=B) , we can list all pairs (s,b) in a vector: x\;=\;\bigl(x_{1,1},\,x_{1,2},\,\dots,\,x_{1,n},\,x_{2,1},\,\dots,\,x_{n,n}\bigr)^{T}. Eq. ( 1.2 ) becomes the standard form as mentioned in [ 20 ] : \min\,x^{T}Qx (6) \displaystyle\text{with}\quad Q_{ee}=w_{s,b}+\lambda_{1}\Delta_{s,b}^{T}+\lambda_{2}\Delta_{s,b}^{V}-2\lambda_{3} \displaystyle\text{and}\quad Q_{ee^{\prime}}=\begin{cases}\lambda_{3}&\text{if }e\text{ and }e^{\prime}\text{ share a node}\\ 0&\text{otherwise.}\end{cases} This QUBO matrix has an interesting tensor structure. To see that, let Q\in\mathbb{R}^{n^{2}\times n^{2}} and Q=\text{diag}_{n^{2}}\left(w_{s,b}-4\lambda_{3}\right)+\lambda_{3}\left(I_{N}\otimes J_{N}+J_{N}\otimes I_{N}\right) (7) \displaystyle\text{where }I_{N}:N\times N\text{ identity matrix} \displaystyle\text{and }J_{N}:N\times N\text{ ``1''-matrix}=\begin{pmatrix}1&1&\cdots&1\\ 1&1&\cdots&1\\ \vdots&\vdots&\ddots&\vdots\\ 1&1&\cdots&1\end{pmatrix} This structure is closely related to the fact that valid solutions can be translated into permutation matrices. This is a property that can be leveraged to improve the quantum solution both in speed and accuracy. (Refer Sec. 2.7 and [ 18 ] ). Constraints and Energy Landscape Analysis We seek a small enough penalty weight \lambda_{3} that guarantees all invalid one-hot assignments lie strictly above all valid ones in the QUBO energy landscape. To derive this, let the matrix representation of the problem C=[c_{ij}]\in\mathbb{R}^{n\times n} . The maximum possible cost-saving from swapping any one assignment is c_{\max}-c_{\min}, and there are n rows (or columns) whose one-hot constraints could be violated. Hence any invalid bitstring can gain at most n\,(c_{\max}-c_{\min}) in the cost term. By choosing \lambda_{3}>n\,(c_{\max}-c_{\min}), we ensure that the penalty for violating even one one-hot constraint outweighs all possible cost savings from invalid assignments. Multiplying by a safety factor >1 yields a strict separation without unduly inflating the penalty. energy E(\mathbf{x}) \lambda_{3} too small feasible infeasible infeasible strings can drop below feasible minima (“cheating”) E(\mathbf{x})=E_{\text{cost}}(\mathbf{x})+\lambda_{3}P(\mathbf{x}) energy E(\mathbf{x}) \lambda_{3} very large feasible infeasible penalty gap feasible energies nearly equal (flat feasible plateau) \Rightarrow weak cost discrimination E(\mathbf{x})\approx\lambda_{3}P(\mathbf{x}) on infeasible set Figure 1 : Schematic energy landscape under two penalty-weight regimes. Left: if \lambda_{3} is too small, infeasible configurations can “cheat” by lowering E_{\text{cost}} enough to overcome penalties. Right: if \lambda_{3} is very large, infeasible states are pushed far above the feasible manifold, but feasible energies compress into an almost flat plateau, reducing cost discrimination among valid matchings. As shown in Fig. 1 , when \lambda_{3} is too small compared to the spread of c_{i,j} , then the sampler can reduce E_{\mathrm{cost}} by picking invalid assignments (e.g. two ones in the same row), because the small penalty is outweighed by cost savings. This produces noisy, infeasible solutions that cheat the one-hot rule in Eq. ( 4 ). Mapping the QUBO to a Quantum Hamiltonian To solve an optimization problem on a quantum computer, its QUBO formulation must be mapped to a quantum Hamiltonian [ 12 ] . This is derived in the standard way by expressing a symmetric QUBO matrix in terms of its components and transforming the upper triangular part into an Ising Hamiltonian. In this formalism, each qubit in the computational basis corresponds to a binary variable and hence an edge (s,b) in the bipartite graph picture. Consider the following generic QUBO matrix: x^{T}Qx=\sum_{i,j}Q_{ij}x_{i}x_{j} (8) where x_{i}\in\{0,1\} are binary variables, and Q_{ij} is the matrix defining the quadratic coefficients. Each binary variable x_{i} is mapped to a qubit using the relation: x_{i}=\frac{1}{2}(I-Z_{i}) (9) where Z_{i} is the Pauli-Z operator acting on the i -th qubit, and I is the identity operator, effectively transforming the binary variable x_{i} into a Pauli-Z operator. See Ref [ 12 ] for details. The full Hamiltonian becomes H=\sum_{i}\frac{Q_{ii}}{2}(I-Z_{i})+\sum_{i<j}\frac{Q_{ij}}{4}\left(I-Z_{i}-Z_{j}+Z_{i}Z_{j}\right). (10) The constant identity terms do not influence the optimization landscape of the QUBO problem and can be omitted. 1.3 Performance metrics Because heuristic samplers return distributions rather than proofs of optimality, a single scalar such as the “best cost” gives an incomplete—and occasionally misleading—picture of performance. A solver call returns N raw samples (“reads”) of bitstrings \mathbf{x}_{k}\in\{0,1\}^{N_{\text{vars}}} 1 1 1 N_{\text{vars}} is the number of binary variables in the problem and thus the length of the bitstring , their QUBO energies E_{k}\equiv E(\mathbf{x}_{k}) , and quadratic penalties P(\mathbf{x}_{k}) which vanish only for feasible matchings (Refer Sec. 1 ). We denote by E_{\star} the exact ground-state energy obtained from the Hungarian algorithm and the corresponding MIQP (mixed-integer quadratic program) baseline (Refer Sec. 2.2 ). Following

Read the complete text