TESIS MAESTRÍA
Implementación de un algoritmo heurístico de Recocido Simulado para el Problema de Enrutamiento de Vehículos con Capacidades Homogéneas
Dalia Vanessa Arce Ortega
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.