Fuzzy Maximum Capacity Path Problem and Its Application to Optimal Routing Control

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Birjand University of Technology, Birjand, Iran.

2 Department of Mathematics and Computer Science, Transilvania University, Brasov, 500091, Romania.

3 Department of Mathematics, Kosar University of Bojnord, Bojnord, Iran.

4 Department of Industrial Engineering, Arak University, Arak, Iran.

Abstract

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.

Keywords

Main Subjects

References

[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
Iranian Journal of Fuzzy Systems
Volume 21, Issue 4
July and August 2024
Pages 123-139

Files

Share

How to cite

Statistics