一种基于Dijkstra的实用多路径求解算法

针对传统的多路径求解算法求解的始终是起点到终点的最短路径,搜索区域上一直没有什么变化,效率较低的问题,提出了一种基于Dijkstra的实用多路径搜索算法,只需求解起点到原最短路径上中间节点的最短路径,最后再补充相关路段,便可以得到权值与最短路径相接近的前几条次短路径。最后结合郑州市某区域的交通网络图进行了实例仿真,结果表明该算法是行之有效的。

一个求解次短和渐次短路径的实用算法

求解第 k 短路径问题在决策支持系统和咨询系统中具有广泛的用途,本文基于 Dijkstra 算法,给出了一个求解次短路径和渐次短路径的算法,并且分析了算法的时间复杂度和空间复杂度。

基于矩阵运算K短路径算法

最短路问题是复杂网络中的经典问题,其求解算法层出不穷,各有优缺点。经典的算法包括Dijkstra算法、Ford算法和Floyd算法等,只能求解两节点间的一条最短路径。在实际生活中,还需要在大型网络中限定一些前提条件求解两点间次短、渐次短的路径问题。为此,提出了一种对距离矩阵和路径矩阵的迭代、替换算法,即从一个节点出发寻找其后继节点,同时通过比较路径长短得到两点间最短路径、次短路径和渐次短路径,并不断重复、替换。为验证所提算法的有效性,以一个大型网络的应用作为实例,应用Matlab对所提算法进行了仿真实验验证。仿真结果表明,所提算法能够在复杂大规模随机网络中满足求解指定顶点间最短、次短和渐次短路径的需要,具有较好的有效性和适用性。

基于最短路径的网络可靠性评估算法

介绍了通信网络可靠性算法的研究现状,分析了各种可靠性算法的优点和不足。从网络拓扑结构和可靠性定义出发,研究了网络可靠性影响因素,建立了可靠性评估模型,对算法思想进行了描述。在网络最短路径和次短路径的基础上,提出了端到端的网络可靠性评估算法,根据网络中的薄弱节点,求得了整个网络可靠性值的近似值。以实例模拟计算,说明其算法的计算过程,验证了算法的准确性。

轨道交通系统票务清分算法

提出了一个实现轨道交通系统票务清分的算法。给出了清分的精确算法 ,在论证精确算法的不可实现性的基础上 ,演变出切实可行的票务清分的近似算法 。

基于社会化库存的多回程物流配送问题的拉格朗日松弛算法

社会化库存是同城配送快速发展所呈现出的一种新特征。在社会化库存模式下,顾客可从多个同城商店订购货物,其物流配送服务需要通过配送车辆在商店与顾客间的多次往返而实现,这是一类特殊的多回程混合取送物流配送问题。针对该问题,建立了混合整数规划模型及改进的拉格朗日松弛算法;考虑到传统拉格朗日松弛算法存在无法有效提供上界的缺陷,引入了基于次短路的可行解生成思想,实现了问题上界的有效求解。仿真算例表明,所提算法能够取得优于CPLEX求解器的计算效率。

基于Kruskal和Floyd算法的馈线新增负荷接入方法

规划人员一般采用简单的方法对配电网网架进行扩展,以应对配电网有新增负荷节点出现的情况,这可能导致电压质量达不到要求或配电网运行不经济等问题。提出一种基于Kruskal和Floyd算法配电网新增负荷的接入方法,该方法计及了新增负荷前配电系统的无功配置情况。通过Kruskal算法得到配电网网架初始结构,以满足供电半径为目标,运用Floyd算法得到新增负荷接入线路的次短路径,当电压不满足要求时,采用无功二次精确矩法确定无功补偿点的位置和补偿容量,以保证系统的电压质量,并进一步降低线损。对算例进行数字仿真,仿真结果验证了该方法的可行性和实用性。