[PYTHON] Smooth flow by optimizing signal control

what is this

Change signal timing to reduce signal waiting.

problem

There is a network as shown below, and there are signals at four locations, D, E, H, and I.

Each of the four users will move as follows:

--At time 0, leave A for L --At time 2, leave B for K --At time 1, leave C for J --At time 2, leave G and head for F

There are 4 patterns of signal timing, and it is assumed that they can move as shown in the table below.

At this time, the timing pattern of the signals D, E, H, and I that flows most smoothly is found.

Try to solve

Network creation

python3

%matplotlib inline
import networkx as nx, matplotlib.pyplot as plt
from more_itertools import chunked
plt.rcParams['figure.figsize'] = 4, 4
g = nx.DiGraph()
for i, ar in enumerate(['ADBECDEFGHIJHKIL', '', 'DEDHEIHI']):
    for fr, to in chunked(ar, 2):
        g.add_edge(fr, to, weight=i+1)
        if i == 2:
            g.add_edge(to, fr, weight=i+1)
pos = {chr(i+65):(int(x),int(y)) for i, (x,y)
    in enumerate(chunked('154504144454011141511040', 2))}
nx.draw(g, pos, node_color='white')
nx.draw_networkx_labels(g, pos);

Create a table corresponding to the flow of a multi-product spatiotemporal network

Separate layers for each user. It is 3D user x time x sky.

python3

import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addvars, addbinvars
def make(g, T):
    stnd, ednd, sttm = 'ABCG', 'LKJF', [0,2,1,2] #The beginning, end, and time of the generating user
    for la in range(4):
        for t1 in range(T):
            for nd in g.nodes():
                yield la, nd, t1, nd, t1+1
            for fr, dc in g.edge.items():
                for to, atr in dc.items():
                    t2 = t1 + atr['weight']
                    if t2 <= T:
                        yield la, fr, t1, to, t2
    for l, c in enumerate(stnd):
        yield l, '_', 0, c, sttm[l]
    for l, c in enumerate(ednd):
        for t in range(8,T):
            t2 = t+sttm[l]
            if t2 < T:
                yield l, c, t2, '_', 0
T = 13
a = pd.DataFrame(make(g, T), columns=['Layer', 'FrNd', 'FrTm', 'ToNd', 'ToTm'])
a['From'] = a.FrNd+a.FrTm.astype(str)
a['To'] = a.ToNd+a.ToTm.astype(str)
a['Weight'] = a.ToTm - a.FrTm
a.loc[a.FrNd == a.ToNd, 'Weight'] = 0.001
a.loc[(a.FrNd == '_') | (a.ToNd == '_'), 'Weight'] = 0
a[:3]

Formulate and solve

python3

m = LpProblem()
vs = addbinvars(4, 4) #DEHI offset
a['Var'] = addvars(len(a), upBound=1) #flow
m += lpDot(a.Weight, a.Var) #Objective function
for i in range(4):
    m += lpSum(vs[i]) == 1 #Only one offset
for v in a[a.FrNd=='_'].Var:
    m += v == 1 #Occurs for each layer
for l in range(4):
    b = a[a.Layer == l]
    for nd in set(b.From.unique()) | set(b.To.unique()):
        #Equal on and out on each layer
        m += lpSum(b[b.From == nd].Var) == lpSum(b[b.To == nd].Var)
for t in range(T):
    b = a[a.FrTm == t]
    for i, s in enumerate(['DH', 'EI', 'HK', 'IL']):
        c = b[b.FrNd==s[0]]
        #Signal control
        m += lpSum(c[c.ToNd==s[1]].Var) <= vs[i][(t+0)%4]+vs[i][(t+1)%4]
        m += lpSum(c[c.ToNd!=s[1]].Var) <= vs[i][(t+2)%4]+vs[i][(t+3)%4]
%time m.solve()
print(LpStatus[m.status], value(m.objective))
print('timing', np.vectorize(value)(vs)@np.arange(4))
>>>
Wall time: 79.5 ms
Optimal 32.001000000000005
timing[ 1.  3.  2.  0.]

that's all