Un algoritmo genético para resolver el problema de asignar y secuenciar entregas con restricción de ventanas de tiempo
Export citation
Abstract
En la presente investigación se muestra la aplicación de una de las técnicas de la Computación Evolutiva conocida como Algoritmos Genéticos (AG), para resolver de manera eficiente una variante del problema de ruteo de vehículos con restricciones de ventanas de tiempo (VRPTW por sus siglas en ingles). Motivado por una problemática real se presenta el desarrollo de un algoritmo que logra llevar a cabo la programación de una flotilla de vehículos para atender la demanda diaria de doce centros de distribución ubicados en diversas zonas geográficas; cada centro de distribución cuenta con ventanas de tiempo predefinidas y demandas diarias conocidas. Los vehículos disponibles para realizar las entregas son considerados con capacidades de carga homogéneas y están disponibles las veinticuatro horas del día. En cada una de las entregas realizadas, que inician y terminan en un depósito central, se atiende específicamente a un centro de distribución. El objetivo central de este trabajo, es lograr minimizar el número de vehículos utilizados por día a través de una secuenciación eficiente que permita una mayor utilización de los vehículos y al mismo tiempo, disminuya el tiempo de espera para una nueva reasignación de viajes. En este estudio se construye una población inicial haciendo uso de un algoritmo mejorador de búsqueda local (glotón) para resolver el problema de asignar los viajes y secuenciar los vehículos con los cuales se atenderá la demanda. Posteriormente se ejecuta un algoritmo genético simple para desarrollar una exploración global dentro del conjunto de toda la población de soluciones encontradas. Con una distribución uniforme para representar la demanda de viajes de la planta a los 12 CDí y un diseño experimental completamente al azar con 5 replicas se generaron 12 instancias para evaluar el desempeño del algoritmo. Posteriormente los resultados obtenidos fueron comparados contra los resultados generados haciendo uso del algoritmo 1-RBH programado en CPlex 81 (González, 2005) en el cual fueron evaluadas las mismas instancias; los resultados obtenidos por este medio sirvieron para la definición de una cota inferior la cual facilitó el análisis del desempeño del algoritmo genético propuesto.