842 666
Full Length Article
International Journal of Neutrosophic Science
Volume 20 , Issue 4, PP: 128-137 , 2023 | Cite this article as | XML | Html |PDF

Title

Solving shortest path problems using an ant colony algorithm with triangular neutrosophic arc weights

  Said Broumi 1 * ,   Prasanta Kumar Raut 2 ,   Siva Prasad Behera 3

1  Laboratory of Information Processing, Faculty of Science Ben M’Sik, University Hassan II, Casablanca, Morocco
    (broumisaid78@gmail.com)

2  Department of Mathematics, C.V. Raman Global University, Bhubaneswar-752054, Odisha, India
    (prasantaraut95@gmail.com)

3  Department of Mathematics, C.V. Raman Global University, Bhubaneswar-752054, Odisha, India
    ( sivaiitkgp12@gmail.com)

Full Text Download


Doi   :   https://doi.org/10.54216/IJNS.200410

Received: December 23, 2022 Accepted: March 26, 2023

Abstract :

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.

Keywords :

Ant colony optimization; Neutrosophic shortest path problem; Neutrosophic directed graph; Single value triangular neutrosophic numbers; Neutrosophic network.

References :

[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.

Cite this Article as :
Style #
MLA Said Broumi, Prasanta Kumar Raut, Siva Prasad Behera. "Solving shortest path problems using an ant colony algorithm with triangular neutrosophic arc weights." International Journal of Neutrosophic Science, Vol. 20, No. 4, 2023 ,PP. 128-137 (Doi   :  https://doi.org/10.54216/IJNS.200410)
APA Said Broumi, Prasanta Kumar Raut, Siva Prasad Behera. (2023). Solving shortest path problems using an ant colony algorithm with triangular neutrosophic arc weights. Journal of International Journal of Neutrosophic Science, 20 ( 4 ), 128-137 (Doi   :  https://doi.org/10.54216/IJNS.200410)
Chicago Said Broumi, Prasanta Kumar Raut, Siva Prasad Behera. "Solving shortest path problems using an ant colony algorithm with triangular neutrosophic arc weights." Journal of International Journal of Neutrosophic Science, 20 no. 4 (2023): 128-137 (Doi   :  https://doi.org/10.54216/IJNS.200410)
Harvard Said Broumi, Prasanta Kumar Raut, Siva Prasad Behera. (2023). Solving shortest path problems using an ant colony algorithm with triangular neutrosophic arc weights. Journal of International Journal of Neutrosophic Science, 20 ( 4 ), 128-137 (Doi   :  https://doi.org/10.54216/IJNS.200410)
Vancouver Said Broumi, Prasanta Kumar Raut, Siva Prasad Behera. Solving shortest path problems using an ant colony algorithm with triangular neutrosophic arc weights. Journal of International Journal of Neutrosophic Science, (2023); 20 ( 4 ): 128-137 (Doi   :  https://doi.org/10.54216/IJNS.200410)
IEEE Said Broumi, Prasanta Kumar Raut, Siva Prasad Behera, Solving shortest path problems using an ant colony algorithm with triangular neutrosophic arc weights, Journal of International Journal of Neutrosophic Science, Vol. 20 , No. 4 , (2023) : 128-137 (Doi   :  https://doi.org/10.54216/IJNS.200410)
↑