Multi-objective Windy Postman Problem in a Fuzzy Transportation Network
Downloads
Researchers have become increasingly captivated by the windy postman problem (WPP), a major combinatorial optimisation problem with several practical applications. It is crucial to take the experts’ belief levels into account when modelling such a real-world application since these applications frequently involve uncertain aspects. A fuzzy set is one of the tools that might be regarded as appropriate for modelling such human perspectives. Applying fuzzy set theory to a multi-objective windy postman problem is the focus of this study. Maximising the overall profit and minimising the transportable time of the route visited by a postman are the objectives of the problem. In an effort to solve the fuzzy multi-objective windy postman problem (FMWPP), we have developed a chance-constrained programming model (CCPM). Subsequently, the epsilon-constraint method, a classical multi-objective solution methodology, is used to solve the deterministic transformation of the relevant CCPM. Moreover, the model is solved using two multi-objective genetic algorithms (MOGAs): fast Pareto genetic algorithm (FastPGA) and nondominated sorting genetic algorithm II (NSGAII). To demonstrate the proposed model, a numerical example is presented. We conclude by comparing the performance of the MOGAs on four randomly generated FMWPP instances.
Downloads
Kwan MK. Graphic programming using odd or even points. Chinese Mathematics. 1962;1:273-277.
Minieka E. The Chinese postman problem for mixed networks. Management Science. 1979;25(7):643-648.
Guan M. On the windy postman problem. Discrete Applied Mathematics. 1984;9(1):41-46. DOI: 10.1016/0166-218X(84)90089-1.
Grötschel M, Win Z. A cutting plane algorithm for the windy postman problem. Mathematical Programming. 1992;55(1-3):339–358. DOI: 10.1007/BF01581206.
Brucker P. The Chinese postman problem for mixed graphs. Noltemeier, H. (eds) Graph theoretic concepts in computer science. WG 1980. Lecture Notes in Computer Science, vol 100. Springer, Berlin, Heidelberg.
Corberán A, Plana I, Rodríguez-Chía AM, Sanchis JM. A branch-and-cut for the maximum benefit Chinese postman problem. Mathematical Programming. 2013;141:21–48. DOI: 10.1007/s10107-011-0507-6.
Benavent E, Corberán Á, Plana I, Sanchis JM. Min-Max K-vehicles windy rural postman problem. Wiley Periodicals, Inc. Networks. 2009;54(4):216–226. DOI: 10.1002/net.20334.
Benavent E, Corberán Á, Sanchis JM. A metaheuristic for the min-max windy rural postman problem with K vehicles. Computational Management Science. 2010;7(3):269-287. DOI: 10.1007/s10287-009-0119-2.
Benavent E, Corberán A, Plana I, Sanchis JM. New facets and an enhanced branch-and-cut for the min–max K-vehicles windy rural postman problem. Networks. 2011;58(4):255–272. DOI: 10.1002/net.20469.
Triki C. Solving the periodic edge routing problem in the municipal waste collection. Asia-Pacific Journal of Operational Research. 2017;34(3):1740015. DOI: 10.1142/S0217595917400152.
Nossack J, Golden B, Pesch E, Zhang R. The windy rural postman problem with a time-dependent zigzag option. European Journal of Operational Research. 2017;258(3):1131-1142. DOI: 10.1016/j.ejor.2016.09.010.
Keskin ME, Yılmaz M, Triki C. Solving the hierarchical windy postman problem with variable service costs using a math-heuristic algorithm. Soft Computing. 2023;27:8789–8805. DOI: 10.1007/s00500-023-08032-z.
Lacomme P, Prins C, Sevaux M. A genetic algorithm for a bi-objective capacitated arc routing problem. Computers and Operations Research. 2006;33(12):3473-3493. DOI: 10.1016/j.cor.2005.02.017.
Grandinetti L, Guerriero F, Laganà D, Pisacane O. An optimization-based heuristic for the multi-objective undirected capacitated arc routing problem. Computers and Operations Research. 2012;39(10):2300-2309. DOI: 10.1016/j.cor.2011.12.009.
Rabbani M, Farshbaf-Geranmayeh A, Haghjoo N. Vehicle routing problem with considering multi-middle depots for perishable food delivery. Uncertain Supply Chain Management. 2016;4(3):171–182. DOI: 10.5267/j.uscm.2016.3.001.
Erdős P, Rényi A. On random graphs. Publicationes Mathematicae. 1959;6:290–297.
Gilbert E. Random graphs. Annals of Mathematical Statistics. 1959;30(4):1141–1144. DOI: 10.1214/aoms/1177706098.
Tan G, Cui X, Zhang Y. Chinese postman problem in stochastic networks. Joint International Conference on Autonomic and Autonomous Systems and International Conference on Networking and Services (ICAS-ISNS’05), 23-28 Oct. 2005, Papeete, Tahiti, French Polynesia. 2005. p. 78–78. DOI: 10.1109/ICAS-ICNS.2005.31.
Wang HF, Wen YP. Time-constrained Chinese postman problems. Computers and Mathematics with Applications. 2002;44:375–38. DOI: 10.1016/S0898-1221(02)00156-6.
Sökmen ÖÇ, Yılmaz M. Hierarchical Chinese postman problem with fuzzy travel times. Iranian Journal of Fuzzy Systems. 2021;18(5):87–105. DOI: 10.22111/ijfs.2021.6257.
Liu B. Uncertainty theory, 2nd ed. Springer, Berlin, 2007.
Majumder S. Some network optimization models under diverse uncertain environments [Internet]. arXiv [cs.AI]. 2021. Available from: http://arxiv.org/abs/2103.08327.
Samanifar S, Ahmadzade H, Nehi HM. Uncertain maximum benefit about Chinese postman problem. Journal of Uncertain Systems. 2024;17(3):2350009. DOI: 10.1142/S1752890924500090.
Samanifar S, Nehi HM, Ahmadzade H. Maximum profit Chinese postman problems using fuzzy weighted edge length. New Mathematics and Natural Computation. 2025. DOI: 10.1142/S1793005726500080.
Samanifar S, Ahmadzade H, Nehi HM. Windy postman problem under uncertainty. Journal of Uncertain Systems. 2024;17(1):2350014. DOI: 10.1142/S1752890923500149.
Haimes YY, Lasdon LS, Wismer DA. On a bi-criterion formulation of the problems of integrated system identification and system optimization. IEEE Transaction on Systems, Man, and Cybernetics. 1971;1(3):296-297. DOI: 10.1109/TSMC.1971.4308298.
Eskandari H, Geiger CD, Lamont GB. FastPGA: A dynamic population sizing approach for solving expensive multi-objective optimization problems. In: Obayashi S, Deb K, Poloni C, Hiroyasu T, Murata T (eds) Evolutionary multi-criterion optimization. EMO 2007. Lecture Notes in Computer Science, vol 4403. Springer, Berlin, Heidelberg, 2007. DOI: 10.1007/978-3-540-70928-2_14.
Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation. 2002;6(2):182- 197. DOI: 10.1109/4235.996017.
Charnes A, Cooper WW. Chance-constrained programming. Management Science. 1959;6(1):73–79. DOI: 10.1287/mnsc.6.1.73.
Liu B, Iwamura K. Chance-constrained programming with fuzzy parameters. Fuzzy Sets and Systems. 1998;94(2):227-237. DOI: 10.1016/S0165-0114(96)00236-9.
Zadeh LA. Fuzzy sets. Information and Control. 1965;8(3):338–353. DOI: 10.1016/S0019-9958(65)90241-X.
Zadeh LA. Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets and Systems. 1978;1:3–28. DOI: 10.1016/S0165-0114(99)80004-9.
Liu B, Liu YK. Expected value of fuzzy variable and fuzzy expected value models. IEEE Transactions on Fuzzy Systems. 2002;10(4):445–450. DOI: 10.1109/TFUZZ.2002.800692.
Liu B. Uncertainty theory: An introduction to its axiomatic foundation, 1st ed. Springer-Verlag, Berlin, 2004.
Liu B. Theory and practice of uncertain programming, 1st ed. Springer-Verlag, Berlin, 2002.
Zhou J, Wang Q, Zhang X. The inverse spanning tree of a fuzzy graph based on credibility measure. Journal of Communications. 2013;8(9):566–571. DOI: 10.12720/jcm.8.9.566-571.
Liu YK, Gao J. The independence of fuzzy variables with applications to fuzzy random optimization. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems. 2007;15(2):1-20. DOI: 10.1142/S021848850700456X.
Fonseca CM, Fleming PJ. Genetic algorithms for multi-objective optimization: Formulation, discussion and generalization. Proceedings of the fifth International Conference on Genetic Algorithms, 1 Jun. 1993, San Francisco, CA, USA. 1993, p. 416-423.
Zitzler E, Thiele L. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation. 1999;3(4):257–271. DOI: 10.1109/4235.797969.
Nebro AJ, et al. Optimal antenna placement using a new multi-objective CHC algorithm. GECCO '07 Proceedings of the 9th annual conference on Genetic and evolutionary computation 2007, 7-11 Jul. 2007, New York, NY, USA. 2007, p. 876-883. DOI: 10.1145/1276958.127712.
Van Veldhuizen DA, Lamont GB. Evolutionary Computation and Convergence to a Pareto Front. In John R. Koza (Ed.). Late Breaking Papers at the Genetic Programming 1998 Conference, 22-25 Jul. 1998, Stanford, CA, USA. 1998, p. 221–228.
Durillo JJ, Nebro AJ. jMetal: A Java framework for multi-objective optimization. Advances in Engineering Software. 2011;42(10):760-771. DOI: 10.1016/j.advengsoft.2011.05.014.
Gardner MJ, Altman DG. Confidence intervals rather than P values: Estimation rather than hypothesis testing. British Medical Journal (Clinical research ed.). 1986;292:746–50.
Copyright (c) 2025 Debosree PAL, Haresh Kumar SHARMA, Olegas PRENTKOVSKIS, Falguni CHAKRABORTY, Lijana MASKELIŪNAITĖ
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
