施設配置問題
【しせつはいちもんだい (facility location problem, plant location problem)】
概要
空間内において最適な点を選択する問題の総称. 通常, 平面または空間内に位置して需要をもつ顧客の集合, ならびに施設の配置可能地点が与えられたとして, 与えられた制約を満足しつつ目的関数を最適化するように施設の配置を決定する問題を指す. 供給施設と需要地の間の輸送問題も含めて考慮する場合もある.
詳説
施設配置問題 (facility location problem)(工場立地問題)とは, 施設の配置可能地点, 需要をもつ顧客の集合が与えられて, ある基準を満たす施設の配置場所を決定する問題の総称である [1]. 適用分野には, 工場, 倉庫, 配送センターから消防署や病院等の緊急施設, 廃棄物処理施設の立地にいたるまで, 広範囲な領域が対象として含まれる.
施設配置問題の基本形としては, メディアン問題 (median problem), センター問題 (center problem), 容量制約なし施設配置問題 (uncapacitated facility location problem)または単純施設配置問題 (simple facility location problem)が挙げられる. 前者の2つの問題は, 選択される施設の個数があらかじめ決められている場合には, 選択する施設数をpとしてそれぞれ, p-メディアン問題 (p-median problem), p-センター問題 (p-center problem)とよばれる.
以下に代表的な構成要素に基づく分類を示す.
- 1. 施設の配置可能地点に基づく分類
- 施設の配置可能地点が, 平面上の任意の場所か(連続型), 既定された有限個の場所か(離散型)に分類される. 連続型で平面上に単一の施設を配置する問題は, ウェーバー問題 (Weber problem)とよばれる.
- 2. 選択可能な施設数に基づく分類
- 選択可能な施設数が単一か複数(個数が固定または任意)かに分類される.
- 3. 評価尺度に基づく分類
- 各顧客に対して, 最も近い施設への距離の合計の最小化, 最も近い施設への距離の最大値の最小化, 施設からの総輸送費用の最小化等が含まれる.
- 4. 品種数に基づく分類
- 施設間を移動する品種が単一か複数かに分類される.
- 5. 施設の容量制約に基づく分類
- 各施設でまかなうことのできる顧客の需要量に制限なしか, 上限・下限が定められる場合に分類される. 容量制約なし施設配置問題に対して施設の容量上限が課される場合には, 容量制約付き施設配置問題 (capacitated facility location problem)とよばれる.
また上記の他に, 時間的な経過を考慮した多期間モデル, 施設から顧客へ需要を配送する際の経路を同時決定するモデル等のバリエーションがある.
施設配置問題のバリエーションの多くはNP困難(NP-hard)であり, 多項式時間の厳密解法は絶望視されているが, 代表的なバリエーションの幾つかに関しては問題の構造の特殊性より, 実務的には比較的扱い易い問題であると考えられている. 厳密解法としては, ラグランジュ緩和法(Lagrangian relaxation method), 双対上昇法(dual ascent method) [2], ベンダース分解法(Benders' decomposition) [3]を用いた方法が挙げられる.
施設配置問題に対する研究は, 特に1960年代に離散型のモデルが紹介されて以来, 理論的に有効な多くの成果が報告されている [4].
実務への適用に関しては, ジオフリオン(A. M. Geoffrion)らによる食品会社のロジスティクスネットワークの再設計 [3] をはじめとして, 多くの事例が評価されている. そこでは現実問題に対処するための単純化や工夫が, データの集成や近似の方法の提示により紹介されている.
参考文献
[1] W. Domschke and A. Drexl, Location and Layout Planning: An International Bibliography, Springer-Verlag, 1985.
[2] D. Erlenkotter, "A Dual-Based Procedure for Uncapacitated Facility Location," Operations Research, 26 (1978), 992-1009.
[3] A. M. Geoffrion and G. Graves, "Multicommodity Distribution System Design by Benders' Decomposition," Management Science, 5 (1974), 822-844.
[4] P. B. Mirchandani and R. L. Francis, Discrete Location Theory, John Wiley & Sons, 1990.