Reducción de la complejidad de implementar el problema de ruteo de vehículos usando estrategias evolutivas y lógica difusa
Palabras clave:
Cómputo evolutivo, estrategias evolutivas, lógica difusa tipo 1, modelo híbrido, problema de ruteo de vehículos.Resumen
El problema de ruteo de vehículos (VRP) clásico, también llamado problema del agente viajero (TSP) es uno de los casos más estudiados de problemas polinomiales no determinísticos (NP) - completos. Para resolver un problema NP-completo en un escenario del mundo real (problema práctico), es necesario generar una solución inicial seguida de una optimización para reducir el costo en el consumo de recursos. En este trabajo se propone un algoritmo híbrido que combina una estrategia evolutiva (ES) para la generación de rutas que representan la entrada para un sistema difuso (FLS) que posteriormente es optimizado por la misma ES una vez resuelto por el sistema difuso. Esta técnica de optimización heurística resuelve el VRP encontrando la ruta que minimiza los costos como objetivo. La unión de las ES con la lógica difusa reduce la complejidad de un sistema difuso puro ya que sólo necesita la distancia en las conexiones entre los vértices para obtener la solución de una función que define el sistema, en comparación con la combinación factorial utilizada en algunas de las metaheurísticas. Esa propuesta pone a prueba el cómputo suave (SC) y su capacidad para resolver problemas combinatorios con mejor precisión que un enfoque metaheurístico como el recocido simulado (SA) y el problema del camino más corto (SP) o modelo de Dijkstra. Los resultados muestran una precisión mayor al 80% que es habitual en las redes neuronales artificiales (ANN), adicionalmente este enfoque dedica sólo el 10% del tiempo computacional requerido por el SA y el SP para obtener una solución factible.
Referencias
[1] Dantzig, G., Ramser, J., (1956). “The truck dispatching problem.” Managements Science 6(1), Pp. 80-91. https://doi.org/10.1287/mnsc.6.1.80
[2] Erdelić, T. & Carić, T., (2019). “A survey on the electric vehicle routing problem: variants and solution approaches”. Journal of Advanced Transportation, 2019, Pp.1-48, https://doi.org/10.1155/2019/5075671
[3] Montes Dorantes P.N., Ireta Sánchez P.H., Velarde Cantú J.M., Liñán García E., Méndez G.M. (2018). “Design and optimization of Distribution Routes Using Evolutionary strategy and Type-1 Singleton Neuro-fuzzy systems”. IEEE LATIN AMERICA TRANSACTIONS, 16(5), Pp. 1499-1507. DOI: 10.1109/TLA.2018.8408447.
[4] Goel R. & Maini R. (2017). “Vehicle routing problem and its solution methodologies: a survey”. International Journal Logistics Systems and Management. 28(4), Pp. 419-435. https://doi.org/10.1504/IJLSM.2017.087786
[5] Han, M. & Wang, Y. (2018, December). “A survey for vehicle routing problems and its derivatives”. In IOP Conference Series: Materials Science and Engineering. 452(4), Pp. 042024. IOP Publishing. https://doi: 10.1088/issn.1757-899X
[6] Bhuvaneswari, M., Eswaran, S., & Rajagopalan, S. P. (2018). “A survey of vehicle routing problem and its solutions using bio-inspired algorithms”. International Journal of Pure and Applied Mathematics,118(9), Pp. 259-64.
[7] Kassem, S., Korayem, L., Khorshid, M., & Tharwat, A. (2019, October). “A hybrid bat algorithm to solve the capacitated vehicle routing problem”. In 2019 Novel Intelligent and Leading Emerging Sciences Conference (NILES) (Vol. 1, pp. 222-225). IEEE.
[8] Ireta Sanchez P.H., Montes Dorantes P.N., Mendoza A. y Solis R. G. (2019). “Problema de trazo de rutas vehiculares con terminación diferente al depósito central”. En: Sánchez Lara B, Torres Mendoza R.M., Gómez Maturano J., Cedillo Campos M.G. (eds) Innovación Logística en América Latina: Nuevas Perspectivas. Asociación Mexicana de logística y cadena de suministro A.C., Universidad Nacional Autónoma de México. ISBN 978-607-96403-1-6, pp. 82-88.
[9] Pérez-Salas G., González-Ramírez R.G., Cedillo-Campos M.G. (2014). “A holistic approach for measuring the international logistics costs”. 2nd International Congress on Logistics & Supply Chain, (CiLOG2014) proceedings of, Universidad Anahuac. Huixquilucan, Estado de México. October 16-17. 2014.
[10] http://vrp.atd-lab.inf.puc-rio.br/index.php/en/
[11]Brekkå, I., Randøy, S., Fagerholt, K., Thun, K., & Vadseth, S. T. (2022). “The Fish Feed Production Routing Problem”. Computers & Operations Research, 144, Pp. 105806.
https://doi.org/10.1016/j.cor.2022.105806
[12] Aliahmadi, S. Z., Barzinpour, F., & Pishvaee, M. S. (2020). “A fuzzy optimization approach to the capacitated node-routing problem for municipal solid waste collection with multiple tours: A case study”. Waste Management & Research, 38(3), Pp.279-290. https://doi.org/10.1177/0734242X19879754
[13] Tordecilla, R. D., Martins, L. D. C., Panadero, J., Copado, P. J., Perez-Bernabeu, E., & Juan, A. A. (2021). “Fuzzy simheuristics for optimizing transportation systems: Dealing with stochastic and fuzzy uncertainty”. Applied Sciences, 11(17), Pp.7950. https://doi.org/10.3390/app11177950
[14] Sánchez-Ansola, E., Pérez-Pérez, A. C., & Rosete, A. (2020). “School Bus Routing Problem with Fuzzy Walking Distance”. Polibits, 62, Pp.69-75. https://doi.org/10.17562/PB-62-8
[15] Zhang, S., Chen, M., Zhang, W., & Zhuang, X. (2020). “Fuzzy optimization model for electric vehicle routing problem with time windows and recharging stations”. Expert systems with applications, 145, Pp.113123. https://doi.org/10.1016/j.eswa.2019.113123
[16] Mendel J. M. (2017). Uncertain rule-based fuzzy systems. Introduction and new directions, Springer.
[17] Goel, R. (2019). “Fuzzy based parameter adaptation in ACO for solving VRP”. International Journal of Operations Research and Information Systems (IJORIS), 10(2), Pp. 65-81. DOI: 10.4018/IJORIS.2019040104
[18] Kondratenko, Y., Kondratenko, G., Sidenko, I., & Taranov, M. (2020, July). “Fuzzy and evolutionary algorithms for transport logistics under uncertainty”. In International Conference on Intelligent and Fuzzy Systems (pp. 1456-1463). Springer, Cham. https://doi.org/10.1007/978-3-030-51156-2_169
[19] Jin, C. X., Zhang, Y., & Li, F. C. (2021, June). “Research on Path Optimization Problem Based on Satisfaction Degree in Fuzzy Demand Environment”. In Journal of Physics: Conference Series 1955(1), Pp. 012056. IOP Publishing. doi: 10.1088/issn.1742-6596
[20] Oliva, D., Copado, P., Hinojosa, S., Panadero, J., Riera, D., & Juan, A. A. (2020). “Fuzzy simheuristics: Solving optimization problems under stochastic and uncertainty scenarios”. Mathematics, 8(12), Pp. 2240. https://doi.org/10.3390/math8122240
[21] Peker, I., Caybasi, G., Buyukozkan, G., & Gocer, F. (2019, July). “Evaluation of home health care vehicle routing methods by intuitionistic fuzzy AHP”. In International Conference on Intelligent and Fuzzy Systems (pp. 607-615). Springer, Cham. DOI: 10.1007/978-3-030-23756-1_74
[22] Yılmaz, M. (2021). “Hierarchical Chinese postman problem with fuzzy travel times”. Iranian Journal of Fuzzy Systems, 18(5), Pp. 87-105. DOI: 10.22111/IJFS.2021.6257
[23] Zheng, J., Wang, S., Wang, L., Chen, J. F., Wang, L., Hao, J.& Sun, Z. (2020, July). “A two-stage algorithm for fuzzy online order dispatching problem”. In 2020 IEEE Congress on Evolutionary Computation (CEC). Pp. 1-8. IEEE. DOI: 10.1109/CEC48606.2020.9185858
[24] Çakır, E., Ulukan, Z., Kahraman, C. (2022). “A Fuzzy Modeling for Time Constrained Vehicle Routing Problem”. In: Kahraman, C., Cebi, S., Cevik Onar, S., Oztaysi, B., Tolga, A.C., Sari, I.U. (eds) Intelligent and Fuzzy Techniques for Emerging Conditions and Digital Transformation. INFUS 2021. Lecture Notes in Networks and Systems, 307. Pp.511-519. Springer, Cham. https://doi.org/10.1007/978-3-030-85626-7_60
[25] Zacharia, P., Drosos, C., Piromalis, D., & Papoutsidakis, M. (2021). “The vehicle routing problem with fuzzy payloads considering fuel consumption”. Applied Artificial Intelligence, 35(15), Pp. 1755-1776. https://doi.org/10.1080/08839514.2021.1992138
[26] Wang, K., Lan, S., & Zhao, Y. (2017). “A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service”. Journal of the Operational Research Society, 68(11), Pp. 1409-1421. https://doi.org/10.1057/s41274-016-0170-7
[27] Zhang, S., Chen, M., Zhang, W., & Zhuang, X. (2020). “Fuzzy optimization model for electric vehicle routing problem with time windows and recharging stations”. Expert systems with applications, 145, 113123. https://doi.org/10.1016/j.eswa.2019.113123
[28] Karimi-Mamaghan, M., Mohammadi, M., Meyer, P., Karimi-Mamaghan, A. M., & Talbi, E. G. (2022). “Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art”. European Journal of Operational Research, 296(2), Pp. 393-422. https://doi.org/10.1016/j.ejor.2021.04.032
[29] Gupta, P., Govindan, K., Mehlawat, M. K., & Khaitan, A. (2022). “Multiobjective capacitated green vehicle routing problem with fuzzy time-distances and demands split into bags”. International Journal of Production Research, 60(8), Pp. 2369-2385. https://doi.org/10.1016/j.ejor.2021.04.032
[30] Villalva, J. R., Monserrate, G. J., (2013). “Optimización del plan de visitas de inspección en el servicio de mantenimiento de áreas verdes de la ciudad de Guayaquil”. (Master dissertation, ESPOL).
[31] Rechenberg, I. (1973) Evolutionsstrategie, Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Stuttgart: Frommann Holzboog
[32] Darwin, C.R. (1859). On the origin of species by means of natural selection, or the preservation of favoured races in the struggle for life. 1st edn. London: John Murray.
[33] Mendel, J. G. (1865) Versuche über Plflanzenhybriden. Verhandlungen des naturforschenden Vereines in Brünn, Bd. IV für das Jahr, Abhandlungen: P.p. 3-47.
[34] Droste, S., Jansen, T., Wegener, I. (2002). “On the analysis of the (1 + 1) evolutionary algorithm”. Theoretical Computer Science, 276, Pp.51–81, https://doi.org/10.1016/S0304-3975(01)00182-7.
[35] Montes-Dorantes, P. N., Santoyo, A. M., & Méndez, G. M. (2018). “Modeling Type-1 Singleton Fuzzy Logic Systems using statistical parameters in foundry temperature control application”. Smart and Sustainable Manufacturing Systems. 2(1), Pp. 180-20 .https://doi.org/10.1520/SSMS20180031
[36] Mandami, E. H., Assilian, S. (1975). “Experiment in Linguistic Synthesis with a Fuzzy Logic Controller”, International Journal of Man-Machine Studies, 7(1), Pp. 1-13, https://doi.org/10.1016/S0020-7373(75)80002-2.
[37] Mendel, J. M. (2001). Uncertain Rule-Based Fuzzy Logic Systems: Introduction and New Directions, Prentice.
[38] Joshaghan, M. A., Kamyad, A. V., Razavi, A. R., Norouzy, (2014). “A. Evaluation of the Nutritional Effects of Fasting on Cardiovascular Diseases, Using Fuzzy Data Mining.” Journal of Fasting and Health, 3(1), Pp. 14-21.
[39] Weisstein, E. W. Platonic Solid. MathWorld: A Wolfram Web Resource. [Online], [date of reference February 24th of 2022]. Available at: http://mathworld.wolfram.com/PlatonicSolid.html.
[40] Brito, J., Campos, C., Castro, J.P., Martínez, F.J., Melián, B., Moreno, J.A., Moreno, J.M. (2008). “Fuzzy Vehicle Routing Problem with time windows”, Proceedings of IPMU'08, Pp. 1266-1273.
[41] Slodowy, P. (1983). Platonic solids, Kleinian singularities, and Lie groups. In Algebraic geometry. Pp. 102-138. Springer Berlin Heidelberg.
[42] S. Kirkpatrick, C. C. D. Gelatt & M. P. Vecchi, (1983). “Optimization by Simulated Annealing. Science”. Science, New Series, 220(4598), pp. 671-680.
[43] V. Cerny, (1985). “Thermodinamical Approach to the Traveling Salesman Problem:An Efficient Simulation Algorithm”. Journal of Optimization Theory and Applications, 45(1), Pp. 41-51, 1985. https://doi.org/10.1007/BF00940812
[44] Huang, C. Y. R., Lai, C. Y., & Cheng, K. T. T. (2009). Fundamentals of algorithms. In Electronic design automation. Pp. 173-234. Morgan Kaufmann.
[45] Fox, B. L., Lenstra, J. K., Rinnooy Kan, A. H. G. and Schräge, L. E. (1978). “Branching from the largest upper bound: folklore and facts”. European Journal of Operational Research. 2, Pp. 191-194. https://doi.org/10.1016/0377-2217(78)90092-9
[46] Chevroton, H., Kergosien, Y., Berghman, L., & Billaut, J. C. (2021). “Solving an integrated scheduling and routing problem with inventory, routing and penalty costs”. European Journal of Operational Research, 294(2), Pp. 571-589. https://doi.org/10.1016/j.ejor.2021.02.012
[47] Anderson, J.A. Redes Neurales. (2007), Alfaomega.
[48] Forget, N., Gadegaard, S. L., Klamroth, K., Nielsen, L. R., & Przybylski, A. (2022). “Branch-and-bound and objective branching with three or more objectives”. Computers & Operations Research, 148, Pp. 106012. https://doi.org/10.1016/j.cor.2022.106012
