基于模拟扩散的最短路径新算法

基于模拟水流扩散的自然现象,提出了一种寻求最优路径的新算法,介绍了该算法原理和具体计算过程,验证了该算法的正确性和合理性.     

基于道路堵塞及顾客时间要求的快件配送最优路径选择

针对道路堵塞如节假日导致的临时最短配送路径失效的问题,提出配送网络最优路径选择模型,并设计了求解快递配送网络关键边和最优路径的算法。首先,计算出整个网络的关键边,掌握配送网络特征;其次,考虑顾客时间要求,研究不完全信息(中断无法提前预知,只有到达中断边的起点处才可知)下的最优路径,根据最短路径上各边新的特点,计算出每条边中断后对应的一组备用路径,再选择运输时间小于或等于顾客可等待时间的路径为有效路径,考虑道路堵塞情况,从有效路径中选择最优路径;最后,结合配送网络的实际情况对最优路径进行了算例分析。     

复杂网络在双曲空间的节点动态择优路径研究

本文研究复杂网络双曲嵌套模型.利用改进克林伯格和克莱尔科夫网络拓扑模型的方法,得到了复杂网络在双曲空间的动态择优路径,推广和发展了复杂网络节点间最优路径的算法.     

弹性光网络一类调度问题的一个新模型和算法

采用网络功能虚拟化技术的弹性光网络是一种新型的网络,其数据中心的合理部署,路由的科学规划及频谱的最优分配是一个关键而具有挑战的问题.为了解决这个问题,建立了弹性光网络资源分配和任务调度问题一个新的优化模型,新模型以虚拟网络功能在数据中心部署的负载最均衡,经过数据中心节点的路径最短以及频谱占用最少为目标,可同时使虚拟网络功能在数据中心部署,路径规划和频谱分配方案最优.为有效求解该模型,分别设计了一个经过所选数据中心的最短路径策略,虚拟网络功能在数据中心的部署策略以及频谱分配策略,构造了初始种群的产生方法,设计了新的变异算子,在此基础上,提出了求解模型的一个新的进化算法.最后进行了仿真实验,结果表明,最大频隙号和数据中心VNF部署数目的标准差相比对比算法有明显降低,验证了所建模型和算法的有效性.     

Bellman最优原理在复杂加权网络中的应用研究

针对现有算法及软件计算复杂加权网络介数的局限性,应用Bellman最优原理于复杂加权网络介数计算中,并针对复杂网络动态演化,节点众多,重点,节点间无边连接等特点作了相应修改.依算法实例计算出了复杂加权网络的最短路径长、最短路径和介数,最后经验证算法具有较快的运行速度和较准确的结果.     

(m,n,k)指派问题的最小费用流模型及其算法

构造(m,n,k)指派问题的最小费用流模型,并将基于对偶原理的最小费用流的允许边算法求解该模型,提出求解(m,n,k)指派问题的一种算法.算法直接在其对应的网络中保持互补松弛条件不变,通过调整节点势以扩大允许网络从而寻求增广链并进行流量增广,直至在网络中得到流量为k的最小费用流,此时非O流边对应(m,n,k)指派问题的最优解.给出了(m,n,k)指派问题的最优解及多重最优解的重要性质,数值试验表明算法有效可行.     

检测网络社团结构的基于最短路径的$k$-均值算法

我们考虑复杂网络社团结构的检测问题,即检测出那些具有高于平均密度的边所连接的节点的集合.本文我们利用模拟退火策略来极大化可表示为稳定效益函数的模量(modularity),并结合基于最短路径的$k$-均值迭代过程来对网络进行分区.该算法不仅能检测出社团,而且能够识别出在最短路径度量下,该社团中位于中心位置的节点.社团的最优数目可以在无需任何关于网络结构的先验信息下自动确定.对人工生成网络和真实世界中的网络的成功应用表明了算法的有效性.     

基于模拟退火算法的充电路径规划

主要利用模拟退火算法解决针对无线传感器网络的充电器路径规划问题,并求得网络中每个传感器对应的最小电池容量.该实际问题可抽象为经典旅行商问题(TSP)以及多旅行商问题(MTSP).针对中小规模的TSP问题,以总路程最小为优化目标,利用模拟退火算法搜索全局最优解;针对MTSP问题,以多条路径中最长的路程和每条支路平均路程的...     

两级定位-路径问题模型及变邻域粒子群算法

为满足B2C电子商务中高效率、低成本配送需求,建立了两级定位-路径问题的三下标车流模型,提出了一种求解该问题的变邻域粒子群算法。该算法引入路径重连思想,将粒子群算法中粒子动态更新设计为当前解的邻域搜索、当前解与个体历史最优解之间的路径重连、当前解与种群历史最优解之间的路径重连;在此基础上,提出变邻域搜索策略,动态改变邻域结构以拓展搜索空间。实验结果表明,该算法能有效求解两级定位-路径问题。     

有向循环图寻径控制

有向循环图 G(N ;1 ,s)作为有向双环网的图论模型备受关注 .本文将图的点集分划为几个不交子集 ,找到任意节点对之间路径沿跳长为 1和跳长为 s的边数的上确界 .找到了判断节点对间最短路径的充要条件 ,利用点集的分布特征设计了一个最优寻径算法 .对双环网络的容错路径进行了深入研究 ,给出了容错直径公式 ,提出了一个最优容错路径算法 .     

一种改进的公交网络最优路径算法

通过对公交网络模型进行分析,考虑公交线路票价变化,按照出行时间最短同时保证换乘次数较少的原则,对现有解决公交网络最短路问题的算法进行改进.应用了将公交线路抽象为顶点,建立邻接矩阵的方法处理换乘问题.通过实际问题计算验证了算法的有效性.     

城市交通拥挤问题的探讨

本文探讨了城市交通拥挤问题的解决方法．根据道路的拥挤状况引入畅通度的概念，量化了道路的拥挤程度．在道路的物理距离的基础上加入畅通因素把它转化为一种新的距离，这样使原有寻找最短路径的算法能继续适用．同时本文详细介绍了公路网络中信息的存储方法：Coordinate Storage（COO），Compressed Sparse Row（CSR），Compressed Sparse Column（CSC），Block Sparse Row，以及最短路径的搜索算法：Dijkstra算法和Bellman—ford算法，同时给出了Dijkstra算法步骤和它的最新改进算法．     

模糊最短路的一种算法

模糊最短路问题在许多领域有着广泛的应用,研究这一问题具有重要意义。根据多准则决策理论求非被支配路径集合,求最大效用模糊最短路以及利用模糊数排序方法求模糊最短路是常用的三种研究方法,本文利用OERI排序原理,使网络模糊边长具有线性可加性,对具有三角模糊数边权的网络给出了一种标号算法,该算法简单高效,且易于在计算机上实现,算法的时间复杂度为O(n^2)。     

结点有约束的交通网络最短路径模型

结点有约束的网络是一类特殊的网络，如具有禁止通行限制信息的交通路网等，由于最短路径的求解是有后效性的，经典的Dijkstra算法等不能直接用来求解该问题，本文提出了一种结点有约束的交通网络最短路径建模方法，该方法所建模型为一般网络模型，可用任一传统高效的算法求其最短路径，从根本上降低了问题的复杂性，为很好地解决交通、通信等领域中的此类问题提供了有益的方法。     

A heuristic approach to hard constrained shortest path problems

Constrained shortest path problems have many applications in areas like network routing, investments planning and project evaluation as well as in some classical combinatorial problems with high duality gaps where even obtaining feasible solutions is a difficult task in general.We present in this paper a systematic method for obtaining good feasible solutions to hard (doubly constrained) shortest path problems. The algorithm is based essentially on the concept of efficient solutions which can be obtained via parametric shortest path calculations. The computational results obtained show that the approach proposed here leads to optimal or very good near optimal solutions for all the problems studied.From a theoretical point of view, the most important contribution of the paper is the statement of a pseudopolynomial algorithm for generating the efficient solutions and, more generally, for solving the parametric shortest path problem.     

基于改进蚁群算法的最短路径问题研究及应用

蚁群系统作为一种蚁群算法是解决最短路径问题的一种行之有效的方法.然而,它自身也存在着一些缺陷,主要针对基本蚁群算法易陷入局部最优这一缺陷对其进行改进,集中体现在初始信息素求解和信息素更新这两方面.为了进一步了解改进蚁群算法的优点,进行了实验仿真:将改进的蚁群算法应用子模拟医疗救护GIS中,利用GIS的网络分析功能对城市道路网络的最短路径选择算法进行了深入地探讨研究,并以山西省太原市的交通路线作为实例进行研究.计算机仿真结果表明,改进的蚁群算法在解决最短路径问题时较基本蚁群算法的性能好,它具有一定的理论参考价值和现实意义.     

A fuzzy shortest path with the highest reliability

This paper concentrates on a shortest path problem on a network where arc lengths (costs) are not deterministic numbers, but imprecise ones. Here, costs of the shortest path problem are fuzzy intervals with increasing membership functions, whereas the membership function of the total cost of the shortest path is a fuzzy interval with a decreasing linear membership function. By the max–min criterion suggested in [R.E. Bellman, L.A. Zade, Decision-making in a fuzzy environment, Management Science 17B (1970) 141–164], the fuzzy shortest path problem can be treated as a mixed integer nonlinear programming problem. We show that this problem can be simplified into a bi-level programming problem that is very solvable. Here, we propose an efficient algorithm, based on the parametric shortest path problem for solving the bi-level programming problem. An illustrative example is given to demonstrate our proposed algorithm.     

Shortest paths in networks with vector weights

For a directed network in which vector weights are assigned to arcs, the Pareto analog to the shortest path problem is analyzed. An algorithm is presented for obtaining all Pareto shortest paths from a specified node to every other node.