Multi-Car Paint Shop Problem

Multi-Car Paint Shop Problem#

In this tutorial, we will solve the Multi-Car Paint Shop (MCPS) problem using JijZept, based on the work of Sheir Yarkoni, et al. [1]. The Multi-Car Paint Shop (MCPS) problem is to minimize the number of color switchings when painting multiple car models at a factory.

Problem Setting#

The Multi-Car Paint Shop (MCPS) problem is to optimize color switching when painting multiple car models at a factory, as described above. In the painting process, there is a base coat, whose color is determined by the customer’s request, and a coating called filler, which is applied underneath the base coat. The color of the filler is determined by the color of the base coat, which must be painted black for darker colors and white for lighter colors. The Multi-Car Paint Shop (MCPS) problem is an optimization problem for this filler coloring. It is necessary to paint as many cars in the queue as possible with the same filler color while satisfying the constraint that the correct filler color is applied to the car. The problem is to paint the car with the correct color and to reduce the number of times the paint color is switched.

Let us consider an example. For simplicity, we consider only two car models, $C_1, C_2$. Suppose that six cars come into the queue waiting to be painted in the order $C_1, C_1, C_2, C_2, C_1, C_2$. Let $k(C_l)\ (l = 1,2)$ denote the number of cars to paint car model $C_l$ in black. Suppose that $k(C_1) = 2,k(C_2) = 1$, i.e., two of car model 1 must be painted black and one of car model 2 must be painted black. When we write $B$ for black and $W$ for white, the least number of repaints will be $B,B,B,W,W,W$ for the incoming cars.

Mathematical model#

We consider $N$ cars that come into the queue, and there are $n$ car models.

Decision variable#

Binary variables $q_i$ are defined as:

\[\begin{split} q_{i} = \begin{cases} 1~\text{$i$th car is painted black}\\ 0~\text{otherwise}\\ \end{cases} \end{split}\]

for all $i \in \{0, ..., N-1\}$.

Constraints#

We have to consider one constraint;

The filler must be painted in the correct number corresponding to the order for each car model.

The number of vehicles of car model $C_l$ that are painted black must equal $k(C_l)$. We can formulate this constraint as an independent $K$-hot constraint on car models $C_l$. Since we are now using the binary variable $q_i$, which is 1 if car $i$ is black, we know that when we sum over all the binary variables for cars belonging to car type $C_l$, the sum should be $k(C_l)$. Therefore, the constraint is

\[ \sum_{i\in C_l} q_i = k(C_l) \ \forall\ l \]

Objective function#

The objective of this problem is to reduce the number of color switches as much as possible; in other words, the objective is to make the color of successive cars the same. The property of being the same color as its neighbors can be formulated using the ferromagnetic formulation in the Ising model The ferromagnetic formulation is

\[ H_A = -\sum_{i=0}^{N-2}s_is_{i+1}. \]

where $s_i\in\{-1,1\}$ is spin variable and there is a relationship $s_i = 2q_i - 1$ between $s_i$ and $q_i$. Therefore, we can rewrite the objective function of this problem using $q_i$ as

\[ H_A = -\sum_{i=0}^{N-2}s_is_{i+1} = -\sum_{i=0}^{N-2}(2q_i - 1)(2q_{i+1} - 1) \]

In conclusion, the Multi-Car Paint Shop (MCPS) problem can be formulated as

\[\begin{split} \begin{aligned} &\text{Minimize}\quad H_A = -\sum_{i=0}^{N-2}(2q_i - 1)(2q_{i+1} - 1) \\ &\text{subject to } \sum_{i\in C_l} q_i = k(C_l)　\forall\ l \end{aligned} \end{split}\]

Modeling by JijModeling#

Next, we show an implementation using JijModeling. We first define variables for the mathematical model described above.

import jijmodeling as jm

N = jm.Placeholder('N') # Number of cars
n = jm.Placeholder('n') # Number of car models
C = jm.Placeholder('C',ndim=2) # indices of each car models
K = jm.Placeholder('K',ndim=1) # Number of black cars for each car models

q = jm.BinaryVar('q', shape=(N,))

j = jm.Element('j', belong_to=(0,N-1))
c = jm.Element('c', belong_to=(0,n))
l = jm.Element('l', belong_to=C[c]) 

The data on the number of cars for each car model becomes like

{1 : [0, 3, 8, 10], 2 :[1, 4, 6, 9, 12],3: [2, 5, 7, 11, 13]}

This data structure expresses that the key of the dictionary corresponds to car models and the value of the dictionary is the indices of each car model. JijZept currently does not support dictionary data structure, so we have to convert this data into a list

[[0, 3, 8, 10], [1, 4, 6, 9, 12], [2, 5, 7, 11, 13]] 

Placeholder can also be used with such a data structure.

Next, let us formulate our models using JijModeling.

problem = jm.Problem("multi car paint")

# Constraints
problem += jm.Constraint("N-hot constraint",jm.sum(l,q[l]) == K[c],forall=c)
# Objective function
problem += -jm.sum(j,(2*q[j] - 1)*(2*q[j+1] - 1))
problem

\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{multi car paint} & & \\& & \min \quad \displaystyle - \sum_{j = 0}^{N - 2} \left(2 \cdot q_{j} - 1\right) \cdot \left(2 \cdot q_{j + 1} - 1\right) & \\\text{{s.t.}} & & & \\ & \text{N-hot constraint} & \displaystyle \sum_{l \in C_{c}} q_{l} = K_{c} & \forall c \in \left\{0,\ldots,n - 1\right\} \\\text{{where}} & & & \\& q & 1\text{-dim binary variable}\\\end{array}\end{split}\]

Prepare an instance#

The [1] uses real data, however, we create a random instance for this problem.

We consider the number of cars $N=30$ and the number of car models is $n=4$ as an example.

import numpy as np

num_carmodels = 4
num_cars = 30
sequence = np.random.choice(range(num_carmodels),num_cars)
carmodels_list = [[] for i in range(num_carmodels)]
for index,car_index in enumerate(sequence):
    carmodels_list[car_index].append(index)

num_blackcar = [int(np.ceil(len(cars)/2)) for cars in carmodels_list]
instance_data = {'N':num_cars, 'n':num_carmodels, 'K':num_blackcar, 'C':carmodels_list}

instance_data

{'N': 30,
 'n': 4,
 'K': [5, 3, 5, 3],
 'C': [[0, 1, 8, 14, 16, 17, 23, 24, 28],
  [2, 4, 5, 7, 15, 26],
  [3, 6, 9, 10, 11, 13, 18, 20, 22, 25],
  [12, 19, 21, 27, 29]]}

Solve by JijSolver#

We solve this MCPS problem using jijsolver.

import jijsolver 

interpreter = jm.Interpreter(instance_data)
instance = interpreter.eval_problem(problem)
solution = jijsolver.solve(instance, time_limit_sec=1.0)

Check the solution#

We check the solution obtained from jijsolver

df = solution.decision_variables
df

	kind	lower	upper	name	subscripts	description	substituted_value	value
id
0	binary	0.0	1.0	q	[0]	<NA>	<NA>	1.0
1	binary	0.0	1.0	q	[1]	<NA>	<NA>	1.0
2	binary	0.0	1.0	q	[2]	<NA>	<NA>	1.0
3	binary	0.0	1.0	q	[3]	<NA>	<NA>	1.0
4	binary	0.0	1.0	q	[4]	<NA>	<NA>	1.0
5	binary	0.0	1.0	q	[5]	<NA>	<NA>	0.0
6	binary	0.0	1.0	q	[6]	<NA>	<NA>	0.0
7	binary	0.0	1.0	q	[7]	<NA>	<NA>	0.0
8	binary	0.0	1.0	q	[8]	<NA>	<NA>	0.0
9	binary	0.0	1.0	q	[9]	<NA>	<NA>	0.0
10	binary	0.0	1.0	q	[10]	<NA>	<NA>	0.0
11	binary	0.0	1.0	q	[11]	<NA>	<NA>	0.0
12	binary	0.0	1.0	q	[12]	<NA>	<NA>	0.0
13	binary	0.0	1.0	q	[13]	<NA>	<NA>	0.0
14	binary	0.0	1.0	q	[14]	<NA>	<NA>	0.0
15	binary	0.0	1.0	q	[15]	<NA>	<NA>	0.0
16	binary	0.0	1.0	q	[16]	<NA>	<NA>	0.0
17	binary	0.0	1.0	q	[17]	<NA>	<NA>	1.0
18	binary	0.0	1.0	q	[18]	<NA>	<NA>	1.0
19	binary	0.0	1.0	q	[19]	<NA>	<NA>	1.0
20	binary	0.0	1.0	q	[20]	<NA>	<NA>	1.0
21	binary	0.0	1.0	q	[21]	<NA>	<NA>	1.0
22	binary	0.0	1.0	q	[22]	<NA>	<NA>	1.0
23	binary	0.0	1.0	q	[23]	<NA>	<NA>	1.0
24	binary	0.0	1.0	q	[24]	<NA>	<NA>	1.0
25	binary	0.0	1.0	q	[25]	<NA>	<NA>	1.0
26	binary	0.0	1.0	q	[26]	<NA>	<NA>	1.0
27	binary	0.0	1.0	q	[27]	<NA>	<NA>	1.0
28	binary	0.0	1.0	q	[28]	<NA>	<NA>	0.0
29	binary	0.0	1.0	q	[29]	<NA>	<NA>	0.0

Visualize the solution#

Finally, we visualize the result.

import matplotlib.pyplot as plt
import matplotlib.patches as patches

solution = df["value"].to_list()
fig, ax = plt.subplots(figsize=(15,8))
ax.tick_params(labelleft=False,left=False,bottom=False)
plt.gca().spines["right"].set_visible(False)
plt.gca().spines["left"].set_visible(False)
plt.gca().spines["top"].set_visible(False)

for i in range(num_cars):
    position = (1.5*i, 0)
    circ = patches.Circle(xy=position, radius=0.5, fc= "k" if solution[i] else "w", ec="k")
    c_txt = plt.text(*position, "C%s"%(sequence[i]), color = "w" if solution[i] else "k", horizontalalignment="center", verticalalignment="center")
    ax.add_patch(circ)
ax.set_xticks(np.arange(num_cars)*1.5, np.arange(num_cars),fontsize=10)   
ax.set_xlim(-1, 1.5*num_cars-0.5)
ax.set_ylim(-1, 1)
ax.set_aspect("equal")
plt.show()

../_images/e519d9ef8b99dbcdc1f5884f3908fc879825843e880ba41146c7c4920f4bc474.png

The color switchings only appear two times in this result.

References#

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