施設配置問題
【英】: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)とよばれる.
また上記の他に, 時間的な経過を考慮した多期間モデル, 施設から顧客へ需要を配送する際の経路を同時決定するモデル等のバリエーションがある.
施設配置問題のバリエーションの多くは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.
生産・在庫・ロジスティクス: | 新聞売り子問題 方策 施設配置ヒューリスティック 施設配置問題 時間枠付き運搬経路問題 混合品種の順序付け 混合品種組立ライン |
組合せ最適化: | 多項式時間アルゴリズム 巡回セールスマン問題 整数計画 施設配置問題 最大クリーク問題 最小木問題 最短路問題 |
「facility location problem」の例文・使い方・用例・文例
- facility location problemのページへのリンク