涟漪算法及其在马斯京根模型参数优化中的应用

基于自然界的涟漪现象,提出一种新的启发式智能优化算法——涟漪算法(Ripple Algorithm,RA)。该算法模仿涟漪的结构,搜索过程采用由中心点出发的三层涟漪随机取点搜索,搜索中心点群以当前适应度与全局最优适应度的比较信息为基础;采用涟漪半径函数与收缩函数对涟漪的展开进行控制,相对独立地向解空间最优点收敛。通过测试函数将涟漪算法与粒子群算法、标准遗传算法、引力搜索算法进行对比测试。结果表明:涟漪算法在较低维度与运用广泛的启发式算法相比有很强的竞争力;在马斯京根模型参数优化应用中,涟漪算法寻优能力强、精度高,有很强的实用性。对涟漪半径函数、收缩函数及其他影响涟漪算法优化过程的参数进行讨论,提出了几种改进涟漪算法的思路与方向。

基于涟漪扩散算法的应急疏散路径优化方法研究

针对大型公共场所内人群应急疏散路径优化问题,本文提出一种考虑容量限制的多起点多终点涟漪扩散算法(Capacity Constrained Ripple Spreading Algorithm,CCRSA)。该算法通过动态更新各链接在各时刻的剩余最大通行容量,容量不足时添加涟漪在节点的等待行为,一次性得出多个起点到多个终点的包含等待时间的疏散时间最短路径;并使用路径寻优规则确定优先疏散路径,分配疏散人员数量,实行差异化疏散,提高路网中各链接的利用率。使用大量具有不同节点数量、不同待疏散人数的随机路网与北京颐和园实际路网案例对算法进行测试,并设置了疏散时间、人员实际/理想疏散时间标准差、程序运行时间这3个评价标准。实验结果表明:与传统的应急疏散路径规划算法相比,CCRSA平均可减少13.07%的人群疏散时间,以较高运行效率得到更加满足各疏散人员期望的疏散方案。

基于涟漪扩散算法的航空器滑行路径优化

针对当前机场场面交通拥挤、航班不正常率日益增高的现状,研究了航空器滑行路径优化问题。结合场面运行规则,提出基于真实滑行路径的多目标涟漪扩散算法以优化进离港航班的滑行路径。构建基于冲突解决的场面优化模型,以天津滨海国际机场为例进行20架航班的仿真验证,将通过广播式自动相关监视系统采集的真实路径集合与改进的涟漪扩散算法获得的帕累托最优路径集合进行比较分析。结果表明:与真实路径相比,20架航班的总滑行时间从7107.1s降至6852.1s,减少255s,总完成时间从7153.2s降至6894.1s,减少259.1s,共6架航班的滑行时间得到明显优化。通过案例仿真结果发现,通过改进的涟漪扩散算法得到的帕累托最优滑行路径以符合真实滑行规则为前提,可以有效的优化机场场面滑行路径。

基于涟漪扩散算法的元胞自动机人员疏散模型研究

为探究大型公共场所内应急疏散调控策略的合理性、有效性和安全性,开展了2类场所的应急疏散调控策略的仿真研究,记录疏散时间、疏散拥堵时间和路径拥堵程度作为衡量应急疏散调控措施的指标,建立以多对多涟漪扩散算法为核心的线性元胞自动机模型。结果显示,与原有的疏散路线相比,使用算法规划的应急疏散路径可以缩短疏散时间;与仅仅使用算法规划应急疏散路径相比,考虑单一的路径拥堵情况或路网结构而增加的调控措施可能与疏散初衷相悖;但在使用算法规划路径的基础上,综合考虑路径拥堵情况和路网结构而增设的调控措施,其疏散效果是最好的。研究结果可为应急疏散管理者提供紧急情况下的调控策略,避免疏散过程中出现的拥挤、踩踏等二次事故的发生,进而保障人群的疏散安全。

城市动态灾害环境下多种类多目标路径优化算法

为提高城市应对动态灾害的响应能力,针对动态灾害环境中应急车辆行驶路线的规划问题,考虑路径安全度为乘法权重,车辆行驶路径长度和通行时间为加法权重,首先,提出一种动态环境下可同时计算乘法与加法权重的多种类多目标路径优化问题(MCMPOP)的求解模型;其次,通过改进涟漪扩散算法(RSA)求解MCMPOP;然后,为验证算法的有效性,通过510组仿真试验,对比MCMPOP下非支配排序遗传算法(NSGA)-Ⅱ与改进RSA的计算时间与解的质量;最后,选取“7·20”郑州特大暴雨事件数据进行实例验证。结果表明:与NSGA-Ⅱ相比,改进的RSA可以求解出完整的Pareto最优路径集合,有效保证算法的计算效率和Pareto最优解的质量;可在应急车辆可接受的安全范围内,筛选出行驶路线长度和时间成本较小的Pareto最优路径,为应急车辆提供更多可靠的行驶路线,提高城市的应急管理能力。

动态路网环境下的路径优化算法研究

为解决真实动态路网环境下,静态路径优化(static path optimization,SPO)方法和传统动态路径优化(dynamic path optimization,DPO)方法由于频繁实时优化计算,规划路径过程中容易出现绕路、折返、计算复杂度高等问题,提出基于涟漪扩散算法(ripple-spreading algorithm,RSA)的重启协同进化路径优化(restart co-evolutionary path optimization,RCEPO)方法。将路径优化过程与路网环境的动态变化过程相结合,提升了路径优化效果。仅当路网环境的动态变化超出预测范围时才进行路径的重新优化计算,降低了计算复杂度。实验结果表明:在动态路网环境下,该方法的实际行进轨迹长度和行进时间相较于传统DPO方法分别缩短了17%和12%。有效解决了真实动态路网环境下路径优化问题。并且通过机器狗实验,验证了该方法的实用性和有效性。

求解多目标路径优化问题的涟漪扩散算法

对于多目标路径优化问题(MOPOP),提出了一种求解完整(非部分或近似的)Pareto最优面的涟漪扩散算法(RSA)。新的涟漪扩散算法是在路网中模拟一场涟漪接力赛,通过对到达终点的涟漪进行回溯来确定完整的Pareto前沿。RSA类似于大多数受自然启发的方法,本质上是一个基于微观智体的自下而上的仿真模型。通过定义微观智体的行为,即路网中的节点根据到达的Pareto非占优涟漪产生新的涟漪,涟漪接力赛在宏观层面的表现为输出完整的Pareto前沿。而且,RSA仅需一次涟漪接力赛就可以找到一对多问题中每个MOPOP的完整Pareto前沿。实验结果验证了新的RSA方法的有效性和高效性。

一种快速求解最短路径巡游问题的涟漪扩散算法

针对最短路径巡游问题(SPTP),提出了基于涟漪扩散算法(RSA)特征的SPTP分解方法。RSA通过模拟水面上涟漪传播的现象,在SPTP子问题间建立联系,相较于其他基于问题分解的算法减少了计算冗余度。进一步改进RSA,使其在维持时间复杂度不变的情况下求解多起点—多终点SPTP。在多种拓扑结构的网络中进行对比实验,结果表明,RSA在保证最优性的同时运算效率最高。RSA对于多起点—多终点SPTP的高效求解,可为多种现实问题快速提供解决方案,具有很高的应用价值。

城市空中交通动态空域垂直起降飞行器路径优化

针对目前城市空中交通动态空域航线优化方法难以保证最优性和计算效率上不足,以及对市区与市郊混合运行场景覆盖的缺陷,首先,提出一种适用于市郊和市区运行的城郊结合路网构建方法;其次,基于电动垂直起降飞行器(eVTOL)飞行动力学模型,提出准确的eVTOL功率消耗模型优化飞行路径;最后,基于涟漪扩散算法(RSA)提出适用于动态空域中的动态加权路网(RSA-DWRN)算法。通过构建包含时变气流和障碍区影响的城郊结合路网结构,以优化路径耗电量、飞行时间、计算时间和匹配度为指标,比较RSA-DWRN和传统动态路径优化算法DPO-A*在5种场景下600次实验优化效果。仿真结果表明:RSA-DWRN算法在4类指标下效果最好,且当动态空域环境因素越复杂时,RSA-DWRN表现越优;当空域中存在移动障碍物时,DPO-A*算法无法预测其运动轨迹且需频繁更新路网状态,大量提高了路径规划计算成本,而RSA-DWRN算法在相同情景下与动态环境变化过程协同进化,得到同时保证优化结果和计算效率的最优解。

自由航线规划技术与算法研究

针对未来可能出现的空域容量不足的问题,提出了允许航空器选择最优飞行路线的自由航线新构想。使用一种涟漪扩散算法,并提出该算法在动态空域模型下的动态加权算法,建立了在考虑移动的恶劣天气区、禁飞区、变化的气流等情况下的数学模型,并使用该模型进行了仿真实验,给出了该算法在特定权重下解决自由航线空域中路线优化问题的确定性方法,并通过几种常见方法的比较,说明该方法的有效性。实验结果表明,可以减少民航运输过程中成本过高、环境污染大和安全性等问题的出现。

基于火场预测和多出口决策的协同进化救援路径优化方法

为给深入火场救援的消防员提供最佳救援路线,掌握营救和自救时机,通过改变涟漪规则、动态调整扩散速度、多出口决策设置来改进基于涟漪扩散算法(RSA)协同进化路径优化方法(CEPO)。基于火场预测和多出口决策提出协同进化救援路径优化(CERPO)方法,并以湖北某校教学楼火灾扩散仿真模拟为背景,在不同时间节点情境下规划最佳救援往返路径并比较路径异同,与D算法对比验证CERPO有效性和灵活性。研究结果表明:CERPO能基于火灾预测提前避障规划最佳路径,并在第500 s情境下及时启动多出口决策,规划新的撤离路径;CERPO与传统算法相比可避免绕路,提高消防救援效率,研究结果可为救援路径规划提供参考。

复杂城市环境下无人机路网模型研究

针对复杂城市环境下无人机路径规划问题,采用三维可视图法研究路网模型。首先,在考虑无人机飞行安全裕度的前提下,将城市密集而不规则的障碍物环境进行变形重组,再以不同的水平和竖直间隔对障碍物外表面进行离散化的节点采集,并构建基于三维可视图的复杂城市低空路网模型。其次,为降低无人机之间的潜在冲突和碰撞风险,引入无人机机动保护区的概念,进一步缩减路网规模,优化路网结构。最后,结合无人机性能和平稳飞行的要求,以最大航向角改变量作为主要限制条件,以最小化路径长度为目标,提出改进的涟漪扩散算法进行求解。仿真结果表明:三维可视图中的采点间隔直接决定了路网模型中节点和链接的数量,并对最优路径与规划时间具有显著影响;1000组仿真实验表明,考虑机动保护区后,最短路径的平均长度相较于无机动保护区时增长了不足1%,而计算耗时降低了近70%。仿真实验验证,通过引入无人机机动保护区和航向角改变量的限制,能够有效降低路网规模,提升运算效率,并有利于获得平滑的路径,降低无人机的潜在碰撞风险。

考虑旅客到达准时性的城市值机移动站点动态分布模型

现有城市值机移动服务站点设施分布模型在优化中未考虑旅客到达服务站点的时间不确定性,其优化结果通常与实际情况存在差异,导致无法对提前或延误到达的旅客进行服务。为解决时间不确定性对优化求解造成的不利影响,研究基于旅客准时性概率函数的动态设施分布模型。针对城市值机移动服务站点布局优化问题,构建完整的数学模型,并提出动态设施分布的优化评价指标。采用正态分布型旅客准时性概率函数,用以预估旅客实际到站时间与申报到站时间的差异。基于不同服务时段客源点的位置分布,采用涟漪扩散算法和遗传算法优化服务站点位置并计算所有旅客与站点间的最优路径。基于天津市路网和旅客分布的真实数据,对旅客准时到站和考虑旅客到站时间不确定2种场景进行仿真对比实验。结果表明:旅客到站时间概率模型优化结果优于旅客准时到站模型,动态设施分布评价指标提升4.31%。其中,旅客到达站点的平均路径长度减少0.35%,旅客可接受距离总超出量减少6.26%,站点服务容量总超出量减少4.13%。旅客到站时间概率模型能够充分考虑到站时间不确定性,并基于旅客实际到站时间更好地优化设施布局。基于旅客准时性概率函数的城市值机移动服务站点动态分布模型具有可移植性,可应用于物流服务的动态选址等问题。

考虑火灾动态扩散过程的高层建筑疏散路径研究

为给火灾中高层建筑人员提供最优逃生路径,提高高层人员面对火灾的应急能力,提出基于涟漪扩散算法(RSA)的协同进化路径优化方法(CEPO);借助火灾动力学软件(FDS)模拟北京某高层建筑的火灾扩散情况,采用CEPO方法优化人员疏散路径,并选取传统动态路径优化方法(DPO)验证CEPO方法的有效性。结果表明:CEPO方法总的疏散时间较传统DPO方法缩短约8%, DPO方法无法成功疏散的总人数是CEPO方法未能成功疏散总人数的270%;用CEPO方法能获得实际最优疏散路径,避免出现绕远的不合理现象,有效提高高层建筑的火灾疏散效果。

市区行李值机服务移动站点优化方法

为提高航空运输的服务质量和竞争力,克服传统城市候机楼在服务范围有限、成本高和选址难度高等弊端,提出1种基于市区移动站点(UMS)的航空旅客行李值机服务模式。UMS基于乘客的实时位置分布差异来动态调配移动站点在城市的位置,因此需要解决UMS站点布局优化问题。综合考虑乘客到服务站点的平均路径长度和乘客最大可接受距离等2个重要指标,基于服务站点位置、不同时段的客源分布和站点的最大服务容量等限制因素对2个重要指标进行约束,建立基于路网的UMS布局优化的数学模型。为满足UMS服务模式对优化运算时效性的严格要求,提出1种混合智能优化算法,采用涟漪扩散算法(RSA)求解乘客与UMS站点多对多路径优化问题,采用自适应遗传算法(AGA)高效优化UMS位置分布。以天津城市路网的实际案例与随机生成测试案例对市区移动站点和城市候机楼2种模式的各服务时段的服务质量进行比较。结果显示:在相同站点数量的情况下,乘客到服务站点的平均路径长度比城市候机楼模式减小30.9%,超出乘客的可接受路径长度比城市候机楼模式减少43.7%;UMS位置分布优化使用混合算法(RSA-AGA),其平均计算时间为377 s,比城市候机楼模式所需的平均计算时间减少了41.2%;UMS服务模式在不同站点数量和随机生成测试案例中,各项优化目标均优于城市候机楼模式,更符合乘客的实时需求,验证了UMS运营模式的优越性。

一种评估网络结点和链接重要性的改进介数

为准确评估出网络系统中的重要结点和链接,首先通过分析网络系统抗打击能力的3类情况,基于传统介数定义,给出一种改进的网络结点和链接介数定义,即网络中所有起点-终点(OD)对之间满足给定约束条件的路径通过某个结点或链接的次数;然后提出一种新的涟漪扩散算法(RSA),用于求解网络结点和链接的改进介数;最后分别计算出北京地铁网络中各结点和链接的传统和改进介数值,用于评估其重要性,通过对比传统介数和改进介数计算结果,结果表明:改进介数是一种普适化的定义,而传统介数只是改进介数的一个特例;改进介数能够从更加全面的角度评估网络结点和链接的重要性。

动态灾害环境下多对多物资配送路径规划方法

动态灾害环境下多对多物资配送路径规划问题具有重大的现实意义,它需要在路径规划的同时应对路网环境随时间的变化,并找到不同应急物资储备点、配送点之间的最佳对应关系,同时保证求解的时效性和成功率。目前的静态预案规划方法(SPO)和动态路径规划方法(DPO)难以确保动态灾害环境下求解效果的理论最优性,甚至可能导致部分配送点不能及时获得应急物质的配送。通过对基于涟漪扩散算法(RSA)的协同进化路径优化(CEPO)方法的修改将其扩展到动态灾害环境下多对多问题的求解,实现通过一次离线运算得到动态灾害环境下多对多路径优化问题的理论最优解。并通过实验验证了该方法的可行性和优越性。

求解时间窗口网络中前k条最短路径的方法

在一个时间窗口网络中寻找前k条最短路径是一项具有挑战性的任务.在时间窗口网络中,一个节点可能只有在某些特定的时间窗口内才能通行.现有的研究大都假设运动体可以立即通过可通行节点,或者在暂不可通行节点处等待直到未来时间窗口的开始时刻才通过.本文针对一个更一般的时间窗口情况,其中运动体一旦到达节点,可以选择在节点的时间窗口中的任何离散时刻通过该节点.本文将这样的时间窗口网络称为拓展时间窗口网络,其解空间大小和复杂程度都显著增加.通过模拟水面上的自然涟漪扩散现象,本文提出了一种有效的涟漪扩散算法,用于求解拓展时间窗口网络中的前k条最短路径.除了一对一问题之外,涟漪扩散算法(ripple spreading algorithm,RSA)还扩展到一对多问题.在一对多问题中,需要找到从给定起点到网络中的每个其他节点的所有前k条最短路径.新方法具有最优性的理论保证,其计算复杂度仅为O(k×NATU×NL),其中NL是网络中链接的数量,NATU是涟漪通过链接平均所需的仿真时间单位数.实验结果证明了RSA的有效性.

一种用于求解项目时间管理问题的前k个最优解的新算法

项目管理问题(Project Management Problcm,PMP)是一个多目标优化问题,它通常需要考虑三个相互冲突的优化目标:时间,质量和成本。大多数现存的方法只能为项目管理问题求解近似的Parcto前沿。理论上,如果能够针对每个单目标优化问题找出前k个单目标最优解,则基于所有单目标优化问题的前k个单目标最优解,就可以保证找到离散多目标优化问题(比如PMP)的完整Parcto前沿。因此,求解多目标优化问题的完整Parcto前沿的关键是要设计有效的方法以求解出每个单目标优化问题的前k个单目标最优解。本文针对如何计算项目时间管理问题(Project Time Management Problem,PTMP)的k个最优解,提出了一种涟漪扩散算法,该算法通过模仿自然涟漪扩散现象,从而确定管理项目的前k个最佳方案,使得项目总时间最短。对比实验证明了新方法的有效性。