以前、施設配置問題としての被覆問題と Gurobi による実装という記事を書きました。被覆問題は例えば

飲食チェーン店を展開させようと思った時、どういうお店の配置にすれば少ない店舗数で多くの客を取り込めるか
ECサービスで、日本全国どこでも商品を2日以内に届けられるようにするためには配送センターをどこに設置すべきか

といった問題を考える際に役立つ数理モデルです。ちなみに前者は「最大被覆問題 (Max Covering Location Problem; MCLP)」、後者は「集合被覆問題 (Set Covering Location Problem; SCLP)」に分類されます。

（図の引用元: https://slideplayer.com/slide/8270990/ ）

この図は最大被覆問題の計算の様子を表しています。施設の数を10個に限定（左）した場合は需要の82%をカバーでき、施設の数を20個にする（右）と需要の97%をカバーできることを意味しています。

（カバーする対象は国土ではなくあくまでも顧客なので、施設数10の場合は国土の半分程度しかカバーしていませんが顧客カバー率は82%となります）

現実世界は単純ではない

ただ、実際に数理モデルを使って施設配置を考えようとした場合、現実世界がその数理モデルよりも複雑であることが原因でかなり雑な議論しかできなかったり、直感的に良いと言い切れない答えが出てきてしまうことがあります。まぁ現実世界を数理モデルで捉えるのは想像よりも難しい話なので仕方が無いところは生じるかもしれません。が、とりあえず以前紹介した被覆問題はちょっと単純過ぎます。

被覆問題の基本モデルに課されている前提条件

以前紹介した被覆問題は前提として

それぞれの施設の処理能力は無限大 であり、近くにどれだけ顧客が多くいても原則すべての顧客をカバーできるとする
処理能力が無限大であるため、顧客は最寄りの施設を無条件で使う ことになる

という前提が置かれています。施設の処理能力が無限大だと考えるのは、場合によってはそれでいいこともあるかもしれませんが、大抵の場合処理能力は有限です。

そこで、施設の処理能力に限界がある条件において被覆問題を扱うモデル が提案されています。

容量制約あり被覆問題 (Capacitated Covering Location Problem)

“Capacitated Covering Model” と題して、被覆問題に施設の処理能力の制限という条件を追加したのは J.R.Current 氏と J.E.Storbeck 氏で、1988年の論文になります。

論文 : https://journals.sagepub.com/doi/abs/10.1068/b150153

この論文では集合被覆問題と最大被覆問題の両方について、容量制約条件を追加する場合の定式化を行っています。

容量制約あり集合被覆問題

$\text{Min} \quad \sum_{j \in J} Y_j$

$\text{s.t.} \quad \sum_{j \in N_i} X_{ij} \geq 1 \qquad \forall i \in I$

$\qquad \sum_{i \in I} a_i x_{ij} - k_j Y_j \leq \quad \forall j \in J$

$Y_j \in 0,1 \qquad \forall j \in J$

それぞれの文字の意味は

$a_i$ : 場所 $i$ における顧客の需要量
$k_j$ : 場所 $j$ に設置できる施設の処理できる需要量
$X_{ij}$ : 決定変数。場所 $i$ における顧客の需要のうち、施設 $j$ で解決されるものの割合（全体を 1 とする）
$Y_j$ : 決定変数。 $Y_j = 1$ なら場所 $j$ に施設を設置、 $Y_j = 0$ なら設置しない

です。通常の集合被覆問題と異なる点は

施設の処理能力 $k_j$ に関する制約条件が追加されている
場所 $i$ の顧客が利用する施設の選択肢が複数箇所になっている（ $X_{ij}$ という変数の導入により実現）

の2点です。

容量制約あり最大被覆問題

$\text{Min} \quad \sum_{i \in I} a_i U_i$

$\text{s.t.} \quad \sum_{j \in N_i} X_{ij} + U_i = 1 \qquad \forall i \in I$

$\qquad \sum_{i \in M_j} a_j X_{ij} - k_j Y_j \leq 0 \qquad \forall j \in J$

$\sum_{j \in J} Y_j = p \qquad$

$Y_j \in 0,1 \qquad \forall j \in J$

それぞれの文字の意味は

$a_i$ : 場所 $i$ における顧客の需要量
$k_j$ : 場所 $j$ に設置できる施設の処理できる需要量
$p$ : 設置する施設の数
$X_{ij}$ : 決定変数。場所 $i$ における顧客の需要のうち、施設 $j$ で解決されるものの割合（全体を 1 とする）
$Y_j$ : 決定変数。 $Y_j = 1$ なら場所 $j$ に施設を設置、 $Y_j = 0$ なら設置しない
$U_i$ : 決定変数。場所 $i$ における顧客の需要のうち、施設で解決されなかったものの割合

です。

Gurobi による実装

容量制約あり集合被覆問題

まず問題設定を次のようにしてみます。

これを図示すると

赤がクライアント（顧客）で、青が施設になります。エッジはそれぞれの施設設置候補がカバーできる顧客の情報に対応しています。

これに対して先程の容量制約付き集合被覆問題 (CSCLP) を実行します。

結果を図示すると

となります。実際に施設が処理している需要の量を調べてみると、確かに施設の処理能力の限界をすべて下回っていることがわかります。またこの計算より、最低でも施設は5つ必要になることがわかりました。

容量制約あり最大被覆問題

先程の CSCLP で施設が5つあったらすべてをカバーできることがわかりました。そこで容量制約あり最大被覆問題 (CMCLP) では 施設数を3つに限定 して計算をしてみようと思います。

計算の実行

図示

この結果から、確かに施設3ではカバーができないことがわかります。また、全くカバーできていないエリア（50と90）がありますが、それ以外にも一部カバーできていないエリア（たとえば170のところ）などが確認できます。

最後に

被覆問題の基礎は Toregas 氏と ReVelle 氏による1972年の論文や Church 氏と ReVelle 氏による1974年の論文で確立されましたが、より現実に即した議論をするために様々な拡張が行われています。今回はその中で施設の処理能力の限界を考慮した場合を取り上げましたが、それ以外にもいろいろなものがあります。論文探しはちょっと面倒ですが、実際に使おうと思った場合はいろいろ調査することが必要になりそうです。

処理能力が有限の施設による被覆問題

現実世界は単純ではない

被覆問題の基本モデルに課されている前提条件

容量制約あり被覆問題 (Capacitated Covering Location Problem)

容量制約あり集合被覆問題

容量制約あり最大被覆問題

Gurobi による実装

容量制約あり集合被覆問題

容量制約あり最大被覆問題

最後に

関連

Be First to Comment

コメントを残すコメントをキャンセル

処理能力が有限の施設による被覆問題

現実世界は単純ではない

被覆問題の基本モデルに課されている前提条件

容量制約あり被覆問題 (Capacitated Covering Location Problem)

容量制約あり集合被覆問題

容量制約あり最大被覆問題

Gurobi による実装

容量制約あり集合被覆問題

容量制約あり最大被覆問題

最後に

共有:

関連

Be First to Comment

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル