最大被覆問題(MCLP)入門¶
1. はじめに¶
集合被覆問題(LSCP)は「すべての需要をカバーする最小の施設数」を求めるモデルであった。しかし現実には、予算の制約で施設数の上限が先に決まっており、その数ではすべての需要をカバーしきれないことも多い。このようなとき、「決められた数の施設で、カバーできる需要をできるだけ多くする」と考えるのが最大被覆問題(Maximal Covering Location Problem、MCLP)である。
LSCP では施設数が出力だったのに対し、MCLP では施設数 $p$ が入力になり、カバーされる需要量が目的関数になる。全需要のカバーが不可能な状況でも、MCLP は実行不能にならず「最善のカバー」を返してくれる。
本資料は講義スライド(最大被覆問題.pdf)の補足であり、p-median 問題入門と同じ地域データを使ってMCLP をPuLP で解く。課題はレポート雛形(MCLP_課題_学籍番号_氏名.docx)に従って提出すること。
2. 前提知識と学習目標¶
本資料を読む前に、p-median 問題入門とLSCP 入門を読んでいることが望ましい(同じ地域データと同じ流儀の定式化を使う)。
学習目標¶
- MCLP が「施設数の上限のもとでカバー需要を最大化する」モデルであることを説明できる。
- LSCP との違い(入力と出力の関係)を説明できる。
- PuLP でモデルを作り、答えを得て、施設数や被覆距離を変えた実験ができる。
3. 問題設定と定式化¶
3.1 問題の具体例¶
p-median 問題入門と同じ地域を使う。12個の街(需要点、人口つき)と3か所の店舗配置候補点がある。施設は直線距離で3.5 km 以内の需要点をカバーできるとし、施設は2か所まで建てられる。カバーできる人口の合計を最大にするには、どの2か所を選べばよいだろうか。
3.2 数学的な定式化¶
3.2.1 定数および決定変数の定義¶
| 名前 | 説明 |
|---|---|
| $I$ | 需要点の集合(この例では12か所) |
| $J$ | 候補点の集合(この例では3か所) |
| $w_i$ | 需要点 $i$ の人口 |
| $D$ | 被覆距離(この例では3.5 km) |
| $N_i$ | 需要点 $i$ をカバーできる候補点の集合 |
| $p$ | 建てられる施設数の上限(この例では2) |
| $x_j$ | 候補点 $j$ に施設を建てるなら1、そうでなければ0 |
| $y_i$ | 需要点 $i$ がカバーされるなら1、そうでなければ0 |
3.2.2 数理モデル¶
$$ \begin{align} \max \ \ & z = \sum_{i \in I} w_i y_i \\ \text{s.t. } \ \ & y_i \leq \sum_{j \in N_i} x_j, \quad \forall i \in I, \\ & \sum_{j \in J} x_j \leq p, \\ & x_j, y_i \in \{0, 1\}. \end{align} $$
目的関数はカバーされた需要点の人口の合計である。1本目の制約は「需要点 $i$ をカバーできる候補点に施設がなければ $y_i = 0$」を表す。2本目は施設数の上限である。LSCP の目的関数と制約が入れ替わったような構造になっていることを確かめてほしい。なお記号の使い方(需要点が $i$、候補点が $j$)は講義スライドとレポート雛形に合わせている。
4. Python + PuLP による実装¶
4.1 準備¶
Google Colab で実行する際には、必ず最初に以下のプログラム2行目のコメントを外して実行すること。また demand.csv と pfl.csv(p-median 問題入門と同じもの)を同じフォルダに置くこと。
# Google Colab の場合は2行目のコメントを外して実行: ライブラリインストール(1回だけ)
# !pip install pulp matplotlib numpy
import math
import numpy as np
import pulp
import matplotlib.pyplot as plt
demands = np.loadtxt('demand.csv', delimiter=',') # 各行 [x, y, 人口]
pfls = np.loadtxt('pfl.csv', delimiter=',') # 各行 [x, y]
I = range(len(demands)) # 需要点
J = range(len(pfls)) # 候補点
D = 3.5 # 被覆距離
p = 2 # 施設数の上限
dist = [[math.dist(pfls[j][:2], demands[i][:2]) for i in I] for j in J]
N = {i: [j for j in J if dist[j][i] <= D] for i in I}
w = demands[:, 2]
print(f'候補点 {len(pfls)}, 需要点 {len(demands)}, 総人口 {int(w.sum())}')
print('カバーできる候補点が存在しない需要点:', [i for i in I if not N[i]])
候補点 3, 需要点 12, 総人口 6000 カバーできる候補点が存在しない需要点: [5, 10]
どの候補点からもカバーできない需要点がいくつか存在する。したがって被覆距離3.5 km では、施設をすべての候補点に建てたとしても全人口はカバーできない(LSCP なら実行不能になる状況である)。MCLP はこの状況でも「カバーできる分を最大化する」答えを返す。
4.2 モデル構築と求解¶
prob = pulp.LpProblem('MCLP', pulp.LpMaximize)
x = pulp.LpVariable.dicts('x', J, cat='Binary') # 候補点に施設を建てるか
y = pulp.LpVariable.dicts('y', I, cat='Binary') # 需要点がカバーされるか
prob += pulp.lpSum(w[i] * y[i] for i in I) # カバー人口の最大化
for i in I:
prob += y[i] <= pulp.lpSum(x[j] for j in N[i]) # カバー判定
prob += pulp.lpSum(x[j] for j in J) <= p # 施設数の上限
prob.solve(pulp.PULP_CBC_CMD(msg=0))
print('求解結果:', pulp.LpStatus[prob.status])
print(f'カバー人口の最大値: {int(pulp.value(prob.objective))} / {int(w.sum())}')
print('開設候補点番号:', [j for j in J if x[j].value() == 1])
print('カバーされない需要点:', [i for i in I if y[i].value() == 0])
求解結果: Optimal カバー人口の最大値: 5100 / 6000 開設候補点番号: [0, 1] カバーされない需要点: [5, 10]
最適解では候補点0 と1 に施設を建て、総人口6000人のうち5100人(85%)をカバーできる。残り900人はどの施設からも3.5 km 以内に入らない。この「切り捨てられる需要」を明示できることがMCLP の特徴であり、例えば「施設をもう1つ増やせば何人救えるか」という問いに答えられる。
4.3 感度分析: 施設数と被覆距離を変える¶
def solve_mclp(D, p):
N = {i: [j for j in J if dist[j][i] <= D] for i in I}
prob = pulp.LpProblem('MCLP', pulp.LpMaximize)
x = pulp.LpVariable.dicts('x', J, cat='Binary')
y = pulp.LpVariable.dicts('y', I, cat='Binary')
prob += pulp.lpSum(w[i] * y[i] for i in I)
for i in I:
prob += y[i] <= pulp.lpSum(x[j] for j in N[i])
prob += pulp.lpSum(x[j] for j in J) <= p
prob.solve(pulp.PULP_CBC_CMD(msg=0))
return int(pulp.value(prob.objective)), [j for j in J if x[j].value() == 1]
for D_test in [3.0, 3.5, 4.0]:
for p_test in [1, 2, 3]:
z, sites = solve_mclp(D_test, p_test)
print(f'D={D_test}, p={p_test}: カバー人口={z}, 開設={sites}')
D=3.0, p=1: カバー人口=1800, 開設=[2] D=3.0, p=2: カバー人口=3500, 開設=[1, 2] D=3.0, p=3: カバー人口=3900, 開設=[0, 1, 2] D=3.5, p=1: カバー人口=3200, 開設=[0] D=3.5, p=2: カバー人口=5100, 開設=[0, 1] D=3.5, p=3: カバー人口=5100, 開設=[0, 1, 2] D=4.0, p=1: カバー人口=3200, 開設=[0] D=4.0, p=2: カバー人口=5600, 開設=[0, 1] D=4.0, p=3: カバー人口=5600, 開設=[0, 1, 2]
施設数 $p$ を増やすほど、また被覆距離 $D$ を大きくするほどカバー人口は増えるが、その増え方は一定ではない。$p$ を2から3に増やしたときの増分が、1から2に増やしたときより小さいことに注目してほしい(効果の逓減)。こうした分析が施設整備の投資判断の材料になる。
5. 課題¶
ある市で、災害時に水を配る給水ステーションを設置したい。設置できる候補地は6か所あり、そのうち設置できるのは2か所までである。各候補地がカバーできる地区と、各地区の人口は次の表のとおりである。カバーされる人口の合計が最大になるように、どの候補地を選べばよいか。
地区には1〜8のIDを付ける(名称との対応表も示す)。
| 地区ID | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 地区名 | A | B | C | D | E | F | G | H |
| 人口 | 50 | 30 | 80 | 40 | 60 | 20 | 70 | 45 |
| 候補地ID | カバーできる地区(ID) |
|---|---|
| 1 | 1, 2, 3 |
| 2 | 3, 4, 5 |
| 3 | 5, 6, 7 |
| 4 | 1, 7, 8 |
| 5 | 2, 4, 6 |
| 6 | 3, 7, 8 |
- この問題を第3節のMCLP に当てはめよ($p = 2$)。
- PuLP で実装して解き、選ぶべき候補地、カバーされる人口の合計、カバーされない地区を求めよ。
- 結果をレポート雛形(
MCLP_課題_学籍番号_氏名.docx)に整理して提出すること。
6. 参考文献¶
- R. Church and C. ReVelle, The maximal covering location problem, Papers of the Regional Science Association, vol.32, pp.101-118, 1974.
7. 注意事項¶
小さな問題なので、施設の組合せ(3か所から2か所を選ぶのは3通り)を全部試せば手でも解ける。プログラムの結果と一致することを確認してみるとよい。理解できない場合には指導教員まで相談すること。
8. 卒業研究概要への手引き¶
- このテーマを卒業研究のテーマにしたい場合は、ここの対応をすること(必ず事前に相談すること)。
- 以下、すべて含めて、A4用紙2枚にまとめること。
- 厳密に守る必要はないが、文章量の比率を目安にすること(15%とは、A4用紙2枚分の15%という意味)。
1章 はじめに(文章量の比率: 15%)¶
- 施設配置問題とは何か、MCLP以外にどのような施設配置問題があるのか(集合被覆問題との違いに触れる)まとめること。
- 最大被覆問題に関する先行研究を紹介すること。
- 施設配置問題を解く際に使われる整数計画法とは何か、まとめること。
2章 MCLP(文章量の比率: 30%)¶
- MCLPの数理モデルについて、説明すること。すべての需要を覆う集合被覆問題に対し、限られた施設数で覆える需要を最大化するという考え方の違いも説明すること。
3章 実験(文章量の比率: 40%)¶
3.1節 概要¶
- 第5節の課題を解いた過程を説明すること。
- さらに、需要と候補地の構成を自分で変えた問題を作成して解き、結果を図または表で示すこと。
3.2節 結果と考察¶
- カバーされる人口の合計がいくつになったか、カバーされない需要がどこかを示すこと。
- そのカバー人口が何を意味しているか説明すること。
- 結果から、どのようなことが言えるか、考え説明すること。
4章 おわりに(文章量の比率: 15%)¶
- 今回の実験に対する感想を記載すること。
- 例えば、直感で施設を配置するのと数理モデルにより配置するのでは、どちらがよさそうか、また良い理由を記載すること。
参考文献¶
参考にした資料を、2〜3件記載すること。以下、書き方の例である。
- [1] 柿本ほか, XXXに関する分析, XXX学会論文誌, 2020.
- [2] XXXに関する情報, http://xxx.ddd.ttt.com, 2020年4月20日閲覧
本文中で引用する場合は「柿本らはXXXを実施している [1]。また、〜」のように、どこで引用したのか明白にすること。