「《地理的最適化》」の版間の差分
(新しいページ: ''''【ちりてきさいてきか (geographical optimization problems)】''' ボロノイ図と呼ばれる幾何学図形を用いて定式化される施設配置問題...') |
|||
| 3行目: | 3行目: | ||
ボロノイ図と呼ばれる幾何学図形を用いて定式化される施設配置問題とその解法を[[地理的最適化]]と呼ぶ. 従来の施設配置問題が, ネットワーク上, もしくは利用者が離散的に分布していることを仮定していたのに対して, この手法では, 利用者が連続に分布していることを仮定している. このことで, 実際の人口分布を含めた地理的な条件を問題の定式化に反映できることが大きな特徴である. | ボロノイ図と呼ばれる幾何学図形を用いて定式化される施設配置問題とその解法を[[地理的最適化]]と呼ぶ. 従来の施設配置問題が, ネットワーク上, もしくは利用者が離散的に分布していることを仮定していたのに対して, この手法では, 利用者が連続に分布していることを仮定している. このことで, 実際の人口分布を含めた地理的な条件を問題の定式化に反映できることが大きな特徴である. | ||
| − | ボロノイ図とは, $n$ 個の点が与えられた時, 平面上の点をそのどれに近いかによって分割することでできる図形である. 平面上の点を$\bx$, 与えられた点を$\bx_1$, ..., $\bx_n$とすると, $\bx_i$に一番近い領域(ボロノイ領域と呼ぶ)は | + | ボロノイ図とは, $n$ 個の点が与えられた時, 平面上の点をそのどれに近いかによって分割することでできる図形である. 平面上の点を$\bx$, 与えられた点を$<math>\bx_1\, </math>$, ..., $<math>\bx_n\, </math>$とすると, $<math>\bx_i\, </math>$に一番近い領域(ボロノイ領域と呼ぶ)は |
| − | V_i=\bigcap_{j:j\not=i}\{\bx\in{\mathbf{ R}}^2~|~\|\bx-\bx_i\|<\| | + | <math>V_i=\bigcap_{j:j\not=i}\{\bx\in{\mathbf{ R}}^2~|~\|\bx-\bx_i\|<\|\bx-\bx_j\|\}\, </math> |
| − | \bx-\bx_j\|\} | ||
| 14行目: | 13行目: | ||
一方で, ボロノイ図の高速構成算法が計算幾何学の分野で開発され[2]上記の施設配置問題の解法として, ボロノイ図をくり返し構成する反復解法が実際的な解法として採用できるようになり, このような問題が実用的な規模で解けるようになった. これらを地理的最適化問題と呼んでいる. | 一方で, ボロノイ図の高速構成算法が計算幾何学の分野で開発され[2]上記の施設配置問題の解法として, ボロノイ図をくり返し構成する反復解法が実際的な解法として採用できるようになり, このような問題が実用的な規模で解けるようになった. これらを地理的最適化問題と呼んでいる. | ||
| − | 地理的最適化問題は, 伊理, 室田, 大屋 [2]によって解かれて以来, 種々の変種が考えられている. これらの問題は, [3]に詳しく解説されている. また, 最近では, $L_1$距離の配置問題や, 球面上の配置問題にもこの手法が適用され, 興味深い結果が得られている. ここでは, 伊理, 室田, 大屋によって解かれた最初の問題, すなわち, 「連続型メディアン問題」を紹介する. | + | 地理的最適化問題は, 伊理, 室田, 大屋 [2]によって解かれて以来, 種々の変種が考えられている. これらの問題は, [3]に詳しく解説されている. また, 最近では, $<math>L_1\, </math>$距離の配置問題や, 球面上の配置問題にもこの手法が適用され, 興味深い結果が得られている. ここでは, 伊理, 室田, 大屋によって解かれた最初の問題, すなわち, 「連続型メディアン問題」を紹介する. |
連続型メディアン問題 | 連続型メディアン問題 | ||
| − | 単位正方形$S$内に利用者が連続に分布しており, そこに, $n$個の施設を配置する. そのとき, 利用者は最も近い施設を利用すると仮定する. すると, 各施設の利用圏は施設を母点とするボロノイ図となる. ここで, 利用者の分布を$\phi(\bx)$, 利用者が施設を利用する費用を利用者から施設までの距離とすると, 次のような目的関数を最小にする最適配置問題が考えられる. | + | 単位正方形$<math>S\, </math>$内に利用者が連続に分布しており, そこに, $<math>n\, </math>$個の施設を配置する. そのとき, 利用者は最も近い施設を利用すると仮定する. すると, 各施設の利用圏は施設を母点とするボロノイ図となる. ここで, 利用者の分布を$<math>\phi(\bx)\, </math>$, 利用者が施設を利用する費用を利用者から施設までの距離とすると, 次のような目的関数を最小にする最適配置問題が考えられる. |
| − | \ | + | <math>F(\bx_1,\ldots,\bx_n)=\int (\min_{i} ||\bx-\bx_i||)\phi(\bx)\rd\bx\, </math> |
| − | |||
| + | 施設の配置問題では, このようなミニサム型の問題を Hakimiの論文 [1]にならってメディアン問題と呼ぶ習わしになっている. 解法は, 基本的な降下法である. すなわち, 上記の目的関数の偏微分係数を求め, 最急降下方向に若干の修正を加えた降下方向に直線探索を行うことを収束解が得られるまで繰り返す. このようにして得られた解は, 6角形を基本としたパターンになっている. 図1に, 利用者が一様に分布している場合の解を示す. | ||
| + | |||
| + | |||
| + | 0209-c-e-06-fig1.gif | ||
| − | |||
| + | 図1: 連続型メディアン問題の解の一例 | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
---- | ---- | ||
2007年7月12日 (木) 18:50時点における版
【ちりてきさいてきか (geographical optimization problems)】
ボロノイ図と呼ばれる幾何学図形を用いて定式化される施設配置問題とその解法を地理的最適化と呼ぶ. 従来の施設配置問題が, ネットワーク上, もしくは利用者が離散的に分布していることを仮定していたのに対して, この手法では, 利用者が連続に分布していることを仮定している. このことで, 実際の人口分布を含めた地理的な条件を問題の定式化に反映できることが大きな特徴である.
ボロノイ図とは, $n$ 個の点が与えられた時, 平面上の点をそのどれに近いかによって分割することでできる図形である. 平面上の点を$\bx$, 与えられた点を$構文解析に失敗 (不明な関数「\bx」): {\displaystyle \bx_1\, } $, ..., $構文解析に失敗 (不明な関数「\bx」): {\displaystyle \bx_n\, } $とすると, $構文解析に失敗 (不明な関数「\bx」): {\displaystyle \bx_i\, } $に一番近い領域(ボロノイ領域と呼ぶ)は
構文解析に失敗 (不明な関数「\bx」): {\displaystyle V_i=\bigcap_{j:j\not=i}\{\bx\in{\mathbf{ R}}^2~|~\|\bx-\bx_i\|<\|\bx-\bx_j\|\}\, }
で定義される. この図は, 与えられた点(母点と呼ぶ)を施設とみなすと, 自然にその施設の勢力圏を与えており, この性質を用いて種々の施設配置問題が考えられる.
一方で, ボロノイ図の高速構成算法が計算幾何学の分野で開発され[2]上記の施設配置問題の解法として, ボロノイ図をくり返し構成する反復解法が実際的な解法として採用できるようになり, このような問題が実用的な規模で解けるようになった. これらを地理的最適化問題と呼んでいる.
地理的最適化問題は, 伊理, 室田, 大屋 [2]によって解かれて以来, 種々の変種が考えられている. これらの問題は, [3]に詳しく解説されている. また, 最近では, $$距離の配置問題や, 球面上の配置問題にもこの手法が適用され, 興味深い結果が得られている. ここでは, 伊理, 室田, 大屋によって解かれた最初の問題, すなわち, 「連続型メディアン問題」を紹介する.
連続型メディアン問題
単位正方形$$内に利用者が連続に分布しており, そこに, $$個の施設を配置する. そのとき, 利用者は最も近い施設を利用すると仮定する. すると, 各施設の利用圏は施設を母点とするボロノイ図となる. ここで, 利用者の分布を$構文解析に失敗 (不明な関数「\bx」): {\displaystyle \phi(\bx)\, } $, 利用者が施設を利用する費用を利用者から施設までの距離とすると, 次のような目的関数を最小にする最適配置問題が考えられる.
構文解析に失敗 (不明な関数「\bx」): {\displaystyle F(\bx_1,\ldots,\bx_n)=\int (\min_{i} ||\bx-\bx_i||)\phi(\bx)\rd\bx\, }
施設の配置問題では, このようなミニサム型の問題を Hakimiの論文 [1]にならってメディアン問題と呼ぶ習わしになっている. 解法は, 基本的な降下法である. すなわち, 上記の目的関数の偏微分係数を求め, 最急降下方向に若干の修正を加えた降下方向に直線探索を行うことを収束解が得られるまで繰り返す. このようにして得られた解は, 6角形を基本としたパターンになっている. 図1に, 利用者が一様に分布している場合の解を示す.
0209-c-e-06-fig1.gif
図1: 連続型メディアン問題の解の一例
参考文献
[1] S. L. Hakimi, "Optimal Distribution of Switching Centers and the Absolute Centers amd Medians of a Graph," Operations Research, 12 (1964), 450-459.
[2] M. Iri, K. Murota and T. Ohya, "A Fast Voronoi Diagram Algorithm with Applications to Geographical Optimization Problems," in P. Throft-Christensen, ed., Lecture Notes in Control and Information Sciences, Vol. 59, System Modelling and Optimization, Proceedings of the 11th IFIP Conference, Copenhagen, Springer-Verlag, 273-288, 1984.
[3] 岡部篤行, 鈴木敦夫, 『最適配置の数理』, 朝倉書店, 1992.