Abstract
In a dynamic network, the quickest path problem asks for a path minimizing the time needed to send a given amount of flow from source to sink along this path. In practical settings, for example in evacuation or transportation planning, the reliability of network arcs depends on the specific scenario of interest. In this circumstance, the question of finding a quickest path among all those having at least a desired path reliability arises. In this article, this reliable quickest path problem is solved by transforming it to the restricted quickest path problem. In the latter, each arc is associated a nonnegative cost value and the goal is to find a quickest path among those not exceeding a predefined budget with respect to the overall (additive) cost value. For both, the restricted and reliable quickest path problem, pseudopolynomial exact algorithms and fully polynomial-time approximation schemes are proposed.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bang, Y.C., Choo, H., Mun, Y.: Reliability problem on all pairs quickest paths. In: Sloot, P.M.A., Abramson, D., Bogdanov, A.V., Gorbachev, Y.E., Dongarra, J., Zomaya, A.Y. (eds.) ICCS 2003. LNCS, vol. 2660, pp. 518–523. Springer, Heidelberg (2003)
Bang, Y.C., Hong, I., Lee, S., Ahn, B.: On algorithms for minimum-cost quickest paths with multiple delay-bounds. In: Laganá, A., Gavrilova, M.L., Kumar, V., Mun, Y., Tan, C.J.K., Gervasi, O. (eds.) ICCSA 2004. LNCS, vol. 3043, pp. 1125–1133. Springer, Heidelberg (2004)
Chen, Y.: Finding the k quickest simple paths in a network. Inform. Process. Lett. 50(2), 89–92 (1994)
Chen, Y., Chin, Y.: The quickest path problem. Comput. Oper. Res. 17(2), 153–161 (1990)
Clímaco, J., Pascoal, M., Craveirinha, J., Captivo, M.: Internet packet routing: Application of a K-quickest path algorithm. European J. Oper. Res. 181(3), 1045–1054 (2007)
Garey, M., Johnson, D.: Computers and Intractability. A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. W.H. Freeman, San Francisco (1979)
Hamacher, H., Tjandra, S.: Mathematical modelling of evacuation problems–a state of the art. In: Schreckenberger, M., Sharma, S. (eds.) Pedestrian and Evacuation Dynamics, pp. 227–266. Springer, Berlin (2002)
Hassin, R.: Approximation schemes for the restricted shortest path problem. Math. Oper. Res. 17(1), 36–42 (1992)
Lin, Y.: Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network. Comput. Oper. Res. 30(4), 567–575 (2003)
Lin, Y.: System reliability for quickest path problems under time threshold and budget. Comput. Math. Appl. 60, 2326–2332 (2010)
Lorenz, D., Raz, D.: A simple efficient approximation scheme for the restricted shortest path problem. Oper. Res. Lett. 28(5), 213–219 (2001)
Moore, M.: On the fastest route for convoy-type traffic in flowrate-constrained networks. Transport. Sci. 10(2), 113–124 (1976)
Papadimitriou, C., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs (1982)
Rosen, J., Sun, S., Xue, G.: Algorithms for the quickest path problem and the enumeration of quickest paths. Comput. Oper. Res. 18(6), 579–584 (1991)
Ruzika, S., Thiemann, M.: Min-max quickest path problems. Tech. rep., University of Kaiserslautern, Department of Mathematics, Report in Wirtschaftsmathematik Nr. 130 (2010)
Xue, G.: End-to-end data paths: quickest or most reliable? IEEE Commun. Lett. 2(6), 156–158 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ruzika, S., Thiemann, M. (2011). Reliable and Restricted Quickest Path Problems. In: Pahl, J., Reiners, T., Voß, S. (eds) Network Optimization. INOC 2011. Lecture Notes in Computer Science, vol 6701. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21527-8_36
Download citation
DOI: https://doi.org/10.1007/978-3-642-21527-8_36
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21526-1
Online ISBN: 978-3-642-21527-8
eBook Packages: Computer ScienceComputer Science (R0)