基于节点可达度的公交多路径搜索算法

针对公交网络路径搜索问题,以复杂网络的角度进行了相关研究。根据出行者实际需求,提出一种基于节点可达度的公交多路径搜索算法。采用复杂二分网络模型来描述公交网络,将公交线路和公交站点分别看做一类节点,每条公交线路与它所经过的公交站点之间存在连边;在分析网络社团结构的基础上定义了节点可达度,算法根据节点可达度逐步搜索直至目的节点,搜索过程保留可能存在的多条最佳路径。实验结果表明,该方法能够得到最小换乘的多条有效路径。     

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

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

A label-setting algorithm for finding a quickest path

The quickest path problem is to find a path to send a given amount of data from the source to the destination with minimum transmission time. To find the quickest path, existing algorithms enumerate non-dominated paths with distinct capacity, and then determine a quickest path by comparing their transmission time. In this paper, we propose a label-setting algorithm for finding a quickest path by transforming a network to another network where an important property holds that each subpath of a quickest path is also a quickest path. The proposed algorithm avoids enumerating non-dominated paths whose transmission time is greater than the minimum transmission time. Although the computational complexity of the proposed algorithm is the same as that of existing algorithms, experimental results show that our algorithm is efficient when a network has two or more non-dominated paths.     

Parallel Algorithms for Dynamic Shortest Path Problems

The development of intelligent transportation systems (ITS) and the resulting need for the solution of a variety of dynamic traffic network models and management problems require faster‐than‐real‐time computation of shortest path problems in dynamic networks. Recently, a sequential algorithm was developed to compute shortest paths in discrete time dynamic networks from all nodes and all departure times to one destination node. The algorithm is known as algorithm DOT and has an optimal worst‐case running‐time complexity. This implies that no algorithm with a better worst‐case computational complexity can be discovered. Consequently, in order to derive algorithms to solve all‐to‐one shortest path problems in dynamic networks, one would need to explore avenues other than the design of sequential solution algorithms only. The use of commercially‐available high‐performance computing platforms to develop parallel implementations of sequential algorithms is an example of such avenue. This paper reports on the design, implementation, and computational testing of parallel dynamic shortest path algorithms. We develop two shared‐memory and two message‐passing dynamic shortest path algorithm implementations, which are derived from algorithm DOT using the following parallelization strategies: decomposition by destination and decomposition by transportation network topology. The algorithms are coded using two types of parallel computing environments: a message‐passing environment based on the parallel virtual machine (PVM) library and a multi‐threading environment based on the SUN Microsystems Multi‐Threads (MT) library. We also develop a time‐based parallel version of algorithm DOT for the case of minimum time paths in FIFO networks, and a theoretical parallelization of algorithm DOT on an ‘ideal’ theoretical parallel machine. Performances of the implementations are analyzed and evaluated using large transportation networks, and two types of parallel computing platforms: a distributed network of Unix workstations and a SUN shared‐memory machine containing eight processors. Satisfactory speed‐ups in the running time of sequential algorithms are achieved, in particular for shared‐memory machines. Numerical results indicate that shared‐memory computers constitute the most appropriate type of parallel computing platforms for the computation of dynamic shortest paths for real‐time ITS applications.     

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

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

基于引力模型及相对路径数的节点重要度评估算法

准确度量复杂网络中节点的重要度对于研究网络结构和功能等方面具有重要的指导意义。现有多数节点重要度评估算法考虑了节点及其邻居节点的相关信息,却忽略了节点间的拓扑结构对节点重要度的影响。针对此问题,提出了基于引力模型及相对路径数的节点重要度评估算法。该算法首先分析了相对最短路径数对节点间信息传播的影响效果,同时考虑到非最短路径及路径距离等因素的影响,然后以三阶范围内邻居节点与中心节点的相互作用力之和定义节点重要度值,最后在六个真实网络中进行仿真实验。实验结果表明,所提算法不仅能有效区分网络中不同节点之间的重要度差异,还能准确度量网络节点的重要度大小。     

Fault-tolerant routing over shortest node-disjoint paths in hypercubes

This paper presented a routing algorithm that finds n disjoint shortest paths from the source node s to target node d in the n-dimensional hypercube. Fault-tolerant routing over all shortest node-disjoint paths has been investigated to overcome the failure encountered during routing in hypercube networks. In this paper, we proposed an efficient approach to provide fault-tolerant routing which has been investigated on hypercube networks. The proposed approach is based on all shortest node-disjoint paths concept in order to find a fault-free shortest path among several paths provided. The proposed algorithm is a simple uniform distributed algorithm that can tolerate a large number of process failures, while delivering all n messages over optimal-length disjoint paths. However, no distributed algorithm uses acknowledgement messages (acks) for fault tolerance. So, for dealing the faults, acknowledgement messages (acks) are included in the proposed algorithm for routing messages over node-disjoint paths in a hypercube network.     

Transient chaotic neural network-based disjoint multipath routing for mobile ad-hoc networks

Due to mobility of wireless hosts, routing in mobile ad-hoc networks (MANETs) is a challenging task. Multipath routing is employed to provide reliable communication, load balancing, and improving quality of service of MANETs. Multiple paths are selected to be node-disjoint or link-disjoint to improve transmission reliability. However, selecting an optimal disjoint multipath set is an NP-complete problem. Neural networks are powerful tools for a wide variety of combinatorial optimization problems. In this study, a transient chaotic neural network (TCNN) is presented as multipath routing algorithm in MANETs. Each node in the network can be equipped with a neural network, and all the network nodes can be trained and used to obtain optimal or sub-optimal high reliable disjoint paths. This algorithm can find both node-disjoint and link-disjoint paths with no extra overhead. The simulation results show that the proposed method can find the high reliable disjoint path set in MANETs. In this paper, the performance of the proposed algorithm is compared to the shortest path algorithm, disjoint path set selection protocol algorithm, and Hopfield neural network (HNN)-based model. Experimental results show that the disjoint path set reliability of the proposed algorithm is up to 4.5 times more than the shortest path reliability. Also, the proposed algorithm has better performance in both reliability and the number of paths and shows up to 56% improvement in path set reliability and up to 20% improvement in the number of paths in the path set. The proposed TCNN-based algorithm also selects more reliable paths as compared to HNN-based algorithm in less number of iterations.     

An efficient network flow code for finding all minimum cost s–t cutsets

Cutset algorithms have been well documented in the operations research literature. A directed graph is used to model the network, where each node and arc has an associated cost to cut or remove it from the graph. The problem considered in this paper is to determine all minimum cost sets of nodes and/or arcs to cut so that no directed paths exist from a specified source node s to a specified sink node t. By solving the dual maximum flow problem, it is possible to construct a binary relation associated with an optimal maximum flow such that all minimum cost s–t cutsets are identified through the set of closures for this relation. The key to our implementation is the use of graph theoretic techniques to rapidly enumerate this set of closures. Computational results are presented to suggest the efficiency of our approach.Scope and purposeThis paper describes the technical details of a network flow algorithm used to find all minimum cost s–t cutsets in any network topology. The motivation for this work was to provide additional automated analysis capability to a military network targeting system. Specifically, the problem is to identify a minimum cost set of nodes and/or arcs that when removed from the network, will disconnect a selected pair of origin–destination nodes. Algorithms for solving this problem are well understood, with an active research thrust in both the operations research and computer science academic communities in developing more efficient algorithms for larger networks. The main contribution of this paper is in extending these algorithms to quickly find all minimum cost cutset solutions. The implementation described in this paper outperformed conventional methods by several orders of magnitude on networks having thousands of nodes and arcs, with empirical solution times that grew linearly with the network size. The results translate to a real-time cutset analysis capability to support military targeting applications.     

基于影响路径的个性化影响最大化算法

个性化影响最大化问题是近年来社交网络影响最大化问题研究领域一个较新的分支,其现有解决方案普遍建立在网络边影响传播强度一致的假设下,该假设对于真实社交网络缺乏普遍适用性。为此基于独立级联模型,提出最大影响路径算法(MIPA)。该算法通过三个阶段来求解个性化影响最大化问题,首先将边影响强度作对数转换以获得最大影响路径,从而计算网络节点对目标节点的邻居节点的影响;然后利用多条经过目标节点邻居的最大影响路径联合计算目标节点受到的影响强度;最后选择Top-k节点作为种子节点,从而摆脱边影响强度的一致性约束,获取高质量的种子集。在不同的真实社交网络数据集上进行的对比实验验证了算法的有效性。     

FDR: fault detection and recovery scheme for wireless sensor networks using virtual grid

Due to autonomous operation and constrained resources, nodes of a wireless sensor network are susceptible to failures. Due to multiple node failures, network topology may change or partition into many disconnected segments causing data/query path breakage. Early detection and recovery of faults is desirable in most scenarios. Also, due to limited battery life of a node, the solution must consume minimum possible energy for prolonged network operation. Hence in this paper, we propose a Fault Detection and Recovery scheme which is an energy efficient fault detection and recovery strategy that achieves minimum data loss by efficiently replacing faulty node on the present route or by finding full or partial alternate paths. Topology is managed by constructing a virtual grid over the entire network which helps in managing dynamically changing network topology easily and makes failure detection and recovery effective. It also helps to create energy efficient path between a source and a sink by finding shortest possible path. Further, nodes’ cooperation is exploited to create certain zones on the data/query path which provides alternate nodes or possible alternate paths if required on some node failures. Thus, scheme achieves fault tolerance and at the same time achieves energy efficiency by always selecting shortest path for data delivery between source and sink. Analytical and simulation study reveals the significant improvement in terms of fault detection and energy conservation over existing similar schemes.     

基于蚁群的无线传感器网络能量均衡非均匀分簇路由算法

无线传感器网络(WSN)路由中,节点未充分考虑路径剩余能量及链路状况进行的路由会造成网络中部分节点网络寿命减少,严重影响网络的生存时间。为此,将蚁群优化算法与非均匀分簇路由算法相结合,提出一种基于蚁群优化算法的无线传感器非均匀分簇路由算法。该算法首先利用考虑节点能量的优化非均匀分簇方法对节点进行分簇,然后以需要传输数据的节点为源节点,汇聚节点为目标节点,利用蚁群优化算法进行多路径搜索,搜索过程充分考虑了路径传输能耗、路径最小剩余能量、传输距离和跳数、所选链路的时延和带宽等因素,最后选出满足条件的多条最优路径,完成源目的节点间的信息传输。实验表明,该算法充分考虑路径传输能耗和路径最小剩余能量、传输跳数及传输距离,能有效延长无线传感器网络的生存期。     

Multi-objective α-reliable path finding in stochastic networks with correlated link costs: A simulation-based multi-objective genetic algorithm approach (SMOGA)

In this study, we propose a new simulation-based multi-objective genetic algorithm (SMOGA) approach to find a portfolio of reliable nondominant (Pareto) paths, a set of paths that is equally good or better at least in one objective space compared to all other paths, in stochastic networks while considering link travel time uncertainties and correlations among link travel times. Our SMOGA model consists of a Monte Carlo simulation, a genetic algorithm, and a Pareto filter module to find a set of Pareto paths that minimize the travel time budgets required to satisfy multiple requirements of travel time reliability pre-determined by users. For our purposes, an alpha (and beta) reliable path finding problem is first formulated as a variant of Chance Constrained Multi-objective Programming (CCMOP) model. Then the simulation module is used to simulate stochastic networks with correlations among link travel times, and genetic algorithm and Pareto filter module are used to effectively search for Pareto paths that satisfy multiple reliability requirements in combinatorial solution space. Numerical results on the Chicago Sketch network demonstrate that our carefully designed genetic representation (a variable-length chromosome and two ways of generating initial population) and genetic operators (a crossover and a mutation operator) effectively explore solution space and ensure the feasibility and diversity of offspring paths. Further, our graphical representations of Pareto paths on the same network indicate that simplified models that do not consider correlations among link travel time distributions may find Pareto paths with a significant bias in travel time budgets and hence provide travelers sub-optimal paths.     

On the sum-max bicriterion path problem

In network analysis, there are many applications in which several weights associated with traversing each arc are given, so it is natural to consider multiple-objective path problems. Usually, there is no path which is simultaneously optimal with respect to all objective functions, so it will be necessary to obtain efficient paths of interest, i.e. paths for which there exists no other path that yields an improvement in one of the objective functions without causing a degradation in the others. Methods for determining efficient paths form part of a very extensive literature on multiple-objective optimization, most of them being proposed for objectives defined by sum functions. Our aim is to study the particular case of a bicriterion problem whose objective functions are defined by a sum and a maximum. A very important aspect of this problem is to find a best compromise solution, which is shown to be equivalent to solve the quickest path problem, which has interesting applications in communication and transportation networks.In this paper, we study a special class of bicriterion path problems where the objective functions are defined by a sum and a maximum: The sum-max bicriterion path problem (SMBPP). After reviewing some special kinds of efficient paths, we propose some algorithms to generate these kinds of efficient paths, based on a progressive reduction of the original network. We analyse its relationship with the quickest path problem (QPP), showing that this is equivalent to the weighted problem associated to the SMBPP, which is also solved by a modification of an algorithm proposed for the QPP. A computational study is presented which shows the superiority of the algorithm proposed in this paper over other existing algorithms to generate the entire set E of efficient paths of the SMBPP.     

A real-time traffic control scheme of multiple AGV systems forcollision free minimum time motion: a routing table approach

A two-staged traffic control scheme, in which sets of candidate paths are prepared off-line prior to overall motion planning process, has been widely adopted for motion planning of mobile robots, but relatively little attention has been given to the application of the two-staged scheme to multiple automated guided vehicle systems (MAGVSs). In the paper, a systematic two-staged traffic control scheme is presented to obtain collision-free minimum-time motions of AGVs along loopless paths. The overall structure of the controller is divided into two tandem modules of off-line routing table generator (RTG) and an online traffic controller (OTC). First, an induced network model is established considering the configurational restrictions of guide-paths. With this model and a modified k-shortest path algorithm, RTG finds sets of k candidate paths from each station nodes to all the other station nodes off-line and stores them in the form of routing tables. Each time a dispatch command for an AGV is issued, OTC utilizes these routing tables to generate a collision-free minimum-time motion along a loopless path. Real-time computation is guaranteed in that the time-consuming graph searching process is executed off-line by RTG, and OTC looks for the minimum time motion among the k candidate paths. The traffic control scheme proposed is suitable for practical application in centralized MAGVS with zone blocking technique     

基于栅格法的虚拟人快速路径规划

在栅格中使用经典的Dijkstra算法进行路径规划有计算量大,规划时间长、进行扩展判断的节点个数多等缺点.栅格的组织结构决定了栅格中最短路径的特性--组成最短路径的各线段间的最小夹角为90°.根据栅格及最短路径的特性,提出了一种在栅格中使用Dijkstra算法规划路径时减少扩展节点的个数,进而缩短规划时间、降低计算代价的算法,并将其用于虚拟人的路径规划.实验验证了算法的可行性和有效性.     

基于量子遗传算法的无线传感器网络路由研究

通过分析无线传感器网络(WSN)分簇路由算法中簇首节点分布,能量消耗,数据传输等问题,提出了一种基于熵权法量子遗传算法的路由算法,该算法在簇首的选举过程中采用熵权法动态的确定节点剩余能量、节点间的通信距离、节点度数和节点与基站的距离这四个因素的权值系数,在簇首选举结束后,利用量子遗传算法寻找出一条遍历所有簇首与基站的路由,通过最佳路由将所采集的数据传输给最终的基站节点。该算法实现了合理的簇首选举,并在簇首间采用最佳路由的方式向基站传输数据的功能。仿真结果分析表明,该算法在网络生存周期、能耗均衡方面均优于LEACH、CECA-GA算法,达到了延长了网络生存周期,均衡能耗的目的。     

基于路径损耗的WSN拓扑控制算法

现有无线传感器网络拓扑控制算法大多基于理想网络模型,且需要节点位置信息。为此,提出一种基于路径损耗的拓扑控制算法。该算法无需任何节点位置信息,通过计算两节点间小于或等于3跳的前向与后向路径损耗,构建网络拓扑。仿真结果表明,该算法能降低网络能耗及节点间的通信干扰,保证网络连通性,延长网络生命周期。     

Transmission reliability of k minimal paths within time threshold

The quickest path problem involving two attributes, the capacity and the lead time, is to find a single path with minimum transmission time. The capacity of each arc is assumed to be deterministic in this problem. However, in many practical networks such as computer networks, telecommunication networks, and logistics networks, each arc is multistate due to failure, maintenance, etc. Such a network is named a multistate flow network. Hence, both the transmission time to deliver data through a minimal path and the minimum transmission time through a multistate flow network are not fixed. In order to reduce the transmission time, the data can be transmitted through k minimal paths simultaneously. The purpose of this paper is to evaluate the probability that d units of data can be transmitted through k minimal paths within time threshold T. Such a probability is called the transmission reliability. A simple algorithm is proposed to generate all lower boundary points for (d, T), the minimal system states satisfying the demand within time threshold. The transmission reliability can be subsequently computed in terms of such points. Another algorithm is further proposed to find the optimal combination of k minimal paths with highest transmission reliability.