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

最小極大マッチング問題に対する(2-1/χ'(G))近似アルゴリズム

最小局部最大匹配问题的(2-1/χ(G))近似算法

• 发表时间: 2010
• 作者: 松本雄介;神山直之;今井桂子
• 通讯作者: 今井桂子