Desarrollo de un algoritmo hibrido para resolver el problema de localización ruteo (lrp)

Abstract

El problema conjunto de localización de instalaciones y enrutamiento de vehículos, con capacidad limitada en depósitos y un vehículo por depósito (LRP, por sus siglas en inglés), es definido como un caso especial del problema de ruteo de vehículos (VRP), donde se determina de forma simultánea la localización de depósitos y las rutas de distribución. Dado un conjunto potencial de depósitos, con sus costos de apertura y capacidad, y demandas esperadas de los clientes para determinado horizonte de tiempo, se tiene como objetivo minimizar el costo total dado por la ubicación y distribución, donde cada cliente es visitado exactamente una vez y asignado a un único depósito, sin exceder su capacidad. En este proyecto, se propone un algoritmo híbrido que emplea optimización por colonia de hormigas (ACO, por sus siglas en inglés), con el uso de tres colonias (selección de depósitos, asignación de clientes y VRP), para generar una solución inicial que es mejorada con búsqueda local iterativa (ILS, por sus siglas en inglés) que consta de cuatro estructuras de vecindad y una perturbación. El algoritmo ACO+ILS es implementado en MATLAB y con un banco de pruebas propuesto se emplea un diseño factorial fraccionado con el fin de determinar el efecto y la mejor combinación en valores de los factores. Los resultados del algoritmo propuesto son comparados con los del ACO tradicional mostrando mejoras significativas frente a este en cuanto a disminución costo total del sistema.