疏散规划的里逆转网络重构

《疏散规划的里逆转网络重构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、疏散规划的里逆转网络重构：一个结果的概要（点此连接察看原文）SanghoKim明尼苏达大学计算机科学系sangho@cs.umn.eduShashiShekhar明尼苏达大学计算机科学系shekhar@cs.umn.edu摘要里逆转，或里反转，是一种在疏散过程通过改变内部道路方向来增加一个真实网络向外部疏散的能力。这个里逆转是讨论了一个潜在的补救措施，以解决在国土安全和自然灾害中疏散时遇到的拥挤情况（例如，飓风）。现有的里逆转算法只处理一个单源，多目的地的情况。这些方法不能处理的多源问题，多源问题在解决从不同的来源的冲突间

2、起着更重要的作用。我们用图和流动理论正式确定疏散的情况，并证明里逆转问题的NP完全性。我们提出了两种具有能力意识全局性的里逆转的探索产生了在面对指向不同源的路径的里逆转策略。我们在利用合成网络以及现实世界的数据集的情况下评估建议试验性质的启发性的探索。此外，我们会提供的代数的成本模型。实验结果表明，我们里逆转方案可以减少30%或者更多的疏散时间。类别和主题描述符F.2.0[理论计算]:算法的分析和问题复杂度的定义一般条款算法，实验关键词里逆转,里反转,疏散计划,时间膨胀图,组合优化,模拟退火1介绍疏散计划，由于越来越多的风

3、险，无论是恐怖袭击事件和自然灾害，是当前具有重大意义的问题。从交通运输体系的角度来看，大规模的交通拥堵，在疏散过程中一直是主要的问题。在经历乔治市在1998年和弗洛伊德市在1999年的飓风后，交通运输的社会观察，有必要增加对疏散路线的能力，以及疏散时间更准确的估计。里逆转，或里反转，已被讨论作为一个潜在的补救措施，以解决如此巨大的拥塞，增加往外疏散的能力。今天，18个沿海的州中的受到飓风威胁的11个，已经考虑使用里逆转作为其部分撤离战略。虽然里逆转主要在疏散过程中起重要作用，但其应用并不应被局限。在华盛顿特区两个中心车道公

4、路系统，就是用里反转的模式，以有效地控制在上午和傍晚繁忙时间。足球比赛后人员离开的里逆转问题，是另一个单源多目的地的典型的情况。尽管它很重要，并有各方面的应用，研究人员还没有从一个可以计算的角度解决里逆转问题。计算机辅助下的里逆转设计可能不仅有助于发展，优化网络配置，而且能量化网络疏散的结果。因此，我们在图形和流理论的帮助下，制定里逆转问题的方案。在用一个有向和权图给定的多源多目的地情况下，我们要找到一个重新配置过的网络来尽量减少疏散时间。除了上述问题的分析，我们猜想这里逆转问题是NP完全的，并提供证明概要。这个问题的NP

5、完全的理解是应用组合优化技术在里逆转问题上应用的踏脚石。就我们所知，算法描述[14]是唯一的解决里逆转问题的方法。在他们疏散建模里，疏散区包含一个源和多个目的地。他们的解决办法是寻求从单一源到目的地的最优路径，并且叠加。这种做法在疏散人员位于不同的源，并且有多个目的地的时不是有效的。该办法由于从不同源到各地的最优路径地的冲突而失效。在另一方面，我们目前的能力认识到全局性的里逆转的探索在多源竞争到多目的地时能产生里逆转网络配置。我们的第一个办法是翻转高流量边（FHFE），这个办法跳过拥有优先级的边，产生一个适当的水平，拥有快

6、速运行时间的高质量的结果。我们的第二个方法是基于模拟退火（SA），其中一种极小局部逃逸的迭代方式有效改善疏散时间。在Monticello，明尼苏达州，美国考察核电厂故障的情况，每一种办法都在综合运输网络和扩展性方面被评估和审查。从实际和综合数据表明，我们的FHFE方案是接近模拟退火的，尽管它运行很快。此外，我们的方案可以减少疏散时间的三分之一。论文的剩余部分，组织如下。第2部分定义里逆转问题，并表明其NP完全性。第3部分介绍了相关工作。在第4部分中，我们描述了两个试验性方案。第5部分介绍了实验装置的信息和本办法的评价。第6

7、条中论述了有关的知识来了解里逆转问题。最后，第7部分总结并对今后工作讨论的一个概括。2问题定义第2部分包括两个小节。第一小节定义了里逆转问题，并给出了一个说明问题的例子。第二小节论述contraflow（里逆转）问题的NP-完全性。2.1问题描述设图G（V，E）的是一个有向的网络，V是点的集合，E是边的集合。每个顶点有一个初始的包含数目，也就是已经存在的人的数量和点总共的包含能力。每条边也有通行能力和通行时间。该疏散的情况可以有多个源和多个目的地。疏散时间被定义为当第一个撤离者离开一个来源顶点到最后撤离人员抵达目的地之间的

8、一段时间条件:1.交通网络图,有向图G(V,E)2.每个点都有一个初始的包含数和包含能力3.每条边都有通行能力和通行时间.4.源和目的地点.找到:里逆转的网络的配置目的:最小化疏散时间.限制:1.通行时间和能力是固定的.2.不能跳过一条线上的点.图1图2图1显示了一个交通运输网络中的简单的撤离情况。每个