A comprehensive survey on the quickest path problem

This work is a survey on a special minsum-maxmin bicriteria problem, known as the quickest path problem, that can model the transmission of data between two nodes of a network. Moreover, the authors review the problems of ranking the K quickest paths, and the K quickest loopless paths, and compare them in terms of the worst-case complexity order. The classification presented led to the proposal of a new variant of a known K quickest loopless paths algorithm. Finally, applications of quickest path algorithms are mentioned, as well as some comparative empirical results. This work was partially supported by FEDER and OE, under the projects POCTI/MAT/139/2001, POCTI/ISFL-1/152, POSI/SRI/37346/2001, and POCTI/MAT/37707/2001.     

Reliability evaluation according to a routing scheme for multi-state computer networks under assured accuracy rate

In many real-time networks such as computer networks, each arc has stochastic capacity, lead time, and accuracy rate. Such a network is named a multi-state computer network (MSCN). Under the strict assumption that the capacity of each arc is deterministic, the quickest path (QP) problem is to find a path that sends a specific amount of data with minimum transmission time. From the viewpoint of internet quality, the transmission accuracy rate is one of critical performance indicators to assess internet network for system administrators and customers. Under both assured accuracy rate and time constraint, this paper extends the QP problem to discuss the flow assignment for a MSCN. An efficient algorithm is proposed to find the minimal capacity vector meeting such requirements. The system reliability, the probability to send \(d\) units of data through multiple minimal paths under both assured accuracy rate and time constraint, can subsequently be computed. Furthermore, two routing schemes with spare minimal paths are adopted to reinforce the system reliability. The enhanced system reliability according to the routing scheme is calculated as well. The computational complexity in both the worst case and average case are analyzed.     

Computational experiments with a lazy version of a <Emphasis Type="Italic">K</Emphasis> quickest simple path ranking algorithm

The quickest path problem is related to the classical shortest path problem, but its objective function concerns the transmission time of a given amount of data throughout a path, which involves both cost and capacity. The K-quickest simple paths problem generalises the latter, by looking for a given number K of simple paths in non-decreasing order of transmission time. Two categories of algorithms are known for ranking simple paths according to the transmission time. One is the adaptation of deviation algorithms for ranking shortest simple paths (Pascoal et al. in Comput. Oper. Res. 32(3):509–520, 2005; Rosen et al. in Comput. Oper. Res. 18(6):571–584, 1991), and another is based on ranking shortest simple paths in a sequence of networks with fixed capacity lower bounds (Chen in Inf. Process. Lett. 50:89–92, 1994), and afterwards selecting the K quickest ones. After reviewing the quickest path and the K-quickest simple paths problems we describe a recent algorithm for ranking quickest simple paths (Pascoal et al. in Ann. Oper. Res. 147(1):5–21, 2006). This is a lazy version of Chen’s algorithm, able to interchange the calculation of new simple paths and the output of each k-quickest simple path. Finally, the described algorithm is computationally compared to its former version, as well as to deviation algorithms.      

On transmission time through k minimal paths of a capacitated-flow network

The quickest path problem is to minimize the transmission time for sending a specified amount of data through a single minimal path. Two deterministic attributes are involved herein; the capacity and the lead time. However, in many real-life networks such as computer systems, urban traffic systems, etc., the arc capacity should be multistate due to failure, maintenance, etc. Such a network is named a capacitated-flow network. The minimum transmission time is thus not a fixed number. This paper is mainly to evaluate system reliability that d units of data can be transmitted through k minimal paths under time constraint T. A simple algorithm is proposed to generate all minimal capacity vectors meeting the demand and time constraints. The system reliability is subsequently computed in terms of such vectors. The optimal k minimal paths with highest system reliability can further be derived.     

The shortest path problem with forbidden paths

We consider a variant of the constrained shortest path problem, where the constraints come from a set of forbidden paths (arc sequences) that cannot be part of any feasible solution. Two solution approaches are proposed for this variant. The first uses Aho and Corasick's keyword matching algorithm to filter paths produced by a k-shortest paths algorithm. The second generalizes Martins' deviation path approach for the k-shortest paths problem by merging the original graph with a state graph derived from Aho and Corasick's algorithm. Like Martins' approach, the second method amounts to a polynomial reduction of the shortest path problem with forbidden paths to a classic shortest path problem. Its significant advantage over the first approach is that it allows considering forbidden paths in more general shortest path problems such as the shortest path problem with resource constraints.     

Calculation of minimal capacity vectors through k minimal paths under budget and time constraints

Reducing the transmission time is an important issue for a flow network to transmit a given amount of data from the source to the sink. The quickest path problem thus arises to find a single path with minimum transmission time. More specifically, the capacity of each arc is assumed to be deterministic. However, in many real-life networks such as computer networks and telecommunication networks, the capacity of each arc is stochastic due to failure, maintenance, etc. Hence, the minimum transmission time is not a fixed number. Such a network is named a stochastic-flow network. In order to reduce the transmission time, the network allows the data to be transmitted through k minimal paths simultaneously. Including the cost attribute, this paper evaluates the probability that d units of data can be transmitted under both time threshold T and budget B. Such a probability is called the system reliability. An efficient algorithm is proposed to generate all of lower boundary points for (d, T, B), the minimal capacity vectors satisfying the demand, time, and budget requirements. The system reliability can then be computed in terms of such points. Moreover, the optimal combination of k minimal paths with highest system reliability can be obtained.     

On Solving Quickest Time Problems in Time-Dependent, Dynamic Networks

In this paper, a pseudopolynomial time algorithm is presented for solving the integral time-dependent quickest flow problem (TDQFP) and its multiple source and sink counterparts: the time-dependent evacuation and quickest transshipment problems. A more widely known, though less general version, is the quickest flow problem (QFP). The QFP has historically been defined on a dynamic network, where time is divided into discrete units, flow moves through the network over time, travel times determine how long each unit of flow spends traversing an arc, and capacities restrict the rate of flow on an arc. The goal of the QFP is to determine the paths along which to send a given supply from a single source to a single sink such that the last unit of flow arrives at the sink in the minimum time. The main contribution of this paper is the time-dependent quickest flow (TDQFP) algorithm which solves the TDQFP, i.e. it solves the integral QFP, as defined above, on a time-dependent dynamic network, where the arc travel times, arc and node capacities, and supply at the source vary with time. Furthermore, this algorithm solves the time-dependent minimum time dynamic flow problem, whose objective is to determine the paths that lead to the minimum total time spent completing all shipments from source to sink. An optimal solution to the latter problem is guaranteed to be optimal for the TDQFP. By adding a small number of nodes and arcs to the existing network, we show how the algorithm can be used to solve both the time-dependent evacuation and the time-dependent quickest transshipment problems. This revised version was published online in August 2006 with corrections to the Cover Date.     

所有点对之间最快路问题

所有点对之间最快路问题就是要在所有点对(Vs，Vt)之间传送数据δs,t,并找出一条最快的路线．解决所有点对之间最快路问题的关键是产生有效解的等价集合．运用动态点对最短路的算法，本文首先设计了一个时间复杂性为O(mn^2)的产生有效解等价集合的算法，然后研究了静态点对之间最快路问题和动态点对之间最快路问题，其算法的时间复杂性分别为O(mn^2)和O(m^2n^2)．最后本文研究了求和对最小的路问题，证明该问题可以在O(mn^2)时间内解决．     

The Safest Escape problem

In this paper, the Safest Escape (SEscape) problem is defined for providing evacuation plans for emergency egress from large buildings or a geographical region. The objective of the SEscape problem is to determine the set of paths and number of evacuees to send along each path such that the minimum probability of arrival at an exit for any evacuee is maximized. Such paths minimize the risk incurred by the evacuees who are forced to take the greatest risk. The problem is considered in a dynamic and time-varying network, where arc capacities are recaptured over time, arc traversal times are time-varying and arc capacities are random variables with probability distribution functions that vary with time. An exact algorithm, the SEscape algorithm, is proposed to address this problem.     

Time version of the shortest path problem in a stochastic-flow network

Many studies on hardware framework and routing policy are devoted to reducing the transmission time for a flow network. A time version of the shortest path problem thus arises to find a quickest path, which sends a given amount of data from the unique source to the unique sink with minimum transmission time. More specifically, the capacity of each arc in the flow network is assumed to be deterministic. However, in many real-life networks, such as computer systems, telecommunication systems, etc., the capacity of each arc should be 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. We extend the quickest path problem to evaluating the probability that d$d$ units of data can be sent under the time constraint T$T$. Such a probability is named the system reliability. In particular, the data are transmitted through two minimal paths simultaneously in order to reduce the transmission time. A simple algorithm is proposed to generate all (d,T)$(d,T)$-MPs and the system reliability can then be computed in terms of (d,T)$(d,T)$-MPs. Moreover, the optimal pair of minimal paths with highest system reliability could be obtained.     

Algorithms for the quickest path problem and the reliable quickest path problem

The quickest path problem consists of finding a path in a directed network to transmit a given amount of items from an origin node to a destination node with minimal transmission time, when the transmission time depends on both the traversal times of the arcs, or lead time, and the rates of flow along arcs, or capacity. In telecommunications networks, arcs often also have an associated operational probability of the transmission being fault free. The reliability of a path is defined as the product of the operational probabilities of its arcs. The reliability as well as the transmission time are of interest. In this paper, algorithms are proposed to solve the quickest path problem as well as the problem of identifying the quickest path whose reliability is not lower than a given threshold. The algorithms rely on both the properties of a network which turns the computation of a quickest path into the computation of a shortest path and the fact that the reliability of a path can be evaluated through the reliability of the ordered sequence of its arcs. Other constraints on resources consumed, on the number of arcs of the path, etc. can also be managed with the same algorithms.     

On a multicriteria shortest path problem

Multicriteria shortest path problems have not been treated intensively in the specialized literature, despite their potential applications. In fact, a single objective function may not be sufficient to characterize a practical problem completely. For instance, in a road network several parameters (as time, cost, distance, etc.) can be assigned to each arc. Clearly, the shortest path may be too expensive to be used. Nevertheless the decision-maker must be able to choose some solution, possibly not the best for all the criteria.In this paper we present two algorithms for this problem. One of them is an immediate generalization of the multiple labelling scheme algorithm of Hansen for the bicriteria case. Based on this algorithm, it is proved that any pair of nondominated paths can be connected by nondominated paths. This result is the support of an algorithm that can be viewed as a variant of the simplex method used in continuous linear multiobjective programming. A small example is presented for both algorithms.     

A bicriterion shortest path algorithm

Among the network models, one of the more popular is the so called shortest path problem. This model is used whenever it is intended to minimize a linear function which represents a distance between a predetermined pair of nodes in a given network.Often a single objective function is not sufficient to completely characterize some real-world problems. For instance, in a road network two parameters - as cost and time - can be assigned to each arc. Clearly the fastest path may be too costly. Nevertheless the decision-maker must choose one solution, possibly not the best for both criteria.In this paper we present an algorithm for this problem. With this algorithm a special set of paths (the set of Pareto optimal paths) is determined. One objective for any Pareto optimal path can not be improved without worsening the other one.     

Bicriteria path problem minimizing the cost and minimizing the number of labels

We address a bicriterion path problem where each arc is assigned with a cost value and a label (such as a color). The first criterion intends to minimize the total cost of the path (the summation of its arc costs), while the second intends to get the solution with a minimal number of different labels. Since these criteria, in general, are conflicting criteria we develop an algorithm to generate the set of non-dominated paths. Computational experiments are presented and results are discussed.     

模糊最短路的一种算法

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

Optimal paths in bi-attribute networks with fractional cost functions

An important routing problem is to determine an optimal path through a multi-attribute network which minimizes a cost function of path attributes. In this paper, we study an optimal path problem in a bi-attribute network where the cost function for path evaluation is fractional. The problem can be equivalently formulated as the “bi-attribute rational path problem” which is known to be NP-complete. We develop an exact approach to find an optimal simple path through the network when arc attributes are non-negative. The approach uses some path preference structures and elimination techniques to discard, from further consideration, those (partial) paths that cannot be parts of an optimal path. Our extensive computational results demonstrate that the proposed method can find optimal paths for large networks in very attractive times.     

On the analysis of optimization problems in arc-dependent networks

This paper is concerned with the design and analysis of algorithms for optimization problems in arc-dependent networks. A network is said to be arc-dependent if the cost of an arc $a$ depends upon the arc taken to enter $a$. These networks are fundamentally different from traditional networks in which the cost associated with an arc is a fixed constant and part of the input. We first study the arc-dependent shortest path (ADSP) problem, which is also known as the suffix-1 path-dependent shortest path problem in the literature. This problem has a polynomial time solution if the shortest paths are not required to be simple. The ADSP problem finds applications in a number of domains, including highway engineering, turn penalties and prohibitions, and fare rebates. In this paper, we are interested in the ADSP problem when restricted to simple paths. We call this restricted version the simple arc-dependent shortest path (SADSP) problem. We show that the SADSP problem is NP-complete. We present inapproximability results and an exact exponential algorithm for this problem. We also extend our results for the longest path problem in arc-dependent networks. Additionally, we explore the problem of detecting negative cycles in arc-dependent networks and discuss its computational complexity. Our results include variants of the negative cycle detection problem such as longest, shortest, heaviest, and lightest negative simple cycles.²     

Shortest path algorithms for knapsack type problems

The group knapsack and knapsack problems are generalised to shortest path problems in a class of graphs called knapsack graphs. An efficient algorithm is described for finding shortest paths provided that arc lengths are non-negative. A more efficient algorithm is described for the acyclic case which includes the knapsack problem. In this latter case the algorithm reduces to a known algorithm.     

The quickest path problem with batch constraints

The quickest path problem has been proposed to cope with flow problems through networks whose arcs are characterized by both travel times and flowrate constraints. Basically, it consists in finding a path in a network to transmit a given amount of items from a source node to a sink in as little time as possible, when the transmission time depends on both the traversal times of the arcs and the rates of flow along arcs. This paper is focused on the solution procedure when the items transmission must be partitioned into batches with size limits. For this problem we determine how many batches must be made and what the sizes should be.     

An equivalent subproblem relaxation for improving the solution of a class of transportation scheduling problems

In this paper an algorithm is presented for determining the K best paths that may contain cycles in a directed network.The basic idea behind the algorithm is quite simple. Once the best path has been determined it is excluded from the network in such a way that no new path is formed and no more paths are excluded. This step leads to an enlarged network where all the paths, but the best one, can be determined. The method is repeated until the desired paths have been computed.The proposed algorithm can be used not only for the classical K shortest paths problem but also for ranking paths under a nonlinear objective function, provided that an algorithm to determine the best path exists.Computational results are presented and comparisons with other approaches for the classical problem are made.