Classical and Quantum Heuristics for the Binary Paint Shop Problem
arXiv:2509.15294 · doi:10.1103/dw96-xxfy
Abstract
The Binary Paint Shop Problem (BPSP) is an -hard optimisation problem arising in automotive manufacturing: given a sequence of cars, comprising distinct models each appearing twice, the task is to decide which of two colours to paint each car so that the two occurrences of each model are painted differently, while minimising consecutive colour swaps. Performance is measured by the paint swap ratio -- the average number of colour changes per car -- which directly affects production efficiency and cost. Prior work showed that the Quantum Approximate Optimisation Algorithm (QAOA) at depth achieves a ratio of , outperforming the then-best-known classical heuristic, Recursive Greedy, with a proven asymptotic expected ratio of [Phys. Rev. A 104, 012403 (2021)]. More recently, the Recursive Star Greedy (RSG) heuristic was proposed with a conjectured expected ratio of . Here, we formally reduce BPSP to weighted MaxCut, yielding an exact Ising formulation, and benchmark two state-of-the-art low-depth QAOA variants -- eXpressive QAOA and Recursive QAOA -- at (denoted XQAOA and RQAOA) against four classical BPSP heuristics. Across instances ranging from to cars, XQAOA achieves an average paint-swap ratio of ; in our instance-wise benchmarks, it outperforms RQAOA on almost all instances and each of the four classical baselines, including RSG, on every instance. Surprisingly, RQAOA deteriorates with problem size despite employing provably near-optimal QAOA parameters at each recursive step, eventually falling behind RSG at the largest sizes. To our knowledge, this is the first report of size-dependent performance degradation of RQAOA at scale. In contrast, XQAOA remains stable across all tested sizes, with no evidence of size-dependent degradation.
32 pages, 3 figures. Final revised version accepted for publication in Physical Review Applied