Error bounds for stochastic shortest path problems

For stochastic shortest path problems, error bounds for value iteration due to Bertsekas elegantly generalize the classic MacQueen–Porteus error bounds for discounted infinite-horizon Markov decision problems, but incur prohibitive computational overhead. We derive bounds on these error bounds that can be computed with little or no overhead, making them useful in practice—especially so, since easily-computed error bounds have not previously been available for this class of problems.     

A comparison of heuristic best-first algorithms for bicriterion shortest path problems

A variety of algorithms have been proposed to solve the bicriterion shortest path problem. This article analyzes and compares the performance of three best-first (label-setting) algorithms that accept heuristic information to improve efficiency. These are NAMOA^∗, MOA^∗, and Tung & Chew’s algorithm (TC). A set of experiments explores the impact of heuristic information in search efficiency, and the relative performance of the algorithms. The analysis reveals that NAMOA^∗ is the best option for difficult problems. Its time performance can benefit considerably from heuristic information, though not in all cases. The performance of TC is similar but somewhat worse. However, the time performance of MOA^∗ is found to degrade considerably with the use of heuristic information in most cases. Explanations are provided for these phenomena.     

Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function

In this paper, the stochastic shortest path problem of determining a path that maximizes the expected utility is considered. The nature of the utility function used to evaluate paths is of a decreasing deadline type. The principal contribution of this paper is the development of exact algorithms that use two types of pruning techniques that are incorporated in labeling procedures. One type of pruning makes use of the concept of local preference relations while the other type makes use of relaxations. Specifically two algorithms are developed, each containing the same preference relation, but two different relaxations. Our extensive computational testing indicate that both these algorithms are able to solve even large size problems quickly. More importantly, even for large problems, both the algorithms solved them by enumerating a very small percentage of all paths.     

Distributionally robust stochastic shortest path problem

This paper considers a stochastic version of the shortest path problem, the Distributionally Robust Stochastic Shortest Path Problem(DRSSPP) on directed graphs. In this model, the arc costs are deterministic, while each arc has a random delay. The mean vector and the second-moment matrix of the uncertain data are assumed known, but the exact information of the distribution is unknown. A penalty occurs when the given delay constraint is not satisfied. The objective is to minimize the sum of the path cost and the expected path delay penalty. As it is NP-hard, we approximate the DRSSPP with a semidefinite programming (SDP for short) problem, which is solvable in polynomial time and provides tight lower bounds.     

Algorithms for time-dependent bicriteria shortest path problems

In this paper we generalize the classical shortest path problem in two ways. We consider two objective functions and time-dependent data. The resulting problem, called the time-dependent bicriteria shortest path problem (TdBiSP), has several interesting practical applications, but has not gained much attention in the literature. After reviewing relevant literature we develop a new algorithm for the TdBiSP with non-negative data. Numerical tests show the superiority of our algorithm compared with an existing algorithm in the literature. Furthermore, we discuss algorithms for the TdBiSP with negative travel times and costs.     

Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs

This paper addresses sensitivity analysis questions concerning the shortest path problem and the maximum capacity path problem in an undirected network. For both problems, we determine the maximum and minimum weights that each edge can have so that a given path remains optimal. For both problems, we show how to determine these maximum and minimum values for all edges in O(m + K log K) time, where m is the number of edges in the network, and K is the number of edges on the given optimal path.     

An efficient algorithm for perturbed shortest path problems

We present an efficient algorithm for perturbed shortest paths problems that arise, e.g., in dynamic games. Via a minmax version of Dijkstra's algorithm we compute piecewise constant upper and lower bounds on the upper value function of the game. Convergence of the bounds in the limit of vanishing cell diameter can be proved. The method is numerically demonstrated on a simple 2d dynamic game, the homicidal chauffeur. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Solvingk-shortest and constrained shortest path problems efficiently

In this paper, we examine the problems of finding thek-shortest paths, thek-shortest paths without repeated nodes, and the shortest path with a single side constraint between an origin and destination pair. Distances are assumed to be non-negative, but networks may be either directed or undirected. Two versions of algorithms for all these problems are compared. The computational results show that, in each case, the advantage of the adaptive version (as measured by total number of permanent labels) grows with the problem size.The views and opinions in this paper are strictly those of the authors and not necessarily those of the IBM Corporation.     

Applications of shortest path algorithms to matrix scalings

Summary A symmetric scaling of a nonnegative, square matrixA is a matrixXAX ^–1, whereX is a nonsingular, nonnegative diagonal matrix. By associating a family of weighted directed graphs with the matrixA we are able to adapt the shortest path algorithms to compute an optimal scaling ofA, where we call a symmetric scalingA ofA optimal if it minimizes the maximum of the ratio of non-zero elements.Dedicated to Professor F.L. Bauer on the occasion of his 60th birthdayThe first author was partially supported by the Deutsche Forschungsgemeinschaft under grant GO 270/3, the second author by the U.S. National Science Foundation under grand MCS-8026132     

Accelerated modified policy iteration algorithms for Markov decision processes

We propose a new approach to accelerate the convergence of the modified policy iteration method for Markov decision processes with the total expected discounted reward. In the new policy iteration an additional operator is applied to the iterate generated by Markov operator, resulting in a bigger improvement in each iteration.     

A column generation method for inverse shortest path problems

In this paper we formulate an inverse shortest path problem as a special linear programming problem. A column generation scheme is developed that is able to keep most columns of the LP model implicit and to generate necessary columns by shortest path algorithms. This method can get an optimal solution in finitely many steps. Some numerical results are reported to show that the algorithm has a good performance.The authors gratefully acknowledge the partial support of Croucher Foundation.     

An applicable method for solving the shortest path problems

A theorem of Hardy, Littlewood, and Polya, first time is used to find the variational form of the well known shortest path problem, and as a consequence of that theorem, one can find the shortest path problem via quadratic programming. In this paper, we use measure theory to solve this problem. The shortest path problem can be written as an optimal control problem. Then the resulting distributed control problem is expressed in measure theoretical form, in fact an infinite dimensional linear programming problem. The optimal measure representing the shortest path problem is approximated by the solution of a finite dimensional linear programming problem.     

Dynamic shortest path problems with time-varying costs

This paper concerns the problem of finding shortest paths from one node to all other nodes in networks for which arc costs can vary with time, each arc has a transit time, and parking with a corresponding time-varying cost is allowed at the nodes. The transit times can also take negative values. A general labeling method, as well as several implementations, are presented for finding shortest paths and detecting negative cycles under the assumption that arc traversal costs are piecewise linear and node parking costs are piecewise constant.     

Modeling wildfire propagation with Delaunay triangulation and shortest path algorithms

In this paper, a methodology for modeling surface wildfire propagation through a complex landscape is presented. The methodology utilizes a Delaunay triangulation to represent surface fire spread within the landscape. A procedure to construct the graph and estimate the rate of spread along the edges of a network is discussed. After the Delaunay data structure is constructed, a two pass shortest path algorithm is incorporated to estimate the minimum travel time paths and fire arrival times. Experimental results are also included.     

Improved approximations for two-stage min-cut and shortest path problems under uncertainty

Mathematical Programming - In this paper, we study the robust and stochastic versions of the two-stage min-cut and shortest path problems introduced in Dhamdhere et al. (in How to pay, come what...     

An aggregate label setting policy for the multi-objective shortest path problem

We consider label setting algorithms for the multi-objective shortest path problem with any number of sum and bottleneck objectives. We propose a weighted sum aggregate ordering of the labels, specifically tailored to combine sum and bottleneck objectives. We show that the aggregate order leads to a consistent reduction of solution times (up to two-thirds) with respect to the classical lexicographic order.     

Improved algorithms for path partition and related problems

We study the L_∞ path partition problem: given a path of n weighted vertices and an integer k, remove k−1 edges from the path so that the maximum absolute deviation of the weights of the resulting k sub-paths from their mean is minimized. Previously, the best algorithm solves this problem in O(nklogk) time. We present an O(nk) time algorithm. We also give improved solutions for two related problems: the L_d path partition problem and the web proxies placement problem.