Skip to content

Solve the multi-car paint shop optimization problem using the LeapHybridCQMSampler.

License

Notifications You must be signed in to change notification settings

dwave-examples/paint-shop-optimization

Repository files navigation

Open in GitHub Codespaces Linux/Mac/Windows build status

Multi-Car Paint Shop Optimization

In car manufacturing, one step of production is painting the car body before assembly. A queue of cars enter the paint shop, undergo the painting procedure, and exit the paint shop. For all practical purposes, the sequence of cars entering the paint shop is assumed to be fixed. However, the colors assigned to the cars within a given sequence can be optimized.

In this problem, the sequence of cars queued for painting consists one or more ensembles, which might represent various car models or orders from different customers, for example. Some cars of each ensemble are to be painted black and the remainder white. The goal of the optimization is to minimize the number of color switches between cars in a paint shop queue, since there is a cost and waste associated with switching paint. This problem is known to be NP-hard. We demonstrate how to formulate this problem using the constrained quadratic model (CQM) class.

The problem instances used in this example are generated randomly. You can generate your own instances by following the format of the example in data/exp.yml, which is taken from the paper by Yarkoni et. al (see Ref [1]).

The formulation of this optimization problem can be summarized as:

  1. Objective: Minimize the number of color changes
  2. Constraint: Ensure that the correct number of cars are painted white/black

This is an example for the generalization of the binary paint shop optimization outlined by Volkswagen team in the paper Ref [1].

Usage

To run a small demo, run the command:

python car_paint_shop.py --filename data/exp.yml

data/exp.yml is a small data set that includes a sequence of cars under sequence and the number of cars to be painted black for each car ensemble under counts.

To run the demo on a random instance, run the command:

python car_paint_shop.py --num-cars 10

You can configure a seed, and a few other parameters to generate your desired random problem. For the full list of parameters please see the docstring of the main function in car_paint_shop.py.

Output

The script car_paint_shop.py creates and solves an optimization problem given an input file or given parameters of a random problem. After creating the optimization problem, it sends it to the CQM solver (LeapHybridCQMSampler). The output of the sampler is processed and the three best feasible solutions are printed. The objective function and the number of color switches are printed. Note that there is a parameter mode that you can pass that determines the objective function. If you set --mode 1, the objective function is the same as the function that computes the number of switches. In Ref [1], the authors used two different functions; one as the objective and one as the number of switches. After the script is complete, you'll also find an image for each of the solutions. The image contains a strip of white or black for each car stacked together horizontally.

The images will be saved in the images folder.

image

The image above shows one optimal solution, where the first four cars (indexed at 0 to 3) and the last four cars (indexed at 10 to 13) are painted black and the rest are painted white. This solution has two color switches. The image below shows another optimal solution with two color switches.

image

Baseline Comparison

To understand the benefits of optimizing the sequence of cars in a paint shop, we study the number of color switches when the sequence is optimized vs two other methods.

First, we color all cars in each ensemble according to the number of required black and white cars. Then, we place the colors in the sequence randomly. This will produce a random color sequence that also satisfies the constraints.

Another method, which will produce better results, is to color the sequence by starting with the color black, and then continuing until we cannot paint a car black (because the number of black cars in that ensemble has reached maximum). At that point, we switch the color and we continue with that color until it's infeasible to use that color again. We also make sure that if the number of cars left in an ensemble equals the number of cars of a certain color, we paint that color, otherwise, the solution will violate the constraints.

The first image shows an example of randomly painting cars in black and white. The number of color switches is 468, which means on average the color changes after painting every two cars. image

The second image shows the solution found with greedy optimization. We start with one color (say black) and we continue to paint with the same color until it becomes infeasible. For example, if we paint 5 of the cars from ensemble one with the color black, and the rest of them need to be painted white, we need to switch the color. As you can probably observe, a greedy solution will start great, but in the end, a lot of color switches are needed to satisfy all the constraints. This results in an overall 111 color switch which is much better than a random solution, but far from ideal. image

Finally, the solution obtained by LeapHybridCQMSampler provides an optimal (or near-optimal) arrangement of color with only 37 switches. It's worth noting that at the beginning there are more color switches than the greedy solution, but towards the end of the sequence, the number of color switches is significantly lower. image

Formulation

Objective

Suppose that we have N cars in a sequence. Each car can be painted black or white. The goal of the optimization is to reduce the number of times the color switches since there is a cost and waste associated with switching paint.

The authors of Ref [1] work with spin variables that take values -1 for white paint and +1 for black paint. This example uses binary variables with values 0 for white paint and 1 for black paint. A spin variable s can be converted to a binary variable x as follows (for reference see Ref [2]).

equation

We can optimize the number of color switches by counting the number of times the binary value of adjacent cars changes.

equation

Alternatively, we can reduce the number of color changes by minimizing a function that rewards (assigns negative values to) assigning the same color to adjacent cars. This function can easily be expressed in terms of spin variables. When two consecutive cars have the same color, the product of their values is positive; if the colors are different, the product is negative.

equation

Equivalently, the equation above can be written with binary variables as:

equation

The following equality shows the equivalence of these two formulations:

equation

Constraints

The sequence of N cars has M unique car ensembles (M < N). For each car ensemble (C_j) we want to make sure that the correct number of the cars in the ensemble (N_j) are painted black (and the remaining ones are painted white).

The equation below represents the constraint that the sum over the binary variables x_i representing cars of ensemble C_j should equal the number of cars that should be painted black (N_j).

equation

Code

The CQM class enables native formulation of objective and constraints using symbolic math.

Let's define x as the list of binary variables x[0] = dimod.Binary(0) to x[9] = dimod.Binary(9) for 10 cars in a sequence. We can compute the number of color changes by looking at the difference between adjacent cars. For example, x1-x0 gives us the difference of +1 or -1 or 0. Since only the value of 0 is desired, we can optimize the square of the difference. The objective function is

import dimod
x = list(dimod.Binaries(range(10)))
objective = 0
for i in range(9):
    objective += (x[i + 1] - x[i]) ** 2

cqm = dimod.ConstrainedQuadraticModel()
cqm.set_objective(objective)

# Assume there is only one unique car ensemble. For this single car ensemble, we 
# want to paint 5 of them black.

count = dimod.quicksum(x)
cqm.add_constraint(count == 5)

Note that the operators - and ** can be used with variables x, which are binary quadratic models. We can then add this objective to a CQM object.

Similarly, you can see that the code above adds an equality constraint (the sum of binary variables x is equal to 5) by defining a quadratic model (count, a quadratic model created by summing a list of binary quadratic models, x) and setting it to the target value.

References

[1] Yarkoni et. al. Multi-car paint shop optimization with quantum annealing, arxiv

[2] https://docs.dwavesys.com/docs/latest/c_gs_9.html#transformations-between-ising-and-qubo

License

Released under the Apache License 2.0. See LICENSE file.

About

Solve the multi-car paint shop optimization problem using the LeapHybridCQMSampler.

Topics

Resources

License

Stars

Watchers

Forks

Contributors 4

  •  
  •  
  •  
  •  

Languages