Todo lo que no sabías sobre el VPR con ventanas de tiempo

En el mundo real cada VRP (Problema de Ruteo de Vehículos) tiene sus propias restricciones y condiciones especiales, las cuales dependen de las variantes del problema que están relacionadas con el tipo de industria y requerimientos del negocio, entre otras cosas.

Una de las variantes más estudiadas del problema de ruteo de vehículos es la que considera ventanas de tiempo (VRPTW por sus siglas en inglés); definir en qué horarios es posible hacer una visita y en cuáles no, mejora la gestión y el funcionamiento de la cadena de transporte, impactando positivamente la experiencia de los clientes que reciben o envían un producto.

‍

Cada variante que conforma un VRP agrega cierto grado de dificultad en la obtención de soluciones de calidad (que no son necesariamente exactas, como vimos en el artículo anterior). En especial, la variante con Ventanas de Tiempo enlentece significativamente el cálculo de rutas, desafiando a SimpliRoute a desarrollar un nuevo algoritmo que brinde soluciones inteligentes en menos de 15 minutos.

La disminución de la velocidad en el cálculo de una solución de calidad se debe principalmente al proceso de verificación que evalúa la factibilidad de insertar un nuevo cliente a la ruta (con su propia ventana de tiempo), sin que afecte las entregas de los que ya fueron evaluados y agregados a dicha ruta.

‍

Cada nuevo cliente a ingresar significa otro round de reevaluación de factibilidad de entregas. Este proceso se realiza tantas veces durante la búsqueda de mejores soluciones, que termina siendo responsable de un gran porcentaje del tiempo total de ejecución del algoritmo. Por ejemplo, si queremos calcular el resultado de un problema con 600 entregas y 35 vehículos, se necesita hacer esa evaluación cerca de 750 millones de veces.

‍

Después de un arduo trabajo investigativo y discusión grupal, se llegó a la conclusión de que para solucionar un VRP con Ventanas de Tiempo en el tiempo deseado, se puede seguir la metodología expuesta por Lu & Dessouky (2006), en donde se calcula el tiempo máximo que un pedido puede ser retrasado sin que afecte las entregas siguientes. Así, usando tal información, es posible calcular mucho más rápidamente si es que dentro de ese intervalo de tiempo es posible insertar una nueva visita a la ruta. Tomando el mismo ejemplo que en el párrafo anterior (600 entregas y 35 vehículos), si aplicamos esta estrategia, el número de chequeos que hay que realizar baja a menos de 100 millones, lo cual permite entregar una solución de la misma calidad en un tiempo 30% menor.

Para demostrar cómo funciona este mecanismo, supongamos que tenemos una ruta que en este momento lleva los pedidos de los clientes “1”, …, “7”, y queremos ver si es posible insertar al cliente “a” entre los clientes “3” y “4”. (en la figura se muestran los tiempos de holgura en globos rosa).

‍

Digamos que antes de insertar al cliente “a”, todos los clientes de la ruta llegan dentro de su ventana horaria, y en particular se llega al cliente “4” a las 13:00. Supongamos también que si se inserta el cliente “a”, como ahora ya no va a dirigirse directamente al “4” después de servir al cliente “3”, si no que pasará primero por “a”, la nueva hora de llegada a “4” son las 13:45. Este retraso de 45 minutos podría causar que la hora de llegada a “4” caiga fuera de su propia ventana horaria, pero también puede pasar que la llegada a “4” no tenga problemas, si no que el retraso haga que alguno de los clientes “5”, “6” o “7” ya no pueda ser servido a tiempo.

En este ejemplo, si utilizamos la forma antigua de evaluar factibilidad para asegurarnos de que todas las entregas siguen cumpliendo con sus ventanas horarias después de agregar la entrega “a” a la ruta, tendríamos que chequear una a una las entregas “4”, “5”, “6” y “7. Por otro lado, si hacemos uso del nuevo algoritmo, sólo tenemos que calcular cuánto más tarde se llega al cliente “4” luego de entregar “a”, y comparar ese valor con el que entrega esta nueva metodología, que corresponde al máximo tiempo que puede retrasarse la llegada a “4” sin que ese atraso haga que algún cliente de más adelante deje de cumplir su ventana horaria. Así, como el retraso es de 45 minutos, sabemos que el cliente no puede ser insertado ya que el globo rosa muestra que el tiempo de holgura es solo de 40 minutos, por lo que antes del cliente “4” solo se puede insertar un cliente que provoque un retraso máximo de 40 minutos.

Entendemos que el tiempo que debe tardar nuestra plataforma en entregar una respuesta es esencial, por lo que siempre que implementamos alguna mejora a nuestros algoritmos, nuestro foco no solo está puesto en entregar rutas con menores costos, si no que también en mantener tiempos de ejecución razonables. En particular, la forma en la que estamos chequeando las ventanas horarias nos permite mantener el tiempo de respuesta en menos de 15 minutos para operaciones de tamaño importante, y en menos de 1 minuto para operaciones pequeñas. Lo que buscamos es que la optimización de rutas sea rápida, para que los ruteadores puedan tomar decisiones, hacer cambios y finalizar su planificación en una sola sesión de trabajo.

‍

¡De nada sirve tener el algoritmo más exacto del mundo si va a tardar 20 días en entregar una respuesta!

‍

¿Te gustaría probar SimpliRoute gratis? Solicita acceso aquí.

‍