多目标优化疏散路线在体育场使用叠加势场网络基础

文摘

定义多目标疏散路线优化问题来找出最佳疏散路线的疏散人员在多个疏散的目标。对于提高疏散效率,我们抽象的疏散区叠加势场网络(SPFN),我们提出了SPFN-based ACO算法(SPFN-ACO),基于该模型来解决这个问题。在武汉体育中心的情况下,我们比较SPFN-ACO算法与HMERP-ACO算法和传统算法算法在三个疏散目标,也就是说,总疏散时间、疏散路线总长度,和累积拥堵程度。实验结果表明,SPFN-ACO算法有更好的性能,同时与HMERP-ACO疏散路线算法和传统算法算法求解多目标优化问题。

1。介绍

疏散计划在大型公共区域通常有两个难点:(1)大范围:大型公共区域有一个复杂的平面结构。它可以容纳成千上万的人。(2)源和multisink:在疏散过程中,疏散人员经常在不同的地方开始从不同的出口在公共区域和逃跑。

总之,大规模的公共区域的疏散规划是一个具有挑战性的问题。为解决这一问题,研究人员提出了一些有效的方法。施等。1)使用基于代理模型来模拟和分析在大型公共建筑在火灾条件下疏散过程。陈和Miller-Hooks [2)采用弯管机分解确定一组疏散路线、疏散人员的分配这些路线对于大型建筑。Tayfur和Taaffe3)利用线性规划松弛模型,解决资源需求和调度问题在医院疏散成本最小化的目标在一个预定的疏散完成时间。方等。4疏散建模过程与multiexits教学楼,通过细胞自动机模拟,分析了multiexits选择现象找出最优退出所有疏散人员的选择组合。通常情况下,需要考虑多个宏观目标在实际疏散计划,和一组nondominated计划需要决策。因此,疏散规划问题可以转化成多目标优化问题。然而,就在研究,如文献[5- - - - - -7),关注。在这些文献中,文献[7疏散路线]成功地解决了多目标优化问题在体育场使用HMERP-ACO算法。方等。7)抽象疏散区作为分层定向网络根据功能,疏散人员通常移动远离中心的疏散区在疏散过程。然而,另一个特点,即每个撤离者常常走向,最终达到出口之一,并不考虑方舟子的论文。那么,如何考虑这两个特性?在物理学中,潜在的一个点在空间产生的多个点费用可以计算电势的叠加原理8]。灵感来自这个,我们的球场的中心点为正电荷,每个出口作为一个消极的点电荷,使用电势的叠加原理一起之前提到的两个特点。的基础上叠加的潜力,我们的武汉体育中心体育馆作为叠加势场网络(SPFN)。SPFN的基础上,我们提出了SPFN-ACO疏散路线算法来解决多目标优化问题。相比之下,HMERP-ACO [7)和算法(9),SPFN-ACO显示更好的优化疏散路线解决多目标优化问题的性能。

本文的其余部分组织如下。部分2介绍了先进的疏散计划利用群体智慧。部分3定义多目标疏散路线优化问题。部分4介绍了SPFN。部分5州SPFN-ACO算法。部分6通过实验验证优化的性能SPFN-ACO和包含了一些分析。部分7本文得出的结论是,这个研究的未来方向。

2。相关的工作

在大型公共场所的人们处于危险之中,因为很多人为或自然的事故,如火灾、飓风,和炸弹10]。为应对这些突发事件,许多科学家和工程师都重视对疏散路线规划研究。在这些研究中,群体智能技术的应用程序疏散路径规划是一个热门话题,因为疏散过程本身是一种集体行为。群体智能技术主要包括粒子群优化(PSO) (11)技术和蚁群优化(ACO) (9)技术。群体智能技术主要用于两个方面:疏散过程的模拟和优化疏散路线7,12]。一方面,群体智能技术有天然优势来模拟疏散等集体行为过程(13]。另一方面,群体智能算法的优化机制可以有效地优化疏散由迭代目标的配置影响疏散效率的因素(7,14]。影响疏散效率的因素包括信息素(7在疏散区[],避难所的位置15],车道的方向[16),道路障碍的位置(17),为每个撤离疏散的调度18]。

此外,疏散路线优化问题通常需要考虑多个目标,如总间隙时间(19掩藏(总数)20.]。几个研究[5,6)疏散涉及到多目标路由优化问题。他们中的一些应用群体智能技术来解决这类问题(7,14]。

3所示。问题公式化

摘要疏散区被分成许多个。疏散计划由每个撤离的路线。所以每个疏散计划可以表示成 在哪里计划的数量,撤离的路线吗,它可以被描述为 在哪里疏散人员的数量,和分别是开始和结束分区吗j撤离路线。是k临时的分区j撤离路线。最终的分区是一个出口的疏散区。

因此,本文中的多目标疏散路线优化问题可以制定算法1。

疏散路线优化问题涉及到三个目标需要同时实现,即最小化总疏散时间的最小化总疏散路线的长度和累积拥堵最小化程度。

(春节)是由总疏散时间 在哪里撤离的撤离时间吗。

总疏散路线长度(TERL)是由 在哪里疏散路线撤离的长度吗。

累积拥堵程度(CCD)是由 在哪里分区的疏散人员数量在t时间步长,分区的疏散能力吗,是时间步骤的数目,个的数量。

4所示。叠加势场网络(SPFN)

点的电势场如图1。如果选择0的潜力无穷,潜力(8]在远处从一个点电荷是 正电荷(图1(一))或 消极的点电荷(图1 (b))。

体育场的中心点可能被视为一个积极的点电荷,每个出口可被视为消极的点电荷。武汉体育中心(图2)可以看到叠加势场。根据电势的叠加原理,叠加在体育场的潜力可以推导出 在哪里是出口的数量,是出口的潜力。退出的容量吗距离出口吗,是中心的潜力点。距离中心点,中心点的容量。

基于叠加的潜力,我们提出了势场叠加网络(SPFN)抽象的体育场。该模型在一定程度上是基于点模型中使用(5]。SPFN可以作为制定 在哪里是一组节点,是链接的集合,是每个节点组的潜力,的设置每个节点的能力。

体育场被划分为157个。在SPFN每个分区都抽象为一个节点。每两个节点之间的联系是一个连接两个恢复之间的关系。每个节点的可能是潜在的中心点对应的分区。每个节点的能力相应的分区的容量。每个节点的坐标的中心点的坐标对应的分区。如果一个撤离或一组撤离者被视为一个积极的测试电荷,它总是从高潜力节点移动到低电位节点。有216个链接和157个节点的SPFN武汉体育中心体育场,包括10个节点和42看台节点退出。图3显示了电位分布的SPFN武汉体育中心体育场。

5。SPFN-ACO

为解决多目标疏散路线优化问题中提到的部分3SPFN的基础上,我们提出SPFN-ACO算法。

5.1。SPFN-ACO算法的主要过程

SPFN-ACO算法的主要过程中列出的算法2。我们用信息素向量来表示信息素配置在每个链接网络。信息素向量(PV)是由 在哪里是信息素kth链接连接节点和节点和在网络节点之间链接的总数。

5.2。重叠节点选择基于势场的轮盘赌方法

叠加的主要过程基于势场的轮中列出的方法算法3。有允许访问的邻居节点。是允许访问的邻居节点的集合。是kth候选节点。是蚂蚁的节点在目前。可以由 你的邻居节点必须符合两个条件:容量约束和潜在的约束。

的容量约束

节点是疏散人员的数量,这是由 在节点是蚂蚁的数量。每只蚂蚁代表疏散人员。

节点的能力吗,这是通过计算 分区的面积是。是一处避难的平均面积通常占据了。由文献[22),每个撤离占地0.3 ?²。

是由潜在的限制 在哪里是当前的潜在访问节点和潜在的下一个访问节点。潜在的约束表明蚂蚁应该从高潜力的节点移动到低电位节点,即潜在的的下一个访问节点应小于潜在的吗当前访问的节点。

叠加的过程显示了基于势场的轮盘赌法算法4。其原理可以解释为一个示例图4。在图4在每个节点上,数字是潜在的价值。撤离的红色节点的节点是在。潜在的,他可以选择节点的潜在价值低于他的节点作为候选人。所以,他可以选择三个邻居节点允许访问节点。允许访问节点的潜力,分别是4,4,2。然后,他必须选择其中一个作为下一个访问节点通过计算每个候选的转移概率和累积跃迁概率算法所示4。

5.3。速度、位置和移动策略

当临时目的地节点被选中时,蚂蚁开始沿着当前节点之间的联系和临时目标节点。移动速度(7]的蚂蚁是由 在哪里节点是疏散人员的数量在tth ste,节点的能力吗,蚂蚁的最大速度吗。

我们定义了一个概念叫做剩余距离临时目标节点测量是否蚂蚁已经到达临时目标节点。保持距离是由的迭代公式 在哪里和在余下的路程吗th和t时间步长。是时间步的间隔,如10到20秒。当一只蚂蚁到达临时目标节点,余下的路程的长度设置为临时目标节点之间的联系和下一个临时目的地节点。

5.4。信息素更新

更新信息素在每个节点之间的联系 在哪里和信息素数量在链接吗节点之间和在th和米th代下信息素向量。变化的信息素量链接吗。信息素的变化量是由 在哪里的长度是链接,节点是疏散人员的数量在tth时间步,节点的能力吗。

6。实验和分析

6.1。实验设计

在本文中,我们采取了20000灾民钻在武汉体育中心体育场为例,做仿真实验。这个体育场看台42个和10个退出。蚂蚁是随机分配到看台42个,每个蚂蚁代表100灾民。每只蚂蚁的最大速度是2吗?米/秒(23从0到2)和不同?米/s along with the congestion degree. The optimization performance of SPFN-ACO was compared with HMERP-ACO and traditional ACO which is used in Fang’s paper [7]。通过经验,三种算法的参数设置如表1。m_马克斯是一代又一代的总数。是疏散计划在每一代的人口规模。每只蚂蚁的最大速度。每个时间步的长度。蚂蚁的总数。每只蚂蚁代表µ疏散人员。一个和ß的参数来控制信息素和启发式信息之间的相对重要性。蒸发率(24),。

6.2。实验结果分析

图5显示了,non-dominated计划的价值来源于三个算法。“蓝十字”、“红五角星形”和“黑色实心圆,”分别代表了,值non-dominated计划来源于SPFN-ACO HMERP-ACO, ACO算法。的,non-dominated计划的价值来源于SPFN-ACO算法更小比其他两个生成的算法。根据Bierlaire的观点(25],疏散过程可以看作是一系列的节点选择由疏散人员,值non-dominated计划将取决于节点选择策略。对于本文中提到的三个算法,节点选择策略的效率诉诸过渡概率。转移概率主要取决于两个方面:候选邻居节点的选择和相对重要性信息素和启发式信息。后者的观点是由相对重要性的设置参数一个和ß。前方面是由条件决定候选人的邻居节点的选择。在条件下,相同容量约束的三种算法。因此,不同的是另一个条件:ACO算法采用禁忌列表;方HMERP-ACO采用层次结构中定义的论文(7];摘要介绍了SPFN-ACO采用潜力。禁忌列表的访问节点在每个蚂蚁的路线为这只蚂蚁禁止访问节点。它没有考虑任何领域知识,可以提高疏散效率。分层定向网络使用功能,每个撤离行动远离球场的中心点,但没有考虑的另一个功能,每个撤离走向一个退出。叠加势场网络的两个特性考虑在内,显然进一步提高疏散效率,改善优化目标。这是的原因,non-dominated计划的价值来源于SPFN-ACO比那些来自HMERP-ACO和算法。

图6显示了疏散曲线(26)的三个算法。到SPFN-ACO, 95%的灾民已经离开了体育场在450秒,和100%的灾民已经被疏散的体育场在725秒。分别通过HMERP-ACO,它需要575和875秒;通过算法,它甚至需要1675和3525秒。结果表明,选择候选节点条件使用领域知识可以缩短疏散时间和提高疏散效率。如果考虑到两个因素,可以促进疏散,疏散时间不到,只是考虑的一个因素。SPFN-ACO显示一个更好的疏散时间性能比其他两种算法。

图7显示节点的时变拥挤度的三个算法。在第一个X秒,所有三个算法表现出相对较高的拥塞节点1到100。随着时间的增加,生成的计划算法和HMERP-ACO算法表现出缓慢降低重型拥塞节点。但拥堵节点计划由SPFN-ACO大幅减少。这表明,与其他两种算法相比,SPFN-ACO最能疏散撤离的体育场的中间地带,因此减少拥堵程度迅速在中间地带。然而,在所有的三个算法,需要一个相对长的时间使所有节点的拥塞度降低为零,虽然SPFN-ACO扩展的时间最少。“长尾信息素”表明,所有这三个算法需要一个相对较长的时间(相对于网络间隙时间)采取一切疏散人员的体育场。此外,SPFN-ACO拥有最小的累积拥堵程度三个算法。因此,完全讲,SPFN-ACO生成计划的拥堵情况优于其他两种算法,但SPFN-ACO的拥堵情况仍需要改善。

图8显示了三个超体积的自然对数算法。横纵坐标是一代又一代的进化;垂直纵是超体积的自然对数(高压)。超体积是趋同的度量(27]。自然对数的超体积越大,算法的收敛性越好。因此,从图8,我们可以得出这样的结论:SPFN-ACO获得最好的收敛性能,HMERP-ACO是第二,ACO最坏的打算。随着一代又一代的崛起,提高所有三个算法的收敛。它表明,迭代每个链接的信息素,所有这三个算法生成的撤离计划可以逐渐略有改善。然而,三种算法之间的优缺点并不是改变。这表明三种算法之间的优缺点是由候选节点的选择和相对重要性信息素和启发式信息但不具体的信息素值在每个链接。

图9显示non-dominated计划在所有计划的比例来自三个算法。如图840代之前,所有三个算法,non-dominated计划的比例波动;从40到197代,比例增加的阶段。但在第198代,HMERP-ACO,比例急剧下降到20%。最后,200代的进化,non-dominated SPFN-ACO计划的比例达到50%,高于HMERP-ACO(20%)和算法(40%)。

7所示。结论和未来的工作

我们提出了一种多目标优化算法的疏散路线SPFN-ACO,基于组织疏散人员的时空路径在一个叠加势场的网络(SPFN)。ACO算法组织疏散人员的时空路径没有任何领域知识,可以帮助提高疏散效率;HMERP-ACO算法只是利用一个奖励的因素来提高疏散效率;SPFN有效地结合在一起,两个因素可以促进提高疏散效率的合理组织疏散人员的时空路径。仿真实验验证,与HMERP-ACO和ACO算法相比,SPFN-ACO算法更适合解决多目标优化问题的疏散路线。

计划做进一步研究的基础上,SPFN-ACO,如定义更现实的疏散场景,研究疏散人员的分组的影响大小和疏散人员的总数对疏散效率,并探讨了人口规模的影响信息素向量和的进化代算法的性能。

承认

这项工作是由美国国家科学基金会支持部分下的中国批准号。61170202,40971233,61202287。

引用

1. 陈任j ., a, c .,“基于代理大型公共建筑在火灾条件下的疏散模型,”自动化建设,18卷,不。3、338 - 347年,2009页。视图:出版商的网站|谷歌学术搜索
2. 陈和大肠Miller-Hooks .“共享信息的建筑疏散问题,”海军研究物流,55卷,不。4、363 - 376年,2008页。视图:出版商的网站|谷歌学术搜索
3. 大肠Tayfur和k . Taaffe”在医院疏散模型来分配资源,”计算机和工业工程卷,57号4、1313 - 1323年,2009页。视图:出版商的网站|谷歌学术搜索
4. z方,w的歌,j·张,h . Wu”exit-selecting行为实验和建模在建筑疏散,”自然史一,卷389,不。4、815 - 824年,2010页。视图:出版商的网站|谷歌学术搜索
5. m . Saadatseresht a Mansourian, m . Taleai“疏散计划使用多目标进化优化方法,”欧洲运筹学杂志》上,卷198,不。1,第314 - 305页,2009。视图:出版商的网站|谷歌学术搜索
6. 答:Stepanov和j·m·史密斯,“多目标交通疏散路由网络,”欧洲运筹学杂志》上,卷198,不。2、435 - 446年,2009页。视图:出版商的网站|谷歌学术搜索
7. x z方,宗庆后,问:李,李问:和美国,“分层多目标疏散路由在体育场使用蚁群优化方法中,“交通地理杂志,19卷,不。3、443 - 451年,2011页。视图:出版商的网站|谷歌学术搜索
8. r·s·艾略特电磁学:历史、理论和应用程序美国新泽西州霍博肯市威利,1999年。
9. 诉Maniezzo m .民宿,a . Colorni”由一群蚂蚁系统:优化代理、合作”IEEE系统,人,控制论B,26卷,不。1,29-41,1996页。视图:出版商的网站|谷歌学术搜索
10. 聚氨酯和s . Zlatanova“内部建筑的疏散路线计算,”灾难管理信息p . van Oosterom s . Zlatanova, e . m . Fendel Eds。施普林格,页1143 - 1161年,柏林,德国,2005年。视图:谷歌学术搜索
11. 进行j·肯尼迪和r·埃伯哈特,“粒子群优化”《IEEE国际会议上神经网络1995年12月,页1942 - 1948。视图:谷歌学术搜索
12. a·拉赫曼a·k·马哈茂德和e·施耐德,“使用以代理人为基础的模拟人类行为的减少疏散时间,”第十一届环太平洋学报》国际会议上多智能:智能代理和多主体系统,第369 - 357页,2008年。视图:谷歌学术搜索
13. z雪,基于粒子群优化的随机多智能主体疏散仿真模型[博士。论文),纽约大学,2009。
14. r·m·塔瓦雷斯和e . r . Galea“数值优化技术应用于疏散分析”行人和疏散动力学2008w·w·f . Klingsch c . Rogsch a . Schadschneider和m . Schreckenberg, Eds。施普林格,页555 - 561年,柏林,德国,2010年。视图:谷歌学术搜索
15. h·d·Sherali t·b·卡特和A·g·Hobeika”子模型和算法疏散计划/飓风洪水条件下,“交通研究B部分,25卷,不。6,439 - 452年,1991页。视图:谷歌学术搜索
16. c .谢D.-Y。林,美国特拉维斯沃勒”,动态车道逆转疏散网络优化问题和消除交叉策略,”交通研究E,46卷,不。3、295 - 316年,2010页。视图:出版商的网站|谷歌学术搜索
17. h . Cai和A·拉赫曼”方法来开发和优化道路障碍的位置在大学校园紧急疏散,”学报建设研究国会:重塑建设创新实践2010年5月,页409 - 419。视图:出版商的网站|谷歌学术搜索
18. h . Sbayti和h s Mahmassani“疏散的最优调度操作,”交通研究记录,没有。1964年,第246 - 238页,2006年。视图:谷歌学术搜索
19. s . c .加尔松Pursals和f . g .“最佳建筑疏散时间考虑疏散路线,”欧洲运筹学杂志》上,卷192,不。2、692 - 699年,2009页。视图:出版商的网站|谷歌学术搜索
20. 林p, s m . Lo h·c·黄和k . k .袁”的使用多级时变最快时间方法优化疏散计划,”消防安全》杂志,43卷,不。4、282 - 290年,2008页。视图:出版商的网站|谷歌学术搜索
21. m . Ancǎu和c . Caizar”计算帕累托最优设置在multicriterial优化快速成型过程中,“计算机和工业工程,卷。58岁的没有。4、696 - 708年,2010页。视图:出版商的网站|谷歌学术搜索
22. j . Izquierdo蒙塔沃,r·佩雷斯和v . s .要塞,“预测行人疏散时间利用群体智慧,”自然史一,卷388,不。7,1213 - 1220年,2009页。视图:出版商的网站|谷歌学术搜索
23. 林志信。陈和f·冯”快速流控制算法实时紧急疏散在大型室内区域,”消防安全》杂志,44卷,不。5,732 - 740年,2009页。视图:出版商的网站|谷歌学术搜索
24. m .民宿和t . Stutzle蚁群优化:概述和最新进展手册的MetaheuristicsEds, m . Gendreau和y波特凡。卷,146国际系列运筹学和管理科学施普林格,页227 - 263年,纽约,纽约,美国,第二版,2010年版。视图:谷歌学术搜索
25. m . Bierlaire g . Antonini, m·韦伯“行人行为动力学,通过网:移动的物理和社会维度旅行,”学报第十届国际会议旅游行为研究,艾德。k . Axhausen页。队,爱思唯尔,阿姆斯特丹,荷兰,2003年。视图:谷歌学术搜索
26. l·d·汉f .元,t . Urbanik”是一种有效的疏散操作什么?”城市规划与发展》杂志上,卷133,不。1,3 - 8,2007页。视图:出版商的网站|谷歌学术搜索
27. 答:钻,j·巴德、d . Brockhoff和e . Zitzler”理论:超体积指标最优μ分布和参考点的选择,”学报第十届ACM SIGEVO研讨会的基础遗传算法(FOGA ' 09)2009年1月,页87 - 102。视图:出版商的网站|谷歌学术搜索

版权

版权©2013古时口等。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。