时间依赖网络中非FIFO弧的转化研究

经典最短路算法不能有效地解决时间依赖网络的最短路问题.时间依赖网络中的非FIFO弧的存在是导致经典的最短路算法失效的原因.本文对非FIFO弧的权函数为非连续(存在有限个非连续点)或者离散情况下转化为FIFO弧进行了研究,在允许等待的前提条件下,提出了解决此类问题的方法.建立在经典Dijkstra算法基础上,本文提出了时间依赖网络最短路算法.     

一类多约束最短路问题的模拟退火算法

讨论了一类NP-C问题——多弧权约束最短路问题．通过对搜索操作和参数的合理设置，提出求解多约束最短路问题的模拟退火算法，并通过对实例的计算表明该算法能快速，有效地求出多约束最短路问题的最优解。     

时间依赖有向无环网最小时间路径算法

经典模型及算法可解决固定弧权条件下的最短路问题,然而实际应用中孤权往往是动态的,即弧权依赖时间变化。本文提出一种特殊最短路径算法,即在有向无环网络中最小时间路径算法的一种实现。该算法是一种改进的扩散法,克服了扩散法的一些显著缺点。文中证明了该理论的正确性,最后列举了一个传统算法不能解决的实例,证明了该算算：法的正确性。     

最短路问题的改进算法

通过引入两个数组,从提高算法效率和增强寻路直观性两个方面对无回路网络最短路问题的权矩阵法进行了改进.改进后的算法既能快速的计算从源节点到其目的节点的最短路权又能更直观的找出最短路.最后算法分析和仿真结果表明,改进算法较权矩阵法相比,运算速度有了明显的提高,是计算无回路网络最短路的一种有效算法.     

无回路网络中最短路问题的高效算法

无回路网络是一类重要的网络,给出在无回路网络中求解最短路树形图和任意顶点对间最短路的高效算法。该算法将顶点进行重新编号,结合广度优先探索法,从源顶点出发依次搜索每个顶点的所有出弧,并在弧的头部进行权值变换操作,可以得到最短路树形图和任意顶点对间最短路,算法复杂度分别为O(m)和O(m(n-m1/2))。该算法思想简便、复杂度低、易于操作。 关键词：     

最短路权矩阵法的改进

最短路权矩阵法是通过权矩阵计算来实现Dijkstra算法的一种方法.针对权矩阵法在大型网络应用中的不足,从提高算法效率和增强寻路直观性两个方面对其进行了改进,并给出了新的算法.新算法既能快速计算最短路权又能更直观地找出网络中的最短路,是一种计算最短路的简捷方法.仿真结果和算例表明了新算法的有效性.     

一种基于离散变权网络的动态最短路径快速算法

在离散变权动态网络中,求解最短路径的最优化算法的计算复杂性通常远大于O(n2),不适用于实时的动态交通信息导航系统。提出的动态最短路径快速算法,是在所有的当前点与下一个待选点之间以及待选点与目标点之间的动态弧的权值之和中选择一个最小值,然后把该待选点作为当前点继续选择下一个待选点,如此反复,直到达到目标点为止。该算法所得到的路径是一个次优解,但其执行时间却比寻找最优解算法要小得多,并且所得到的解要优于选择最短距离路径的动态解。实验结果证明这是一种适用于动态交通导航的有效算法。     

一个变权路径最优搜索算法

在经典的最短路问题中,诸弧的权是事先给定并固定不变的。但是在最短路径问题的实际应用中,需要求解两点间的最短运行时间或最小费用,这时各路径的权值根据不同情况可能发生变化。本文针对变权路径问题,提出了一个基于知识层次的变权路径最优搜索算法。实验结果很好地验证了算法的有效性。     

带杂交算子的蚁群算法求解动态网络中的最短路径问题

动态网络与传统的网络模型相比更具有现实意义，具有广泛的应用领域。本文对动态网络模型进行了描述，用实例证明了著名的Dijkstra算法在动态网络中不能有效地求解最短路径问题，提出了一种用带杂交算子的蚁群算法来求解动态网络最短路径问题的新算法。此算法不仅能够以较大的概率找到最优解而且对网络没有任何约束条件，即对离散
散和连续的动态网络模型都有效，而且用实例证明了算法的稳定性。     

无回路网络最短路径的一种新算法

对于求解小规模无回路网络的最短路径这一问题,目前大多数算法都是基于Dijkstra算法或者穷举法的思想,不仅计算量大而且操作复杂。文中在深入分析已有算法的基础上,给出了一种新的简单易行的方法。该算法通过不断消去中间节点和弧以简化图的结构,既能快速地计算出源点到目的节点的最短路径,又能直观地找出最短路。最后算法通过具体实例分析表明,该算法不仅思想简便、易于操作,同时有效地降低了算法复杂度,是计算小规模无回路网络的一种行之有效的算法。     

稳定的最短路径树及其构造算法

构建最短路径树是动态网络研究的重要问题之一。在动态网络中,当边状态发生变化时会引发最短路径树动态的重新构建,反复地计算不仅消耗大量时间,也会导致最短路径树的频繁变化。提出一种稳定的最短路径树构造算法,使得构造的路径树在动态网络上更稳定,即更新最短路径树所需的操作数更少。该算法通过记录频繁变化的不稳定边并尽可能避免将其加入最短路径树中,从而能够高效地减少边变化带来的操作。实验结果表明,与传统的动态最短路径树算法相比,该算法可以得到更稳定的最短路径树,并且更新时间减少了57.24%,结点更新次数降低了43.6%。     

Manhattan空间有障碍的最短路径和3-Steiner树算法

在VLSI设计中,多点互连是物理设计阶段的关键问题之一,而互连的点数等于2或大于2分别对应于Manhattan空间上有障碍时的最短路径问题和最小Steiner树问题,显然前者是后者的基础.连接图是研究最短路径问题的有效工具,已有的典型连接图包括基于轨迹的GC和GT以及基于自由区的GF和GG.工作包括3个方面:设计并分析了在各种连接图上实现动态的点对之间的最短路径查询算法;分析了在各个连接图上构造3-Steiner树的算法,对于已有的GC上的3-Steiner算法,将其Steiner顶点的候选集合规模从O((e+p)2)降低到了O((t+p)2),其中e,t,p分别表示边数、障碍极边数和顶点数;设计了在GG上的3-Steiner树构造算法,其平均情况时间复杂度只有(θ)(t).     

具有树和路约束的平行机排序问题

考虑具有树和路约束的平行机排序问题,其工件集对应于无向图(有向图)的边(弧)集。目标是选取工件集的一个子集使其满足树或路的约束,将其放在平行机上处理,使得机器的最大完工时间(makespan)尽可能地小。通过分析此类问题的组合性质,得到如下结论：在K-树约束下,利用最小支撑K-树的性质可得一个有效多项式时间近似方案;在两固定点间路的约束下,通过构造辅助实例以控制边的权重,分析辅助实例的输出值与目标实例最优值之间的关系,利用最短路的性质可以得到一个2-近似算法;在单源点最短路径树的约束下,根据最短路径树的性质可以得到一个有效多项式时间近似方案;在两固定点间最短路的约束下,在所有的两点间最短路构成的子图基础上,通过构造新的辅助图以控制弧的权重,再利用最短路的性质可以得到一个1.618-近似算法。     

Shortest path based simulated annealing algorithm for dynamic facility layout problem under dynamic business environment

This paper studies a new kind of dynamic multi-stage facility layout problem under dynamic business environment, in which new machines may be added into, or old machines may be removed from the plant. We define this problem first on the basis of unequal area machines and continual presentation of layouts. Compared with nodes and arcs of the flow chart, we convert this problem into a shortest path problem by studying its cost function and machine adding/removing heuristic rules, and the corresponding mathematical model for this problem is established. An auction algorithm is proposed here to solve the shortest path problem. Finally, a shortest path based simulated annealing algorithm is presented to solve the optimization problem. Parameters of the SP based SA algorithm are discussed to improve the performance of the algorithm. Some cases are used to verify the proposed algorithm.     

适用于无向网络的动态Dijkstra算法优化

网络拓扑发生变化时,利用静态Dijkstra算法重新计算最短路径树(SPT)会造成冗余计算。动态Dijkstra算法解决了这个问题,但目前动态算法一般是基于有向网络模型进行的研究。在已有的动态Dijkstra算法基础上,提出适用于无向网络的动态Dijkstra算法。算法主要解决了在无向网络中如何确定待更新节点的问题,对网络中的一条边权值增大、减小的处理方法进行了详细描述,并对已有的算法的筛选机制进行了优化。为了验证算法的正确性,用仿真实验实现了该算法并与静态算法进行性能比较。实验结果表明,新算法更能提高节点更新的时间效率。     

The fuzzy shortest path length and the corresponding shortest path in a network

The fuzzy shortest path (SP) problem aims at providing decision makers with the fuzzy shortest path length (FSPL) and the SP in a network with fuzzy arc lengths. In this paper, each arc length is represented as a triangular fuzzy set and a new algorithm is proposed to deal with the fuzzy SP problem. First, we proposed a heuristic procedure to find the FSPL among all possible paths in a network. It is based on the idea that a crisp number is a minimum number if and only if any other number is larger than or equal to it. It owns a firm theoretic base in fuzzy sets theory and can be implemented effectively. Second, we propose a way to measure the similarity degree between the FSPL and each fuzzy path lengths. The path with the highest similarity degree is the SP. An illustrative example is given to demonstrate our proposed approach.     

Multicriteria Stochastic Shortest Path Problem for Electric Vehicles

This paper formulates the reliable routing of electric vehicles in stochastic networks as a multicriteria shortest path problem with travel time and charging cost components. The reliability term is defined as the probability of finishing the trip without running out of charge. The arc travel times are represented as stochastic variables, and arc energy consumption is modeled as a linear function of arc length and arc travel time. The traveler aims to minimize the generalized cost, formulated as a linear function of travel time and charging cost, subject to a minimum reliability threshold, representing the level of risk a traveler is willing to take in favor of routes with lower cost. We propose a solution algorithm based on generalized dynamic programming and show that the optimal solution may include cycles that visit at least one charging station. The properties of the proposed multicriteria shortest path problem are mathematically proved. The simulation results on randomly-generated networks show that cyclic paths are very rare, and that the generalized cost of travel is a monotone increasing function of minimum reliability threshold.     

Dynamic algorithms for the shortest path routing problem: learning automata-based solutions.

This paper presents the first Learning Automaton-based solution to the dynamic single source shortest path problem. It involves finding the shortest path in a single-source stochastic graph topology where there are continuous probabilistic updates in the edge-weights. The algorithm is significantly more efficient than the existing solutions, and can be used to find the "statistical" shortest path tree in the "average" graph topology. It converges to this solution irrespective of whether there are new changes in edge-weights taking place or not. In such random settings, the proposed learning automata solution converges to the set of shortest paths. On the other hand, the existing algorithms will fail to exhibit such a behavior, and would recalculate the affected shortest paths after each weight-change. The important contribution of the proposed algorithm is that all the edges in a stochastic graph are not probed, and even if they are, they are not all probed equally often. Indeed, the algorithm attempts to almost always probe only those edges that will be included in the shortest path graph, while probing the other edges minimally. This increases the performance of the proposed algorithm. All the algorithms were tested in environments where edge-weights change stochastically, and where the graph topologies undergo multiple simultaneous edge-weight updates. Its superiority in terms of the average number of processed nodes, scanned edges and the time per update operation, when compared with the existing algorithms, was experimentally established. The algorithm can be applicable in domains ranging from ground transportation to aerospace, from civilian applications to military, from spatial database applications to telecommunications networking.