最適な施設の立地

施設配置問題 (FLP)の研究は、配置分析とも呼ばれ、住宅や競合施設の近くに危険物を置かないようにするなどの要因を考慮しながら、輸送コストを最小限に抑えるための施設の最適な配置に関するオペレーションズ リサーチと計算幾何学の分野です。この手法は、クラスター分析にも適用されます。

単純な施設配置問題はウェーバー問題であり、単一の施設を配置する問題で、唯一の最適化基準は、特定のポイント サイト セットからの距離の加重合計を最小化することです。この分野で検討されるより複雑な問題には、複数の施設の配置、施設の場所の制約、およびより複雑な最適化基準が含まれます。

基本的な定式化では、施設の配置問題は、施設を開設できる可能性のある施設のサイトLのセットと、サービス提供が必要な需要ポイントDのセットで構成されます。目標は、開設する施設のサブセットF を選択し、各需要ポイントから最も近い施設までの距離の合計と、施設の開設コストの合計を最小化することです。

一般的なグラフ上の施設配置問題は、（たとえば）集合被覆問題からの還元によって最適に解くことがNP 困難です。施設配置問題とその多くの変種に対して、多数の近似アルゴリズムが開発されてきました。

クライアントとサイト間の距離の集合に関する仮定がない場合（特に、距離が三角不等式 を満たすと仮定しない場合）、この問題は非メトリック施設配置と呼ばれ、係数 O(log n )以内に近似できます 。 ^[1]この係数は、集合被覆問題からの 近似値保存縮小により厳密になります。

クライアントとサイト間の距離が無向であり、三角不等式を満たすと仮定すると、メトリック施設配置 (MFL)問題になります。MFL は依然として NP 困難であり、1.463 より優れた係数で近似することは困難です。^[2]現在知られている最も優れた近似アルゴリズムは、近似比 1.488 を達成しています。^[3]

ミニマックス施設配置問題は、ある点から施設までの距離が、その点から最も近い施設までの距離である、施設までの最大距離を最小化する場所を探します。正式な定義は次のとおりです。

点集合P ⊂ が与えられたとき、 ${\displaystyle \mathbb {R} ^{d}}$max _{p ∈ P} (min _{q ∈ S} (d( p , q )) )が最小となる 点 集合S ⊂ , | S | = k を求めます。${\displaystyle \mathbb {R} ^{d}}$

k = 1のユークリッド計量の場合、これは最小包囲球問題または1 中心問題として知られています。その研究は少なくとも 1860 年まで遡ります。

k中心問題の正確な解は NP 困難であることが証明されています。 ^{[4] [5] [6]} 問題の近似も、誤差が小さい場合は NP 困難であることがわかりました。近似アルゴリズムの誤差レベルは近似係数として測定され、近似と最適値の比率として定義されます。近似係数が 1.822 (次元 = 2) ^[7]または 2 (次元 > 2)未満の場合は、 k中心問題の近似は NP 困難であることが証明されています。 ^[6]

正確なソルバー

この問題の正確な解を求めるアルゴリズムが存在する。1つの正確なソルバーは時間内に実行される。^{[8] [9]}${\displaystyle n^{O({\sqrt {k}})}}$

1 + ε近似

1 +  ε近似は、近似係数が 1 + ε以下の解を見つけることです 。ε は任意であるため、この近似は NP 困難です。実行複雑度が である、コアセットの概念に基づく 1 つのアプローチが提案されています 。^[10] 代替として、コアセットに基づく別のアルゴリズムも利用できます。これは で実行されます。^[11]著者は、実行時間は最悪の場合よりもはるかに短いため、kが小さい場合 (  k  < 5 など) にいくつかの問題を解決できると主張しています。 ${\displaystyle O(2^{O(k\log k/\varepsilon ^{2})}dn)}$${\displaystyle O(k^{n})}$

最遠点クラスタリング

この問題の難しさから、正確な解や正確な近似値を得るのは非現実的です。代わりに、k が大きい場合には係数 = 2 の近似値が広く使用されています。この近似値は、最遠点クラスタリング (FPC) アルゴリズム、または最遠点優先探索と呼ばれます。^[6]このアルゴリズムは非常に単純です。集合から任意の点を 1 つの中心として選び、残りの集合から最も遠い点を別の中心として探します。このプロセスをk個の中心が見つかるまで繰り返します。

このアルゴリズムが線形時間で実行されることは容易にわかります。係数が 2 未満の近似は NP 困難であることが証明されているため、FPC は見つけられる最良の近似であると見なされました。

実行性能に関しては、ボックス分解技術により時間計算量はO( n  log  k )に改善された。 ^[7]

最大最小施設配置問題または不快施設配置問題は、施設までの最小距離を最大化する場所を求める問題である。ユークリッド距離の場合、これは最大空球問題として知られている。平面の場合（最大空円問題）は最適時間Θ（n  log n）で解くことができる 。 ^{[12] [13]}

施設の配置問題は、整数計画問題として解かれることが多い。この文脈では、施設の配置問題は次のように示されることが多い。施設 と顧客があるとする。一定の需要を最小コストで満たすために、 (1) どの施設を開設するか、(2) どの (開設済みの) 施設を顧客に供給するかを選択する。次の表記を導入する。に対して、施設 の開設にかかる (固定) コストを で表す。に対して、施設 から顧客 への製品の出荷コストを で表す。に対する顧客の需要を で表す。さらに、各施設 には最大出力があるとする。施設 で生産できる製品の最大量を で表す、つまり、施設 の生産能力を で表す。このセクションの残りの部分は^[14]に従う。${\displaystyle n}$${\displaystyle m}$${\displaystyle n}$${\displaystyle m}$${\displaystyle f_{i}}$${\displaystyle i}$${\displaystyle i=1,\dots ,n}$${\displaystyle c_{ij}}$${\displaystyle i}$${\displaystyle j}$${\displaystyle i=1,\dots ,n}$${\displaystyle j=1,\dots ,m}$${\displaystyle d_{j}}$${\displaystyle j}$${\displaystyle j=1,\dots ,m}$${\displaystyle u_{i}}$${\displaystyle i}$${\displaystyle u_{i}}$${\displaystyle i}$

当初の定式化では、の2値変数を導入します。ここで、施設が開いている場合は 、そうでない場合は です。さらに、の変数 を導入します。これは、施設 によって満たされる需要の割合を表します。いわゆる容量制限付き施設配置問題は、次のように表されます。${\displaystyle x_{i}}$${\displaystyle i=1,\dots ,n}$${\displaystyle x_{i}=1}$${\displaystyle i}$${\displaystyle x_{i}=0}$${\displaystyle y_{ij}}$${\displaystyle i=1,\dots ,n}$${\displaystyle j=1,\dots ,m}$${\displaystyle d_{j}}$${\displaystyle i}$$${\displaystyle {\begin{array}{rl}\min &\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{m}c_{ij}d_{j}y_{ij}+\sum _{i=1}^{n}f_{i}x_{i}\\{\text{s.t.}}&\displaystyle \sum _{i=1}^{n}y_{ij}=1{\text{ for all }}j=1,\dots ,m\\&\displaystyle \sum _{j=1}^{m}d_{j}y_{ij}\leqslant u_{i}x_{i}{\text{ for all }}i=1\dots ,n\\&y_{ij}\geqslant 0{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m\\&x_{i}\in \{0,1\}{\text{ for all }}i=1,\dots ,n\end{array}}}$$

2 番目の制約セットにより、、つまり施設が開いていない場合には、すべての、つまり、どの顧客に対する需要も施設 から満たすことができないことが保証されることに注意してください。 ${\displaystyle x_{i}=0}$${\displaystyle i}$${\displaystyle y_{ij}=0}$${\displaystyle j}$${\displaystyle i}$

上記の容量制限付き施設配置問題の一般的なケースは、すべての に対しての場合です。この場合、顧客の需要をすべて最も近い空き施設で満たすことが常に最適です。このため、上記の連続変数をバイナリ変数に置き換えることができます。ここで、顧客が施設 によって供給されている場合は、それ以外の場合は です。容量制限なしの施設配置問題は次のように表されます。${\displaystyle u_{i}=+\infty }$${\displaystyle i=1,\dots ,n}$${\displaystyle j}$${\displaystyle y_{ij}}$ ${\displaystyle z_{ij}}$${\displaystyle z_{ij}=1}$${\displaystyle j}$${\displaystyle i}$${\displaystyle z_{ij}=0}$$${\displaystyle {\begin{array}{rl}\min &\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{m}c_{ij}d_{j}z_{ij}+\sum _{i=1}^{n}f_{i}x_{i}\\{\text{s.t.}}&\displaystyle \sum _{i=1}^{n}z_{ij}=1{\text{ for all }}j=1,\dots ,m\\&\displaystyle \sum _{j=1}^{m}z_{ij}\leqslant Mx_{i}{\text{ for all }}i=1\dots ,n\\&z_{ij}\in \{0,1\}{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m\\&x_{i}\in \{0,1\}{\text{ for all }}i=1,\dots ,n\end{array}}}$$

ここで、は適切に大きくなるように選択された定数です。 の選択は計算結果に影響を与える可能性があります。この場合の最適な選択は明らかで、 を取ることです。 次に、 の場合、 の任意の選択は2 番目の制約セットを満たします。 ${\displaystyle M}$${\displaystyle M}$${\displaystyle M=m}$${\displaystyle x_{i}=1}$${\displaystyle z_{ij}}$

容量制限のない施設配置問題に対するもう 1 つの定式化の可能性は、容量制約 (大きな制約) を分解することです。つまり、制約を制約に置き換えます。実際には、この新しい定式化は、最初の定式化よりも線形計画法の緩和がきついという意味で、大幅に優れたパフォーマンスを発揮します。 ^[14]新しい制約を合計すると、元の大きな制約が得られることに注意してください。容量制限のあるケースでは、これらの定式化は同等ではありません。容量制限のない施設配置問題の詳細については、「離散配置理論」の第 3 章を参照してください。^[15]${\displaystyle M}$$${\displaystyle \sum _{j=1}^{m}z_{ij}\leqslant Mx_{i}{\text{ for all }}i=1,\dots ,n}$$$${\displaystyle z_{ij}\leqslant x_{i}{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m}$$${\displaystyle M}$

医療分野では、施設の立地場所の誤った決定は、単純なコストやサービスの指標を超えて、地域社会に深刻な影響を及ぼします。たとえば、アクセスが困難な医療施設は、罹患率や死亡率の上昇につながる可能性があります。この観点から、医療分野の施設立地モデル化は、他の分野の同様のモデル化よりも重要です。^[16]

都市固形廃棄物管理は、廃棄物の増加と廃棄物管理に関連するコストの高騰により、発展途上国にとって依然として課題となっています。施設配置問題の定式化と正確な解決により、廃棄物処理のための埋立地の場所を最適化することができます。^[17]

クラスター分析問題の特定のサブセットは、施設配置問題として見ることができます。重心ベースのクラスタリング問題では、データポイント（共通のメトリック空間の要素）を同値クラス（多くの場合、色と呼ばれます）に分割し、同じ色のポイントが互いに近くなるように（つまり、異なる色のポイントが互いに遠くなるように）することが目的です。^[18]${\displaystyle n}$

重心ベースのクラスタリング問題を（メトリック）施設配置問題として見る（「変換」または「縮小」する）方法を確認するには、前者の各データ ポイントを後者の需要ポイントとして見ます。クラスタリングするデータがメトリック空間の要素であるとします（たとえば、をある固定された に対する次元ユークリッド空間とします）。構築している施設配置問題では、施設をこのメトリック空間内の任意のポイントに配置できます。これにより、許可される施設の場所の集合が定義されます。コストは、場所と需要ポイントのペア間のペアワイズ距離として定義します（たとえば、メトリック k-center を参照）。重心ベースのクラスタリング問題では、データを同値クラス（つまり、色）に分割し、各クラスには重心が 1 つあります。構築した施設配置問題のソリューションでも、このような分割がどのように実現されるかを見てみましょう。実行可能なソリューションは、場所の空でないサブセットです。施設配置問題におけるこれらの場所は、重心ベースのクラスタリング問題における重心のセットを構成します。次に、各需要ポイントを、サービス コストを最小化する場所に割り当てます。つまり、データ ポイントを重心に割り当てます (同点の場合は任意に決定します)。施設配置問題のコストが重心ベースのクラスタリング問題の距離関数のイメージになるように定義されている 場合、これにより分割が実現されます。${\displaystyle M}$${\displaystyle M}$${\displaystyle p}$${\displaystyle p}$${\displaystyle M}$${\displaystyle L}$${\displaystyle c_{\ell ,d}}$${\displaystyle k}$${\displaystyle L'\subseteq L}$${\displaystyle k}$${\displaystyle k}$${\displaystyle d}$${\displaystyle \ell ^{*}}$${\displaystyle d}$${\displaystyle \ell ^{*}:=\mathrm {arg\,min} _{\ell \in L}\{c_{\ell ,d}\}}$${\displaystyle c_{\ell ,d}}$

アルゴリズムに関する有名な教科書「アルゴリズム設計」 ^[19]には、関連する問題の説明と近似アルゴリズムが記載されている。著者らは、メトリック施設配置問題（すなわち、重心ベースのクラスタリング問題またはメトリック中心問題）を中心選択問題と呼んでおり、これにより同義語のリストが増えている。 ${\displaystyle k}$

さらに、上記の施設配置問題の定義では、目的関数が一般化されていることに注意してください。 の特定の選択によって、施設配置問題のさまざまなバリエーションが生成され、したがって、重心ベースのクラスタリング問題のさまざまなバリエーションが生成されます。たとえば、各場所から割り当てられた各需要ポイントまでの距離の合計を最小化することを選択する場合 ( Weber 問題)、またはそのような距離の最大値をすべて最小化することを選択する場合 ( 1 中心問題) があります。 ${\displaystyle f}$${\displaystyle f}$

• グラフの中心
• 二次方程式の割り当て問題
• 位置割り当て
• ダイクストラのアルゴリズム
• 空間解析ソフトウェア一覧
• 施設配置競争ゲーム
• 頂点k中心問題
• 幾何平均線

• EWGLA EURO 位置分析ワーキング グループ。
• 施設の立地に関係する専門団体であるINFORMSの立地分析セクション。
• Trevor Haleが収集した施設の所在地に関する書誌。3,400 件を超える記事が含まれています。
• 位置アルゴリズムのライブラリ
• Web ベースの施設ロケーション ユーティリティ (単一施設)
• Facility Location Optimizer は、施設の配置問題を解決するための MATLAB ベースのツールです。