A bi-objective approach for shortest-path network interdiction

In the literature, solution approaches to the shortest-path network interdiction problem have been developed for optimizing a single figure-of-merit of the network configuration when considering limited amount of resources available to interdict network links. This paper presents a newly developed evolutionary algorithm that allows approximating the optimal Pareto set of network interdiction strategies when considering bi-objective shortest path problems. Thus, the paper considers the concurrent optimization of two objectives: (1) maximization of shortest-path length and (2) minimization of interdiction strategy cost. Also, the paper considers the transformation of the first objective into the minimization of the most reliable path reliability. To solve these multi-objective optimization problems, an evolutionary algorithm has been developed. This algorithm is based on Monte Carlo simulation, to generate potential network interdiction strategies, graph theory to analyze strategies’ shortest path or most reliable path and, an evolutionary search driven by the probability that a link will appear in the optimal Pareto set. Examples for different sizes of networks and network behavior are used throughout the paper to illustrate and validate the approach.     

A constrained binary knapsack approximation for shortest path network interdiction

A modified shortest path network interdiction model is approximated in this work by a constrained binary knapsack which uses aggregated arc maximum flow as the objective function coefficient. In the modified shortest path network interdiction problem, an attacker selects a path of highest non-detection probability on a network with multiple origins and multiple available targets. A defender allocates a limited number of resources within the geographic region of the network to reduce the maximum network non-detection probability between all origin-target pairs by reducing arc non-detection probabilities and where path non-detection probability is modeled as a product of all arc non-detection probabilities on that path. Traditional decomposition methods to solve the shortest path network interdiction problem are sensitive to problem size and network/regional complexity. The goal of this paper is to develop a method for approximating the regional allocation of defense resources that maintains accuracy while reducing both computational effort and the sensitivity of computation time to network/regional properties. Statistical and spatial analysis methods are utilized to verify approximation performance of the knapsack method in two real-world networks.     

A fast genetic algorithm for a critical protection problem in biomedical supply chain networks

In this paper, we present a new bilevel model for a biomedical supply chain network with capacity and budget constraint due to the protection and interdiction operations. The components considered in this model are biomedical devices, distribution centers (DCs), medical suppliers (MSs), and hospitals and patients as the demand points. On the other hand, two levels of decisions in the network planning is suggested: (1) the defender’s decision about protection operations of MSs and DCs, the assignment of clients to the DCs, and quantity of products shipped to DCs from MSs to minimize the demand-weighted traveling costs and transport costs and (2) the attacker’s decision about interdiction operations of MSs and DCs to maximize the capacity or service reduction and losses. Because of nondeterministic polynomial time (NP)-hardness of the problem under consideration, an efficient and fast approach based on a genetic algorithm and a fast branch and cut method (GA–FBC) was developed to solve the proposed model. Also, the efficiency via the comparison of results with the genetic algorithm based on CPLEX (GA-CPLEX) and decomposition method (DM) is investigated. In order to assess the performance of the presented GA–FBC, a set of 27 instances of the problem is used. Comprehensive analysis indicates that the proposed approach significantly solves the problem. In addition, the benefits and advantages of preference with running times and its accuracy is shown numerically. Simulation results clearly demonstrate that the defender’s objective effectively reduced and CPU time also within the large-sized instances of the problem in comparison with the GA-CPLEX and DM.     

低代价最短路径树的快速算法

低代价最短路径树是一种广泛使用的多播树.它能够在保证传送时延最小的同时尽量降低带宽消耗.在DDSP(destination-driven shortest path)算法的基础上,通过改进节点的搜索过程,提出了快速低代价最短路径树算法FLSPT(fast loW-coSt shortest path tree).该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP算法.随机网络模型的仿真结果表明,FLSPT算法效率更高.     

基于路径集合运算的公交网络寻径算法研究

大规模多换乘网络中最短时间路径精确查询的算法是公交网络寻径问题的研究难点之一,近似搜索算法的求解满意度不高,而精确搜索算法的效率较低.提出了基于路径集合运算的公交网络寻径算法,按换乘次数从低到高依次求取路径集合,通过删除大量冗余路径来优化路径集合并减少计算量,最后生成最短时间路径汇总集合用于快速精确寻径.实验结果表明了算法的可行性和有效性.     

Call Control in Rings

The call control problem is an important optimization problem encountered in the design and operation of communication networks. The goal of the call control problem in rings is to compute, for a given ring network with edge capacities and a set of paths in the ring, a maximum cardinality subset of the paths such that no edge capacity is violated. We give a polynomial-time algorithm to solve the problem optimally. The algorithm is based on a decision procedure that checks whether a solution with at least k paths exists, which is in turn implemented by an iterative greedy approach operating in rounds. We show that the algorithm can be implemented efficiently and, as a by-product, obtain a linear-time algorithm to solve the problem in chains optimally. For the weighted version of call control in rings, where each path is associated with a weight and the goal is to maximize the total weight of the paths in the solution, we present a simple 2-approximation algorithm and a polynomial-time approximation scheme. While the complexity of the weighted version remains open, we show that it is at least as hard as the bipartite exact matching problem, which has not been resolved to be in P or NP-hard. This latter result follows from recent work by Hochbaum and Levin.     

基于PCNN的交通路径寻优算法研究

路径寻优作为智能交通系统的重要组成部分,搜索效率需要提高,但是目前的算法未能快速准确地实现大规模交通路网路径寻优的计算功能。本文提出脉冲耦合神经网络（PCNN）求解最短路径,根据PCNN独特的自动波并行传播特性,结合大规模路网“节点数目多、结构复杂”的特点,采用PCNN改进模型。各神经元点火形成脉冲波在路网传播,记录最先到达脉冲波走过的路径为最短路径。最后给出路径搜索实现算法并与蚁群算法、Dijkstra算法比较,通过实例验证了改进模型和算法的有效性,该算法对求解大规模实时问题具有一定优越性。     

Low overhead path regeneration

Monte Carlo Path Tracing is a core light transport technique which is used for modern methods (like BDPT, MLT, VCM and others). One of the main challenge of efficient GPU Path Tracing implementation is inefficient workload caused by paths of different lengths; few threads process the long paths, while other threads are idle. A work distribution technique called “Path Regeneration” is commonly used to solve this problem. We introduce a novel GPU implementation of path regeneration technique called “in place block based path regeneration.” In comparison to previous approaches our algorithm possesses two main advantages: it has lower self-cost and it does not move any per-ray data along threads in memory, thus, our algorithm can be easily integrated to any advanced path tracing technique (like BDPT, MLT and other) or photon mapping. We tested our solution with path tracing using both CUDA and OpenCL.     

Techniques for critical path reduction of scalar programs

Scalar performance on processors with instruction level parallelism (ILP) is often limited by control and data dependences. This paper describes a family of compiler techniques, called Critical Path Reduction (CPR) techniques, which reduce the length of critical paths through control and data dependences. Control CPR reduces the number of branches on the critical path and improves the performance of branch intensive codes on processors with inadequate branch throughput or excessive branch latency. Data CPR reduces the number of arithmetic operations on the critical path. Optimization and scheduling are adapted to support CPR.     

符号执行中高语句覆盖率的路径调度

符号执行和约束求解相结合的软件测试方法采用深度优先搜索的路径调度算法会造成测试路径聚居性问题,实际软件中存在路径爆炸,使得采用该算法的测试语句覆盖率低下。提出一种新的PSHC路径调度算法。先将路径分为前缀和后缀两部分,每次测试总是试图寻找这样的路径,该路径与已存在的路径具有最短的相同前缀,并且包含尽可能多的尚未被访问过的基本块作为其后缀。基于Phoenix漏洞发掘工具的实验结果表明,PSHC算法可以迅速提高测试的语句覆盖率到100%,有效解决由于深度优先搜索的路径聚居性导致的测试代码的局部性问题,PSHC算法产生的路径数与循环深度无关,软件规模越大,该算法的表现越好。     

无线自组网络基于遗传算法的多播路由算法

随着无线自组网络技术的发展,多播应用日益广泛。文章研究无线自组网络多插路由问题,针对已有算法在时延约束多播路由树费用优化方面的不足,提出基于遗传算法的多播路由算法。该算法首先通过Dijkstra算法得到源节点到每个接收节点间的最多K条路径;其次给这些路径编号,进行编码,设计遗传操作;最后,进行遗传迭代运算找到费用全局优...     

SDN中基于负载均衡的最优路径选择算法研究

针对传统网络控制与转发的紧耦合,其路径分配算法的全局性差,实时性不足,根据软件定义网络的集中控制,提出一种基于马尔科夫链负载均衡(Markov Chain-Load Balancing ,MC-LB)算法。该算法使用马尔科夫链的转移概率计算链路重要性,并同时对业务流请求量和网络负载均衡率两个目标进行优化,获得多请求下的最优路径分配。通过大量实验对比表明该算法优于传统SPF（Shortest Path First）算法,最大可以增加网络负载均衡率30%,提升网络业务流请求接受率20%。达到了负载均衡效果,提高了网络的性能。     

Implementation and analysis of alternative algorithms for generalized shortest path problems

This paper addresses a special class of deterministic dynamic programming problems which can be formulated as a generalized network problem. Because of the similarities between this class of dynamic programming problems and shortest path problems, we are naming it the Generalized Shortest Path problem. A new primal extreme point algorithm and a new special dual algorithm are proposed here. While researchers have presented a variety of algorithms to solve this class of problems, there has been no comuptational analysis of these algorithms. An in-depth computational analysis is performed to determine the most efficient set of rules for implementing the algorithms of this paper.     

Decentralized control of a group of mobile robots for deployment in sweep coverage

This paper addresses a problem of sweep coverage by deploying a network of autonomous mobile robots. We propose a decentralized control algorithm for the robots to accomplish the sweep coverage. The sweep coverage is achieved by coordinating the robots to move along a given path that is unknown to the vehicles a priori. The motion coordination algorithm is developed based on simple consensus algorithms. The effectiveness of the algorithm is demonstrated via numerical simulations. The proposed algorithm would have applications to military and civilian operations.     

大规模通信网络带宽优化分配问题研究

提出一种大规模通信网络带宽分配的新方法．作者将大系统理论中的分解—协调方法运用于解决大规模通信网络带宽分配的优化问题，大型网络的优化问题被分解成一些互相关联的小型子网的优化问题．整个带宽优化分配问题的解决分为三个阶段：分解、协调优化及合并优化．计算结果表明，与现有算法相比，分解—协调大规模带宽管理算法(DCLPBM)既保证了很高的计算精度，又降低了时间与空间复杂度．由于算法中用到的协调机制较简单，DCLPBM易于推广到分布式计算环境，从以网络来治理网络的角度看，它具有较广的前景．     

Maximizing lifetime in wireless sensor networks with multiple sensor families

Wireless sensor networks are generally composed of a large number of hardware devices of the same type, deployed over a region of interest in order to perform a monitoring activity on a set of target points. Nowadays, several different types of sensor devices exist, which are able to monitor different aspects of the region of interest (including sound, vibrations, proximity, chemical contaminants, among others) and may be deployed together in a heterogeneous network. In this work, we face the problem of maximizing the amount of time during which such a network can remain operational, while maintaining at all times a minimum coverage guarantee for all the different sensor types. Some global regularity conditions in order to guarantee a fair level of coverage for each sensor type to each target are also taken into account in a second variant of the proposed problem. For both problem variants we developed an exact approach, which is based on a column generation algorithm whose subproblem is either solved heuristically by means of a genetic algorithm or optimally by an appropriate ILP formulation. In our computational tests the proposed genetic algorithm is shown to be able to dramatically speed up the procedure, enabling the resolution of large-scale instances within reasonable computational times.     

Evaluation of Routing with Robustness to the Variation in Traffic Demand

In this paper, we focus on routing problem in the face of variation in traffic demands. We implement a Robust Routing algorithm (RRT) with an aim of satisfying networking goals such as load balancing, routing robustness to the range of traffic demand matrices or to the traffic changes caused by uncertain traffic demands. We conduct simulation experiments on range of topologies that includes, real network and randomly generated synthetic network topologies. Simulation results show marked improvement in the maximum link utilization compare to Open Shortest Path First. K-shortest path implementation of RRT can be extended for Multi Protocol Level Switching.     

基于不定期决策过程的最短路径搜索算法

不定期决策过程具有广泛的应用领域。该文针对基于不定期决策过程的段数不定线路网,在动态规划的基础上,提出了SPUCN算法(ShortestPathProblemofUncertainColumnNetwork),该算法通过对UCN模型进行分析转换,建立起能够以动态规划基本方程进行分析求解的理想模型,然后对该模型进行动态规划的后向分析求解,文章给出了算法的正确性和理论性证明,最后通过实例验证了算法的有效性。     

Traffic recovery time constrained shared sub-path protection algorithm in survivable WDM networks

With the development of real-time applications, the traffic recovery time, which is defined as the duration between the failure occurrence on the working path and the interruptive traffic has been successfully switched to the backup path, has become the basic Quality-of-Service (QoS) requirement in survivable WDM networks. In this paper, we address the problem of shared sub-path protection with considering the constraint of traffic recovery time and propose a new heuristic algorithm called Traffic recovery time Constrained Shared Sub-Path Protection (TC_SSPP) to compute the working path and the Shared-Risk-Link-Group (SRLG)-disjoint backup sub-paths. The main target of our work is to improve the resource utilization ratio and reduce the blocking probability for dynamic network environment. By properly setting the delay parameter for each link and running the Delay Constrained Shortest Path Algorithm (DCSPA) to compute the backup sub-paths, TC_SSPP can effectively guarantee the traffic recovery time. Simulation results show that the proposed TC_SSPP can outperform the traditional algorithms.     

大规模图上具有约束的多起点路径规划算法

路径规划查询是图数据上的一个基本问题,在众多的领域都有重要的应用价值。通常在实际问题中查询的路径是具有约束的,例如在外卖配送和共享出行问题中路径具有节点约束,其路径需要满足节点之间的先后关系约束。目前对于具有节点约束的路径查询问题,大多数的工作都在研究单起点的节点约束路径查询,但很难拓展到多起点节点约束问题中。因为具有节点约束的多起点路径查询问题是NP-hard的,所以该问题的大多数已有方法是使用贪心增量处理,但对于处理静态规则集拓展性不足。因此,提出了基于子路径的启发式算法和基于约束集拓展的精确算法,并在真实数据集上验证了算法的有效性。实验结果表明,启发式算法能够给出问题的精确解,而启发式算法能快速给出较好的近似解。