Una metaheurística híbrida aplicada a un problema de planificación de rutas

Abstract

El problema de planeación de rutas en el ámbito del enrutamiento de transporte ha sido un tema de gran interés debido a su alta complejidad computacional. Algunas de las variaciones a este problema son: el problema d el agente viajero – Travel Salesman Problem (TSP) –, el problema de enrutamiento de vehículos – Vehicle Routing Problem (VRP ) – y el múltiple problema del agente viajero – Multiple Travel Salesman Problem (mT SP ) –. Dentro del VRP se encuentra el problema de recolección, el cual además de designar varias rutas para prestar un servicio de recolección a varios usuarios, tiene en cuenta la capacidad de la flota y la cantidad o demanda de capacidad por usuario. En este artículo se propone un algoritmo híbrido entre un algoritmo genético y un algoritmo de colonia de hormigas para tratar el problema de recolección básico con una flota de capacidad homogénea , múltiples depósitos y un periodo de m días. Finalmente, este trabajo muestra experimentalmente, el comportamiento del algoritmo híbrido en encontrar una solución óptima para el problema particular de recolección.