Optimización del problema del cartero chino utilizando un gráfico ponderado con prioridad restringida en un entorno difuso
- Jay Chandra Yadav
, - Mohammad Rizwanullah
Resumen
A principios de los años 1960, el matemático chino Mei-Ko Kwan (M. Guan) introdujo un método destinado a minimizar las longitudes de las rutas de los carteros. Este método condujo a la exploración de varias formulaciones del Problema del Cartero Chino (CPP), lo que dio como resultado al menos ocho formulaciones distintas. En respuesta a una preocupación práctica, surgió una nueva formulación del problema denominada Problema del Cartero Chino con Prioridad Restringida (PCCPP). En PCCPP, se proporciona un orden lineal para un conjunto de nodos significativos y el objetivo es atravesar todos los bordes al menos una vez mientras se prioriza la visita rápida de los nodos de mayor prioridad. Este artículo presenta un enfoque modificado para los Problemas del Cartero Chino (CPP) utilizando prioridades en una función de clasificación de entorno difuso aplicada a los nodos prioritarios en CPP para obtener el resultado óptimo. Finalmente, este artículo también ilustra y justifica la implementación del enfoque modificado con un problema numérico. La consideración de múltiples factores en un multigrafo con prioridades brinda otro alcance de investigación.
Códigos JEL: C44
Recibido: 18/07/2024. Aceptado: 29/09/2024. Publicado: 13/10/2024.
Palabras clave
Prioridad, recorrido euleriano, , algoritmo de Fleury, algoritmo de Dijkstra, grafo no dirigido, número difuso triangular
Citas
- 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
- 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
- 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).
- Kramberger, T., & Zerovnik, J. (2007). Priority constrained Chinese postman problem. Logistics & Sustainable Transport, 1(1), 33-46.
- 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
- 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.
- 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
- 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
- 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
- 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
- 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
- Zhang, B., & Peng, J. (2015). Chinese Postman Problem in Unecertain Network. Proceedings of the Conference on Operations Research.