应急模糊网络系统最大满意度路径的选取

讨论给定限制期条件下的应急系统模糊路径问题.当边的长度为对称三角模糊数 (Symmetric Triangular Fuzzy Number)时,由于模糊数的不可比性,网络中一般不存在绝对 最短的路.为此,引入了路径满意度函数的概念,从而问题就变成:寻找一条从起点到终点的 通路,应急车辆经过此路的时间不超过限制期t的满意度最大.这样的路径选取问题实际可 转化为一个比例路径问题,尽管许多比例路径问题已被证明是NP问题,完全可以针对问题 的具体特点,运用最短路方法的变权迭代实现对该问题的精确求解.     

随机时间依赖网络的K期望最短路径

首先给出了随机时间依赖网络模型，K期望是短路径问题的形式化描述，并针对公交网络推导出到达弧头结点的时刻所服从的概率密度函数，路径期望耗费的计算方法，然后，基于随机一致性假设和胡机优势的概念给出了K期望最短路径问题的理论基础和算法并证明了算法的正确性，最后，给出了公交网络的应用实例和实验结果。     

Finding the shortest path in stochastic networks

Common network parameters, such as number of nodes and arc lengths are frequently subjected to ambiguity as a result of probability law. A number of authors have discussed the calculation of the shortest path in networks with random variable arc lengths. Generally, only a subset of intermediate nodes chosen in accordance with a given probability law can be used to transition from source node to sink node. The determination of a priori path of the minimal length in an incomplete network is defined as a probabilistic shortest path problem. When arc lengths between nodes are randomly assigned variables in an incomplete network the resulting network is known as an incomplete stochastic network. In this paper, the computation of minimal length in incomplete stochastic networks, when travel times between nodes are allowed to be exponentially distributed random variables, is formulated as a linear programming problem. A practical application of the methodology is demonstrated and the results and process compared to the Kulkarni’s [V.G. Kulkarni, Shortest paths in networks with exponentially distributed arc lengths, Networks 16 (1986) 255–274] method.     

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.     

时间依赖的网络中最小时间路径算法

时间依赖的网络与传统网络模型相比更具有现实意义，具有广泛的应用领域，交通网络和通信网络可以抽象为时间依赖的网络模型，当模型中弧的工度是时间依赖的变量，最短路径问题的求解变得非常困难，早期的研究者通过具体的网络实例认识到传统最短路径算法在这种情况下是不正确的，因此给出限制性条件使得传统最短路径算法是有效的。该文从最短路径算法的理论基础入手，从理论上证明了传统最短路径算法，如Dijkstra算法和标号设置算法，在时间依赖的网络上不能有效地求解最短路径问题，并且，在没有任何限制性条件下，给出了时间依赖的网络模型，理论基础，求解最小时间路径的优化条件和SPTDN算法，从理论上证明了SPTDN算法的正确性，算法的实验结果是正确的，最后给出了时间依赖的网络应用实例。     

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.     

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

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

The constrained shortest path tour problem

In this paper, we study the constrained shortest path tour problem. Given a directed graph with non-negative arc lengths, the aim is to find a single-origin single-destination shortest path, which needs to cross a sequence of node subsets that are given in a fixed order. The subsets are disjoint and may be of different size. In addition, it is required that the path does not include repeated arcs.Theoretical properties of the problem are studied, proving that it belongs to the complexity class NP-complete. To exactly solve it, a Branch & Bound method is proposed. Given the problem hardness, a Greedy Randomized Adaptive Search Procedure is also developed to find near-optimal solutions for medium to large scale instances.Extensive computational experiments, on a significant set of test problems, are carried out in order to empirically evaluate the performance of the proposed approaches. The computational results show that the Greedy Randomized Adaptive Search Procedure is effective in finding optimal or near optimal solutions in very limited computational time.     

动态网络最短路问题的复杂性与近似算法

有向网络的最短路问题在交通、通信系统的最优路径计算以及多阶段决策过程的最优轨线设计等实际问题中有着重要应用.经典模型及算法解决固定弧权条件下的最短路问题,而实际中,网络往往是动态的,即弧权依赖于时间变化,例如在交通拥堵时运行时间会变长,这时经典的最短路算法不再适用.文中证明了动态网络的最短路问题是NP-困难的;给出了最短路稳定性的充要条件,并在此基础上提出一种基于稳定区间的近似算法,通过模拟实验验证了该算法的有效性.     

Shortest path problem with uncertain arc lengths

Uncertainty theory provides a new tool to deal with the shortest path problem with nondeterministic arc lengths. With help from the operational law of uncertainty theory, this paper gives the uncertainty distribution of the shortest path length. Also, it investigates solutions to the α-shortest path and the most shortest path in an uncertain network. It points out that there exists an equivalence relation between the α-shortest path in an uncertain network and the shortest path in a corresponding deterministic network, which leads to an effective algorithm to find the α-shortest path and the most shortest path. Roughly speaking, this algorithm can be broken down into two parts: constructing a deterministic network and then invoking the Dijkstra algorithm.     

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.     

Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network

From the point of view of quality management, it is an important issue to reduce the transmission time in the network. The quickest path problem is to find the path in the network to send a given amount of data from the source to the sink such that the transmission time is minimized. Traditionally, this problem assumed that the capacity of each arc in the network is deterministic. However, the capacity of each arc is stochastic due to failure, maintenance, etc. in many real-life networks. This paper proposes a simple algorithm to evaluate the probability that d units of data can be sent from the source to the sink through the stochastic-flow network within T units of time. Such a probability is called the system reliability. The proposed algorithm firstly generates all lower boundary points for (d,T) and the system reliability can then be computed in terms of such points.Scope and purposeThe shortest path problem is a well-known problem in operations research, computer science, etc. Chen and Chin have proposed a variant of the shortest path problem, termed the quickest path problem. It is to find a path in the network to send a given amount of data from the source to the sink with minimum transmission time. More specifically, the capacity of each arc in the network is assumed to be deterministic. However, in many real-life networks such as computer systems, telecommunication systems, etc., the capacity of each arc is stochastic due to failure, maintenance, etc. Such a network is named a stochastic-flow network. Hence, the minimum transmission time is not a fixed number. This paper proposes a simple algorithm to evaluate the probability that the specified amount of data can be sent from the source to the sink through the network within a given time. Such a probability is called the system reliability.     

Enjoy the most beautiful scene now: a memetic algorithm to solve two-fold time-dependent arc orienteering problem

Traditional route planners commonly focus on finding the shortest path between two points in terms of travel distance or time over road networks.However,in real cases,especially in the era of smart cities where many kinds of transportation-related data become easily available,recent years have witnessed an increasing demand of route planners that need to optimize for multiple criteria,e.g.,finding the route with the highest accumulated scenic score along(utility)while not exceeding the given travel time budget(cost).Such problem can be viewed as a variant of arc orienteering problem(AOP),which is well-known as an NP-hard problem.In this paper,targeting a more realistic AOP,we allow both scenic score(utility)and travel time(cost)values on each arc of the road network are time-dependent(2TD-AOP),and propose a memetic algorithm to solve it.To be more specific,within the given travel time budget,in the phase of initiation,for each population,we iteratively add suitable arcs with high scenic score and build a path from the origin to the destination via a complicate procedure consisting of search region narrowing,chromosome encoding and decoding.In the phase of the local search,each path is improved via chromosome selection,local-improvement-based mutation and crossover operations.Finally,we evaluate the proposed memetic algorithm in both synthetic and real-life datasets extensively,and the experimental results demonstrate that it outperforms the baselines.     

A hill-jump algorithm of Hopfield neural network for shortest path problem in communication network

In this paper, we present a hill-jump algorithm of the Hopfield neural network for the shortest path problem in communication networks, where the goal is to find the shortest path from a starting node to an ending node. The method is intended to provide a near-optimum parallel algorithm for solving the shortest path problem. To do this, first the method uses the Hopfield neural network to get a path. Because the neural network always falls into a local minimum, the found path is usually not a shortest path. To search the shortest path, the method then helps the neural network jump from local minima of energy function by using another neural network built from a part of energy function of the problem. The method is tested through simulating some randomly generated communication networks, with the simulation results showing that the solution found by the proposed method is superior to that of the best existing neural network based algorithm.     

一类标准矩形网络节点间最短路径的求解方法

针对常见的交通道路最短路径问题, 提出标准矩形网络的概念, 分析其节点间最短路径的性质, 并在此基础上给出一种新颖的最短路径求解算法. 该算法利用标准矩形网络的几何性质, 简化了搜索方向和步长的判断, 同时指出常见的交通道路网络一般均可以整体或部分化为标准矩形网络. 与常见的求取最短路径的Dijkstra、Floyd、ACO、A* 等算法进行仿真实验比较, 实验结果表明, 对于大规模标准矩形道路网络, 所提出算法具有更好的寻优精度、稳定性和寻优速度.

     

基于k-shell的复杂网络最短路径近似算法

复杂网络最短路径经典算法的处理效率较低，不适用于大规模复杂网络，而现有近似算法通用性有限，且计算准确率不理想，不能满足规模日益扩大的复杂网络中的最短路径计算需求。针对于此，提出基于[k]-shell的复杂网络最短路径近似算法。算法利用节点的[k]-shell值进行网络划分并引导搜索路径，利用超点聚合处理[k]-shell子网来降低路径搜索中节点和连边的规模，通过在路径搜索过程使用双向搜索树方法提高算法的计算效率和准确率。实验结果表明，算法通用性较好，在现实与仿真大规模复杂网络中均具有较高的计算效率和准确率。     

基于概率优化的水下通道感知能量优化路由

针对水下传感器网络能量损耗较大,延迟较严重的问题,提出一种基于概率优化的水下通道感知能量优化路由（PPUN）。在能量优化上,针对水下节点随机覆盖存在的多余感测覆盖范围所造成的额外能量损耗问题,采用传感器节点数量的概率优化方法,在保证覆盖率和节点连通率的情况下推导出网络所需要的最小节点数目,从减少传感器数目的问题上来优化总体能量。而针对路由的能量损耗问题,在节点的链路规划上采用了通道感知路由算法,考虑了在一定能量损耗阈值条件下的最短节点路径,避免水下节点盲目选择能量损耗较大的最短路径而导致数据转发失败,消耗更多能量。延迟问题抓住主要的解码延迟问题进行了分析并利用HARQ-III方案对延迟时间加以控制。实验对比分析表明,算法采取控制传感器数目和链路规划的方法,在实现能量优化上具有一定优势,延迟控制方案也得到了较好的效果。     

弹性光网络中基于频谱连续度的算法研究

针对光网络中可用的波长资源有限、频谱利用率不高的问题,提出了一种基于KSP算法的频谱连续度感知算法（KSPDP）。该方法在路由选择方面,用KSP算法求得源节点和目的节点之间的不同的路径长度,并根据业务请求所需的频谱资源数量,分配不同的路径。在频谱分配方面,算法将感知各链路的频谱连续情况,最大限度减少业务分配的路径上各链路的频谱碎片。仿真结果表明,所提出的算法与传统的最短路径RMSA算法相比,能降低频谱阻塞率,提高频谱资源利用率。     

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

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

A modified pulse coupled neural network for shortest-path problem

Shortest-path problem is well-known optimization problem and has been studied by many authors in recent years. Typically it is solved by using the famous Dijkstra's algorithm, which would quickly provide a global optimization solution in most instances. However, as the problem scale increases, this method is inefficient and may consume a considerable amount of CPU time. Neural networks, which are massively parallel models, can solve this question easily. This paper presents a novel biological neural network based algorithm for the finding of the shortest path in large scale systems. The start neuron fires first, and then the firing event spreads out through the lateral connections among the neurons, like the propagation of a wave. Then the generated spiking wave spreads at a constant speed so that the time of travel between two neurons is proportional to the path length between them. The computational complexity of the algorithm is only related to the length of the shortest path, and independent of the number of existing paths in the graph. Simulation results show that the proposed method is more efficient than Dijkstra's in the larger scale systems.