# Traffic lights optimization

I am interested in the following problem dealing with the optimization of traffic lights on the intersection illustrated below:

The goal is maximize the duration during which each movement $$m\in M=\{a,...,j\}$$ has a green light, subject to the following constraints:

• incompatible movements cannot be done simultaneously
• each movement has to have a green light for at least $$s$$ seconds
• the duration of a complete cycle must equal $$C$$ seconds

One strategy is to:

1. Consider the compatibility graph $$G=(V,E)$$ (an edge exists between two movements if they can be done simultaneously):

1. Find a vertex cover of cliques (sets of pairwise compatible movements) ordered in a circular fashion:

1. Solve the following linear program: let $$t_i$$ be a continuous variable representing duration of green light for clique $$K_i$$, and maximize $$\sum_{m\in M}\sum_{i|m\in K_i} t_i$$ subject to $$\left\{\sum_i t_i=C,\sum_{i|m\in K_i} t_i \ge s \; \forall m\in M \right\}$$.

I find Step 2 (order the maximal cliques in a circular fasion) to be a bit tedious and am trying to figure out a (mixed integer) linear formulation for this problem. Any suggestions are welcome.

If a movement belongs to $$c$$ cliques, then you want $$c-1$$ of those cliques to be followed by another clique from the same set.

Let $$k$$ be the number of cliques and let $$H_m=\lbrace i : m\in K_i\rbrace$$ for all movements $$m\in M.$$ Define binary variables $$z_{ij}$$ for all pairs of clique indices $$i\neq j,$$ where $$z_{ij}=1$$ will signal that clique $$j$$ follows clique $$i$$ in a clockwise traversal of your circle. Fix $$z_{ii}=0$$ for all $$i$$ (to simplify the indexing in what follows) and dd the constraints $$\sum_{i=1}^k z_{ij} = 1\quad \forall j\in \lbrace 1,\dots, k\rbrace$$ and $$\sum_{j=1}^k z_{ij} = 1\quad \forall i\in \lbrace 1,\dots, k\rbrace$$ to ensure that every clique is preceded/followed by exactly one clique.

Now for each movement $$m$$ add the constraint $$\sum_{i,j\in H_m : i < j} ( z_{ij} + z_{ji}) \ge \vert H_m \vert - 1.$$ This says that the total number of transitions between cliques containing $$m$$ has to be at least the number of such cliques minus 1, or equivalently that the number of times in a cycle you transition from a clique containing $$m$$ to a clique not containing $$m$$ is at most 1. (I used $$\ge$$ rather than $$=$$ in case you might have a movement permissible throughout the entire cycle of the light.)

• Thank you! Your formulation requires having the cliques at disposal though. I am not 100% sure that finding such cliques so that your formulation is always feasible is easy. Would it be safer to build the cliques within the formulation ? Commented Apr 13, 2023 at 11:36
• To clarify my question: a movement $m$ can of course belong to different cliques, but not all such cliques must define $H_m$. $H_m$ must be defined such that a circular layout is possible, and this is the part that I find difficult to anticipate. Perhaps we could add a binary variable for all possible cliques (?) and select only the appropriate ones (??)..not sure. Commented Apr 13, 2023 at 11:42
• Your question was predicated on maximal cliques, so I assumed that you wanted to use those (only) in your model. You can certainly include other cliques and binary variables indicating which cliques are used. The RHS of my first two constraints would change from 1 to the binary variable for clique j or i being used, and $\vert H_m\vert$ would change to the sum of the binary variables for cliques containing movement $m.$
– prubin
Commented Apr 13, 2023 at 15:49

I'd try by defining binary variables $$x$$ indexed on set of compatible edges $$E$$ & time $$t$$ over set $$C$$. Also define a set of edges, F where simultaneous movement is possible. Then add constraints like:
$$sx_{\epsilon,t-1} - \sum_{k=1}^{t-2}x_{\epsilon,k} \le sx_{\epsilon,t} \quad \forall \epsilon \in E \ \ \forall t$$: ensures contiguous allocation of $$\ge s$$ secs

$$\sum_{\epsilon} x_{\epsilon,t} \le 1 \ \forall t \quad \forall \epsilon \in E\setminus F$$