Dos Enfoques para la Solución del Problema de Ruteo de Vehiculos (CVRP): Aplicación a un Caso Real de Recolección de Residuos

Abstract

Los problemas de enrutamiento, tales como el Problema de Ruteo de Vehículos con restricciones de Capacidad, CVRP; han recibido especial atención en los últimos años, debido a su gran aplicabilidad en problemas de logística. El CVRP, puede ser formulado como un problema de programación lineal entera, en el cual el número de restricciones de conectividad de la solución y los requerimientos de capacidad vehicular, crecen exponencialmente con el número de nodos a atender. Esto implica que la solución exacta al problema planteado, sólo puede ser alcanzada para instancias pequeñas del mismo y por lo tanto su utilidad decae en la resolución de problemas de la vida real. En este escenario se presentan al menos dos opciones posibles para abordar esta dificultad: la primera consiste en considerar un conjunto de restricciones alternativas que crezcan polinomialmente con el número de nodos y resolver el nuevo problema con paquetes de software comercial. La segunda opción es la utilización de metaheurísticas, tales como algoritmos meméticos, que suelen presentar como principales desventajas la no garantía de optimalidad y los altos tiempos de cómputo asociados. En este trabajo se propone comparar el desempeño de ambos enfoques, utilizando un software comercial para el primer procedimiento y, para el segundo enfoque, un Algoritmo Memético, 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 en diferentes problemas test presentes en la literatura, y finalmente su aplicación a un problema real de recolección de residuos infecciosos en la ciudad de Rio Cuarto