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

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

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

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

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

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

基于下一跳可用带宽和链路利用率的路径选择算法

路径选择算法的优劣直接影响着网络性能。基于最大可用带宽选路的ESG算法在下一跳链路带宽不同时,存在次优选路决策问题。本文提出一种ESG的改进算法——IESG,该算法将下一跳链路的可用带宽和链路利用率统一考虑,生成反映下一跳链路传输能力的链路传输能力因子,以其作为路径选择决策的依据。仿真结果表明,IESG算法克服ESG算法的不足,具有较高的选路成功概率且执行复杂度相当。

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

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

求解必经点k条最优路径问题的粒子群优化算法

提出了一种解决指定必经点k 条最优路径问题的粒子群优化算法。算法以k 条最优路径集合作为优化目标,将粒子种群划分为k 个子种群,通过各子种群的局部搜索和子种群间的相互协作,使种群在搜索过程中易于找到k 条最优路径。为了提高含有多必经节点的初始生成路径的多样性,设计了基于弹性拉伸原理的种群初始化方法。在随机生成的26 个节点65 条边,50 个节点262 条边和80 个节点410 条边的拓扑图中,分别选取不同的源节点和目的节点,以及必经节点对算法进行了测试。数值实验结果表明,提出的算法在求解网络规模比较大、必经点数比较多的无环k 条最优路径问题中具有比较好的性能。

基于约束聚类和粒子群算法的多路径规划

大型物流中心物流管理信息系统在进行物流配送中,必须进行多配送中心车辆路径问题研究,用尽可能少的车辆,完成货物的配送,并使得行驶总里程最小。业界已经针对多中心路径规划中k条最短路径难问题进行了深入的研究,通过采用传统的聚类算法已经能够实现多路径规划问题,但是在现实多配送中心车辆路径规划中,运输工具的运输能力和用户的需求存在特定限制,本文在聚类算法基础上引入约束机制,将多配送中心问题通过聚类算法降维为单配送中心问题,并在此基础上引入粒子群算法求解单配送中心多路径规划的最优解。通过实验验证该方法的优越性,他比传统粒子群算法的收敛速度至少提升了n(配送中心个数)倍,为路径规划提出了新的解决思路。

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

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

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

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

T-aware:一种基于AS拓扑的可用带宽预测算法

为提高端到端可用带宽的预测精度,提出了一种基于自治域(AS)拓扑的可用带宽预测算法T-aware.该算法结合网络的AS拓扑信息,为符合超度量空间的节点和不符合超度量空间的节点分别选择测量点,对2类节点分别进行预测.在HP scalable sensing service数据集上的实验结果表明,T-aware的预测精度与PathGuru算法相比可提高10%以上.

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

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

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

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

面向NFV中间盒依赖关系的有效路由策略

在软件定义网络中,通过网络功能虚拟化(network function virtualization,NFV)可以有效地优化中间盒的部署以及数据包的路由,但是受中间盒之间存在的依赖关系约束,不适当的部署策略会为运营商带来额外的路由成本,降低资源利用率。为此,文章建立混合整数线性规划模型,提出一种服务链感知精准算法用于计算受中间盒依赖关系以及链路带宽约束的最小路由成本。该算法首先基于中间盒的依赖关系构造有向层级图,然后从该层级图中的源点到终点之间的最短路径中筛选出满足带宽要求的链路作为数据包的路由。仿真实验结果表明,该算法可以快速获取最优解,具有较好的应用前景。