Análisis de espacio de búsqueda del problema de ruteo de vehículos

Abstract

La optimización y resolución para problemas complejos es uno de los campos que más investigación y recursos recibe desde diferentes sectores. El problema sobre el que se trabaja durante el desarrollo del proyecto, es el problema de ruteo de vehículos con latencia, junto a los aspectos teóricos que engloba. Se trata de lograr una resolución del problema de manera práctica y eficiente empleando varias técnicas metaheurísticas en instancias de diferentes tamaños. Para lograr los objetivos a nivel práctico se utilizan algunas tecnologías como MongoDB, encargado del almacenamiento de las soluciones que formarán el espacio de búsqueda, CPLEX, la cual nos ayuda a comprobar que los valores de función objetivo de las soluciones alcanzadas son correctos o D3.js empleada en la representación visual del espacio de búsqueda. Con la implementación de las técnicas VNS y LNS se busca obtener soluciones factibles al problema, al mismo tiempo que se realiza comparaciones entre las diferentes metaheurísticas a nivel práctico, contemplando de esta forma la calidad de las soluciones y el tiempo empleado por cada una de ellas en las distintas instancias. De estos resultados extraemos, por ejemplo, que la técnica VNS emplea menos tiempo para la obtención de una solución, pero suele tener menos calidad que las logradas por la LNS. Por último, se estudia el “Fitness landscape” mediante el uso de diferentes métricas, las cuales nos indican la naturaleza del paisaje formado por un conjunto determinado de soluciones del problema, al mismo tiempo que conocemos la aptitud de cada una de ellas.

The optimization and resolution of complex problems is one of the fields that receives more research and resources from different sectors. The problem that is worked on during the development of the project, is the vehicle routing problem with latency as objective function, along with the theoretical aspects that encompasses. The intention is to achieve a resolution of the problem in a practical and efficient using various metaheuristic techniques in instances of different sizes. To achieve the objectives at a practical level, some technologies are used, such as MongoDB, in charge of storing the solutions that will make up the search space, CPLEX, which helps us to verify that the objective function values of the solutions reached are correct or D3.js used in the visual representation of the search space. With the implementation of the VNS and LNS techniques we seek to obtain feasible solutions to the problem, at the same time that comparisons are made between the different metaheuristics at a practical level, contemplating in this way the quality of the solutions and the time used by each one of them in the different instances. From these results we extract, for example, that the VNS technique takes less time to obtain a solution, but usually has less quality than those achieved by the LNS. Finally, the “Fitness landscape” is studied through the use of different metrics, which indicate the nature of the landscape formed by a specific set of solutions to the problem, at the same time that we know the suitability of each of them.