The most likely path on series-parallel networks

✍ Scribed by Daniel Reich; Leo Lopes

• Publisher: John Wiley and Sons
• Year: 2010
• Tongue: English
• Weight: 281 KB
• Volume: 58
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.20416

✦ Synopsis

Abstract

In this article, we present a stochastic shortest path problem that we refer to as the Most Likely Path Problem (MLPP). We demonstrate that optimal solutions to the MLPP are not composed of optimal subpaths, which limits the computational tractability of exact solution methods. On series‐parallel networks, we produce analytical bounds for the MLPP's optimality indices, the probabilities of given paths in the network being shortest, and compute these bounds efficiently via numerical integration. These bounds can also be used independently of the MLPP to gain further understanding for paths of interest that are identified by other stochastic shortest path frameworks, e.g., robust shortest paths or expected shortest paths. Additionally, we present a heuristic method that uses dynamic programming and ordinal optimization to identify an MLP on series‐parallel networks. Our computational study shows our bounds to be tight in a majority of test networks and shows our heuristic to be both efficient and highly accurate for identifying an MLP in all test networks. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 58(1), 68–80 2011