Implementación de un algoritmo heurístico de Recocido Simulado para el problema de enrutamiento de vehículos con capacidades homogéneas

Dentro de muchas de las empresas de México y el mundo y más específicamente en el campo de la logística de las mismas, existen muchos problemas generados al momento de la repartición de productos. La investigación que se realiza trabaja con el modelo de Enrutamiento de Vehículos con Capacidades Homogéneas (por sus siglas en inglés Capacited Vehicle Routing Problem CVRP), dicho problema es la representación de un problema de reparto de bienes, el cual, genera rutas de entrega para varios vehículos que cuentan con una capacidad idéntica, y deben repartir productos a un conjunto de clientes dispersos geográficamente, el propósito del problema es minimizar los costos de cada ruta, esto, minimizando la distancia recorrida cambiando el orden de visita de los clientes. En el CVRP se cuenta con un número total de clientes, un conjunto de vehículos y una capacidad para los vehículos, los 3 parámetros no deben ser sobrepasados y en caso de los clientes no puede faltar ninguno por abastecer. El presente problema fue resuelto aplicando la metaheurística del algoritmo: Recocido Simulado e incorporando 3 vecindarios diferentes para la mejora de la solución inicial generada de manera aleatoria. Posteriormente el algoritmo fue probado con instancias de la literatura con el fin de medir su eficacia en calidad de la solución y tiempo de ejecución, dichas instancias van desde los 31 a 80 clientes, perteneciendo a dos grupos distintos de instancias. Los resultados obtenidos, fueron muy satisfactorios y se logró igualar el resultado óptimo conocido en más del 60% de las instancias con las que fue probado el algoritmo. En comparación con otros métodos heurísticos implementados al problema, los resultados reportados en ésta tesis demostraron ser competitivos y muy buenos en cuestión de calidad de solución.

Within many of the companies in Mexico and the world, and more specifically in the field of their logistics, there are many problems generated when distributing products. The investigation that is carried out works with the model of Routing of Vehicles with Homogeneous Capacities (for its acronym in English: Capacitated Vehicle Routing Problem CVRP). This problem is the representation of a problem of distribution of goods, which generates delivery routes for several vehicles that have an identical capacity, and must deliver products to a set of geographically dispersed customers. The purpose of the CVRP is to minimize the costs of each route, thus, minimizing the distance traveled by changing the order of customer visits. In the CVRP there is a total number of customers, a set of vehicles and a capacity for the vehicles, the 3 parameters must not be exceeded and in the case of customers, none can be missing to supply. This problem was solved by applying the metaheuristics of the algorithm: Simulated Annealing and incorporating 3 different neighborhoods to improve the randomly generated initial solution. Subsequently, the algorithm was tested with instances from the literature in order to measure its effectiveness in terms of solution quality and execution time.