In the easy-to-learn optimization flow, we have taken an easy-to-explain problem and explained the process of performing combinatorial optimization processing with an annealing machine by defining requirements, formulation, input data preparation, and executing. Let's take your learning one step further by experiencing the development flow of a combinatorial optimization system using a CMOS annealing machine through a series of steps from problem requirements definition to executing.

This article provides an exercise to realize a signal control system to relieve traffic congestion as a signal control system by processing it with a CMOS annealing machine as a combinatorial optimization problem.

Although traffic signals are not currently controlled by processing them as a combinatorial optimization problem, the economic loss caused by traffic congestion is said to be enormous, and it is one of the social issues that need to be addressed. Eliminating traffic congestion is expected to be effective in reducing economic losses and energy consumption.

The contents of this page are based on the paper by Toyota Central R&D Labs., Inc. and the University of Tokyo [1] and the blog post by Jij Inc. [2], which is based on the paper, and are reorganized so that you can practice what you have learned in "Easy-to-learn optimization flow" as an exercise for CMOS annealing machines. The knowledge explained in "Easy-to-learn optimization flow" is added to the explanation of defining requirements, constraint setting, formulation, etc. defined in the above paper and blog, which are the preliminary steps to perform in CMOS annealing, aiming to provide both review and application.

- [1]Toyota Central R&D Labs, University of Tokyo, "Traffic Signal Optimization on a Square Lattice
with Quantum
Annealing".

https://arxiv.org/abs/2003.07527 - [2] A blog by Jij Inc. that explains the same paper in detail.

Signal Control Optimization on a Square Grid Intersection Cluster Using D-Wave

What optimization problem can be formulated to solve the practical problem of reducing traffic congestion? The objective of the optimization problem discussed here is to reduce traffic congestion by making cars flow as smoothly as possible. In other words, what we want to achieve is to equalize the number of cars waiting vertically and horizontally at each intersection through signal control. For this problem, let's define the requirements, i.e., the language to communicate to the computer what we want to do.

- Roads are given as grids.
- All intersections are adjacent to four intersections, up, down, left, and right.
- Vertical and horizontal signals are installed.

Adapted from reference [2]

- Vehicles may go straight, turn left, or turn right at intersections.
- Let $a$ be the fraction of cars going straight at the intersection.
- The ratio of cars turning left and right is considered to be the same and expressed as $(1-a)/2$, respectively.

Adapted from reference [2]

One difficulty with this problem is that trying to eliminate the bias in the number of cars at an intersection can have a positive or negative impact on the number of cars at neighboring intersections, and the conditions for optimization change over time. How do we model this complex assumption?

First, we define "improving the state" for each and every intersection. To improve the condition of each and every intersection means to change one signal to green and the signal in the crossing direction to red.

However, it cannot be left to luck to determine whether operating a single intersection will move the entire area in the direction of eliminating traffic congestion. If a horizontal traffic signal is left green and left unattended, vertical traffic will naturally become congested. Next, we must define the "relationship between intersection $i$ and $j$" and the "relationship between time ($t$) and time ($t+1$)," taking into account time variation.

Next, let us formulate the signal control as an Ising model. At this point, we will try to incorporate changes in the time direction by including the "time variation considerations" described in the previous section.

First we assign the Ising variables $+1$ and $-1$ to the signal control, which is the smallest element for "improving the state" of each and every intersection.

- If there are more vertical vehicles than horizontal vehicles at intersection $i$, we want to assign the vertical signal to green. That is, $\sigma_i=+1$
- If there are more horizontal vehicles than vertical vehicles at intersection $i$, we want to assign the horizontal signal to green. That is, $\sigma_i=-1$

Adapted from reference [2]

The direction (vertical or horizontal) of the signal to be green could be set as an Ising variable.

Next, for the ultimate goal of optimization, which is to eliminate traffic congestion, we consider modeling with consideration given to the flow of time and the state of each case.

The object to be optimized, i.e., the state of the signal, is given by the quantity of cars at the next time. The amount of cars at the next time can be expressed using the signal assignment $\sigma$ at the immediately preceding time t and the ratio $a$ of the direction of car travel.

Two variables are defined for the quantity of cars: $q_{ij}$ and $x_i$. $q_{ij}$ is used to represent the quantity of cars moving from intersection $j$ to intersection $i$. On the other hand, $x_i$ is a variable that represents the amount of cars waiting at an intersection. Let's first take a closer look at the definition of $q_{ij}$.

- Let $q_{ij}(t)(≠q_{ji})$ be the amount of cars on the road connecting intersection $j$ to intersection $i$ at time $t$
- Let $\sigma_i(t)$ and $\sigma_j(t)$ be the traffic light parameters at intersections $i$ and $j$ at time $t$, respectively
- Then the quantity of cars on road $j$→$i$ at time $t+1$ is
#### $$\tag*{Equation(1)} q_{ij} (t+1) = q_{ij} + \frac{s_{ij}}{2} ( - \sigma_i (t) + \alpha \sigma_j (t))$$

Adapted from reference [2]

where $s_{ij}$ is the road direction parameter, $s_{ij} = +1$ if road $j→i$ is vertical and $s_{ij} = -1$ if road $j→i$ is horizontal.

$q_{ij}$ represents the quantity of cars at the previous time, $-s_{ij}\sigma_i(t)/2$ represents the quantity of cars leaving, and $s_{ij}\alpha_{\sigma_j}(t)/2$ represents the quantity of cars coming in. In other words, equation (1) shows that the quantity of cars at time (t+1) represents the quantity of cars at the previous time plus the quantity of cars coming in and the quantity of cars going out. Note that $\alpha=2a-1$ is substituted to simplify the equation.

Next, let's look at how the variable $x_i$ is defined.

- Let $q_{ij}$ denote the average value $x_i$ of the difference between the amount of cars waiting
vertically and horizontally at
intersection $i$.
#### $$\tag*{Equation(2)} x_{i} (t) = \frac{1}{2} \sum_{j \in N(i)} s_{ij} \cdot q_{ij} (t)$$

Adapted from reference [2]

In other words, equation (2) represents the amount of vehicles heading from intersection $j$ to intersection $i$ and waiting at intersection $i$.

$s_{ij}$, which constitutes equation (2), is the directional parameter of the road, and $q_{ij}$ is the amount of cars entering intersection $i$ from intersection $j$. In other words, it adds up to the case where the vertical direction is red and cars are waiting, and the horizontal direction is red and cars are waiting.

Let us imagine where cars enter and exit in the four directions adjacent to intersection $i$ when
$\sigma_i = +1$ and $\sigma_i = -1$,
respectively. For intersection $i$, there are four possible intersections $j$. To account for the
amount of cars from each
of them, the formula is $\Sigma$.

Cars waiting vertically at intersection $i$ may come from the north or from the south. And the cars
waiting horizontally
at intersection $i$ may come from the east or from the west.

If the amount of cars waiting vertically and horizontally is not biased, it approaches $x_i(t) = 0$.

- From equations (1) and (2), the quantity of cars on the road adjacent to intersection $i$ at
time $t+1$, $x_i(t+1)$, is
#### $$ \begin{align*} \tag*{Equation(3)} x_{i} (t+1) &= \frac{1}{2} \sum_{j \in N(i)} s_{ij} \cdot q_{ij} (t+1) \\ &= \frac{1}{2} \sum_{j \in N(i)} s_{ij} \cdot q_{ij} + \frac{1}{2} ( - \sigma_i (t) + \alpha \sigma_j (t) ) \\ &= x_i (t) + \frac{1}{4} \sum_{j \in N(i)} ( - \sigma_i (t) + \alpha \sigma_j (t) ) \end{align*} $$

Adapted from reference [2]

Now we have an equation that expresses the relationship between the color of the traffic light at an intersection and the amount of cars.

We have been able to model the relationship between the amount of cars and the color of the signal. Now we can proceed to optimize it with a CMOS annealing machine. For the relational equation we have established, we can evaluate it as follows, taking into account what kind of operation "makes it better" to achieve our objective.

- If $x_i(t+1) > 0$, the vertical signal is green because of the amount of vertical cars
- When $x_i(t+1) < 0$, the horizontal signal is green because of the number of horizontal cars

Rewriting this in matrix form for all intersections yields the following equation

Adapted from reference [2]

The optimization is to equalize the number of vehicles waiting horizontally and vertically at a given
intersection.

In other words, it can be said to be a problem of determining the signal assignment
$\boldsymbol{\sigma}(t)$ such that $\boldsymbol{x}(t+1)$ is close to $0$. By squaring this, $0$ is the
minimum value. Therefore, the objective function can be set as follows

This is how the square of the matrix representation is written: the symbol $^T$ is called a transpose, which means to swap the rows and columns of a matrix; to square the vector $\boldsymbol{x}_i(t+1)$, the $\boldsymbol{x}(t+1)$ to be transposed is the row component, and the $\boldsymbol{x}(t+1)$ in the column direction is multiplied to it, indicating the operation. The reference link [4] describes it clearly.

Reference [3]: On the product of transposed vectors

This section explains that the relational expression in (3) can be rewritten in matrix form as (4). A matrix is "a collection of numbers and formulas with similar properties that can be written together in the form of a matrix to simplify computation."[4]

Reference[4] What is
Matrix, Meaning/Purpose of Matrix

Although Equation (3) allows us to establish a relationship between the intersection and its four neighboring intersections (signal color and vehicle volume) at time $t+1$ at intersection $i$ and the previous time $t$, it does not express the objective of making the vehicle volume uniform at all intersections in the entire area. Furthermore, the energy function is not in the form that would result in the least amount of energy for the optimal solution. To solve all these problems at once, and to create an equation that calculates the state of all intersections, and to represent it simply, we will use "matrices" here.

For the sake of understanding, let us define 9 intersections arranged in a grid with 3 horizontal rows and 3 vertical columns, and represent them in matrix representation.

Matrix representation of 9 intersections

The variables $x_i(t)$ and $x_i(t+1)$ in equation (3) represent the state of a single intersection, while $x(t)$ and $x(t+1)$ in the matrix notation of equation (4) are in vector notation and represent all intersections simultaneously, so the meaning is different. In addition to the fact that the $i$'s can be taken, the typefaces are often expressed differently in terms of appearance.

A *vector is a matrix whose components are in a single column or row.

(4") is the distribution of ( ) in (4), where $I$ is called the identity matrix, and is the matrix representation as $\sigma_i(t)$ outside of $\Sigma$, which was inside $\Sigma$ in (3), but. Since $\Sigma$ represents the addition of the terms of road $j$ in the four directions for each intersection $i$, the terms of $i$ can be calculated outside of $\Sigma$.

(4") is further rewritten as a matrix representation of the components, with each term corresponding to (4'). The last term on the right-hand side is the component of $j$ that adds up to $\Sigma$. $A$ represents the component matrix that specifies the intersection in the four directions relative to intersection $i$. In this case, we have the following nine intersections in matrix form: for intersection 1, it is the adjacent numbers 2 and 4 that are designated as $j$. In (4"), the $i=1$ relation computes the elements of the first row.

Now that we know what is involved in processing the matrix representation, we will process it to form it as a cost function at the next section.

Speaking of constraints, the increase in the number of vehicles at an intersection may cause congestion at adjacent intersections, but these constraints have already been taken into account in the modeling up to this point, so there is no need to consider new ones.

There is something else to consider in this problem. In this problem, signals change to reduce vehicle congestion, but if they change too frequently, they can impede the flow of vehicles. Therefore, it is necessary to set a penalty (weighting) for cases where the signal changes at adjacent times. This is the optimal solution.

Adapted from reference [2]

This is the matrix representation of $\boldsymbol{\sigma}$, i.e., the difference between time $t$ and the previous time $t-1$ for the entire area $\boldsymbol{\sigma}$, and then squared.

The value of $\boldsymbol{\sigma}(t)-\boldsymbol{\sigma}(t-1)$ is $0$ if it is the same at time $t$ and $t-1$, and $+2$ (or $-2$) if it is different.

With the derived cost and penalty functions, the energy function of the Ising model for obtaining the optimal solution is as follows

Writing all this down in terms of $\boldsymbol{\sigma}(t)$, we get

$J$,$h$ is as follows. $c(t)$ is the constant term.

Adapted from reference [2]

The annealing machine is now ready to be shaped in such a way that it can derive the optimal solution.

Now that we have defined the requirements and formulated the formulation (modeling, setting the objective function, and organizing the constraints).

From this point on, let's narrow down the range of roads and consider $3 \times 3 = 9$ intersections, and actually create and run the data to be input to the CMOS annealing machine.

How was it? Here is a video of an even larger road with optimized signal control. This demonstration shows the results of a simulation in which traffic congestion is eliminated by optimizing 64 x 64 = 4096 intersections using a large-scale CMOS annealing system to be exhibited in the Cooperative Research Building at Hitachi, Ltd.

This article is part of the ACW Skills Roadmap. Use the skills roadmap to learn with ACW.

Did you find the article helpful? Please share it with others.