权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

動線を最適化する平面計画問題に対する効率的な組合せ最適化アルゴリズムの研究

优化流线平面规划问题的高效组合优化算法研究

基本信息

批准号：
07J08388
负责人：
神山直之
金额：
$ 1.15万
依托单位：
Kyoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2007
资助国家：
日本
起止时间：
2007 至 2008
项目状态：
已结题

项目摘要

本年度は,動線を最適化する平面計画問題として,大規模災害時に住民を迅速に避難させる問題をモデル化した動的ネットワーク上の避難計画問題と,都市における避難において優先的に確保すべき道路を決定する問題や避難地図を作成する問題をモデル化した有向グラフ上の有向木問題の研究を行い,以下の成果を得た.まず,避難計画問題に関する成果を説明する.避難計画問題では,最後にシンクに到着する人の避難完了時間を最小にするフローを求めることを目的としているが,現実問題としては任意の時刻において可能な限りの人がシンクに到着しているような最速フローが望ましい.この問題に対して,本研究では,現実のモデル化の際に頻出する全ての辺の容量が一定のグリッド構造ネットワークを一般化したネットワークに対する多項式時間アルゴリズムを開発することに成功した.次に,有向グラフ上の有向木問題に関する成果を説明する.まず,都市ネットワークにおける避難地図を作成する問題をモデル化した有向木被覆問題に対する多項式時間アルゴリズムを開発した.さらに,この有向木被覆問題をさらに一般化した,避難地図の総長を最小化する問題に関しても,部分的な場合に対して多項式時間アルゴリズムを開発した.都市における避難において優先的に確保すべき道路を決定する問題をモデル化した有向木詰込問題に関しては,単に辺素な有向木を詰め込むだけではなく,各点から根に向かう辺に関して点素であるような一般化された問題を扱い,本研究では,いくつかの場合に対してそのような有向木が存在する必要十分条件を明らかにし,同時にそのような有向木を見つける多項式時間アルゴリズムも与えた.

This year, we conducted research on the optimization of dynamic routes and the planning of evacuation for residents in case of large-scale disasters. We conducted research on the optimization of dynamic routes and the planning of evacuation for residents in case of large-scale disasters. Please explain the results of the evacuation plan. Evacuation planning problem: last minute, last minute. In this paper, we propose a new method to solve this problem. Next, the results of the directed tree problem are explained. The problem of creating an urban shelter is solved by a polynomial. In this paper, the problem of directional tree covering is generalized, and the problem of minimizing the total length of refuge is solved in some cases. The problem of ensuring the priority of urban evacuation and the problem of determining the road are related to the problem of directional trees, and the problem of generalization of each point is related to the problem of directional trees. This study is to clarify the necessary conditions for the existence of directional trees in the case of urban evacuation. At the same time, there is a direction to see the polynomial time.