Keyword: 公共サービス, 最適化, 施設配置, セットカバー問題, MILP
公共サービス分野の最適化問題:消防署の最適配置
問題の概要
消防署の最適配置問題は、火災発生時に迅速に対応し、住民の安全を確保するために生じています。限られた数の消防署で管轄エリア全体を効果的にカバーする必要があるため、消防署を戦略的に配置することが重要です。適切な配置により、火災による人的被害や財産の損失を最小限に抑えることができます。さらに、効率的な配置は、消防署の建設・運営コストの削減にもつながります。
この問題を解決するには、いくつかの制約条件を考慮する必要があります。主な制約条件は、各地区が少なくとも1つの消防署によってカバーされるようにすることです。この制約により、全ての地区で一定レベル以上の消防サービスが提供されることを保証します。また、消防署の設置数を最小限に抑えることで、限られた予算内で最大限の効果を発揮することを目指します。
消防署配置の最適化(具体例)
ここでは、ある市における消防署の最適配置問題を考えます。この市には7つの地区(A~G)があり、各地区が少なくとも1つの消防署によってカバーされるようにしたいと考えています。市には消防署の候補地が5ヶ所(1~5)あり、各消防署が担当できる地区は以下の表の通りです。
地区 | 担当可能な消防署の候補地 |
---|---|
A | 1, 2 |
B | 1, 3 |
C | 2, 3 |
D | 2, 4 |
E | 2, 4 |
F | 4, 5 |
G | 5 |
この問題を解くことで、全ての地区をカバーしつつ、必要な消防署の数を最小限に抑える配置を求めることができます。
問題の定式化
パラメータ
パラメータ | 説明 | 値 |
---|---|---|
消防署の候補地数 | 5 | |
地区の数 | 7 | |
候補地 |
1 (全候補地で同一とする) | |
候補地 |
1 (カバー可能), 0 (カバー不可) |
決定変数
変数 | 説明 | 範囲 |
---|---|---|
候補地 |
0 または 1 |
目的関数
目的 | 式 |
---|---|
消防署の設置数の最小化 |
制約条件
制約 | 式 | 説明 |
---|---|---|
カバー制約 | 各地区が少なくとも1つの消防署によってカバーされる | |
二値制約 | 各候補地には消防署を配置するか配置しないかのどちらか |
コード例
以下に、この混合整数線形計画問題を nAG Library for Python のMILP ソルバー関数 handle_solve_milp を用いて解くコード例を示します。
今回の問題は変数と制約条件の数が比較的少なく、小規模な混合整数線形計画問題であるため、汎用的なMILPソルバーである handle_solve_milp を選択しました。
import numpy as np
from naginterfaces.base import utils
from naginterfaces.library import opt
from naginterfaces.library import mip
# 問題のサイズ
= 5 # 消防署の候補地数
n_stations = 7 # 地区の数
n_districts
# 目的関数の係数(各消防署のコスト)
= np.ones(n_stations)
c
# 制約条件の係数行列(各消防署が担当できる地区)
= np.array([
A 1, 1, 0, 0, 0], # 地区A
[1, 0, 1, 0, 0], # 地区B
[0, 1, 1, 0, 0], # 地区C
[0, 1, 0, 1, 0], # 地区D
[0, 1, 0, 1, 0], # 地区E
[0, 0, 0, 1, 1], # 地区F
[0, 0, 0, 0, 1] # 地区G
[
])
# 制約条件の右辺
= np.ones(n_districts)
bl = np.full(n_districts, np.inf)
bu
# 変数の下限と上限
= np.zeros(n_stations)
xl = np.ones(n_stations)
xu
# nAGのハンドルを作成
= opt.handle_init(nvar=n_stations)
handle
# 目的関数を設定
=c)
opt.handle_set_linobj(handle, cvec
# 線形制約条件を設定
=bl, bu=bu, irowb=A.nonzero()[0]+1, icolb=A.nonzero()[1]+1, b=A[A.nonzero()])
opt.handle_set_linconstr(handle, bl
# 変数の下限と上限を設定
=xl, bu=xu)
opt.handle_set_simplebounds(handle, bl
# 変数を0-1の整数に設定
=handle, ptype='BINARY', idx=list(range(1, n_stations+1)))
opt.handle_set_property(handle
# アルゴリズムのオプションを設定
'Print Level = 0')
opt.handle_opt_set(handle,
# 問題を解く
= mip.handle_solve_milp(handle)[0]
x
# 結果を表示
print(f'必要な消防署の数: {int(sum(x))}')
print(f'配置する消防署: {np.where(x > 0.5)[0] + 1}')
# ハンドルを破棄
opt.handle_free(handle)
結果例
コードを実行した結果、以下のような出力が得られました。
必要な消防署の数: 3
配置する消防署: [2 3 5]
この結果から、最適解は候補地2、3、5に消防署を配置することであり、必要な消防署の数は3であることがわかります。この配置により、全ての地区が少なくとも1つの消防署によってカバーされ、かつ消防署の設置数が最小限に抑えられています。
まとめ
ここでは、混合整数線形計画法を用いて消防署の最適配置問題を定式化し、nAG Library for Pythonのソルバーを用いて最適解を求めました。得られた結果は、限られた資源で最大限の効果を発揮する消防署の配置を提示しています。この手法は、消防署の配置問題だけでなく、他の公共施設や民間施設の配置問題にも応用可能です。例えば、警察署、救急車の配備拠点、小売店舗、倉庫など、様々な施設の最適配置に活用できます。さらに、モデルに新たな制約条件を追加することで、より現実的な問題設定に対応することも可能です。例えば、消防署間の距離制約や、各消防署の能力の差異を考慮するなどの拡張が考えられます。