Reducing the complexity of implementing the vehicle routing problem using evolutionary strategies and fuzzy logic
Keywords:
Evolutionary computing, evolutionary strategies, hybrid model, Type-1 singleton fuzzy logic system, vehicle routing problem.Abstract
The classical vehicle routing problem (VRP) also called travelling salesman problem (TSP) is one of the most studied cases of nondeterministic polynomial (NP)-complete problems. To solve the NP-complete problem in a real-world scenario (practical problem), it is necessary to generate an initial solution followed by an optimization to reduce the cost in resource consumption. In this paper we propose a hybrid algorithm that combines an evolutionary strategy (ES) for the generation of routes that represent the inputs to a fuzzy logic system (FLS) that is subsequently optimized by the same ES once solved by the fuzzy system. This heuristic optimization technique solves the VRP by finding the route that minimizes the costs as a goal. The union of ES with FLS reduces the complexity of a pure FLS as it only needs the distance in the connections between vertexes to obtain the solution of a system-defining function in comparison to the factorial combination used in some metaheuristics. This proposal tests soft computing (SC) and its capacity to solve combinatorial problems with better precision than a metaheuristic approach such as simulated annealing (SA) and shortest path problem (SP) or Dijkstra model. The results show an accuracy higher than 80% that is usual in the artificial neural networks (ANN); additionally, this approach spends only the 10% of computational time required by SA and SP to obtain a feasible solution.
References
[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
