Volume 20 , Issue 4 , PP: 128-137, 2023 | Cite this article as | XML | Html | PDF | Full Length Article
Said Broumi 1 * , Prasanta Kumar Raut 2 , Siva Prasad Behera 3
Doi: https://doi.org/10.54216/IJNS.200410
Indeed, one of the most well-known topics in the area of graph theory is the shortest path (SP) problem, which has practical applications in various areas of research, including transportation, communication via networks, life-saving services, fire department services, etc. The edges of the connected SP problems are typically characterized by various numbers in practical applications. In this research paper, we calculate the shortest path using an ant colony optimization (ACO) algorithm with single value triangular neutrosophic numbers as arc weights. The method is used to estimate the shortest path of a neutrosophic network. One numerical example is used to test the suggested method, and outcomes are provided.
Ant colony optimization , Neutrosophic shortest path problem , Neutrosophic directed graph , Single value triangular neutrosophic numbers , Neutrosophic network.
[1] Dorigo, M. (1992). Optimization, learning and natural algorithms. Ph. D. Thesis, Politecnico di Milano.
[2] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2001). Introduction to algorithms, 2nd edn Cambridge. MA: The MIT Press.[Google Scholar].
[3] Cheng, E., Grossman, J. W., Lipták, L., Qiu, K., & Shen, Z. (2010). Distance formula and shortest paths for the (n, k)-star graphs. Information Sciences, 180(9), 1671-1680.
[4] Hassanzadeh, R., Mahdavi, I., Mahdavi-Amiri, N., & Tajdin, A. (2013). A genetic algorithm for solving fuzzy shortest path problems with mixed fuzzy arc lengths. Mathematical and Computer Modelling, 57(1-2), 84-99.
[5] Hernandes, F., Lamata, M. T., Verdegay, J. L., & Yamakami, A. (2007). The shortest path problem on networks with fuzzy parameters. Fuzzy sets and systems, 158(14), 1561-1570.
[6] Klein, C. M. (1991). Fuzzy shortest paths. Fuzzy sets and systems, 39(1), 27-41..
[7] Lin, K. C., & Chern, M. S. (1993). The fuzzy shortest path problem and its most vital arcs. Fuzzy Sets and Systems, 58(3), 343-353.
[8] Okada, S., & Soper, T. (2000). A shortest path problem on a network with fuzzy arc lengths. Fuzzy sets and systems, 109(1), 129-140.
[9] Sheng, G., Su, Y., & Wang, W. (2019). A new fractal approach for describing induced-fracture porosity/permeability/compressibility in stimulated unconventional reservoirs. Journal of Petroleum Science and Engineering, 179, 855-866.
[10] Takahashi, M. T., & Yamakami, A. (2005, June). On fuzzy shortest path problems with fuzzy parameters: an algorithmic approach. In NAFIPS 2005-2005 Annual Meeting of the North American Fuzzy Information Processing Society (pp. 654-657). IEEE.
[11] Wang, R., Wang, J., Gao, H., & Wei, G. (2018). Methods for MADM with picture fuzzy muirhead mean operators and their application for evaluating the financial investment risk. Symmetry, 11(1), 6.
[12] Yager, R. R. (1986). Paths of least resistance in possibilistic production systems. Fuzzy sets and systems, 19(2), 121-132.
[13] Cheng, E., Grossman, J. W., Lipták, L., Qiu, K., & Shen, Z. (2010). Distance formula and shortest paths for the (n, k)-star graphs. Information Sciences, 180(9), 1671-1680.
[14] Raut, P. K., Behera, S. P., Broumi, S., & Kar, P. K. (2023). Evaluation of Shortest path of a Network Using Fuzzy Floyd Warshall Algorithm based on the uncertain environment.
[15] Almasi, M. H., Mirzapour Mounes, S., Koting, S., & Karim, M. R. (2014). Analysis of feeder bus network design and scheduling problems. The Scientific World Journal, 2014.
[16] Weide, O., Ryan, D., & Ehrgott, M. (2010). An iterative approach to robust and integrated aircraft routing and crew scheduling. Computers & Operations Research, 37(5), 833-844.
[17] Sivakumar, B., Bhalaji, N., & Sivakumar, D. (2014). A survey on investigating the need for intellige nt power-aware load balanced routing protocols for handling critical links in MANETs. The Scientific World Journal, 2014.
[18] Xue, G. (2003). Minimum-cost QoS multicast and unicast routing in communication networks. IEEE Transactions on Communications, 51(5), 817-824.
[19] Dubois, D. J. (1980). Fuzzy sets and systems: theory and applications (Vol. 144). Academic press.
[20] Chanas, S., & Kamburowski, J. (1983). The fuzzy shortest route problem. In Interval and Fuzzy Mathematics, Proc. Polish Symp., Technical University of Poznan, Poznan (pp. 35-41).
[21] Klein, C. M. (1991). Fuzzy shortest paths. Fuzzy sets and systems, 39(1), 27-41.
[22] Mahdavi, I., Nourifar, R., Heidarzade, A., & Amiri, N. M. (2009). A dynamic programming approach for finding shortest chains in a fuzzy network. Applied Soft Computing, 9(2), 503-511.
[23] Tajdin, A., Mahdavi, I., Mahdavi-Amiri, N., & Sadeghpour-Gildeh, B. (2010). Computing a fuzzy shortest path in a network with mixed fuzzy arc lengths using α -cuts. Computers & Mathematics with Applications, 60(4), 989-1002.
[24] Dou, Y., Zhu, L., & Wang, H. S. (2012). Solving the fuzzy shortest path problem using multi-criteria decision method based on vague similarity measure. Applied Soft Computing, 12(6), 1621-1631.
[25] 25.Deng, Y., Chen, Y., Zhang, Y., & Mahadevan, S. (2012). Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment. Applied Soft Computing, 12(3), 1231-1237.
[26] Zhang, Y., Zhang, Z., Deng, Y., & Mahadevan, S. (2013). A biologically inspired solution for fuzzy shortest path problems. Applied Soft Computing, 13(5), 2356-2363.
[27] Hassanzadeh, R., Mahdavi, I., Mahdavi-Amiri, N., & Tajdin, A. (2013). A genetic algorithm for solving fuzzy shortest path problems with mixed fuzzy arc lengths. Mathematical and Computer Modelling, 57(1-2), 84-99.
[28] Ebrahimnejad, A., Karimnejad, Z., & Alrezaamiri, H. (2015). Particle swarm optimisation algorithm for solving shortest path problems with mixed fuzzy arc weights. International Journal of Applied Decision Sciences, 8(2), 203-222.
[29] Ebrahimnejad, A., Tavana, M., & Alrezaamiri, H. (2016). A novel artificial bee colony algorithm for shortest path problems with fuzzy arc weights. Measurement, 93, 48-56.
[30] Calle, J., Rivero, J., Cuadra, D., & Isasi, P. (2017). Extending ACO for fast path search in huge graphs and social networks. Expert Systems with Applications, 86, 292-306.
[31] 31.Ashour, W., Muqat, R., & Al-Talli, H. (2018). Optimization of Traveling Salesman Problem based on Adaptive Affinity Propagation and Ant Colony Algorithms. Int. J. Comput, 181, 25-31.
[32] 32. Changdar, C., Pal, R. K., & Mahapatra, G. S. (2017). A genetic ant colony optimization based algorithm for solid multiple travelling salesmen problem in fuzzy rough environment. Soft Computing, 21, 4661-4675.
