救急車配置問題 - OR機関誌10月号より

これなに

OR学会の機関誌10月号「学生たちのOR」特集から、適当に最適化の問題をピックアップしてPythonで解いてみたいと思います。
準備として、pandas, pulp, ortoolpy が必要です。環境構築は、組合せ最適化を使おうを参考にしてください。

救急車配置問題

論文「救急車再配置問題に対する遺伝的プログラミングを用いた効果的手法の設計」の問題を使わせてもらいましょう。
論文では、救急車再配置問題ですが、ここでは、救急車配置問題にします。

複数の地域に救急車を配置する。各地域には、配置可能な容量、需要量が定められる。また、移動は10分以内でないといけない。このとき、総移動時間を最小化せよ。

考え方

p-メディアン問題なのでサクッと解きましょう。

Pythonで解く

まず、ランダムなデータを作成します。

python

import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addvar, addvars

n = 3 # 地域数
rn = range(n)
np.random.seed(2)
tm = (np.random.rand(n, n) * 20).round(0)
tm[np.diag_indices(n)] = 0
tm # 移動時間(分)
>>>
array([[  0.,   1.,  11.],
       [  9.,   0.,   7.],
       [  4.,  12.,   0.]])

python

cap = np.random.randint(2, 5, n)
cap # 容量
>>>
array([4, 2, 2])

python

dem = np.random.randint(2, 4, n)
dem # 需要
>>>
array([2, 3, 3])

変数表を作成します。このとき、移動時間が10分以上の変数は作成しないようにします。

python

a = pd.DataFrame(((i,j,dist[i,j]) for i in rn for j in rn
        if dist[i,j]<=10), columns=['From', 'To', 'Tm'])
a['Var'] = addvars(len(a))
a[:3]

	From	To	Tm	Var
0	0	0	0.0	v1
1	0	1	1.0	v2
2	1	0	9.0	v3

定式化して解いてみましょう。

python

m = LpProblem()
m += lpDot(a.Tm, a.Var)
for i, t in a.groupby('From'):
    m += lpSum(t.Var) <= cap[i]
for i, t in a.groupby('To'):
    m += lpSum(t.Var) >= dem[i]
m.solve()
a['Val'] = a.Var.apply(value)
a[a.Val > 0]

	From	To	Tm	Var	Val
0	0	0	0.0	v1	2.0
1	0	1	1.0	v2	2.0
3	1	1	0.0	v4	1.0
4	1	2	7.0	v5	1.0
6	2	2	0.0	v7	2.0

以上