地理的最適化

【ちりてきさいてきか (geographical optimization)】

概要

ボロノイ図という幾何学図形を用いて定式化される施設配置問題とその解法を呼ぶ. ボロノイ図は, $n\,$ 個の点が与えられたとき, 平面上の点をそのどれに近いかによって分割することでできる図形である. この図は, 与えられた点を施設とみなすと, 自然にその施設の勢力圏を与えており, この性質を用いて種々の施設配置問題が考えられる. このボロノイ図の高速構成算法が計算幾何学の分野で開発され, 実用的な規模の問題が解けるようになった.

詳説

　ボロノイ図と呼ばれる幾何学図形を用いて定式化される施設配置問題とその解法を地理的最適化と呼ぶ. 従来の施設配置問題が, ネットワーク上, もしくは利用者が離散的に分布していることを仮定していたのに対して, この手法では, 利用者が連続に分布していることを仮定している. このことで, 実際の人口分布を含めた地理的な条件を問題の定式化に反映できることが大きな特徴である.

　ボロノイ図とは, n 個の点が与えられた時, 平面上の点をそのどれに近いかによって分割することでできる図形である. 平面上の点を${\boldsymbol {x}}\,$, 与えられた点を${\boldsymbol {x}}_{1}\,$, ..., ${\boldsymbol {x}}_{n}\,$とすると, ${\boldsymbol {x}}_{i}\,$に一番近い領域(ボロノイ領域と呼ぶ)は

$V_{i}=\bigcap _{j:j\not =i}\{{\boldsymbol {x}}\in {\mathbf {R} }^{2}~|~\|{\boldsymbol {x}}-{\boldsymbol {x}}_{i}\|<\|{\boldsymbol {x}}-{\boldsymbol {x}}_{j}\|\}\,$

　で定義される. この図は, 与えられた点(母点と呼ぶ)を施設とみなすと, 自然にその施設の勢力圏を与えており, この性質を用いて種々の施設配置問題が考えられる.

　一方で, ボロノイ図の高速構成算法が計算幾何学の分野で開発され[2]上記の施設配置問題の解法として, ボロノイ図をくり返し構成する反復解法が実際的な解法として採用できるようになり, このような問題が実用的な規模で解けるようになった. これらを地理的最適化問題と呼んでいる.

　地理的最適化問題は, 伊理, 室田, 大屋 [2]によって解かれて以来, 種々の変種が考えられている. これらの問題は, [3]に詳しく解説されている. また, 最近では, $L_{1}\,$距離の配置問題や, 球面上の配置問題にもこの手法が適用され, 興味深い結果が得られている. ここでは, 伊理, 室田, 大屋によって解かれた最初の問題, すなわち, 「連続型メディアン問題」を紹介する.

連続型メディアン問題

　単位正方形$S\,$内に利用者が連続に分布しており, そこに, $n\,$個の施設を配置する. そのとき, 利用者は最も近い施設を利用すると仮定する. すると, 各施設の利用圏は施設を母点とするボロノイ図となる. ここで, 利用者の分布を$\phi ({\boldsymbol {x}})\,$, 利用者が施設を利用する費用を利用者から施設までの距離とすると, 次のような目的関数を最小にする最適配置問題が考えられる.

$F({\boldsymbol {x}}_{1},\ldots ,{\boldsymbol {x}}_{n})=\int (\min _{i}||{\boldsymbol {x}}-{\boldsymbol {x}}_{i}||)\phi ({\boldsymbol {x}}){\rm {d}}{\boldsymbol {x}}\,$

　施設の配置問題では, このようなミニサム型の問題を Hakimiの論文 [1]にならってメディアン問題と呼ぶ習わしになっている. 解法は, 基本的な降下法である. すなわち, 上記の目的関数の偏微分係数を求め, 最急降下方向に若干の修正を加えた降下方向に直線探索を行うことを収束解が得られるまで繰り返す. このようにして得られた解は, 6角形を基本としたパターンになっている. 図1に, 利用者が一様に分布している場合の解を示す.

図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.