これなに
信号のタイミングを変えて、信号待ちを減らします。
問題
下図のようなネットワークがあり、D, E, H, I の4か所に信号があります。
4人のユーザが それぞれ、下記のように移動します。
- 時刻 0 に、A を出発し L に向かう
- 時刻 2 に、B を出発し K に向かう
- 時刻 1 に、C を出発し J に向かう
- 時刻 2 に、G を出発し F に向かう
信号のタイミングは、4パターンあり、下表のように動けるとします。
| パターン | T1 | T2 | T3 | T4 |
|---|---|---|---|---|
| 0 | 上下 | 左右 | 左右 | 上下 |
| 1 | 上下 | 上下 | 左右 | 左右 |
| 2 | 左右 | 上下 | 上下 | 左右 |
| 3 | 左右 | 左右 | 上下 | 上下 |
このとき、最もスムースに流れる、信号D, E, H, I のタイミングのパターンを求めます。
解いてみる
ネットワーク作成
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);
多品種時空間ネットワークのフローに対応する表を作成
ユーザごとにレイヤをわけます。ユーザ×時×空の3次元になります。
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] # 発生ユーザの始と終と時
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]
| Layer | FrNd | FrTm | ToNd | ToTm | From | To | Weight | |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | J | 0 | J | 1 | J0 | J1 | 0.001 |
| 1 | 0 | A | 0 | A | 1 | A0 | A1 | 0.001 |
| 2 | 0 | B | 0 | B | 1 | B0 | B1 | 0.001 |
定式化して解く
python3
m = LpProblem()
vs = addbinvars(4, 4) # DEHI の offset
a['Var'] = addvars(len(a), upBound=1) # フロー
m += lpDot(a.Weight, a.Var) # 目的関数
for i in range(4):
m += lpSum(vs[i]) == 1 # offsetは１つのみ
for v in a[a.FrNd=='_'].Var:
m += v == 1 # レイヤーごとに発生
for l in range(4):
b = a[a.Layer == l]
for nd in set(b.From.unique()) | set(b.To.unique()):
# 各レイヤーで入と出が等しい
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]]
# 信号制御
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('タイミング', np.vectorize(value)(vs)@np.arange(4))
>>>
Wall time: 79.5 ms
Optimal 32.001000000000005
タイミング [ 1. 3. 2. 0.]
以上