基于A~*算法的机场滑行路径优化研究

研究机场场面航班的滑行路径分配和滑行冲突问题。针对目前滑行效率制约机场调度。滑行冲突影响飞行安全的状态,提出将安全间隔、滑行规则和冲突避免限制规则作为约束条件建立了滑行路径优化模型。采用了A*算法给出了问题的优化,在保证滑行道调度零冲突的前提下,缩小航班的总滑行时间,提高了滑行效率。以重庆江北国际机场为例,与管制员依据机场细则得到的路径相比,结果表明提出的滑行道调度模型和优化方法是可行的,在实现较优的滑行路径的基础上能智能的发现冲突、解决冲突,可为繁忙机场的机场调度提供了决策支持。     

面向场面滑行的机场关键资源蚁群调度模型*

每一架飞机场面滑行时间的长短和飞机总体滑行时间的均衡性反应了机场调度的合理性。跑道和停机位的分配直接决定了飞机的滑行时间。根据不同航班占用停机位的时间不同,将航班的停机位分配约束关系表示成图的权值0-1。充分考虑跑道容量等约束条件,对航班进行跑道初始化分配。基于停机位类型、航班类型、经计算得出的图的权值和跑道分配结果,运用蚁群算法,以最少数量的航班分配到远停机位和飞机总体滑行时间的均衡性为目标函数,对航班进行停机位分配。然后根据停机位分配结果,对跑道分配进行调整,反复迭代求出最优结果,并对枢纽机场进行调度仿真,验证了算法的合理性,可作为机场调度的参考。     

基于改进蚁群协同算法的枢纽机场场面滑行道优化调度模型

滑行道连接停机位和跑道,是机场场面调度的重要关键环节。基于飞机滑行时的冲突约束和跑道资源的动态分配,采用改进蚁群协同算法与滑动窗口控制相结合的方法,对滑行道进行优化调度。在保证滑行道零冲突、兼顾单个航班滑行时间的前提下,缩小机场进出港航班总滑行时间。对国内某枢纽机场的滑行道调度仿真实验表明,所提出的方法和模型具有明显的优势,可为枢纽机场的场面滑行调度提供决策支持。     

基于免疫遗传算法的停机位动态再分配优化

针对兼顾旅客转机行走距离、航班场面滑行距离和停机位使用效率的多目标停机位分配的问题,以最小化航班停机位分配的扰动性为优化目标,建立停机位动态再分配混合整数规划模型.提出基于航班序列的自然数编码方案,设计改进的免疫遗传求解算法,保证个体在遗传操作中的可行性.将免疫算法中个体密度的概念引入对个体适应度值的评价过程,以保持种群的多样性,避免算法过早收敛.实例仿真结果表明,所提出的优化方法能够有效降低延误航班对停机位预分配计划造成的影响.     

基于蚁群协同算法的图权值停机位分配模型

停机位分配关系到整个机场系统的运行,是机场地面作业的核心部分。根据不同航班占用停机位的时间冲突约束,将航班之间的冲突关系表示成图的权值0-1,基于停机位、航班类型的匹配约束和得到的图的权值,运用蚁群协调算法,在保证不存在停机位分配冲突约束的前提下,以最少数量航班被分配到远停机位和旅客到停机位总行走时间最小为目标函数,对航班进行停机位分配。对枢纽机场进行停机位分配,并与遗传算法在停机位分配上的应用做比较,表明蚁群协调算法在停机位分配上的应用从运行时间和实验结果都明显好于遗传算法,验证了算法的合理性,这一算法可作为机场停机位分配的参考。     

基于改进A^*算法的机场场面滑行路径优化

为了缓解机场场面交通拥挤状况,提高空侧交通运行效率和安全性,以优化进离场航班的滑行路径为目标,通过分析机场场面滑行路径优化问题,构建了机场场面滑行路径优化模型,并提出基于变步长的滑动时间窗方法和A*算法相结合的模型求解算法。以北京首都国际机场为例进行算例分析,与未考虑冲突的路径优化方案相比较,上述方法得到的总滑行时间节省121秒,通过算法实现对滑行冲突的智能识别与解脱,可为繁忙机场的调度工作提供了决策支持。     

基于松弛算法的停机位分配优化方法

针对机场近机位资源紧缺及实际航班到离港时间偏离计划时间对停机位分配所造成的扰动，提出了在同机位相邻航班间加入缓冲时间的停机位分配调度方法。首先，建立了以机位空闲时间、远机位占用时间最小为目标的鲁棒性停机位分配模型；然后，设计了一种基于双目标的拉格朗日松弛优化算法，并使用次梯度算法求解拉格朗日松弛算法中的对偶问题。基于国内某枢纽机场运行数据的仿真结果表明，所提方法的优化方案和原始机位分配方案相比，机位使用量和机位空闲时间分别降低了15.79%、7.56%，机位占用率提高了18.72%，并且冲突率降低到3.57%，达到了有效提高停机位利用率与鲁棒性的目的。     

基于动态优先级的机场滑行道调度优化算法

为提高机场航班的地面运行效率,针对航班滑行道调度问题,提出一种动态调整航班优先级序列的滑行道调度优化策略。为实现该策略,对遗传算法进行改进,采用双链染色体编码的方式,并行优化航班的滑行路径和优先级序列。通过设定两个适应度函数,利用改进的遗传算法确定各航班的滑行路径,根据滑行路径的变化动态调整航班优先级序列,在此基础上由冲突解脱算法得到具体的调度计划。实验结果表明,该算法有效解决了航班间的冲突问题,能得到最优的调度滑行路径和优先级序列。     

多蚁群协同进化的滑行道调度优化

针对当前机场滑行道调度效率较低的问题,提出一种基于协同进化的多蚁群算法。利用蚁群算法在解决复杂的组合优化问题方面的显著优势,在种群内部搜索滑行时间短且没有冲突的路径,在种群间利用蚁群算法良好的协同能力同时进行多个航班的调度,解决滑行的路径搜索问题,实现调度顺序的优化调整。冲突解决是解决滑行道调度问题的关键,采用基于两段锁的思想解决冲突。利用公共数据集对该算法进行验证,实验结果表明了该算法的有效性。     

基于多目标优化禁忌搜索算法的停机位分配方法研究

针对机位资源分配不均给机场运行多方带来的公平性问题，提出多目标优化的停机位分配方法。建立以旅客通行距离、飞机滑行距离和远机位使用次数最小为多目标优化分配模型。分析航班属性设置分配优先级表。设计一种基于pareto最优的多目标优化禁忌搜索算法，使用pareto最优策略对解集进行筛选。在机场实际分配方案的基础上进行仿真实验,旅客通行距离和飞机滑行距离分别缩短18%和5%，机位资源的使用数量减少20%，航班靠桥率提高到93%，多目标优化禁忌搜索算法比遗传算法更优。     

基于背压路由算法的离港飞机滑行路径优化

针对现有优化算法仅从最短路径或最小滑行时间的角度出发,忽略了航空公司满意度和滑行道负载率对滑行道调度影响的问题,提出了基于背压路由的离港滑行路径优化算法．算法首先将离港滑行路径优化问题等价转化为网络拓扑结构中的路由搜索问题,然后利用背压路由算法求解具有最大航空满意度和最小滑行道负载率的滑行路径．对国内某枢纽机场实际运行数据的仿真结果表明,运用该算法获得的滑行路径在保证跑道及滑行道效用的同时,能够有效减少飞机滑行时间,改善机场拥塞问题,缓解机场容量与需求的矛盾,提高机场运行效率,为离港航班滑行路径优化提供了新的研究思路．     

紧致密集Auto Store系统AGV路径规划与避碰策略

针对新兴紧致密集仓储系统Auto Store具有短途挪库作业多、顶层AGV冲突多、货架结构性角落多等特点,提出一种离线-在线两阶段AGV优化调度方法。离线路径规划阶段,给出改进双层A*算法,在拓扑图建模划分搜索区域基础上,上层通过考虑冲突的启发式函数和考虑转弯的代价函数寻求可行区域,下层在此区域基础上搜索最优路径。在线AGV运行阶段,针对两AGV冲突,扩充了回退策略和路线重规划策略;针对多AGV冲突,提出一种基于贪心算法的区域避碰决策策略,以控制问题规模。最后利用Flexsim仿真进行了验证,结果表明,较于标准A*算法,改进A*算法能在保证搜索效率的同时获得冲突较少的初始路径方案;较于优先级策略,区域避碰策略能减少AGV等待时间;将二者相结合,能缩短整体作业完成时间,且随着AGV数量和作业任务增多,优势越明显。     

基于差分进化算法的飞行器航迹规划

提出了一种基于差分进化算法的高超声速飞行器航迹规划方法并进行了仿真验证。建立威胁模型,将威胁模型投影到赤道平面内,利用一个有限项的多项式函数来逼近实际航迹在赤道平面内的投影,使航迹规划问题简化为在一个多项式系数空间中的搜索寻优问题。利用差分进化算法,鉴于高超声速飞行器特点,规划得到赤道平面内的航迹,根据对应关系,最后得到实际航迹。仿真结果表明,生成的航迹自动避开了威胁。     

基于信息物理系统的多分拣移动机器人调度策略

研究基于信息物理系统建模的多分拣移动机器人(multi-SMR)调度策略.首先,在基于实际应用场景的拓扑地图建模中加入新的路径弧时间损耗指标,以实现对货物不均匀比例和多机器人拥堵状态的精确估计;其次,提出一种改进的启发式路径规划算法,并在路径评估过程中增加目的地距离和时间损耗指标;最后,将完整的调度过程以分层式结构部署在信息物理系统模型中,包括控制层的时间损耗指标更新、交通管制监测,以及物理层的分布式路径规划和机器人状态更新.仿真实验结果表明,改进的调度策略可以进一步提升系统分拣效率,降低计算成本,有效解决机器人拥堵和安全问题.     

多Agent的航空器滑行策略优化

快速发展的民航事业导致很多机场容量不足。为缓解大型机场交通拥堵的现状,研究了航空器滑行策略优化问题。滑行路径优化是指在特定的时间段内,根据机场资源信息和地面运行管理系统对进离场航空器在跑道和停机位之间的距离进行优化管理。通过深入剖析机场地面的网络结构,综合考虑滑行冲突、地面运行规则等因素,提出了多Agent滑行策略优化方法,该方法提升了机场资源利用率;基于地面网络链路结构的概念,建立了航空器滑行策略优化模型;结合多Agent的基本理论,设计了跑道出口选择概率函数和多Agent系统滑行路径优化结构,以寻求航空器的最优滑行路径。以国内某大型机场的实际情况为研究背景进行了航空器滑行策略实验,结果表明,与以往的算法相比,多Agent滑行策略优化方法的效果更为显著。设置跑道口的速度和同一交叉口航空器的最小间隔距离,通过对跑道出口的选择和Agent间的交互协商,航空器能够对原滑行路径进行有效调整,并缩短其在机场场面上的滑行时间。与最短路径算法相比,多Agent滑行策略方法在航空器的总滑行距离、航空器在滑行道上的密度以及平均等待时间方面的优化效果更好,且其对滑行道资源的分配更合理。其中,航空器在节点处的平均等待时间减少了8.26%。所提策略可有效缓解机场交通拥堵的现状,提高场面运行效率,对减少航空器延误和保障机场的运营安全具有重要意义。     

基于改进遗传算法的无人机路径规划

针对传统遗传算法收敛速度慢、容易陷入局部最优、规划路径不够平滑、代价高等问题,提出了一种基于改进遗传算法的无人机（UAV）路径规划方法,该算法对遗传算法的选择算子、交叉算子和变异算子进行改进,从而规划出平滑、可飞的路径。首先,建立适合UAV田间信息获取的环境模型,并考虑UAV的目标函数与约束条件以建立适合本场景的更为复杂、精确的数学模型;然后,提出了混合无重串选择算子、非对称映射交叉算子和启发式多次变异算子,寻找最优路径以及扩大种群搜索范围;最后,采用三次B样条曲线对规划出的路径进行平滑,得到平滑的飞行路径,并且减少了算法的计算时间。实验结果表明,与传统遗传算法相比,所提算法的代价值降低了68%,收敛迭代次数减少了67%;相较蚁群优化（ACO）算法,其代价值降低了55%,收敛迭代次数减少了58%。通过大量对比实验得出,当交叉率的值为（1/染色体长度）时,算法的收敛效果最好。在不同环境下进行算法性能测试,结果表明所提算法具有很好的环境适应性,适合于复杂环境下的路径规划。     

仓储物流机器人批量拣选路径规划仿真

针对仓储物流机器人在拣选作业过程中难以进行高效实时的路径规划问题,提出一种有效的解决方法。首先,根据拣选作业的需要建立一个灵活的仓储空间模型并对拣选作业任务流程进行描述。其次,根据批量拣选作业任务的特点,建立以路径总长度最小为优化目标的旅行商问题的数学模型。再次,提出改进的自适应遗传算法解决旅行商问题。最后,在考虑路径转折角代价的前提条件下,提出改进的A*算法,并与改进的自适应遗传算法相结合实现批量拣选的路径规划。仿真结果表明,该方法具有较快的收敛速度、较小的平均路径长度以及较少的算法运行时间,能很好地适应机器人批量拣选路径规划的要求。      

大规模AGV的改进时间窗路径规划

在机器人路径规划中,A*算法搜索路径时存在大量冗余节点,随着任务量增加,其搜索效率也会急剧下降,因此无法适应大规模任务下的路径规划。为此提出一种改进时间窗的有界次优A*算法用于求解大规模自动导引车（automatic guided vehicle,AGV）路径规划问题。算法使用时间启发式,并在搜索过程中采用时空搜索,规划无冲突的最优或次优路径。算法主要进行了三处改进：采用时间启发式,缩短了路径时间;采用动态时间窗算法,避免多次路径规划;优化了聚焦搜索算子,降低负反馈。通过MATLAB实验结果证明改进后的算法在进行多机器人路径规划时,能快速有效地规划出无冲突的平滑次优路径,搜索效率高,稳定性强。