Quantum Algorithms Optimise Highway Vehicle Pairings for Fuel Savings

Chinonso Onah and colleagues at Volkswagen AG, in a collaboration between Volkswagen AG and Jülich Supercomputing Centre, Forschungszentrum Jülich, have formulated Quadratic Unconstrained Binary Optimisation (QUBO) to compare classical and new quantum computational approaches. The study explores metaheuristics such as simulated annealing and tabu search, alongside quantum heuristics including quantum annealing and Quantum Approximate Optimisation Algorithm variants. Establishing QUBO as a unifying framework enables the development of a flexible set of tools, classical, quantum, and hybrid, to address the complex optimisation challenges of coordinating vehicle platoons and potentially leading to more efficient road transport systems. The findings offer a key method for optimising highway platooning to reduce aerodynamic drag sharply. Mean Energy gap reduction validates QUBO for vehicle platooning optimisation A reduction in the Mean Energy gap to under one percent represents a substantial improvement over previous problem-specific approaches. This threshold validates the Quadratic Unconstrained Binary Optimisation (QUBO) formulation, enabling consistent benchmarking of diverse solvers against a known optimum derived from a Mixed Integer Quadratic Programming (MIQP) baseline. Previously, comparing classical and quantum optimisation techniques for vehicle platooning was hampered by a lack of standardised problem representation, requiring custom implementation for each algorithm. Aerodynamic drag, a significant contributor to fuel inefficiency in long-haul trucking and passenger vehicles, can be substantially reduced by vehicles travelling in proximity, forming platoons. However, the optimal configuration of these platoons, determining which vehicles should lead and follow, is a computationally intensive problem, especially as the number of vehicles increases. The MIQP baseline provides a definitive, albeit computationally expensive, solution against which the performance of heuristic algorithms can be measured. The QUBO formulation allows for the translation of the vehicle platooning problem into a format suitable for both classical and quantum solvers, facilitating a fair and rigorous comparison. QUBO provides a unifying framework for assessing the performance of solvers, including simulated annealing, tabu search, quantum annealing, and Quantum Approximate Optimisation Algorithm variants, on a common field. Employing a logarithmic cooling schedule, simulated annealing achieved convergence to the global optimum in probability, while tabu search utilised short-term memory to avoid revisiting previously explored solutions. Detailed analysis, presented in supplementary material, offers a reproducible reference for comparing solver performance across varying problem sizes and methodologies, ensuring transparency and facilitating further research. Simulated annealing, a probabilistic technique inspired by the annealing process in metallurgy, explores the solution space by gradually decreasing a ‘temperature’ parameter, allowing it to escape local optima. The logarithmic cooling schedule ensures a controlled reduction in temperature, promoting convergence towards the global optimum. Tabu search, conversely, employs a ‘tabu list’, a short-term memory, to prevent the algorithm from revisiting recently explored solutions, thereby encouraging exploration of new areas of the solution space. The effectiveness of both algorithms is heavily dependent on parameter tuning, and the study provides insights into optimal parameter settings for the vehicle platooning problem. The detailed supplementary material is crucial for verifying the results and enabling other researchers to build upon this work. Quantum annealing failed to produce feasible solutions for problem instances of five or more variables, likely due to embedding limitations and restricted sampling; this highlights the current challenges in scaling quantum hardware to tackle realistic optimisation problems. This limitation underscores the need for continued development in quantum computing technology to address complex optimisation tasks. Quantum annealing leverages quantum-mechanical effects, such as quantum tunnelling, to explore the solution space more efficiently than classical algorithms. However, current quantum annealers have limitations in terms of the number of qubits (quantum bits) available and the connectivity between them. Embedding the QUBO problem onto the quantum hardware requires mapping the binary variables to physical qubits, and this process can be challenging, especially for large problem instances. Restricted sampling, due to the limited number of reads allowed from the quantum annealer, further hinders its ability to find optimal solutions. The established framework is valuable for assessing optimisation techniques, acknowledging that quantum computing remains a developing field with practical limitations. By formulating the platooning problem using QUBO, a mathematical structure common to both classical and quantum algorithms, performance of different solvers can be compared without being constrained by specific hardware or software, accelerating progress through hybrid approaches and efficient testing of emerging quantum heuristics alongside established methods. This allows researchers to identify the strengths and weaknesses of each approach and potentially combine them to achieve better results. Evaluating platoon formation using a quantum-inspired optimisation framework Vehicle platooning promises substantial gains in highway efficiency, reducing fuel consumption and congestion by allowing vehicles to travel in close formation. Realising this potential, however, requires overcoming significant hurdles, including the challenge of optimally matching ‘surfers’, vehicles seeking to join a platoon, with suitable ‘breakers’ willing to lead. Recent work has introduced “Windbreaking-as-a-Service” as a pragmatic first step, but a more flexible and powerful approach to optimisation is needed to truly unlock the benefits of coordinated driving. The aerodynamic drag reduction achieved through platooning is not uniform across all vehicles; the lead vehicle experiences the least drag reduction, while trailing vehicles benefit the most. This creates an economic incentive for vehicles to ‘surf’ behind others, but it also requires a mechanism for fairly compensating the ‘breakers’ who bear the brunt of the drag. “Windbreaking-as-a-Service” proposes a market-based approach where breakers are compensated for their efforts, but this requires careful consideration of pricing and incentive structures. A unified mathematical language for optimising vehicle platoons marks a key advancement in cooperative driving systems. Adopting QUBO allowed direct comparison of solver performance, accelerating progress beyond tailored solutions. This standardised approach opens avenues for hybrid workflows, combining the strengths of different computational techniques to tackle complex traffic flow optimisation, and it can optimise vehicle platoons, reducing congestion and fuel consumption. Such a unified approach will likely accelerate development and begin a new era of coordinated highway driving. The ability to model the platooning problem in a standardised format allows for the integration of real-time data, such as traffic conditions and vehicle speeds, to dynamically adjust the platoon configuration and maximise efficiency. Furthermore, the QUBO framework can be extended to incorporate additional constraints, such as vehicle capabilities and driver preferences. Hybrid workflows, combining the speed of classical heuristics with the potential accuracy of quantum algorithms, offer a promising path towards solving increasingly complex optimisation problems in the future. The implications extend beyond fuel efficiency, potentially leading to reduced emissions and improved traffic flow on highways. The research successfully demonstrated a unified method, using Quadratic Unconstrained Binary Optimisation (QUBO), for optimising vehicle platoons of any size. This standardised language allows both classical and emerging quantum computers to tackle the complex problem of coordinating vehicles to reduce aerodynamic drag and, consequently, fuel consumption. By fairly compensating lead vehicles, the ‘breakers’, for shielding others, this approach facilitates a potential “Windbreaking-as-a-Service” model. Future work could integrate real-time traffic data into the QUBO framework and explore hybrid computational methods to further refine platoon configurations and improve highway efficiency. 👉 More information 🗞 Quantum and classical approaches to the optimization of highway platooning: the two-vehicle matching problem 🧠 ArXiv: https://arxiv.org/abs/2603.18919 HIGHWAY PLATOONING QUANTUM ANNEALING QUANTUM APPROXIMATE OPTIMIZATION ALGORITHM QUBO FORMULATION SIMULATED ANNEALING TABU SEARCH VEHICLE PLATOONING WINDBREAKING-AS-A-SERVICE