Mutiobjective Optimization Strategy for Solving Interval-valued Fuzzy Constrained Shortest Path Problems
محورهای موضوعی : Fuzzy Optimization and Modeling Journal
1 - Department of Mathematics,Payame Noor University, Tehran,Iran.
کلید واژه: Constrainted Shortest Path, Interval-valued Fuzzy Number, Multiobjective Optimization,
چکیده مقاله :
The constrained shortest path (CSP) problem is one of the most used and tangible applications of network flow problems that aside from its straightforward application is arised as auxiliary problems in flight planning, tail assignment problem in aircraft scheduling and crew rostering problems, among others. The objective of the CSP problem is to determine a minimum cost path between two specified nodes that the traversal time of the path does not exceed from a specified time. Conventional CSP problem generally assumes that the weights of arc costs and times are defined by real variables, though these values are unpredictable due to some uncontrollable factors. The present study formulates a CSP problem when values of arc costs and times are interval-valued triangular fuzzy numbers and proposes a multi-objective optimization strategy to obtain the efficient solution of the resulting problem. The applicability of the proposed approach is illustrated through an example dealing with wireless sensor networks
The constrained shortest path (CSP) problem is one of the most used and tangible applications of network flow problems that aside from its straightforward application is arised as auxiliary problems in flight planning, tail assignment problem in aircraft scheduling and crew rostering problems, among others. The objective of the CSP problem is to determine a minimum cost path between two specified nodes that the traversal time of the path does not exceed from a specified time. Conventional CSP problem generally assumes that the weights of arc costs and times are defined by real variables, though these values are unpredictable due to some uncontrollable factors. The present study formulates a CSP problem when values of arc costs and times are interval-valued triangular fuzzy numbers and proposes a multi-objective optimization strategy to obtain the efficient solution of the resulting problem. The applicability of the proposed approach is illustrated through an example dealing with wireless sensor networks
1. Abbaszadeh Sori, A., Ebrahimnejad, A., & Motameni, H. (2020). The fuzzy inference approach to solve multi-objective constrained shortest path problem. Journal of Intelligent & Fuzzy Systems, 38(4), 4711-4720.
2. Abbaszadeh Sori, A., Ebrahimnejad, A., Motameni, H., & Verdegay, J. L. (2021). Fuzzy constrained shortest path problem for location-based online services. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 29(02), 231-248.
3. Broumi, S., Raut, P. K., & Behera, S. P. (2023). Solving shortest path problems using an ant colony algorithm with triangular neutrosophic arc weights. International Journal of Neutrosophic Science, 20(4), 128-28.
4. Chaini, B., & Ranarahu, N. (2024). Solving fuzzy shortest path problem with vertex transfer penalties under type-2 fuzzy environment. International Journal of Mathematics in Operational Research, 28(4), 526-548.
5. Deng Y, Chen Y, Zhang Y and Mahadevan S 2012 Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment. Applied Soft Computing, 12: 1231–1237
6. Dey, A., Pradhan, R., Pal, A., & Pal, T. (2018). A genetic algorithm for solving fuzzy shortest path problems with interval type-2 fuzzy arc lengths. Malaysian Journal of Computer Science, 31(4), 255-270.
7. Di Caprio, D., Ebrahimnejad, A., Alrezaamiri, H., & Santos-Arteaga, F. J. (2022). A novel ant colony algorithm for solving shortest path problems with fuzzy arc weights. Alexandria Engineering Journal, 61(5), 3403-3415.
8. 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.
9. Dudeja, C. (2024). PSO Based Constraint Optimization of Intuitionistic Fuzzy Shortest Path Problem in an Undirected Network. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 32(03), 303-323.
10. Ebrahimnejad, A., Tabatabaei, S., & Santos-Arteaga, F. J. (2020). A novel lexicographic optimization method for solving shortest path problems with interval-valued triangular fuzzy arc weights. Journal of Intelligent & Fuzzy Systems, 39(1), 1277-1287.
11. Elloumi, W., Baklouti, N., Abraham, A., & Alimi, A. M. (2014). The multi-objective hybridization of particle swarm optimization and fuzzy ant colony optimization. Journal of Intelligent & Fuzzy Systems, 27(1), 515-525.
12. Enayattabr, M., Ebrahimnejad, A., Motameni, H., & Garg, H. (2019). A novel approach for solving all-pairs shortest path problem in an interval-valued fuzzy network. Journal of Intelligent & Fuzzy Systems, 37(5), 6865-6877.
13. Funck J, and Gühmann C (2014) Comparison of approaches to time-synchronous sampling in wireless sensor networks, Measurement 56: 203–214.
14. 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.
15. Jamil, M., & Sharma, A. (2018). Reconfiguration of electrical distribution system using ACO methodology. Journal of Intelligent & Fuzzy Systems, 35(5), 4901-4908.
16. Keshavarz, E., & Khorram, E. (2009). A fuzzy shortest path with the highest reliability. Journal of Computational and Applied Mathematics, 230(1), 204-212.
17. Kung, J. Y., Chuang, T. N., & Lin, C. T. (2007). A new dynamic programming approach for finding the shortest path length and the corresponding shortest path in a discrete fuzzy network. Journal of Intelligent & Fuzzy Systems, 18(2), 117-122.
18. Lin, L., Wu, C., & Ma, L. (2021). A genetic algorithm for the fuzzy shortest path problem in a fuzzy network. Complex & Intelligent Systems, 7, 225-234.
19. Motameni, H., & Ebrahimnejad, A. (2018). Constraint shortest path problem in a network with intuitionistic fuzzy arc weights. In International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (pp. 310-318). Cham: Springer International Publishing.
20. Niroomand, S., Mahmoodirad, A., Heydari, A., Kardani, F., & Hadi-Vencheh, A. (2017). An extension principle based solution approach for shortest path problem with fuzzy arc lengths. Operational Research, 17(2), 395-411.
21. Özçelik, G. (2022). The attitude of MCDM approaches versus the optimization model in finding the safest shortest path on a fuzzy network. Expert Systems with Applications, 203, 117472.
22. Parimala, M., Broumi, S., Prakash, K., & Topal, S. (2021). Bellman–Ford algorithm for solving shortest path problem of a network under picture fuzzy environment. Complex & Intelligent Systems, 7, 2373-2381.
23. Peng, Z., Abbaszadeh Sori, A., Nikbakht, M., & Ebrahimnejad, A. (2023). Computing constrained shortest path in a network with mixed fuzzy arc weights applied in wireless sensor networks. Soft Computing, 1-14.
24. Rosyida, I., Asih, T. S. N., Waluya, S. B., & Sugiyanto. (2021). Fuzzy shortest path approach for determining public bus route (Case study: Route planning for “Trans Bantul bus” in Yogyakarta, Indonesia). Journal of Discrete Mathematical Sciences and Cryptography, 24(2), 557-577.
25. Yang, Y., Yan, D., & Zhao, J. (2017). Optimal path selection approach for fuzzy reliable shortest path problem. Journal of intelligent & fuzzy systems, 32(1), 197-205.
