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

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

基本信息

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

项目摘要

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

今年，我们对动态网络上的疏散计划问题进行了研究，该研究模拟了迅速撤离大规模灾难的居民的问题，以及有向图上的定向树问题，该问题建立了确定确定城市中疏散道路的问题的问题，以及创建疏散映射的问题。首先，我们解释了疏散计划问题的结果。疏散计划问题的目的是找到一个流量，以最大程度地减少那些到达水槽的人的疏散完成时间，但实际上，希望以最快的方式以尽可能多的人到达水槽到达水槽的方式。为了解决这个问题，在这项研究中，我们为网络开设了多项式时间算法，该网络通过网格结构网络概括，在建模过程中经常发生的各个方面恒定容量。我们已经成功地创建了这个问题。接头，我们将在有向图上解释有向树问题的结果。首先，我们为定向树覆盖问题开发了一种多项式时间算法，该算法建立了在城市网络中创建撤离图的问题，该问题是为了开发了一个多态度算法的一般图像，该问题是针对整个问题，该案例的整体范围，该问题是针对分子问题，该问题是一个问题，该问题是一个问题，该问题是一个问题，该问题是一个问题，该问题是一个问题，该问题是一个问题，该问题是一个问题，该问题是一个问题，该问题是一个问题。 this directed tree cover problem, and also develops a polynomial-time algorithm for partial cases.For the directed tree packing problem, which modeled the problem of determining the roads to be prioritized for evacuation in urban areas, we do not simply pack the edges of the directional trees, but also deal with a generalized problem where the edges from each point to the roots.In this study, we clarify the necessary and sufficient conditions for such directed trees for some cases, and还提供了一种多项式时间算法，用于查找此类定向树。