Skip to main navigation menu Skip to main content Skip to site footer

Vol. 24 No. 2 (2024)
Inquietud Empresarial 24(2) Julio-Diciembre

DECISION-MAKING

Optimization of Chinese Postman Problem Using Fuzzy-Based Priority Weighted Graph

https://doi.org/10.19053/uptc.01211048.17896

Published 2024-10-13

  • Jay Chandra Yadav
    • ,
  • Mohammad Rizwanullah

Jay Chandra Yadav
Research Scholar, Department of Mathematics and Statistics; Manipal University Jaipur; Jaipur-Ajmer Express Highway, Dehmi Kalan, Near Gvk Toll Plaza, Jaipur, Rajasthan 303007

Mohammad Rizwanullah
Department of Mathematics and Statistics; Manipal University Jaipur; Jaipur-Ajmer Express Highway, Dehmi Kalan, Near Gvk Toll Plaza, Jaipur, Rajasthan 303007

Abstract

: In the early 1960s, Chinese mathematician Mei-Ko Kwan (M. Guan) introduced a method aimed at minimizing mail carriers’ route lengths. This method led to the exploration of various formulations of the Chinese Postman Problem (CPP), resulting in at least eight distinct formulations. In response to a practical concern, a new problem formulation called the Priority Constrained Chinese Postman Problem (PCCPP) emerged. In PCCPP, a linear order is provided for a set of significant nodes, and the objective is to traverse all edges at least once while prioritizing the prompt visitation of higher-priority nodes. This paper presents a modified approach to Chinese Postman Problems (CPP) using priorities in a fuzzy environment ranking function applied to priority nodes in CPP to get the optimal result. Finally, this paper also illustrates and justifies the implementation of the modified approach with a numerical problem. The consideration of multi-factors in a multi-graph with priorities gives another scope of research.

 JEL Codes: C44

Received: 18/07/2024. Accepted: 29/09/2024. Published: 13/10/2024.

Keywords

Priority, Eulerian tour, fleury algorithm, Dijkstra’s algorithms, Undirected Graph, Triangular Fuzzy Number

PDF

References

  1. Campbell, J. F., Corberán, A., Plana, I., Sanchis, J. M., & Segura, P. (2021). Solving the length constrained K-drones rural postman problem. European Journal of Operational Research, 292(1), 60-72. https://doi.org/10.1016/j.ejor.2020.10.035 DOI: https://doi.org/10.1016/j.ejor.2020.10.035
  2. Keskin, M. E., & Triki, C. (2022). On the periodic hierarchical Chinese postman problem. Soft Computing, 26(2), 709-724. https://doi.org/10.1007/s00500-021-06213-2 DOI: https://doi.org/10.1007/s00500-021-06213-2
  3. Kramberger, T., & Zerovnik, J. (2005). Chinese postman problem with priorities. In Proceedings of the International Conference on Systems, Operational Research and Informatics (SOR) (Vol. 5, pp. 357-362).
  4. Kramberger, T., & Zerovnik, J. (2007). Priority constrained Chinese postman problem. Logistics & Sustainable Transport, 1(1), 33-46.
  5. Nilofer, M., & Rizwanullah, M. (2020). An implementation of Chinese postman problem with priorities. Journal of Intelligent & Fuzzy Systems, 38(3), 3301-3305. https://doi.org/10.3233/JIFS-190035 DOI: https://doi.org/10.3233/JIFS-190035
  6. Sokmen, O. C., Emec, S., Yilmaz, M., & Akkaya, G. (2019, September). An overview of Chinese postman problem. In Proceeding of the 3rd International Conference on Advanced Engineering Technologies.
  7. Tan, G., Cui, X., & Zhang, Y. (2005, October). Chinese postman problem in stochastic networks. In Proceeding in Joint International Conference on Autonomic and Autonomous Systems and International Conference on Networking and Services (pp. 78-78). IEEE. https://doi.org/10.1109/ICAS-ICNS.2005.31 DOI: https://doi.org/10.1109/ICAS-ICNS.2005.31
  8. Xin, J., Yu, B., D’Ariano, A., Wang, H., & Wang, M. (2022). Time-dependent rural postman problem: Time-space network formulation and genetic algorithm. Operational Research, 22(3), 2943-2972. https://doi.org/10.1007/s12351-021-00639-0 DOI: https://doi.org/10.1007/s12351-021-00639-0
  9. Yadav, J. C., & Rizwanullah, M. (2022, December). Combinatorial Optimization of Type-l Fuzzy Travelling Salesman Problem. In Proceeding of the 2022 International Conference on Computational Modelling, Simulation and Optimization (ICCMSO) (pp. 108-116). IEEE. https://doi.org/10.1109/ICCMSO58359.2022.00033 DOI: https://doi.org/10.1109/ICCMSO58359.2022.00033
  10. Yılmaz, M. (2021). Hierarchical Chinese postman problem with fuzzy travel times. Iranian Journal of Fuzzy Systems, 18(5), 87-105. https://doi.org/10.22111/ijfs.2021.6257
  11. Yu, W., & Batta, R. (2010). Chinese Postman Problem. InWiley Encyclopedia of Operations Research and Management Science. https://doi.org/10.1002/9780470400531.eorms0142 DOI: https://doi.org/10.1002/9780470400531.eorms0142
  12. Zhang, B., & Peng, J. (2015). Chinese Postman Problem in Unecertain Network. Proceedings of the Conference on Operations Research.

Downloads

Download data is not yet available.