地理情報システムにおけるデータ構造と最適化問題に関する研究
【研究分野】情報学基礎
【研究キーワード】
アルゴリズム理論 / 地理情報システム / 最適化問題 / 施設配置問題 / ラベル配置問題 / 最小極大マッチング / 近似アルゴリズム / 集団下校経路 / 階層型施設配置 / GIS用データ構造 / 集団下校経路決定 / 配送計画問題
【研究成果の概要】
地理情報システムにおいては,大量のGISデータを用いた最適化問題が非常に多く存在し,それらを実用的に解く解法が求められており,それには大規模なデータを効率的に扱うことのできるデータ構造と高速なアルゴリズムが必要となる.本研究では,集団下校の経路生成問題,施設配置問題などの最適化問題の解法や海上輸送分析の手法を研究し,そのためのデータ構造の構築を行い,実用的な成果を得た.また,最小極大流に関しては,最小極大マッチング問題を整数計画問題として定式化し, 2つの近似アルゴリズムを開発するなど理論的研究を行った.
【研究代表者】
【研究分担者】 |
| 鳥海 重喜 | 中央大学 | 理工学部 | 助教 | (Kakenデータベース) |
|
【研究連携者】 |
| 今井 浩 | 東京大学 | 大学院・情報理工学系研究科 | 教授 | (Kakenデータベース) |
|
【研究種目】基盤研究(C)
【研究期間】2009 - 2011
【配分額】3,900千円 (直接経費: 3,000千円、間接経費: 900千円)