Exploring Quantum Algorithms for Optimal Sensor Placement in Production Environments
To increase efficiency in automotive manufacturing, newly produced vehicles can move autonomously from the production line to the distribution area. This requires optimal sensor placement to ensure full coverage while minimizing the number of sensors used. The underlying optimization problem presents a computational challenge due to its large-scale nature, making classical exact solvers infeasible for real-world instances.
Classical solvers like Gurobi and CPLEX can provide near-optimal solutions but rely on heuristics for large instances, leading to potentially suboptimal sensor distributions and increased operational costs. Each sensor costs up to €5,000 annually, meaning improved optimization could yield cost savings of over 1 Million € per year across the BMW Group’s production facilities.
Our approach explores quantum computing methods to potentially outperform classical heuristics in the future. We implemented quantum annealing with D-Wave, transforming the problem into a quadratic unconstrained binary optimization formulation with one-hot and binary encoding. We also implemented a gate-based QAOA approach with IBM and Pennylane and used classical benchmarks to evaluate solution quality and scalability.
Our results indicate that quantum annealing can be used to solve instances close to industrial applicability today by means of decomposition. Experiments with QAOA demonstrate the potential of gate model computing on smaller toy instances.
Despite existing challenges, the BMW Group’s involvement ensures real-world applicability. The problem’s origin in an actual factory setting and the use of real data indicate that this is a highly relevant industrial quantum optimization use case that aligns with TRL 4 criteria. Through this work, we provide key insights into the different algorithms and their upsides and weaknesses, demonstrating how quantum computing could contribute to cost-efficient, large-scale optimization problems once the hardware matures.
