Research on data structures and optimization problems in GIS

GIS数据结构及优化问题研究

• 批准号: 21500021
• 负责人: IMAI Keiko
• 金额: $ 2.5万
• 依托单位: Chuo University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21500021/
• 关键词: アルゴリズム理論; 地理情報システム; 最適化問題; 施設配置問題; ラベル配置問題; 最小極大マッチング; 近似アルゴリズム; 集団下校経路; 階層型施設配置; GIS用データ構造; 集団下校経路決定; 配送計画問題

In the Geographic Information Systems(GIS), there are a lot of optimization problems. In order to solve such problems, efficient data structures and algorithms that deal with a large amount of GIS data are strongly required. We developed data structures and algorithms for optimization problems in GIS, for example, a problem of deciding school-commuting routes for elementary school students, facility location problems in times of disaster, etc. We also analyzed marine transportation using a time-space network. Moreover, from a theoretical point of view, we proposed two approximation algorithms for a minimum maximal matching problem that have a strong relationship with minimum maximal flow problem in traffic flow.

在地理信息系统（GIS）中，存在着大量的优化问题。为了解决这些问题，高效的数据结构和算法，处理大量的GIS数据是强烈需要的。我们开发了GIS中最优化问题的数据结构和算法，例如，小学生的学校通勤路线的决定问题，灾害时的设施位置问题等。我们还使用时空网络分析了海上运输。此外，从理论的角度来看，我们提出了两个近似算法的最小最大匹配问题有很强的联系，在交通流中的最小最大流问题。

项目成果

An Algorithm for Composing Principal Road Network from Digital Road Map by Using Topological Information

利用拓扑信息从数字路图中构建主路网的算法

• 发表时间: 2009
• 期刊: FORMA
• 作者: 吉田祐太;今井桂子;H. Umeo and T. Yanagihara;佐藤貴彦;Shigeki TORIUMI
• 通讯作者: Shigeki TORIUMI

計算幾何学における離散幾何図形

计算几何中的离散几何

• 发表时间: 2011
• 作者: Yasunori Ushiro;Yoshinari Fukui;Hidehiko Hasegawa;今井桂子
• 通讯作者: 今井桂子

エネルギー資源の海上輸送におけるチョークポイント分析

能源海上运输瓶颈分析

• 发表时间: 2011
• 作者: 鳥海重喜;高嶋隆太
• 通讯作者: 高嶋隆太

Mathematical Model for Required Number of EV Stations in Highway Networks

公路网中电动汽车站所需数量的数学模型

• 发表时间: 2010
• 作者: Y.Honma;S.Toriumi
• 通讯作者: S.Toriumi

グローバル化の中での海上物流

全球化背景下的海运物流

• 发表时间: 2010
• 作者: 相澤裕司;今井桂子;Shozo Hori and Takako Nakatani and KeiichiKatamine and Naoyasu Ubayashi and Masaaki Hashimoto;齋藤翼;鳥海重喜
• 通讯作者: 鳥海重喜