p-median 問題による最適なスーパーマーケットの配置計画の立案¶
- ある地域にスーパーマーケットのような施設を複数建設する際には、満たさなければいけない条件の下で利便性を上げることを考える必要がある。
- そのような問題を施設配置問題と呼ぶ。
- ここでは代表的な施設配置問題であるp-median問題をpython を使って実装し、卒業研究として仕上げることを目標とする。
おまじないとして以下のコードをコピペして実行すること。
このセルでは、地域を描画するための関数plot_region を定義している。
この関数一つで、
- 街と店舗配置候補点だけの描画（引数
x,yを渡さない） - 求解結果の描画（引数
x,yを渡す） の両方ができる。
from matplotlib import pyplot as plt
def plot_region(demands, pfls, x=None, y=None):
"""対象地域を描画する関数
Parameters
----------
demands : np.ndarray, shape=(需要点数, 3)
各行が [x座標, y座標, 人口] の需要点データ
pfls : np.ndarray, shape=(配置点数, 2)
各行が [x座標, y座標] の配置点データ
x : np.ndarray or None, shape=(需要点数, 配置点数)
x[i, j]=1 なら需要点i の住民が配置点j の店舗を利用。
None なら配分の線は描画しない。
y : np.ndarray or None, shape=(配置点数,)
y[j]=1 なら配置点j に店舗が配置されている。
None なら店舗配置の強調表示はしない。
"""
fig, ax = plt.subplots(figsize=(8, 8))
# データ全体の座標範囲からマージンとアノテーションオフセットを計算
all_x = list(demands[:, 0]) + list(pfls[:, 0])
all_y = list(demands[:, 1]) + list(pfls[:, 1])
x_min, x_max = min(all_x), max(all_x)
y_min, y_max = min(all_y), max(all_y)
x_range = x_max - x_min or 1.0
y_range = y_max - y_min or 1.0
margin = max(x_range, y_range) * 0.1
ann_dx = x_range * 0.035
ann_dy = y_range * 0.035
ax.set_xlim(x_min - margin, x_max + margin)
ax.set_ylim(y_min - margin, y_max + margin)
ax.set_aspect('equal')
# 配分の線（x が与えられたときのみ）
if x is not None:
for i in range(len(demands)):
for j in range(len(pfls)):
if x[i, j] == 1:
ax.plot(
[demands[i, 0], pfls[j, 0]],
[demands[i, 1], pfls[j, 1]],
color='steelblue', alpha=0.5, linewidth=1.5, zorder=1,
)
# 需要点（青）
ax.scatter(demands[:, 0], demands[:, 1], s=250, zorder=2)
for i in range(len(demands)):
# ノード番号（白字、中央寄せ）
ax.text(demands[i, 0], demands[i, 1],
str(i + 1), color='white', size=10, fontweight='bold',
ha='center', va='center', zorder=3)
# 人口（青字、右上）
ax.text(demands[i, 0] + ann_dx, demands[i, 1] + ann_dy,
str(int(demands[i, 2])), color='steelblue', size=9,
ha='left', va='bottom')
# 配置点（赤）
ax.scatter(pfls[:, 0], pfls[:, 1], c='tomato', s=300, zorder=2)
# 実際に店舗が配置された点（黄色で上書き）
if y is not None:
chosen = [j for j in range(len(pfls)) if y[j] == 1]
if chosen:
ax.scatter(pfls[chosen, 0], pfls[chosen, 1],
c='gold', s=300, edgecolors='orange', linewidths=1.5, zorder=2)
for j in range(len(pfls)):
ax.text(pfls[j, 0], pfls[j, 1],
str(j + 1), color='white', size=10, fontweight='bold',
ha='center', va='center', zorder=3)
plt.tight_layout()
plt.show()
1. 対象地域¶
12個の街と3つの店舗配置候補点が存在する地域を考えてみよう。 まずは街と店舗配置候補点の座標が書き込まれているデータをロードしよう。
import numpy as np
# 街の座標と人口（列: x座標, y座標, 人口）
demands = np.loadtxt('demand.csv', delimiter=',')
# 店舗配置候補点の座標（列: x座標, y座標）
pfls = np.loadtxt('pfl.csv', delimiter=',')
plot_region(demands, pfls)
この画像におけるそれぞれの点をノードと呼ぶ。 青いノードが街、赤いノードが店舗配置候補点である。 今後、街のことは需要点（店の需要である住民がいるため）、店舗配置候補点を配置点と呼ぶ。 需要点と配置点の中に書かれている数字は、そのノードの番号を示している。 また、需要点の右上に書かれている数字はその需要点の人口を示している。
ここでこの地域にスーパーマーケットをいくつか出店することを考えてみよう。 例えば、2つのスーパーマーケットを出店する場合にはどこに店舗を配置すれば効率がよいだろうか。 この効率を考えるためにあらかじめ各需要点から各配置点までの距離を計算しておこう。 以下のコードで計算できる。
def cal_distance(demands, pfls):
"""需要点と配置点の全ペアに対するユークリッド距離を計算する．
Returns
-------
distance : np.ndarray, shape=(需要点数, 配置点数)
distance[i, j] は需要点i と配置点j の距離．
"""
# demands[:, :2] は (需要点数, 2)，pfls は (配置点数, 2)
# ブロードキャストで差分を取り，ユークリッド距離を一括計算する
diff = demands[:, np.newaxis, :2] - pfls[np.newaxis, :, :]
distance = np.sqrt((diff ** 2).sum(axis=2))
return distance
distance = cal_distance(demands, pfls)
distance
array([[7.61577311, 2.82842712, 5.09901951],
[2.23606798, 7.28010989, 6.40312424],
[3.16227766, 4.47213595, 1.41421356],
[5.38516481, 3. , 6.70820393],
[2. , 3.16227766, 4. ],
[8.06225775, 3.60555128, 5. ],
[3.16227766, 5.65685425, 7.07106781],
[3. , 5.38516481, 2.23606798],
[5.65685425, 3.16227766, 2. ],
[3.16227766, 7.21110255, 7.61577311],
[5.38516481, 8.06225775, 4.12310563],
[7.28010989, 2.23606798, 5.38516481]])
2. p-median 問題¶
p-median問題 とはざっくりいうと、対象地域の全住民の移動距離が最も小さくなるような p個の施設を配置する問題である。 またp-median問題は目的関数と制約条件から構成される。
目的関数とは最小化もしくは最大化すべき指標のことで、制約条件とは目的関数を最小化もしくは最大化する際に満たすべき条件のことである。 ここを押さえて p-median 問題の目的関数と制約条件を見てみよう。
目的関数（最小化）
- 重み付き総移動距離
制約条件
- ある街の住民たちは一番使いやすい1店舗しか利用しない
- ある街の住民が店舗を利用するには実際に店舗が配置されていなければいけない
- 出店されるスーパーマーケットの数は2店舗
このように目的関数と制約条件で表された問題を最適化問題と呼ぶ。
重み付き総移動距離とは街の住民とその住民が利用する店舗までの距離の総和である。 これは「街の人口×その街から店舗が配置された街までの距離」で表すことができる。 例えば街Aの人口が100人、街Bの人口が200人であり、店舗までの距離がそれぞれ 1km と2km であれば
Aの人口×Aから店舗までの距離 + Bの人口×Bから店舗までの距離 = 100人×1km + 200人×2km = 500 人/km
が重み付き総移動距離となる。 人口と距離を掛けているので、単位は[km] ではなく[人/km] （全住民の移動距離の合計、延べ移動距離）になることに注意すること。
2.1 p-median 問題の定式化¶
前項では文章でいろいろと説明してきたが、コンピュータで扱えるように数学でこの問題を記述してみよう。
記号と変数¶
まず、二つの記号を用意する。 一つは住民が住んでいるノードを表す$i$ である（これを需要点と呼ぶ）。 もう一つは店舗を配置することのできるノードを表す$j$ である（これを配置点と呼ぶ）。 今回のグラフでは需要点$i$ が12個、配置点$j$ が3個であるから
$i = 1, 2, \cdots, 12$
$j = 1, 2, 3$
となる。
次に需要点$i$ の住民が配置点$j$ に配分されているかどうかを表す変数$x_{ij}$ を考える。 この変数$x_{ij}$ は0 か1 のみを取る変数であり、例えば、需要点3 の住民が配置点2の店舗を利用するとき$x_{3, 2}=1$ となる。 もう少し一般的に書いてみると次のようになる。
$x_{ij} = 1:$ 需要点$i$ の住民が配置点$j$ の店舗を利用する、$0$: その他
次に配置点$j$ に施設が配置されているかどうかを表す変数$y_j$ を考える。 変数$y_j$ も同様に0 か1 のみを取る変数となっている。 すなわち、
$y_j = 1:$ 配置点$j$ に店舗が配置されている、$0$: その他
となる。
定数¶
あらかじめ与えられた値は定数として扱う。 今回の例ではそれぞれの街の人口と、各需要点から各配置点までの距離が定数になる。 それぞれ次のように定義しよう。
- $p_i$: 需要点$i$ の人口
- $d_{ij}$: 需要点$i$ と配置点$j$ との距離
また、配置したい施設の数も定義しておく。
- $k$: 配置される施設数（今回は$k = 2$）
目的関数¶
目的関数は前項で述べたように重み付き総移動距離、すなわち人口×移動距離の総和である。 これを上述した記号や変数、定数で表現してみよう。 需要点$i$ から配置点$j$ への重み付き移動距離は次のように表現できる。
$p_i \cdot d_{ij}$
この式は、需要点$i$ の住民が配置点$j$ に配置された店舗を利用する場合、すなわち$x_{ij} = 1$ のときのみ有効にならなければならない。すなわち
$p_i \cdot d_{ij} \cdot x_{ij}$
となる（$x_{ij}=0$ のときはこの式全体が$0$ になるので、「利用しない店舗はカウントされない」がうまく表現できている）。 この式が需要点$i$ から配置点$j$ に対する重み付き移動距離となる。 今度は需要点$i$ からすべての配置点に対する重み付き移動距離を考えてみよう。 上記の式をすべての配置点について足してあげれば実現できるはずである。 すなわち、
$p_i \cdot \sum_{j = 1}^{3} d_{ij} \cdot x_{ij}$
となる。 簡単な復習になるが$\sum$ は総和を意味しており、例えば $\sum_{i = 1}^{3} a_i = a_1 + a_2 + a_3$ である。 これで需要点$i$ から配置点に対する重み付き移動距離を数式で表現することができた。 最後に需要点$i$ だけでなくすべての需要点について同じような重み付き移動距離を考えてそれらすべてを足してみよう。 すなわち、
$\sum_{i = 1}^{12} p_i \cdot \sum_{j = 1}^{3} d_{ij} \cdot x_{ij}$
である。 これが対象地域上の全住民の移動距離を考慮した重み付き総移動距離となり、目的関数となるわけである。 今回は目的関数を最小化するので、これを以下のように表現する。
$\sum_{i = 1}^{12} p_i \cdot \sum_{j = 1}^{3} d_{ij} \cdot x_{ij} \rightarrow \min$
一見難しい表記に見えるが$\rightarrow \min$ は左の目的関数を最小化するという意味である。
制約条件¶
今回の問題では制約条件が三つあった。それぞれ順番に数学的に表現してみよう。
- 制約条件1
まずは「各需要点の住民が利用する店舗は一つ」である。 住民が店舗を利用するかどうかは変数$x_{ij}$ で表現することができた。 そこで変数$x_{ij}$ を使ってこの制約条件を表現してみよう。 まずは具体例として「需要点$1$ の住民が利用する店舗は一つだけ」という制約条件を考えよう。 これは
$\sum_{j=1}^{3} x_{1,j} = 1$
となる。 $x_{1,j} = 1$ は需要点$1$ の住民が配置点$j$ の店舗を利用する、という意味なのですべての配置点$j$ について$x_{1,j}$ を足してあげればいいわけである。 この式は需要点$1$ についてのみ考えているので、すべての需要点について考えてあげると以下のように12個の式ができる。
$\sum_{j=1}^{3} x_{1,j} = 1$
$\sum_{j=1}^{3} x_{2,j} = 1$
$\cdots$
$\sum_{j=1}^{3} x_{12,j} = 1$
これらはまとめて次のように表記できる。
$\sum_{j=1}^{3} x_{i,j} = 1, \forall i\in \{1, 2, \cdots, 12\}$
$\forall i\in \{1, 2, \cdots, 12\}$ は「すべての$i$ について（$i=1$ から$12$ のどれでも）この式が成り立つ」という意味の表記である。
- 制約条件2
次に「配置点$j$ に店舗が配置されていなければ需要点の住民は配置点$j$に買い物に行けない」である。 当たり前のことだが、これもしっかりと数式で表してあげる。 繰り返しになるが、住民が店舗を利用するかどうかは変数$x_{ij}$ で表せる。 そのため、$y_{j}=1$ （店舗が配置される）でなければ$x_{ij}=1$ （その店舗を利用する）にならない。 つまり制約条件は次のような式で表せる。
$x_{ij} \leq y_{j}$
配置点$j$ に店舗が配置された（$y_{j}=1$）時のみ需要点$i$ の住民がその店舗を利用できる（$x_{ij}=1$ になれる）、という意味になっている。 $y_j = 0$ のときは$x_{ij} \leq 0$ となるので$x_{ij}$ は$0$ しか取れない、と考えると納得しやすい。 この式をすべての需要点と配置点について考えると次のように表記できる。
$x_{ij} \leq y_{j}, \forall i \in \{1, 2, \cdots, 12\}, \forall j \in \{1, 2, 3\}$
- 制約条件3
次に「出店されるスーパーマーケットの数は2店舗」である。 スーパーマーケットが配置点$j$ に出店されているかどうかは変数$y_{j}$ で表現することができた。 変数$y_{j}$ が$1$ であれば出店されており、$0$ であれば出店されていない、という意味になる。 そのため、出店されているスーパーマーケットの数は変数$y_{j}$ の足し算で考えることができる。 すなわち出店されているスーパーマーケットの数は
$\sum_{j=1}^{3} y_{j}$
と表現することができる。 今回は出店舗数$k$ が$2$ であるからこの制約条件は以下のように表現できる。
$\sum_{j=1}^{3} y_{j} = 2$
これで出店舗数に関する制約条件を数学的に表現することができた。
2.2 p-median 問題の数理モデル¶
目的関数と制約条件を数学的に表現することができたので、これらをまとめて数理モデルとして表現しよう。 今回の問題（需要点12個、配置点3個、出店舗数2）の数理モデルは次のように表現される。
\begin{align} &\sum_{i = 1}^{12} p_i \cdot \sum_{j = 1}^{3} d_{ij} \cdot x_{ij} \rightarrow \min, \\ &\text{s.t. } \ \ \sum_{j=1}^{3} x_{i,j} = 1, \forall i\in \{1, 2, \cdots, 12\}, \\ &\ \ \ \ \ \ \ \ x_{ij} \leq y_{j}, \forall i \in \{1, 2, \cdots, 12\}, \forall j \in \{1, 2, 3\}, \\ &\ \ \ \ \ \ \ \ \sum_{j=1}^{3} y_{j} = 2. \end{align}
なお、需要点の数を$n$、配置点の数を$m$、出店舗数を$k$ という記号で書くと、どんな地域や店舗数にも使える一般形になる。 課題では需要点、配置点や店舗数を自分で変えるので、この形も覚えておくと便利である。
\begin{align} &\sum_{i = 1}^{n} p_i \cdot \sum_{j = 1}^{m} d_{ij} \cdot x_{ij} \rightarrow \min, \\ &\text{s.t. } \ \ \sum_{j=1}^{m} x_{i,j} = 1, \forall i\in \{1, 2, \cdots, n\}, \\ &\ \ \ \ \ \ \ \ x_{ij} \leq y_{j}, \forall i \in \{1, 2, \cdots, n\}, \forall j \in \{1, 2, \cdots, m\}, \\ &\ \ \ \ \ \ \ \ \sum_{j=1}^{m} y_{j} = k. \end{align}
それではここからはこれをコンピュータに解かせてみよう。
3. p-median 問題の定式化とpython による求解¶
まずは需要点と配置点の数や距離、需要点の人口などの定数を定義していく。
# 需要点の数
n_demands = len(demands)
# 配置点の数
n_pfls = len(pfls)
# 各需要点の人口
population = demands[:, 2]
# 配置する店舗の数
n_stores = 2
各需要点の人口を確認してみよう。
list(population)
[np.float64(500.0), np.float64(300.0), np.float64(600.0), np.float64(900.0), np.float64(100.0), np.float64(500.0), np.float64(800.0), np.float64(1000.0), np.float64(200.0), np.float64(400.0), np.float64(400.0), np.float64(300.0)]
一番上の行が需要点1、二つ目が2, といった感じになっている。 つまり需要点1 の人口は500人、需要点2 は300人となっていて、最初に示した図と一致していることがわかる。
次に各需要点と各配置点の距離を確認してみよう。
distance
array([[7.61577311, 2.82842712, 5.09901951],
[2.23606798, 7.28010989, 6.40312424],
[3.16227766, 4.47213595, 1.41421356],
[5.38516481, 3. , 6.70820393],
[2. , 3.16227766, 4. ],
[8.06225775, 3.60555128, 5. ],
[3.16227766, 5.65685425, 7.07106781],
[3. , 5.38516481, 2.23606798],
[5.65685425, 3.16227766, 2. ],
[3.16227766, 7.21110255, 7.61577311],
[5.38516481, 8.06225775, 4.12310563],
[7.28010989, 2.23606798, 5.38516481]])
一番目の行の一列目は需要点1 から施設点1 への距離を表している。 距離の単位は何でもよいが、ここでは[km] としておこう。 つまり需要点1 から配置点1 への距離は約7.6[km] であるということがわかる。
数式に進む前に、一つだけ具体的な数字で「重み付き移動距離」を計算してみよう。 例えば需要点1（人口500人）の住民が配置点2（距離約2.83km）の店舗を利用するとする。 このときの重み付き移動距離は
500人 × 2.83km ≒ 1414 人/km
である。コードで書くと次のようになる。
# 需要点1 の人口 × 需要点1 から配置点2 までの距離
# （プログラムでは番号が0 から始まるので，需要点1 は demands[0]，配置点2 は distance[0, 1]）
demands[0, 2] * distance[0, 1]
np.float64(1414.213562373095)
p-median 問題は、このような「人口 × 距離」の掛け算を「誰がどの店舗を使うか」に応じて全員分足し合わせ、その合計が最も小さくなる店舗の置き方を探す問題である。 次の節ではこれを数式で書いていく。
これらの定数をもとに今回はpulp というソフトを用いてp-median問題を定式化して解を求めてみる。
数式で使った記号とコード内の変数は次のように対応している。 コードを読むときはこの表を手元に置いて見比べてみるとよい。
| 数式の記号 | 意味 | コード内の変数 |
|---|---|---|
| $n$（=12） | 需要点の数 | n_demands |
| $m$（=3） | 配置点の数 | n_pfls |
| $p_i$ | 需要点$i$ の人口 | population[i] |
| $d_{ij}$ | 需要点$i$ と配置点$j$ の距離 | distance[i, j] |
| $k$（=2） | 配置する店舗の数 | n_stores |
| $x_{ij}$ | 需要点$i$ が配置点$j$ を利用するか (0/1) | x[i][j] |
| $y_j$ | 配置点$j$ に店舗を置くか (0/1) | y[j] |
以下のコードが先ほど示した数理モデルを表している。 余裕のある人はコードの意味を自分で調べてみるといいかもしれない。
import pulp
def solve_pmedian(n_demands, n_pfls, population, distance, n_stores):
"""p-median 問題を解く．
Parameters
----------
n_demands : int
需要点の数．
n_pfls : int
配置点の数．
population : array-like, shape=(n_demands,)
各需要点の人口．
distance : np.ndarray, shape=(n_demands, n_pfls)
需要点と配置点の間の距離．
n_stores : int
配置する店舗の数．
Returns
-------
objective : float
目的関数値（重み付き総移動距離）．
x : np.ndarray, shape=(n_demands, n_pfls), dtype=int
x[i, j]=1 なら需要点i の住民が配置点j の店舗を利用．
y : np.ndarray, shape=(n_pfls,), dtype=int
y[j]=1 なら配置点j に店舗が配置されている．
"""
# 問題設定（最小化問題）
prob = pulp.LpProblem('p-median', pulp.LpMinimize)
# 決定変数（すべて 0/1 のバイナリ変数）
x = [[pulp.LpVariable(f'x_{i+1}_{j+1}', cat=pulp.LpBinary)
for j in range(n_pfls)] for i in range(n_demands)]
y = [pulp.LpVariable(f'y_{j+1}', cat=pulp.LpBinary)
for j in range(n_pfls)]
# 目的関数：重み付き総移動距離の最小化
prob += pulp.lpSum(
population[i] * distance[i, j] * x[i][j]
for i in range(n_demands) for j in range(n_pfls)
)
# 制約条件1: 各需要点の住民は必ず1つの店舗を利用する
for i in range(n_demands):
prob += pulp.lpSum(x[i][j] for j in range(n_pfls)) == 1
# 制約条件2: 店舗が配置されていない配置点は利用できない
for i in range(n_demands):
for j in range(n_pfls):
prob += x[i][j] <= y[j]
# 制約条件3: 配置する店舗数は n_stores
prob += pulp.lpSum(y[j] for j in range(n_pfls)) == n_stores
# 求解
solver = pulp.PULP_CBC_CMD(msg=False)
prob.solve(solver)
print('求解結果:', pulp.LpStatus[prob.status])
# 結果を numpy 配列に整形して返す
objective = pulp.value(prob.objective)
x_val = np.array(
[[int(pulp.value(x[i][j])) for j in range(n_pfls)]
for i in range(n_demands)],
dtype=np.int32,
)
y_val = np.array(
[int(pulp.value(y[j])) for j in range(n_pfls)], dtype=np.int32
)
return objective, x_val, y_val
f, x, y = solve_pmedian(n_demands, n_pfls, population, distance, n_stores)
求解結果: Optimal
「求解結果: Optimal」と表示されたはずである。
これは最適解、すなわち最も目的関数が小さくなる解を見つけることができた、ということを示している。
それでは、実際にどこに店舗が配置されたのか確認してみよう。
店舗の配置を示す変数はy であったのでy の中身を確認してみる。
y
array([1, 1, 0], dtype=int32)
これは$y_1 = 1, y_2 = 1, y_3 = 0$ であることを示している。 すなわち、配置点1 と2 に店舗が配置されたということになる。
次に実際に重み付き総移動距離はいくつくらいになったのか確認してみよう。
print(f'{f:.2f}')
18937.25
これは対象地域上の住民が今回配置された店舗を使ったとき、その重み付き総移動距離（人口×距離の合計）が18937.25[人/km] になることを表している。 どんな2店舗の置き方をしても、この値より小さくすることはできない、という意味で「最適」である。
それでは図に示して確認してみよう。 施設が配置されたノードを黄色で示してみる。
plot_region(demands, pfls, y=y)
配置されたノードを見てみると周りに需要点がきれいに散らばっており、なんとなく正しそうである。
もっと具体的にどの需要点がどの店舗を利用しているのか図示して確認してみよう。 これには変数$x_{ij}$ の情報を使う必要がある。 まずは中身を見てみよう。
x
array([[0, 1, 0],
[1, 0, 0],
[1, 0, 0],
[0, 1, 0],
[1, 0, 0],
[0, 1, 0],
[1, 0, 0],
[1, 0, 0],
[0, 1, 0],
[1, 0, 0],
[1, 0, 0],
[0, 1, 0]], dtype=int32)
例えば1行目の2列目が1 になっているが、これは需要点1 の住民が配置点2 に配置された店舗を利用していることを示している。
この情報を使えばだれがどの店舗を使っているのか図示できそうである。
plot_region(demands, pfls, x=x, y=y)
詳細に確認することは難しいが、配置点から需要点までの距離のバランスがよくうまく配置されていることがわかる。
ちなみに重み付き総移動距離とは「需要点と配置点を結ぶ線の長さ×その需要点の人口」をすべての線について足したものである。 図で見ると少しわかりやすいだろうか。
4. 課題¶
(1) 今回はあらかじめ需要点と配置点が用意されていた。課題では配置点の数と座標を変えてみて新たな地域を作成すること。
座標はx座標、y座標とも1~10である。 例えば、座標(1, 3)、(5, 5)に新たな配置点を置きたければ次のようにすること。
# 以下を自由に編集してください（[x座標, y座標] を好きな数だけ並べる）．
# 例として3つの配置点を置いています．
pfls = np.array([
[1, 3],
[5, 5],
[8, 2],
])
# demands は demand.csv のまま利用する場合はこのまま。
# 新しい地域にしたければ np.array で [x座標, y座標, 人口] を直接定義してもよい．
新たに設定した座標を確認したければ以下のようにコマンドを打つこと。
plot_region(demands, pfls)
(2) 新たに作成した地域で問題を作成するために必要な定数を定義すること。なお、配置する店舗の数は自由に設定すること。
具体的には、以下の5つの変数を定義すること。
n_demands: 需要点の数n_pfls: 配置点の数population: 各需要点の人口（demands[:, 2]で取得できる）distance: 需要点と配置点の距離行列（cal_distance(demands, pfls)で取得できる）n_stores: 配置する店舗の数（自由に設定）
(3) 配置する店舗の数が変わっているため数理モデルの表記も変わる。このページ内の「p-median 問題の数理モデル」を参考に作成した問題を表す数理モデルを表記せよ。
(4) 新たに定義した定数を使って問題を解いてみよ。
問題は次のコードで解くことができ、目的関数値と変数$x_{ij}, y_j$ はそれぞれf,x,yに格納される。
# 新しい定数を使って解く．課題(2) で以下の変数を自分で定義しておくこと．
# n_demands, n_pfls, population, distance, n_stores
f, x, y = solve_pmedian(n_demands, n_pfls, population, distance, n_stores)
求解結果: Optimal
(5) 得られた結果を図示せよ。
次のコードで図示できる。
plot_region(demands, pfls, x=x, y=y)
5. 卒業研究概要への手引き¶
- このテーマを卒業研究のテーマにしたい場合は、ここの対応をすること（必ず事前に相談すること）。
- 以下、すべて含めて、A4用紙2枚にまとめること。
- 厳密に守る必要はないが、文章量の比率を目安にすること（15%とは、A4用紙2枚分の15%という意味）。
1章 はじめに（文章量の比率: 15%）¶
- 施設配置問題とは何か、p-median問題以外にどのような施設配置問題があるのかまとめること。
- p-median を用いた施設配置問題に関する先行研究を紹介すること。
- 施設配置問題を解く際に使われる整数計画法とは何か、まとめること。
2章 p-median問題（文章量の比率: 30%）¶
- p-median 問題の数理モデルについて、説明すること。
3章 実験（文章量の比率: 40%）¶
3.1節 概要¶
- 上の課題に示した(1)~(5) を説明すること。
- 実際に新たな地域を作成して問題を解き、図示すること。
3.2節 結果と考察¶
- 重み付き総移動距離がいくつになったか示すこと。
- その重み付き総移動距離が何を意味しているか説明すること。
- 図示した画像から、どのようなことが言えるか、考え説明すること。
4章 おわりに（文章量の比率: 15%）¶
- 今回の実験に対する感想を記載すること。
- 例えば、直感で店舗を配置するのと数理モデルにより店舗を配置するのでは、どちらがよさそうか、また良い理由を記載すること。
参考文献¶
参考にした資料を、2〜3件記載すること。以下、書き方の例である。
- [1] 柿本ほか, XXXに関する分析, XXX学会論文誌, 2020.
- [2] XXXに関する情報, http://xxx.ddd.ttt.com, 2020年4月20日閲覧
本文中で引用する場合は「柿本らはXXXを実施している [1]。また、〜」のように、どこで引用したのか明白にすること。