Process Optimisation in Manufacturing Industry

We implement a quantum optimisation algorithm to find the minimum number of colour-switches necessary to cover all cars queued in a car paint shop.

The multi-car paint shop problem is an important optimisation task in the automotive industry (NP-complete). The objective is to reduce costs and production time, by finding the minimum number of colour switches for painting adjacent cars in a paint-shop queue.

Formally the problem is described as N cars entering the paint shop to be painted with a black or white filler layer. Each car in the sequence belongs to one of M ensembles (e.g. defined by the car type), with the constraint that in each ensemble a given number k_M of cars must be painted black. Our quantum system decides how to paint each car in the sequence, such that the number of filler-colour switches between adjacent cars is minimal, while the ensemble constraints are satisfied. The proof-of-concept experiment elaborated below shows that AQT’s quantum computers can be harnessed to solve real-world optimisation problems. Our systems will be accessible via the Cloud to also solve your optimisation problem!

For the experimental implementation of the car-paint shop problem we use a 10-qubit register on AQT’s quantum computer, and encode the following settings (see figure 1):

Following ref. [https://www.computer.org/csdl/proceedings-article/qce/2021/169100a035/1yEZ9U3caCk], we represent each car by a qubit and encode the problem in an Ising-type Hamiltonian:

The ground state of the Hamiltonian represents the optimum solution of our problem. We get approximate solutions for the ground state using the variational QAOA (Quantum Approximate Optimisation Algorithm) of the Qiskit SDK (see figure 2). Results are returned as a bit-string, directly corresponding to the suggested sequence of black (0) and white (1) filler-colour for the incoming cars.

Note that for 10 cars there exist 2¹⁰ = 1024 possible colour sequences, for 30 cars this already amounts to 1 billion. From all possibilities we let the quantum implementation preselect 200 promising candidate solutions and subsequently classically pick the best (lowest energy) solution that fulfils the ensemble constraints.

Using our quantum computer for the quantum preselection, we successfully find the ideal solution for the filler-paint sequence:[1, 1, 1, 0, 0, 0, 0, 0, 0, 0] = [‘W’, ‘W’, ‘W’, ‘B’, ‘B’, ‘B’, ‘B’, ‘B’, ‘B’, ‘B’], corresponding to only 1 colour switch (see figure 3).

Obtaining such an optimised solution, while fulfilling the ensemble constraints, is not trivial. In comparison, one can try a classical heuristic “black-first algorithm”: it paints cars black as long as the ensemble constraints allow for. That is, if the incoming car belongs to ensemble “Small” it is painted black if the number of “small” cars to be painted black is not yet exceeded. Otherwise, it is painted white. This classical greedy algorithm finds a solution with 6 colour switches:[‘B’, ‘B’, ‘W’, ‘B’, ‘B’, ‘W’, ‘B’, ‘B’, ‘W’, ‘B’], which would be associated with significantly higher costs or time compared to the solution calculated on the AQT quantum computer.