この投稿は以前 qiita に上げた記事を移行させたものになります

施設配置問題の種類

施設配置問題 (Facility Location Problem) とは、日本オペレーションズ・リサーチ学会の Wiki に基づくと

施設の配置可能地点, 需要をもつ顧客の集合が与えられて, ある基準を満たす施設の配置場所を決定する問題の総称

と定義されます。

例えばイギリスの各地に分布しているスーパーマーケット（需要を持つ顧客）に対して、商品の倉庫（施設）をどう設置すれば輸送コストと建設コストの和を最も抑えることができるか、といったことを考えます（下図）。

（図は http://examples.gurobi.com/facility-location/ より）

ただし、一口に施設配置問題と言っても複数のバリエーションがあり、それぞれ目的関数の立て方などが異なります。

最小コストで顧客全員にサービス提供できる施設の数と配置を考える

目的関数は、施設の設置コストと輸送コストの和の最小化。先程の図の例が該当します。

施設1つあたりのサービス提供能力に制限が無い場合
- 容量制約なし施設配置問題 (Uncapacitated Facility Location Problem; UFLP)
施設1つあたりのサービス提供能力に制限がある場合
- 容量制約付き施設配置問題 (Capacitated Facility Location Problem; CFLP)

施設の数は p 個で固定にし、顧客全員にサービス提供できる配置を考える

目的関数は以下の2つのとり方があります。

顧客・施設間の距離の総和を最小化する（Minisum）
- p-median 問題
顧客・施設間の距離の最大値を最小化する（Minimax）
- p-center 問題

顧客のカバー率を考える（被覆問題）

最小コストで全員をカバーできる配置を求める
- 集合被覆問題 (Set Covering Location Problem; SCLP)
特定の予算でカーバできる領域を最大化させる
- 最大被覆問題 (Maximal Covering Location Problem; MCLP)

他社がすでに進出しているエリアに対して自社の施設を配置してシェアを奪う場合を考える

競合施設配置問題 (Competitive Location Models)

単純に施設配置問題と言っても上記のように様々なバリエーションがあるので、自分が解きたい問題が施設配置問題の中のどれに該当するのかを正しく判断することが大切かと思います。

UFLP と p-median の違い

UFLP と p-median は先程の説明でも感じられたかと思いますがとても似ています。実際、 p-median 問題の p の値を変動させる場合を考えれば UFLP に近い分析が可能です。この2つの違いは

UFLPでは場所ごとに設置コストがいくらになるのか考えるが、p-median ではどの場所に設置してもコストは変わらないという前提がある
UFLPでは施設の建設数に制限が無いが、p-medinaは p 個という制限がある
UFLPは大抵の場合だと顧客と施設の場所が別々に用意されることになるが、p-medianでは顧客のいる場所に施設を設置するということも可能

というのが挙げられています（ https://pdfs.semanticscholar.org/111a/92b71a4adb8ace1cb1ac4b2f2ab5f5811c99.pdf ）。

以下では施設配置問題のうち、有名な UFLP, p-median, p-center を概観したあと、gurobi で実際に計算をしてみようと思います。

UFLP

UFLPは施設の設置コストとサービスの輸送コストを吟味して、総コストが最小になるような施設の数とその設置場所を求めます。式は以下のように記述されます。

$\text{Max} \quad \sum_i \sum_j c_{ij} x_{ij} + \sum_i f_i y_i$

$\text{s.t.} \quad \sum_i x_{ij} = 1 \quad \forall j$

$\qquad x_{ij} \leq y_i \quad \forall i,j$

$\qquad x_{ij} \geq 0 \quad \forall i,j$

$\qquad y_i \in {0, 1} \quad \forall i,j$

それぞれの文字の意味は

$c_{ij}$ : 地点 $i$ の施設が地点 $j$ の顧客へサービス提供する際の総コスト
$f_i$ : 地点 $i$ に施設を設置する際のコスト
$x_{ij}$ : 決定変数。地点 $j$ の顧客の需要量全体を1としたときの、地点 $i$ の施設が解決した地点 $j$ の顧客の需要量が占める割合
$y_i$ : 決定変数。 $y_i = 1$ ならば地点 $i$ に施設を設置する。0ならば設置しない。

式の意味としては

目的関数 : （顧客へのサービス提供にかかるコスト） + （施設の固定費）を最小化させる
制約条件1 : 地点 $j$ にいる顧客の需要は、合計すると1になる
制約条件2 : 地点 $i$ に施設が建設されない場合 ( $y_i = 0$ )、地点 $i$ でのサービス提供はない
制約条件3 : $x_ij$ （地点 $j$ の顧客の需要のうち地点 $i$ において解決される量）は0以上
制約条件4 : $y_i$ （地点 $i$ に施設を建設するか否か）は 0 か 1 の値しか取らない

となります。

アルゴリズム

UFLPを解くアルゴリズムは Efroymson 氏と Ray 氏が1966年に発表した分枝限定法 (Branch-and-Bound; BB) を用いる方法や、Donald Erlenkotter 氏が1978年に発表した双対上昇法 (Dual Ascent Method) による方法などが挙げられます。どうやら双対上昇法のほうがより効率的であるようですが、 Gurobi などのソルバーを使う場合はそもそもソルバーに実装されている混合整数計画問題のアルゴリズムを使うことになると思うので分枝限定法ベースの解き方になるのかなと思います。

p-median 問題

p-median 問題は、施設の数が p 個で固定の状態で、顧客と施設の間の距離の合計が最小となるような施設の配置を考えます。距離の合計が最小になるということは、輸送コストが最小になると捉えてもよいかと思います。現実的な話として、建設する施設の数が p 個と決まっている場合とはどんなときなのだろうかと私は少し疑問に思いました。調べてみたところ、政治的な理由で施設数が決まっている場合や、全体の予算が決まっていてかつどこに施設を設置してもコストが対して変わらない場合などが該当するようです。

p-median 問題の前提条件

p-median 問題は以下のような前提をまず置きます。

設置する施設は p 個で固定
施設と顧客の対応関係が特に指定されない場合、顧客は自身の最寄りの施設を利用する
顧客は最寄りの施設に向けて最短経路をたどって移動する

二番目の前提は結果的に、同じエリアの顧客は同じ最寄りの施設を利用することに繋がります。そのためもしも得られた計算結果に、同じエリアの顧客なのに異なる施設を利用していることがあったら、それは最適解ではない可能性が高いと言えます。というのも、2つの施設が等距離に無い限り、より近い側の施設を利用すればコストの削減が可能になるからである（もちろん施設のサービス提供能力に制限があればこの限りではないです。いわゆる Allocation の問題になりますが、ここでは割愛します）。

p-median問題の定式化

p-median 問題は S.L.Hakimi 氏が1964年に提出した論文が始まりとされています。この論文はグラフ理論で “absolute median” （良い日本語訳がよくわかりません）を求める手法を取り扱っています。実はこのタイミングでは整数計画問題の形の記述がされていませんでした。 p-median 問題を整数計画問題として初めて定式化を行ったのは Charles S. ReVelle 氏と Ralph Swain 氏で、1970年になります（ちなみにこのふたりは Hakimi 氏の論文との関連性に言及はしておらず、 median という表現もしていませんでした）。