Implementación de rugle para resolver el problema de enrutamiento de vehículos con ventanas de tiempo duras (VRPHTW)

Abstract

Los VRP y sus variantes, son unos de los problemas de optimización combinatoria más tratados en la literatura. Estos ya han demostrado ser NP-Hard, debido a que, a medida que aumenta el número de nodos en la red objeto de estudio, el espacio de soluciones a explorar se incrementa de manera desmesurada, por lo tanto, una búsqueda exhaustiva entre todo el espacio de soluciones posible no sería factible y aún no se conoce un algoritmo en Tiempo Polinomial P) para resolverlos de manera óptima. La presente investigación pretende aprovechar el gran potencial que esconde la plataforma online Google Maps, con el fin de resolver la variante más tratada en la literatura del VRP: EL Problema de Enrutamiento de Vehículos con Ventanas de Tiempo Duras (VRPHTW), sometido a rutas con congestión en determinadas horas del día. A través de RuGle, una herramienta informática de código abierto, desarrollada en el lenguaje de programación Ruby y basada en la API de Google Maps, para resolver este problema combinatorio multiobjetivo. Para las instancias de prueba se utilizaron ubicaciones reales, y para calcular la distancia, tiempo de viaje con estimación de tráfico y sin ella, entre los nodos que conforman la red objeto de estudio (instancias), se empleó la API de Google Maps.