国际航线网络中K条最短路径算法改进与仿真

K条最短路径(KSP)问题是国际航线网络实际路径优化问题。通过对航线网络特征与K条最短路径算法的分析,研究了解决KSP问题的典型Yen算法。针对Yen算法求解候选路径占用大量运算时间的问题,提出一种改进Yen算法。改进Yen算法通过借助A*算法的启发式策略,减少了产生候选航线路径的时间,从而提高了算法的搜索效率并减小了算法搜索的规模。通过对国际航线网络实例的仿真,实验结果表明改进Yen算法能够快速求解国际航线网络中的KSP问题;同时,与Yen算法相比,运算效率提升了75.19%以上,能够为航线路径优化提供决策支持。

第k条最大可用带宽路径算法

该文提出了无环路的第k条最大可用带宽路径算法 .由于具有凹性的带宽和具有加性的代价存在本质区别 ,第k条最大可用带宽路径算法不能通过简单修改第k条最短路径算法得到 .该文结合两个新定义的路径操作和修改的二重扫除算法完成第k条最大可用带宽路径算法 ,并证明其正确性、无环性和具有多项式复杂性 ,最后给出实例并讨论算法实际应用 .该文解决了基于带宽度量的路由算法中一类很基本的问题 ;因算法采用能反映网络实时特性的可用带宽作为路由度量 ,能直接保证网络带宽资源的最优利用 .

复杂网络中最短K条路径问题的求解算法研究

以时间代价作为目标函数,针对复杂网络的优化问题进行研究,给出了目标评价函数模型的建立过程,提出了基于改进的A*算法求解复杂网络中最短K条路径问题的算法,并以城市交通为例,对算法进行了验证。实验结果表明所提出的算法可适用于一般多重图中最短K条路径问题的快速求解,具有广泛的应用价值。

求解k条最优路径问题的遗传算法

文章提出的任意两点间k条最优路径问题的遗传算法,采用节点的自然路径作为染色体编码,根据路径节点的连接实施染色体的交叉操作,将节点路径块作为染色体的变异基因块实施变异操作。算法结构简明,收敛速度快,可应用于求解大规模网络中的多条最优路径问题。

K条路的两个问题

关于寻找有向连通图G=(V,E)的最小最大的k条弧不交路的问题是NP-完备的.研究这个问题的推广———有容量限制的k条路问题:①寻找k条路,使得k条路的费用之和尽可能小;②寻找k条路,使得k条路中最长的路的费用尽可能小.给出了问题①的一个最优算法,其复杂度为O(k|V|2),同时证明了该算法对于问题是k-近似的.

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

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

K(≤3)条渐次短路径搜索算法的研究

Dijkstra算法是经典的最短路径搜索算法。该文在Dijkstra算法的基础上,提出了在单限制多权值的条件下k(≤3)条渐次短路径的搜索算法。算法的实例表明,该算法切实有效。

灾害条件下多层次应急疏散模型的构建方法研究

人们每天都要面对各种造成严重财产和人身安全损失的重大灾害,如何建立灾害条件下中国人口高密度大范围的应急疏散模型,具有重大的意义。该文基于我国灾害条件下高密度人口的集体疏散模式,按照灾害区域的具体情况和人口分布,以道路实时速度和路面损毁程度所决定的道路阻抗性作为评判道路疏散能力的依据,构建从危险区域的多集结点到安全区域的多安置点的多层次应急疏散模型,确定集体疏散人员的疏散路径、人数和车辆,实现在最短的时间内的受灾群众整体最优疏散,并以山东省德州发生地震作为实验区,采用Google Map API和C#搭建多层次应急疏散平台,验证了多层次应急疏散模型的可行性。

一种应用于路由规划的实用无环K路算法

在对已有第K条最短路算法进行分析和比较的基础上提出了一种新的无环K路算法。该算法基于最短路计算，具有复杂度较低、收敛快以及无环等特点，在路由规划中的应用以及仿真分析都证明本算法是有效、实用的。

基于扩展KMCSP的国际航线运价搜索模型及算法

为提升国际航线运价搜索效率,建立一个国际航线运价搜索的EKMCSP模型,该模型基于K条多约束最短路径(KMCSP)问题并进行扩展。国际航线运价搜索的各种因素被表示为EKMCSP模型中的变量、约束和目标;针对建立的国际航线运价搜索EKMCSP模型提出A*Level算法,结合国际航线运价搜索的特点,采用有限层搜索的思想,提高搜索效率并减小搜索规模。大量实验结果表明,该算法可实现国际航线运价搜索的EKMCSP问题的快速求解,且解集具有较高的正确率。

基于Dijkstra算法的两点间多目标最优路径问题建模和优化

配送在物流系统中扮演着重要的角色,是物流顺利实施的根本保障。在信息技术高速发展的今天,设计高效实用的物流配送算法为物流配送系统实现合理路径运输,从而节约运输时间、减少运输费用,提高现代物流系统效率和降低成本非常必要。借鉴已有的数学模型,建立城市配送中心两点间的多目标最优路径问题模型,并在此基础上借助运筹学路网中的最短路径算法和前k条简单路径的算法对此模型给出三种算法。最后选择一种较为理想的算法利用C++语言编写了程序,在DevC++编译器上进行了编译和调试后,程序在三个目标权值下成功地给出了九条路径,并把这九条路径的各个目标权值列成表格以备分析。程序给出了较为理想的结果。

PVC塑窗密封条的选用

本文通过PVC塑窗密封条的作用及主要性能、密封条技术要求等的论述,指出了密封条的注意事项及质量检查要点。

城市公交查询系统的研究与设计

给出了城市公交查询系统的空间数据结构。在Dijkstra算法的基础上,借助人工智能中状态空间搜索和动态截枝的思想,提出了状态空间搜索求第K最短路径的智能搜索算法。该算法能对所查询的交通路线与乘车方案等用电子地图的形式给予显示,并更换不同城市的地图。测试表明,该系统具有速度快、多媒体显示、维护方便、通用性强等特点。

基于综合运输网络的客流分配优化模型与算法

以综合运输网络条件下的客流分配为研究对象,提出更适合表现旅客出行需求和各种运输方式相互竞争关系的运输细分方式,采用可量化表征综合运输网络当前客流状态的区间饱和度和径路饱和熵,并结合旅客出行广义费用函数,构造旅客出行阻抗函数,给出以综合运输网络中旅客出行总阻抗最小为目标的客流分配优化模型。基于k条最短路算法和混沌优化算法,在径路选择时考虑当前综合运输网络的旅客出行阻抗因素,设计客流分配迭代优化的动态求解算法。算例表明,利用给出的模型和算法能够得到可行和更为细分的综合运输网络客流分配方案。

多指标综合评价的负载均衡路由策略研究

如何在规模庞大的数据中心网络内部进行负载均衡,实现网络资源的优化利用,是个亟待解决的问题.OpenFlow技术提供了一种可编程操作的流量控制方法,已成为近期解决负载均衡问题的热门关键技术.针对数据中心常见的Fat-tree网络拓扑,就数据流在OpenFlow网络中的路径设计问题,利用OpenFlow网络控制器集中控制的优势,在控制器上设计并实现了一种动态负载均衡路由策略.该策略首先选出源节点与目的节点间的前K条最短路径,然后根据获取的网络链路实时状态信息,对选出的前K条路径进行多指标综合评价,并从中选出数据流的最优转发路径.最后,采用Floodlight控制器和Mininet仿真平台,对提出的负载均衡路由策略进行可行性验证和性能验证.结果表明,该策略有效缓解了网络阻塞,提高了链路利用率.

船舶舱室噪声传递路径分析的声振熵赋权图法

针对传统的矢量迭加法难以满足噪声分布具有中高频域特点的船舶声学分析要求,将船舶噪声分析统计能量系统比拟为热力学系统,引入声振温度和声振熵的概念,并结合图论提出识别船舶舱室噪声传递路径的声振熵赋权图法.将噪声传递路径分析问题转化为求解声振熵赋权图最短路径问题,混合熵增率累计最大的路径即为能量传递的主路径.通过对比算例和超大型油轮上层建筑舱室空气噪声能量传递路径分析算例,验证了船舶舱室噪声传递路径的声振熵赋权图法的有效性,初步揭示了超大型船舶舱室噪声分布与传播机理,为超大型油轮减振与声学设计决策及后续优化提供指导.

一种时延约束最小代价路由选择算法

使用禁忌搜索方法寻找最优路径,将最小时延路径作为初始解,在满足时延约束的情况下根据禁忌搜索规则求解代价最小的路径。仿真实验证明DCLC_TSR算法具有代价性能良好、可靠性高、耗时少、收敛速度快的优越特点。

基于移动实时位置信令数据的轨道交通换乘行为分析

介绍了上海轨道交通清分规则。在现有上海轨道交通K条最短路径的清分算法基础上,融合移动实时位置信令(OIDD)数据,对换乘行为中的主要换乘路径选择比例进行精细化设置,并对次要换乘路径的换乘比例算法作出补充。通过对乘客行为的分析和应用,实现了对现有上海轨道交通清分规则中换乘路径比例的精细化计算。

棉花物流运输路径建模及仿真应用研究

分析我国棉花物流运输现状及问题,以降低运输成本为目标,综合考虑发货点、收货点、运输方式、油费、路桥费、运输时间等因素,建立棉花运输路径模型,运用前k条最短路径算法求解最优路径。

一种基于拓扑分析的网络攻击流量分流和阻断方法

现有的针对流量型网络攻击的防御方法主要是在监测点发现异常后对流量进行阻断,仅能降低所在路径的攻击流量但无法降低整个网络的负载。针对这种情况,文章提出一种基于拓扑分析的网络攻击流量分流和阻断方法,基于拓扑分析从网络全局角度出发实现攻击流量分流阻断。该方法基于多种发现策略获取网络拓扑,在网络攻击阶段采用基于K条最短路径分流的方法实现网络流量分流;同时基于主机行为特征对网络攻击进行溯源,并采用基于流表的报文实时过滤方案进行阻断。实验结果表明,该方法具有系统开销小、鲁棒性好、阻断效率高的特点,实用价值较强。