A precise solution to the shortest path optimization problem in graphs using Z-numbers

Nurdoğan Güner; Halit Orhan; Tofigh Allahviranloo; Bilal Usanmaz; Nurdoğan Güner; Halit Orhan; Tofigh Allahviranloo; Bilal Usanmaz

doi:10.3934/math.20241454

AIMS Mathematics

2024, Volume 9, Issue 11: 30100-30121. doi: 10.3934/math.20241454

Previous Article Next Article

Research article

A precise solution to the shortest path optimization problem in graphs using Z-numbers

1.
Department of Mathematics, Faculty of Science, Atatürk University, 25240 Erzurum, Türkiye
2.
Research Center of Performance and Productivity Analysis, Istinye University, Istanbul, Türkiye
3.
Department of Computer Engineering, Faculty of Engineering, Atatürk University, 25240 Erzurum, Türkiye

Received: 26 August 2024 Revised: 05 October 2024 Accepted: 10 October 2024 Published: 23 October 2024
MSC : 90C70

Communication networks are exposed to internal or external risks that can affect all or part of the system. The most important components that form the infrastructure of these systems are routers, which act as nodes. In the field of graph theory, there are sophisticated techniques that can be used to optimize the path of a packet as it travels through various routers from its origin to its destination. A notable example of such an algorithm is Dijkstra's algorithm, which is designed to efficiently determine the shortest path. The algorithm works under the assumption that the system operates under ideal conditions. Real-time systems can perform better if risk factors and optimal conditions are taken into account. The relationship between the nodes can be expressed by various metrics such as distance, delay, and bandwidth. The aforementioned metrics facilitate the calculation of the optimal path, with the ultimate objective of achieving low-latency networks characterized by rapid response times. Round-trip time (RTT) can be employed as a metric for measuring enhancements in a range of latency types, including those associated with processing, transmission, queuing, and propagation. The use of Z-numbers was employed in this study to incorporate risk into the optimal path metric. RTT was the preferred metric and reliability was represented by fuzzy linguistic qualifiers. A comparison of several scenarios was shown using a numerical example of a communication network. It is expected that this study will have a significant impact on the evolution from models that consider only ideal conditions to real-time systems that include risks using Z-numbers.
- Z-number,
- Dijkstra algorithm,
- Z-graph, Z-cost,
- Z-ranking
Citation: Nurdoğan Güner, Halit Orhan, Tofigh Allahviranloo, Bilal Usanmaz. A precise solution to the shortest path optimization problem in graphs using Z-numbers[J]. AIMS Mathematics, 2024, 9(11): 30100-30121. doi: 10.3934/math.20241454

Related Papers:

Abstract

Communication networks are exposed to internal or external risks that can affect all or part of the system. The most important components that form the infrastructure of these systems are routers, which act as nodes. In the field of graph theory, there are sophisticated techniques that can be used to optimize the path of a packet as it travels through various routers from its origin to its destination. A notable example of such an algorithm is Dijkstra's algorithm, which is designed to efficiently determine the shortest path. The algorithm works under the assumption that the system operates under ideal conditions. Real-time systems can perform better if risk factors and optimal conditions are taken into account. The relationship between the nodes can be expressed by various metrics such as distance, delay, and bandwidth. The aforementioned metrics facilitate the calculation of the optimal path, with the ultimate objective of achieving low-latency networks characterized by rapid response times. Round-trip time (RTT) can be employed as a metric for measuring enhancements in a range of latency types, including those associated with processing, transmission, queuing, and propagation. The use of Z-numbers was employed in this study to incorporate risk into the optimal path metric. RTT was the preferred metric and reliability was represented by fuzzy linguistic qualifiers. A comparison of several scenarios was shown using a numerical example of a communication network. It is expected that this study will have a significant impact on the evolution from models that consider only ideal conditions to real-time systems that include risks using Z-numbers.

References

[1]	L. A. Zadeh, Fuzzy sets, Inf. Control, 8 (1965), 338–353. https://doi.org/10.1016/S0019-9958(65)90241-X doi: 10.1016/S0019-9958(65)90241-X
[2]	L. A. Zadeh, The concept of a linguistic variable and its application to approximate reasoning–-Ⅰ, Inf. Sci., 8 (1975), 199–249. https://doi.org/10.1016/0020-0255(75)90036-5 doi: 10.1016/0020-0255(75)90036-5
[3]	L. A. Zadeh, A note on Z-numbers, Inf. Sci., 181 (2011), 2923–2932. https://doi.org/10.1016/j.ins.2011.02.022 doi: 10.1016/j.ins.2011.02.022
[4]	B. Kang, D. Wei, Y. Li, Y. Deng, Decision making using Z-numbers under uncertain environment, J. Comput. Infor. Syst., 8 (2012), 2807–2814.
[5]	P. Patel, S. Rahimi, E. Khorasani, Applied Z-numbers, 2015 Annual Conf. North American Fuzzy Inf. Proc. Soc., 5 (2015), 1–6. https://doi.org/10.1109/NAFIPS-WConSC.2015.7284154 doi: 10.1109/NAFIPS-WConSC.2015.7284154
[6]	Z. Ren, H. Liao, Y. Liu, Generalized Z-numbers with hesitant fuzzy linguistic information and its application to medicine selection for the patients with mild symptoms of the COVID-19, Comput. Industr. Engin., 145 (2020), 106517. https://doi.org/10.1016/j.cie.2020.106517 doi: 10.1016/j.cie.2020.106517
[7]	T. Zamali, M. A. Lazim, Multi-criteria decision making based on Z-Number valuation for uncertain information, 2021 2nd Int. Conf. Artif. Intell. Data Sci., 2 (2021), 1–4. https://doi.org/10.1109/AiDAS53897.2021.9574134 doi: 10.1109/AiDAS53897.2021.9574134
[8]	B. Kang, D. Wei, Y. Li, Y. Deng, A method of converting Z-number to classical fuzzy number, J. Infor. Comput. Sci., 9 (2012), 703–709.
[9]	R. A. Aliev, A. Alizadeh, R. R. Aliyev, O. H. Huseynov, The arithmetic of Z-Numbers: Theory and applications, Singapore: World Scientific, 2015. https://doi.org/10.1142/9575
[10]	R. A. Aliev, A. V. Alizadeh, O. H. Huseynov, The arithmetic of discrete Z-numbers, Infor. Sci., 290 (2015), 134–155. http://dx.doi.org/10.1016/j.ins.2014.08.024 doi: 10.1016/j.ins.2014.08.024
[11]	R. A. Aliev, O. H. Huseynov, L. M. Zeinalova, The arithmetic of continuous Z-numbers, Inf. Sci., 373 (2016), 441–460. https://doi.org/10.1016/j.ins.2016.08.078 doi: 10.1016/j.ins.2016.08.078
[12]	A. S. A. Bakar, A. Gegov, Multi-layer decision methodology for ranking Z-numbers, Int. J. Comput. Intell. Syst., 8 (2015), 395–406. https://doi.org/10.1080/18756891.2015.1017371 doi: 10.1080/18756891.2015.1017371
[13]	R. A. Aliev, O. H. Huseynov, R. Serdaroglu, Ranking of Z-numbers and its application in decision making, Int. J. Inf. Tech. Decision Making, 15 (2016), 1503–1519. https://doi.org/10.1142/S0219622016500310 doi: 10.1142/S0219622016500310
[14]	S. Ezadi, T. Allahviranloo, New multi-layer method for Z-number ranking using hyperbolic tangent function and convex combination, Int. Autom. Soft Comput., 2017, 1–7. https://doi.org/10.1080/10798587.2017.1367146 doi: 10.1080/10798587.2017.1367146
[15]	S. Ezadi, T. Allahviranloo, S. Mohammadi, Two new methods for ranking of Z-numbers based on sigmoid function and sign method, Int. J. Intell. Syst., 33 (2018), 1476–1487. https://doi.org/10.1002/int.21987 doi: 10.1002/int.21987
[16]	Online content: OSPF protocol analysis, 1991. Available from: https://www.rfc-editor.org/rfc/rfc1245.
[17]	Y. Deng, Y. Chen, Y. Zhang, S. Mahadevan, Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment, Appl. Soft Comput., 12 (2012), 1231–1237. https://doi.org/10.1016/j.asoc.2011.11.011 doi: 10.1016/j.asoc.2011.11.011
[18]	K. K. Mishra, Dijkstra's Algorithm for solving fuzzy number Shortest Path Problem, Malaya J. Matematik, 8 (2019), 714–719.
[19]	A. Candra, M. A. Budiman, K. Hartanto, Dijkstra's and a-star in finding the shortest path: A tutorial, J. 2020 Int. Conf. Data Sci. Artif. Intell. Business Anal., 58 (2020), 28–32. http://dx.doi.org/10.1109/DATABIA50434.2020.9190342 doi: 10.1109/DATABIA50434.2020.9190342
[20]	M. Akram, A. Habib, J. C. R. Alcantud, An optimization study based on Dijkstra algorithm for a network with trapezoidal picture fuzzy numbers, Neural Comput. Appl., 33 (2021), 1329–1342. https://doi.org/10.1007/s00521-020-05034-y doi: 10.1007/s00521-020-05034-y
[21]	S. S. Biswas, Z-Dijkstra's algorithm to solve shortest path problem in a Z-Graph, Oriental J. Comput. Sci. Techn., 10 (2017), 180–186. http://dx.doi.org/10.13005/ojcst/10.01.24 doi: 10.13005/ojcst/10.01.24
[22]	P. Veerammal, Fuzzy Z-Number shortest path problem using Dijkstra algorithm, Periodico di Mineral., 91 (2022), 942–950.
[23]	A. Papoulis, Random variables and stochastic processes, New York: McGraw Hill, 1965.
[24]	M. D. Springer, The algebra of random variables, New York: Wiley, 1979.
[25]	B. Bede, Fuzzy analysis, Heidelberg: Springer, 2013. https://doi.org/10.1007/978-3-642-35221-8_8
[26]	E. Eljaoui, S. Melliani, L. S. Chadli, Multiplication operation and powers of trapezoidal fuzzy numbers, Cham: Springer, 2019. https://doi.org/10.1007/978-3-030-02155-9_11
[27]	H. Nasseri, Fuzzy numbers: Positive and nonnegative, Int. Mathem. Forum, 3 (2008), 1777–1780.
[28]	B. Kang, Y. Deng, R. Sadiq, Total utility of Z-number, Appl. Intell., 48 (2018), 703–729. https://doi.org/10.1007/s10489-017-1001-5 doi: 10.1007/s10489-017-1001-5
[29]	K. R. Saoub, Graph theory: An introduction to proofs, algorithms, and applications, Florida: CRC Press, 2021.
[30]	E. W. Dijkstra, A note on two problems in connexion with graphs, New York: Association for Computing Machinery, 2022. https://doi.org/10.1145/3544585.3544600
[31]	A. Atary, A. Bremler-Barr, Efficient round-trip time monitoring in OpenFlow networks, IEEE INFOCOM 2016 35th Annual IEEE Int. Conf. Comput. Commun., 31 (2016), 1–9. https://doi.org/10.1109/INFOCOM.2016.7524501 doi: 10.1109/INFOCOM.2016.7524501
[32]	G. Martínez, J. A. Hernández, P. Reviriego, P. Reinheimer, Round trip time (rtt) delay in the internet: Analysis and trends, IEEE Net., 38 (2023), 280–285. https://doi.org/10.1109/MNET004.2300008 doi: 10.1109/MNET004.2300008
[33]	M. T. Keller, W. T. Trotter, Applied combinatorics, California: Open Textbook Library, 2017.
[34]	D. Rachmawati, L. Gustin, Analysis of Dijkstra's algorithm and A* algorithm in shortest path problem, J. Phys. Confer. Series, 1566 (2020), 012061. http://dx.doi.org/10.1088/1742-6596/1566/1/012061 doi: 10.1088/1742-6596/1566/1/012061
[35]	B. Erkayman, E. Gundogar, A. Yılmaz, An integrated fuzzy approach for strategic alliance partner selection in third-party logistics, Sci. World J., 2012 (2012), 486306. http://dx.doi.org/10.1100/2012/486306 doi: 10.1100/2012/486306
[36]	M. Ebrat, R. Ghodsi, Construction project risk assessment by using adaptive-network-based fuzzy inference system: An empirical study, KSCE J. Civil Engin., 18 (2014), 1213–1227. https://doi.org/10.1007/s12205-014-0139-5 doi: 10.1007/s12205-014-0139-5

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)