7
$\begingroup$

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

enter image description here

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):

enter image description here

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

enter image description here

  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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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.)

$\endgroup$
3
  • $\begingroup$ 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 ? $\endgroup$
    – Kuifje
    Commented Apr 13, 2023 at 11:36
  • $\begingroup$ 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. $\endgroup$
    – Kuifje
    Commented Apr 13, 2023 at 11:42
  • $\begingroup$ 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.$ $\endgroup$
    – prubin
    Commented Apr 13, 2023 at 15:49
-1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.