Multi-car paint shop optimization with quantum annealing

IEEE International Conference on Quantum Computing and Engineering (QCE), pp. 35–41

Abstract

We present a generalization of the binary paint shop problem (BPSP) to tackle an automotive industry application, the multi-car paint shop (MCPS) problem. The objective of the optimization is to minimize the number of color switches between cars in a paint shop queue during manufacturing, a known NP-hard problem. We distinguish between different sub-classes of paint shop problems, and show how to formulate the basic MCPS problem as an Ising model. The problem instances used in this study are generated using real-world data from a factory in Wolfsburg, Germany. We compare the performance of the D-Wave 2000Q and Advantage quantum processors to other classical solvers and a hybrid quantum-classical algorithm offered by D-Wave Systems. We observe that the quantum processors are well-suited for smaller problems, and the hybrid algorithm for intermediate sizes. However, we find that the performance of these algorithms quickly approaches that of a simple greedy algorithm in the large size limit.

Authors 6

1. Sheir Yarkoni Aachen

   Leiden University · Data:Lab Munich (Germany)

   Affiliation as printed

   LIACS, Leiden University, Leiden, The Netherlands

   Volkswagen Data:Lab Munich, Germany

   Volkswagen Data:Lab Munich,Germany

2. Alex Alekseyenko

   Volkswagen Group (United States)

   Affiliation as printed

   Volkswagen Group of America, San Francisco, CA, USA

   Volkswagen Group of America,San Francisco,CA,USA

3. Michael Streif

   Friedrich-Alexander-Universität Erlangen-Nürnberg · Data:Lab Munich (Germany)

   Affiliation as printed

   Institute of Theoretical Physics, University Erlangen-Nürnberg, Nürnberg, Germany

   Volkswagen Data:Lab Munich, Germany

   Volkswagen Data:Lab Munich,Germany

4. David Von Dollen Aachen

   Leiden University · Volkswagen Group (United States)

   Affiliation as printed

   LIACS, Leiden University, Leiden, The Netherlands

   Volkswagen Group of America, San Francisco, CA, USA

   Leiden University (LIACS), Leiden, The Netherlands

5. Florian Neukart Aachen

   Leiden University · Data:Lab Munich (Germany)

   Affiliation as printed

   LIACS, Leiden University, Leiden, The Netherlands

   Volkswagen Data:Lab Munich, Germany

   Volkswagen Data:Lab Munich,Germany

6. Thomas Bäck Aachen

   Leiden University

   Affiliation as printed

   LIACS, Leiden University, Leiden, The Netherlands

   Leiden University (LIACS), Leiden, The Netherlands