Algoritmo ant colony para solucionar problemas de localización y ruteo de vehículos con flota homogénea
Cargando...
Archivos
Fecha
2016
Profesor/a Guía
Facultad/escuela
Idioma
es
Título de la revista
ISSN de la revista
Título del volumen
Editor
Universidad Andrés Bello
Nombre de Curso
Licencia CC
Licencia CC
Resumen
La metaheurística Ant Colony Optimization (ACO) ha demostrado ser eficiente para resolver problemas combinatorios. Se implementa para resolver el problema de localización y ruteo de vehículos con flota homogénea (CLRP). En particular, el problema consiste en determinar depósitos a ser abiertos, los clientes a ser asignado a cada depósito, y las rutas a ser construidas para satisfacer las demandas de los clientes. El objetivo es minimizar la suma de los costos de apertura de los depósitos, los costos de los vehículos utilizados y los costos variables relacionados con la distancia recorrida en cada ruta. En este trabajo se presenta un enfoque de solución ACO a partir de una solución inicial generada mediante el problema del vendedor viajero (TSP, por sus siglas en inglés), adaptada para un VRP (problema de rutas de vehículos), así para dar solución al problema de localización y ruteo de vehículos (LRP).
La metaheurística ACO es un algoritmo no determinista, dado que las hormigas se mueven aleatoriamente en la búsqueda de una sustancia química, llamada feromona, que indica el camino que debe buscar la hormiga. Los parámetros de ACO, afectan directamente en la calidad de la solución. Por lo tanto, los resultados son obtenidos luego de una exhaustiva calibración de parámetros.
Los mejores resultados obtenidos tienen un gap de 2.258% en promedio, considerando 10 instancias de la literatura, comparados con el mejor costo encontrado de los algoritmos considerados.
Notas
Tesis (Ingeniero Civil Informático)
El proyecto fue parcialmente financiado por fondos estatales, FONDECYT 11150370.
El proyecto fue parcialmente financiado por fondos estatales, FONDECYT 11150370.
Palabras clave
Algoritmos Ant, Optimización Combinatoria, Problema de Rutas de Vehículos