Aspiration Level-Based Non-Dominated Sorting Genetic Algorithm II & III to Solve Fuzzy Multi-objective Shortest Path Problem
DOI:
https://doi.org/10.2298/YJOR230218015TKeywords:
Multi-objective shortest path problem, fuzzy membership function, α-level set, triangular fuzzy number, aspiration levelAbstract
The present article provides aspiration level-based non-dominated sorting genetic algorithm-II and III techniques for solving a fuzzy multi-objective shortest path problem utilizing an exponential membership function with a possibility distribution. Furthermore, in this study, using α-level sets, fuzzy judgement was categorized for the decision maker to simultaneously optimize fuzzy objective functions scenarios as optimistic, most likely, and pessimistic. A numerical illustration is presented together with a data set to demonstrate the use of the suggested techniques. A comparison is performed between the suggested methodology and several other approaches. The sensitivity of the objective functions is also investigated using aspiration levels and shape parameters. The coverage is computed to assess the effectiveness of the proposed methods. This research concludes that the suggested approaches can manage fuzzy multi-objective shortest path problems competently and efficiently with a solid yield, allowing the decision maker to make a decision based on its aspiration level.References
R. Bellman, “On a routing problem,” Quarterly of applied mathematics, vol. 16, no. 1, pp. 87-90, 1958.
E. W. Dijkstra et al., “A note on two problems in connexion with graphs,” Numerische mathematik, vol. 1, no. 1, pp. 269-271, 1959.
R. W. Floyd, “Algorithm 97: shortest path,” Communications of the ACM, vol. 5, no. 6, p. 345, 1962.
S. E. Dreyfus, “An appraisal of some shortest-path algorithms,” Operations research, vol. 17, no. 3, pp. 395-412, 1969.
P. Hansen, “Bicriterion path problems,” in Multiple criteria decision making theory and application. Springer, 1980, pp. 109-127.
E. Q. V. Martins, “On a multicriteria shortest path problem,” European Journal of Operational Research, vol. 16, no. 2, pp. 236-245, 1984.
P. Serafini, “Some considerations about computational complexity for multi objective combinatorial problems,” in Recent advances and historical development of vector optimization. Springer, 1987, pp. 222-232.
X. Gandibleux, F. Beugnies, and S. Randriamasy, “Martins’ algorithm revisited for multiobjective shortest path problems with a maxmin cost function,” 4OR, vol. 4, no. 1, pp. 47-59, 2006.
Z. Tarapata, “Selected multicriteria shortest path problems: An analysis of complexity, models and adaptation of standard algorithms,” International Journal of Applied Mathematics and Computer Science, vol. 17, no. 2, p. 269, 2007.
J. C. Clímaco and M. M. Pascoal, “Multicriteria path and tree problems: discussion on exact algorithms and applications,” International Transactions in Operational Research, vol. 19, no. 1-2, pp. 63-98, 2012.
A. Sedeno-Noda and A. Raith, “A dijkstra-like method computing all extreme supported nondominated solutions of the biobjective shortest path problem,” Computers & Operations Research, vol. 57, pp. 83-94, 2015.
A. Sedeno-Noda and M. Colebrook, “A biobjective dijkstra algorithm,” European Journal of Operational Research, vol. 276, no. 1, pp. 106-118, 2019.
L. D. P. Pugliese, J. Granat, and F. Guerriero, “Two-phase algorithm for solving the preferencebased multicriteria optimal path problem with reference points,” Computers & Operations Research, vol. 121, p. 104977, 2020.
C. Ntakolia and D. K. Iakovidis, “A swarm intelligence graph-based pathfinding algorithm (sigpa) for multi-objective route planning,” Computers & Operations Research, vol. 133, p. 105358, 2021.
P. M. de las Casas, A. Sedeño-Noda, and R. Borndörfer, “An improved multiobjective shortest path algorithm,” Computers & Operations Research, p. 105424, 2021.
D. J. Dubois, Fuzzy sets and systems: theory and applications. Academic press, 1980, vol. 144.
S. Okada and T. Soper, “A shortest path problem on a network with fuzzy arc lengths,” Fuzzy sets and systems, vol. 109, no. 1, pp. 129-140, 2000.
I. Mahdavi, R. Nourifar, A. Heidarzade, and N. M. Amiri, “A dynamic programming approach for finding shortest chains in a fuzzy network,” Applied Soft Computing, vol. 9, no. 2, pp. 503- 511, 2009.
A. Tajdin, I. Mahdavi, N. Mahdavi-Amiri, and B. Sadeghpour-Gildeh, “Computing a fuzzy shortest path in a network with mixed fuzzy arc lengths using α-cuts,” Computers & Mathematics with Applications, vol. 60, no. 4, pp. 989-1002, 2010.
S. Mukherjee, “Fuzzy programming technique for solving the shortest path problem on networks under triangular and trapezoidal fuzzy environment,” International Journal of Mathematics in Operational Research, vol. 7, no. 5, pp. 576-594, 2015.
A. Ebrahimnejad, Z. Karimnejad, and H. Alrezaamiri, “Particle swarm optimisation algorithm for solving shortest path problems with mixed fuzzy arc weights,” International Journal of Applied Decision Sciences, vol. 8, no. 2, pp. 203-222, 2015.
A. Ebrahimnejad, M. Tavana, and H. Alrezaamiri, “A novel artificial bee colony algorithm for shortest path problems with fuzzy arc weights,” Measurement, vol. 93, pp. 48-56, 2016.
G. Sheng, Y. Su, and W. Wang, “A new fractal approach for describing induced-fracture porosity/permeability/compressibility in stimulated unconventional reservoirs,” Journal of Petroleum Science and Engineering, vol. 179, pp. 855-866, 2019.
Y. Yang, J. Hu, Y. Liu, and X. Chen, “Alternative selection of end-of-life vehicle management in china: A group decision-making approach based on picture hesitant fuzzy measurements,” Journal of cleaner production, vol. 206, pp. 631-645, 2019.
H. Zhao, L. Xu, Z. Guo, W. Liu, Q. Zhang, X. Ning, G. Li, and L. Shi, “A new and fast waterflooding optimization workflow based on insim-derived injection efficiency with a field application,” Journal of Petroleum Science and Engineering, vol. 179, pp. 1186-1200, 2019.
M. Enayattabr, A. Ebrahimnejad, H. Motameni, and H. Garg, “A novel approach for solving all-pairs shortest path problem in an interval-valued fuzzy network,” Journal of Intelligent & Fuzzy Systems, vol. 37, no. 5, pp. 6865-6877, 2019.
M. Enayattabar, A. Ebrahimnejad, and H. Motameni, “Dijkstra algorithm for shortest path problem under interval-valued pythagorean fuzzy environment,” Complex & Intelligent Systems, vol. 5, no. 2, pp. 93-100, 2019.
A. Ebrahimnejad, S. Tabatabaei, and F. J. Santos-Arteaga, “A novel lexicographic optimization method for solving shortest path problems with interval-valued triangular fuzzy arc weights,” Journal of Intelligent & Fuzzy Systems, vol. 39, no. 1, pp. 1277-1287, 2020.
A. Ebrahimnejad, M. Enayattabr, H. Motameni, and H. Garg, “Modified artificial bee colony algorithm for solving mixed interval-valued fuzzy shortest path problem,” Complex & Intelligent Systems, vol. 7, no. 3, pp. 1527-1545, 2021.
A. Abbaszadeh Sori, A. Ebrahimnejad, and H. Motameni, “Elite artificial bees’ colony algorithm to solve robot’s fuzzy constrained routing problem,” Computational Intelligence, vol. 36, no. 2, pp. 659-681, 2020.
A. Ebrahimnejad, “An acceptability index based approach for solving shortest path problem on a network with interval weights,” RAIRO-Operations Research, vol. 55, pp. S1767-S1787, 2021.
L. Lin, C. Wu, and L. Ma, “A genetic algorithm for the fuzzy shortest path problem in a fuzzy network,” Complex & Intelligent Systems, vol. 7, no. 1, pp. 225-234, 2021.
D. Di Caprio, A. Ebrahimnejad, H. Alrezaamiri, and F. J. Santos-Arteaga, “A novel ant colony algorithm for solving shortest path problems with fuzzy arc weights,” Alexandria Engineering Journal, vol. 61, no. 5, pp. 3403-3415, 2022.
G. V. Rani and B. Reddy, “Multi-objective fuzzy shortest path selection for green routing and scheduling problems.” International Journal of Advanced Research in Computer Science, vol. 8, no. 7, 2017.
Y. Zhang, P. Liu, L. Yang, and Y. Gao, “A bi-objective model for uncertain multi-modal shortest path problems,” Journal of Uncertainty Analysis and Applications, vol. 3, no. 1, pp. 1-17, 2015.
M. Bagheri, A. Ebrahimnejad, S. Razavyan, F. Hosseinzadeh Lotfi, and N. Malekmohammadi, “Fuzzy arithmetic dea approach for fuzzy multi-objective transportation problem,” Operational Research, pp. 1-31, 2020.
S. Ghosh, S. K. Roy, A. Ebrahimnejad, and J. L. Verdegay, “Multi-objective fully intuitionistic fuzzy fixed-charge solid transportation problem,” Complex & Intelligent Systems, vol. 7, no. 2, pp. 1009-1023, 2021.
M. Bagheri, A. Ebrahimnejad, S. Razavyan, F. H. Lotfi, and N. Malekmohammadi, “Solving fuzzy multi-objective shortest path problem based on data envelopment analysis approach,” Complex & Intelligent Systems, vol. 7, no. 2, pp. 725-740, 2021.
A. Abbaszadeh Sori, A. Ebrahimnejad, and H. Motameni, “The fuzzy inference approach to solve multi-objective constrained shortest path problem,” Journal of Intelligent & Fuzzy Systems, vol. 38, no. 4, pp. 4711-4720, 2020.
R.-C. Wang and T.-F. Liang, “Applying possibilistic linear programming to aggregate production planning,” International journal of production economics, vol. 98, no. 3, pp. 328-341, 2005.
P. Gupta and M. K. Mehlawat, “A new possibilistic programming approach for solving fuzzy multiobjective assignment problem,” IEEE Transactions on Fuzzy Systems, vol. 22, no. 1, pp. 16-34, 2013.
L. A. Zadeh, “Fuzzy sets,” in Fuzzy sets, fuzzy logic, and fuzzy systems: selected papers by Lotfi A Zadeh. World Scientific, 1996, pp. 394-432.
Y.-J. Lai and C.-L. Hwang, “A new approach to some possibilistic linear programming problems,” Fuzzy sets and systems, vol. 49, no. 2, pp. 121-133, 1992.
A. R. Tailor and J. M. Dhodiya, “Genetic algorithm based hybrid approach to solve optimistic, most-likely and pessimistic scenarios of fuzzy multi-objective assignment problem using exponential membership function,” Journal of Advances in Mathematics and Computer Science, pp. 1-19, 2016.
R. K. Rekh and J. M. Dhodiya, “Solution of fuzzy multi criteria project management problem by fuzzy programming technique with possibilistic approach,” Indian J. Sci. Technol, vol. 12, pp. 1-21, 2019.
N. Srinivas and K. Deb, “Muiltiobjective optimization using nondominated sorting in genetic algorithms,” Evolutionary computation, vol. 2, no. 3, pp. 221-248, 1994.
D. Gordberg, Genetic Algorithm in Search, Optimization and Machine Learning. Addison- Wesley, Readingm MA, 1989.
K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan, “A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: Nsga-ii,” in International conference on parallel problem solving from nature. Springer, 2000, pp. 849-858.
K. Deb and H. Jain, “An evolutionary many-objective optimization algorithm using referencepoint- based nondominated sorting approach, part i: solving problems with box constraints,” IEEE transactions on evolutionary computation, vol. 18, no. 4, pp. 577-601, 2013.
K. Deb, S. Bandaru, and H. Seada, “Generating uniformly distributed points on a unit simplex for evolutionary many-objective optimization,” in International Conference on Evolutionary Multi-Criterion Optimization. Springer, 2019, pp. 179-190.
I. Das and J. E. Dennis, “Normal-boundary intersection: A new method for generating the pareto surface in nonlinear multicriteria optimization problems,” SIAM journal on optimization, vol. 8, no. 3, pp. 631-657, 1998.
K. Deb, Multi-Objective Optimization using Evolutionary Algorithms. Wiley India Pvt. Limited, 2010. ISBN 9788126528042. [Online]. Available: https://books.google.co.in/books?id=Cph6cgAACAAJ
K. Deb, L. Thiele, M. Laumanns, and E. Zitzler, “Scalable test problems for evolutionary multiobjective optimization,” in Evolutionary multiobjective optimization. Springer, 2005, pp. 105-145.
R. V. Rao, Jaya: an advanced optimization algorithm and its engineering applications. Springer, 2019.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
