Algoritmos Meméticos Aplicados a la Resolución de un Problema de Ruteo de Vehículos Periódico

Abstract

La provisión de servicios tales como la recolección de residuos infecciosos, residuos urbanos, recolección y transporte de leche en los tambos, transporte de personas, etc, tienen a menudo grandes problemas de prestación y altos costos de recolección y procesamiento, por lo que la optimización de sus recorridos tiene un fuerte incentivo económico. Los problemas de ruteo representan una de las más importantes clases de problemas dentro de la logística computacional. En este trabajo se presenta una metodología para la resolución de un problema que incluye la planificación de un esquema de visitas y construcción del conjunto de rutas óptimo, que se describe como un problema de ruteo de vehiculo periódico (PVRP, Periodic Vehicle Routing Problem), aplicado a un caso real de recolección de residuos infecciosos en la ciudad de Río Cuarto. Es conocido que el PVRP está incluido dentro de los problemas catalogados como NP-Hard, razón por la cual las heurísticas aparecen como métodos de resolución atractivos por su capacidad de brindar soluciones de alta calidad en tiempos razonables, para instancias de tamaño considerable, tal como aparecen en las aplicaciones reales. En el procedimiento de resolución propuesto, en este trabajo, se construye un Algoritmo Memético, que está basado en técnicas de Computación Evolutiva equipadas con diferentes y variados mecanismos de búsqueda local que aseguran la explotación intensiva de regiones promisorias del espacio de búsqueda. Se presenta la metodología y su desempeño para la optimización de la prestación del servicio de recolección diferenciada y transporte de residuos patógenos.