اخبار و اعلانات
آمار
| تعداد نشریات | 33 |
| تعداد شماره‌ها | 776 |
| تعداد مقالات | 7,514 |
| تعداد مشاهده مقاله | 12,601,413 |
| تعداد دریافت فایل اصل مقاله | 8,522,403 |
Fuzzy Maximum Capacity Path Problem and Its Application to Optimal Routing Control | ||
| Iranian Journal of Fuzzy Systems | ||
| دوره 21، شماره 4، مهر و آبان 2024، صفحه 123-139 اصل مقاله (1.36 M) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22111/ijfs.2024.49145.8665 | ||
| نویسندگان | ||
| Javad Tayyebi* 1؛ Adrian Deaconu2؛ Elham Hosseinzade3؛ Amir Mohmmad Golmohammadi4 | ||
| 1Department of Industrial Engineering, Birjand University of Technology, Birjand, Iran. | ||
| 2Department of Mathematics and Computer Science, Transilvania University, Brasov, 500091, Romania. | ||
| 3Department of Mathematics, Kosar University of Bojnord, Bojnord, Iran. | ||
| 4Department of Industrial Engineering, Arak University, Arak, Iran. | ||
| چکیده | ||
| The maximum capacity path problem (MCPP) is a classical combinatorial optimization problem that seeks to find a path with the maximum capacity in a network. In this paper, we consider a fuzzy extension of the MCPP, where the capacities are given as arbitrary fuzzy numbers. Unlike previous approaches that rely on ranking functions or specific orderings, we formulate the fuzzy MCPP as a bi-objective path-finding problem, where one objective is to maximize the nominal capacity and the other is to optimize the reliability value of the path. We propose an efficient algorithm that can find a Pareto optimal path for any aggregation function between the two objectives. We also analyze the special case where the network is acyclic and show that the algorithm can be specialized to run in strongly polynomial time. Furthermore, we present an application of the fuzzy MCPP to the field of optimal control, where we use a discretization algorithm to transform a continuous routing problem into a discrete one and solve it using the proposed algorithm as a subroutine. To implement this application in practice, we run the algorithm on an old real-world project in Iran called Iranrud. Moreover, we report some computational results on grid networks with different sizes that illustrate the performance of the proposed algorithm. | ||
| کلیدواژه‌ها | ||
| Routing؛ Maximum capacity path؛ Fuzzy capacity؛ Optimal control؛ Iranrud project | ||
| مراجع | ||
|
[1] R. Ahuja, T. Magnanti, J. Orlin, Network flows: Theory, algorithms, and applications, Prentice-Hall, 1995. http: //hdl.handle.net/1721.1/49424 [2] M. Akram, A. Habib, J. C. Alcantud, An optimization study based on Dijkstra algorithm for a network with trapezoidal picture fuzzy numbers, Neural Computing and Applications, 33(4) (2021), 1329-1342. https://doi.org/10. 1007/s00521-020-05034-y [3] M. Akram, S. Shahzadi, S. M. U. Shah, T. Allahviranloo, An extended multi-objective transportation model based on Fermatean fuzzy sets, Soft Computing, (2023), 1-23. https://doi.org/10.1007/s00500-023-08117-9 [4] T. A. Almeida, V. N. Souza, F. M. S. Prado, A. Yamakami, M. T. Takahashi, A genetic algorithm to solve minimum spanning tree problem with fuzzy parameters using possibility measure, In NAFIPS 2005-2005 Annual Meeting of the North American Fuzzy Information Processing Society, IEEE. (2005, June), 627-632. https://doi.org/10.1109/ NAFIPS.2005.1548610 [5] M. Bagheri, A. Ebrahimnejad, S. Razavyan, F. Hosseinzadeh Lotfi, N. Malekmohammadi, Fuzzy arithmetic DEA approach for fuzzy multi-objective transportation problem, Operational Research, (2022), 1-31. https://doi.org/ 10.1007/s12351-020-00592-4 [6] G. Baier, E. K¨ohler, M. Skutella, The k-splittable flow problem, Algorithmica, 42(3-4) (2005), 231-248. https: //doi.org/10.1007/s00453-005-1167-9 [7] O. Berman, G. Y. Handler, Optimal minimax path of a single service unit on a network to nonservice destinations, Transportation Science, 21(2) (1987), 115-122. https://doi.org/10.1287/trsc.21.2.115 [8] S. Broumi, P. K. Raut, S. P. Behera, Solving shortest path problems using an ant colony algorithm with triangular neutrosophic arc weights, International Journal of Neutrosophic Science, 20(4) (2023), 128-28. https://doi.org/ 10.54216/IJNS.200410 [9] M. R. Bussieck, A. Meeraus, General algebraic modeling system (gams), Springer US, Boston, MA, (2004), 137-157. https://doi.org/10.1007/978-1-4613-0215-5-8 [10] S. Chanas, W. Kolodziejczyk, Maximum flow in a network with fuzzy arc capacities, Fuzzy Sets and Systems, 8(2) (1982), 165-173. https://doi.org/10.1016/0165-0114(82)90006-9 [11] J. C. N. Cl´ımaco, M. M. B. Pascoal, J. M. F. Craveirinha, M. E. V. Captivo, Internet packet routing: Application of a k-quickest path algorithm, European Journal of Operational Research, 181(3) (2007), 1045-1054. https://doi. org/10.1016/j.ejor.2006.03.013 [12] S. Dan, S. Majumder, M. B. Kar, S. Kar, On type-2 fuzzy weighted minimum spanning tree, Soft Computing, 25 (2021), 14873-14892. https://doi.org/10.1007/s00500-021-06052-1 [13] A. Dey, S. Mondal, T. Pal, Robust and minimum spanning tree in fuzzy environment, International Journal of Computing Science and Mathematics, 10(5) (2019), 513-524. https://doi.org/10.1504/IJCSM.2019.103679 [14] A. Dey, A. Pal, Prim’s algorithm for solving minimum spanning tree problem in fuzzy environment, Annals of Fuzzy Mathematics and Informatics, 12(3) (2016), 419-430. [15] A. Dey, L. H. Son, A. Pal, H. V. Long, Fuzzy minimum spanning tree with interval type 2 fuzzy arc length: Formulation and a new genetic algorithm, Soft Computing, 24 (2020), 3963-3974. https://doi.org/10.1007/ s00500-019-04166-1 [16] S. Dhouib, S. Broumi, M. Talea, Solving the minimum spanning tree problem under interval-valued fermatean neutrosophic domain, Neutrosophic Sets and Systems, 67(1) (2024), 2. https://doi.org/10.5281/zenodo.11098903
[17] D. Di Caprio, A. Ebrahimnejad, H. Alrezaamiri, F. J. Santos-Arteaga, A novel ant colony algorithm for solving shortest path problems with fuzzy arc weights, Alexandria Engineering Journal, 61(5) (2022), 3403-3415. https: //doi.org/10.1109/ICCCNT56998.2023.10308130 [18] D. Dubois, H. Prade, Shortest path algorithms with fuzzy data (in French), RAIRO-Oper. Res., 12(2) (1978), 214-227. https://doi.org/10.1051/ro/1978120202131 [19] C. Dudeja, 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) (2024), 303-323. https: //doi.org/10.1142/S0218488524500120 [20] I. Dumitrescu, N. Boland, Algorithms for the weight constrained shortest path problem, International Transactions in Operational Research, 8(1) (2001), 15-29. https://doi.org/10.1111/1475-3995.00003 [21] A. Ebrahimnejad, M. Enayattabr, H. Motameni, H. Garg, Modified artificial bee colony algorithm for solving mixed interval-valued fuzzy shortest path problem, Complex and Intelligent Systems, 7 (2021), 1527-1545. https: //doi.org/10.1007/s40747-021-00278-0 [22] J. Edmonds, R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, Journal of the ACM, 19(2) (1972), 248-264. https://doi.org/10.1007/3-540-36478-1_4 [23] P. Erdos, A. R´enyi, On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci, 5(1) (1960), 17-60. https://doi.org/10.1515/9781400841356.38 [24] H. N. Gabow, Scaling algorithms for network problems, Journal of Computer and System Sciences, 31(2) (1985), 148-168. https://doi.org/10.1016/0022-0000(85)90039-X [25] F. Hernandes, M. T. Lamata, M. T. Takahashi, A. Yamakami, J. L. Verdegay, An algorithm for the fuzzy maximum flow problem, 2007 IEEE International Fuzzy Systems Conference, (2007), 1-6. https://doi.org/10.1109/FUZZY. 2007.4295464 [26] S. Hong, J. K. Hedrick, Roll prediction-based optimal control for safe path following, 2015 American Control Conference (ACC). IEEE, (2015), 3261-3266. https://doi.org/10.1109/ACC.2015.7171835 [27] A. Iftar, E. J. Davison, A decentralized discrete-time controller for dynamic routing, International Journal of Control, 69(5) (1998), 599-632. https://doi/abs/10.1080/002071798222596 [28] A. A. Keller, Multi-objective optimization in theory and practice II: Metaheuristic algorithms, Bentham Science Publishers, 2019. https://books.google.com/books?id=3uyRDwAAQBAJ [29] W. Kolodziejczyk, The shortest spanning tree problem in a network with fuzzy parameters, Report 44, Institute of Production Engineering and Management, Technical University of Wroclaw, 44 (1984). [30] R. Kumar, S. Jha, R. Singh, A different approach for solving the shortest path problem under mixed fuzzy environment, International Journal of Fuzzy System Applications (IJFSA), 9(2) (2020), 132-161. https://doi.org/10. 4018/IJFSA.2020040106 [31] A. Kumar, M. Kaur, An algorithm for solving fuzzy maximal flow problems using generalized trapezoidal fuzzy numbers, International Journal of Applied Science and Engineering, 8(2) (2010), 109-118. https://doi.org/10. 6703/IJASE.2010.8(2).109 [32] A. Kumar, M. Kaur, An improved algorithm for solving fuzzy maximal flow problems, International Journal of Applied Science and Engineering, 10(1) (2012), 19-27. https://doi.org/10.6703/IJASE.2012.10(1).19 [33] S. Majumder, B. Saha, P. Anand, S. Kar, T. Pal, Uncertainty based genetic algorithm with varying population for random fuzzy maximum flow problem, Expert Systems, 35(4) (2018), e12264. https://doi.org/10.1111/exsy. 12264 [34] E. Q. V. Martins, J. L. E. Santos, An algorithm for the quickest path problem, Operations Research Letters, 20(4) (1997), 195-198. https://doi.org/10.1016/S0167-6377(97)00008-4 [35] D. Medhi, K. Ramasamy, Network routing: Algorithms, protocols, and architectures, second edition, Morgan Kaufmann Publishers, Cambridge, MA (2017). https://doi.org/10.1016/C2013-0-18604-7
[36] A. Mert, Defuzzification of non-linear pentagonal intuitionistic fuzzy numbers and application in the minimum spanning tree problem, Symmetry, 15(10) (2023), 1853. https://doi.org/10.3390/sym15101853 [37] A. Mohammadi, J. Tayyebi, Maximum capacity path interdiction problem with fixed costs, Asia-Pacific Journal of Operational Research, 36(4) (2019), 1950018. https://doi.org/10.1142/S0217595919500180 [38] M. Parimala, S. Broumi, K. Prakash, S. Topal, Bellman–Ford algorithm for solving shortest path problem of a network under picture fuzzy environment, Complex and Intelligent Systems, 7 (2021), 2373-2381. https://doi. org/10.1007/s40747-021-00430-w [39] Z. Peng, M. Nikbakht, A. Ebrahimnejad, F. Hosseinzadeh Lotfi, T. Allahviranloo, Fully interval-valued fuzzy transportation problems: Development and prospects, Computational and Applied Mathematics, 43(1) (2024), 15. https://doi.org/10.1007/s40314-023-02523-3 [40] A. Plus, What is of construction of shipping canal linking Caspian Sea and Persian Gulf to Tajikistan, (2022). https://www.asiaplustj.info/en/news/tajikistan/economic/20221213/ what-is-of-construction-of-shipping-canal-linking-caspian-sea-and-persian-gulf-to-tajikistan [41] M. Pollack, The maximum capacity through a network, Operations Research, 8(5) (1960), 733-736. https://doi. org/10.1287/opre.8.5.733 [42] A. P. Punnen, A linear time algorithm for the maximum capacity path problem, European Journal of Operational Research, 53(3) (1991), 402-404. https://doi.org/10.1016/0377-2217(91)90073-5 [43] R. Ramaswamy, J. B. Orlin, N. Chakravarti, Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs, Mathematical Programming, 102(2) (2005), 355-369. https://doi.org/10. 1007/s10107-004-0517-8 [44] J. Shekel, LINGO–A programming language for linear network analysis at a remote teletype terminal, Proceedings of the IEEE, 55(11) (1967), 2014-2015. https://doi.org/10.1109/PROC.1967.6034 [45] G. H. Shirdel, H. Rezapour, Time-varying maximum capacity path problem with zero waiting times and fuzzy capacities, SpringerPlus, 5(1) (2016), 1-9. https://doi.org/10.1186/s40064-016-2654-y [46] J. Tayyebi, A. Mitra, J. A. Sefair, The continuous maximum capacity path interdiction problem, European Journal of Operational Research, 305(1) (2023), 38-52. https://doi.org/10.1016/j.ejor.2022.05.028 [47] S. Tragoudas, The most reliable data-path transmission, IEEE Transactions on Reliability, 50(3) (2001), 281-285. https://doi.org/10.1109/24.974124 [48] Wikipedia contributors, Iranrud — Wikipedia, The Free Encyclopedia, (2023) [Online; accessed 19-March-2024]. https://en.wikipedia.org/w/index.php?title=Iranrud&oldid=1192043540 | ||
|
آمار تعداد مشاهده مقاله: 169 تعداد دریافت فایل اصل مقاله: 197 |
||