Optimal path selection approach for fuzzy reliable shortest path problem. (English) Zbl 1366.90071
Summary: In real-world problems, the shortest path might contain more edges which may be full of uncertainty and risk of potential data loss. In this paper, we propose a novel algorithm, solving the fuzzy reliable shortest path problem in a mixed network with various fuzzy arc lengths, for dealing with reliability and safety in the presence of uncertainty. For this purpose, it makes us try to avoid the path containing lots of edges. Here, we first present a \(R_s\) path selection approach for computing the fuzzy reliable shortest path in a network with several typesof fuzzy arc lengths by defining a distance function for fuzzy weight of edge using \(\alpha-cut\). Finally, examples are worked out to illustrate the application of the fuzzy reliable shortest path. Extensive experiments using fuzzy networks and the results of statistical tests have shown that the proposed method has an appropriate trade-off both the reliable path and the shortest path.
MSC:
| 90B18 | Communication networks in operations research |
| 90B10 | Deterministic network models in operations research |
| 05C38 | Paths and cycles |
Keywords:
fuzzy reliable shortest path; fuzzy arc length; \(\alpha-cut\) and \(D_{p,q}\) distance function; fuzzy number; communication networkReferences:
| [1] | Nepomniaschaya, A simple implementation of dijkstra’s shortest path algorithm on associative parallel processors, Journal of Intelligent and Fuzzy Systems 43 pp 227– (2000) · Zbl 0965.68126 |
| [2] | Elimam, Two engineering applications of a constrained shortest-path model, European Journal of Operational Research 103 pp 426– (1997) · Zbl 0926.90061 · doi:10.1016/S0377-2217(97)00149-5 |
| [3] | Wakuta, A multi-objective shortest path problem, Mathematical Methods of Operations Research 54 pp 445– (2001) · Zbl 1031.90054 · doi:10.1007/s001860100169 |
| [4] | Surynek and Pavel, On the complexity of optimal parallel cooperative path-finding, Journal of Intelligent and Fuzzy Systems 137 (2015), 517–548. · Zbl 1357.68248 |
| [5] | Zhu, Approximate path searching for supporting shortest path queries on road networks, Information Sciences 325 pp 409– (2015) · doi:10.1016/j.ins.2015.06.045 |
| [6] | Akay, A GIS-based decision support system for determining the shortest and safest route to forest fires: A case study in Mediterranean Region of Turkey, Environmental Monitoring and Assessment 184 pp 1391– (2012) · doi:10.1007/s10661-011-2049-z |
| [7] | Messica, Optimal expenditure patterns of a double-path engineering project, Journal of Optimization Theory and Applications 105 pp 441– (2000) · Zbl 0958.90032 · doi:10.1023/A:1004670120484 |
| [8] | Yang, Quasi-linear optimal path controller applied to post impact vehicle dynamics, IEEE Transactions on Intelligent Transportation Systems 13 pp 1586– (2012) · doi:10.1109/TITS.2012.2204875 |
| [9] | Salmanpour, Optimal path planning for mobile robot using Intelligent Water Drops algorithm, Journal of Intelligent and Fuzzy Systems 27 pp 1519– (2014) |
| [10] | Nip, A combination of flow shop scheduling and shortest path problem, Journal of Combinatorial Optimization 29 pp 36– (2015) · Zbl 1328.90129 · doi:10.1007/s10878-013-9670-4 |
| [11] | Dubois D. , and Prade H. , Fuzzy Sets and Systems: Theory and Application, New York: Academic Press, 1980. · Zbl 0444.94049 |
| [12] | Eppstein, Finding the k-shortest paths, Proceedings of the 35nd Annual Symposium on Foundations of Computer Science pp 154– (1994) · Zbl 0912.05057 · doi:10.1109/SFCS.1994.365697 |
| [13] | Mahdavi, A dynamic programming approach for finding shortest chains in a fuzzy network, Applied Soft Computing 9 pp 503– (2009) · doi:10.1016/j.asoc.2008.07.002 |
| [14] | Tajdin, A novel approach for finding a shortest path in a mixed fuzzy network, Wireless Sensor Network 2 pp 148– (2010) · doi:10.4236/wsn.2010.22020 |
| [15] | Tajdin, Computing a fuzzy shortest path in a network with mixed fuzzy arc lengths using {\(\alpha\)} – cuts, Computers and Mathematics with Application 60 pp 989– (2010) · Zbl 1201.90196 · doi:10.1016/j.camwa.2010.03.038 |
| [16] | Hassanzadeh, A genetic algorithm for solving fuzzy shortest path problems with mixed fuzzy arc lengths, Mathematical and Computer Modeling 57 pp 84– (2013) · Zbl 1305.90429 · doi:10.1016/j.mcm.2011.03.040 |
| [17] | Nayeem, A new expected value model for the fuzzy shortest path problem, pp, Proceedings of the 2nd International Conference on Soft Computing for Problem Solving pp 209– (2014) |
| [18] | Zhang, A biologically inspired optimization Algorithm for solving fuzzy shortest path problems with mixed fuzzy arc lengths, Journal of Optimization Theory and Applications 163 pp 1049– (2014) · Zbl 1305.65157 · doi:10.1007/s10957-014-0542-6 |
| [19] | Zhang, A bi-objective model for uncertain multi-modal shortest path problems, Joural of Uncertainty Analysis and Applications 3 pp 2– (2015) |
| [20] | Lin, The fuzzy shortest path problem and its most vital arcs, Fuzzy Sets and Systems 58 pp 343– (1993) · Zbl 0804.90138 · doi:10.1016/0165-0114(93)90508-F |
| [21] | Frank, Shortest paths in probabilistic graphs, Operations Research 17 pp 583– (1969) · Zbl 0176.48301 · doi:10.1287/opre.17.4.583 |
| [22] | Chen, Path finding under uncertainty, Journal of Advanced Transportation 39 pp 19– (2005) · doi:10.1002/atr.5670390104 |
| [23] | Chen, Finding reliable shortest paths in road networks under uncertainty, Networks and Spatial economics 13 pp 123– (2013) · Zbl 1332.90032 · doi:10.1007/s11067-012-9175-1 |
| [24] | Koller D. , and Friedman N. , Probabilistic Graphical Models: Principles and Techniques, Massachusetts, US: MIT Press, 2009. · Zbl 1183.68483 |
| [25] | Qiu, New approach to delay-dependent H control for continuous-time Markovian jump systems with time-varying delay and deficient transition descriptions, Journal of the Franklin Institute 352 pp 189– (2015) · Zbl 1307.93444 · doi:10.1016/j.jfranklin.2014.10.022 |
| [26] | Qiu, Recent advances on fuzzy-model-based nonlinear networked control systems: A survey, IEEE Transactions on Industrial Electronics 63 pp 1207– (2016) · doi:10.1109/TIE.2015.2504351 |
| [27] | Qiu J.B. , Ding S.X. , Gao H.J. , and Yin S. , Fuzzy-model-based reliable static output feedback H control of nonlinear hyperbolic PDE systems, IEEE Transactions on Fuzzy Systems 99 (2015), doi: 10.1109/TFUZZ.2015.2457934 · doi:10.1109/TFUZZ.2015.2457934 |
| [28] | Qiu J.B. , Ding S.X. , Li L.L. , and Yin S. , Reliable fuzzy output feedback control of nonlinear parabolic distributed parameter systems with sensor faults, 29 (2015), 1197–1208. · Zbl 1361.93027 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
