" métodos heuristicopara la solución de problemas de ruteo de vehículos con capacidad (cvrp) "

Abstract

El problema de ruteo de vehículos con capacidad ha sido de gran interés a través de los años debido a que representa un ahorro significante para las empresas en la entrega de sus pedidos, este tipo de problemas consiste en encontrar la ruta óptima de un conjunto de rutas con un costo mínimo de ruteo para una flota de vehículos idénticos con capacidad, que pueda visitar a todos los clientes requeridos y satisfacer sus demandas. Desde un punto de vista matemático, el CVRP es un problema de optimización combinatoria que permite establecer diferentes rutas desde un mismo punto de origen hacia todos y cada uno de los nodos del problema, terminando su recorrido en el punto de partida, cumpliendo con una serie de restricciones sujetas a la capacidad del vehículo. Los algoritmos estudiados en este proyecto son el algoritmo de ahorros de Clarke and Wright y el algoritmo del vecino más cercano. Se resuelven ciertas instancias por los dos métodos para comparar resultados y determinar que en la mayoría de los casos el algoritmo de ahorros de Clarke and Wright presenta menores costos que el del vecino. Dentro del desarrollo del proyecto se hace un enfoque puntual en el algoritmo de ahorros para implementar una mejora donde se usa un parámetro llamado forma de la ruta para incrementar los buenos resultados del algoritmo y previene la formación de rutas circulares. Una vez comparados todos los resultados, ahora con el algoritmo de ahorros mejorado, en el software H-CVRP, que fue creado para facilitar cálculos de este tipo para instancias con más de 50 nodos, se comprueba que el algoritmo de ahorros presenta mejores resultados con el parámetro forma de la ruta en la mayoría de las veces que el algoritmo de ahorros sin mejora y que el del vecino más cercano.