Conversemos

Funcionalidades -Aug 14, 2018

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

Photo by the author

SimpliRoute

Industria

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

Comienza a optimizar tus rutas ahora 🚀

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í.

Te podría interesar

Política de Inventarios Cómo Construir Una
NOTICIAS

Política de Inventarios: Cómo Construir Una

Contar con una política de inventarios clara permite a las empresas mantener un equilibrio entre disponibilidad de productos y eficiencia operativa.
En esta nota, te explicamos qué es una política de inventarios, cuáles son sus objetivos, los tipos más comunes y cómo diseñarla según las necesidades de tu empresa. También te damos recomendaciones para aplicarla de manera efectiva y asegurar un flujo logístico sin interrupciones.

May 20, 2025

Drones de Entrega: Qué Debes Saber

Drones de Entrega: Qué Debes Saber

Los drones de entrega están transformando la logística al ofrecer soluciones rápidas y eficientes para el transporte de mercancías. Estos vehículos aéreos no tripulados permiten realizar entregas en zonas de difícil acceso, reducir los tiempos de distribución y minimizar costos operativos. Empresas como Zipline y Wing ya implementan estos sistemas en diversos países, demostrando su eficacia en la entrega de suministros médicos y productos de consumo. Sin embargo, su adopción enfrenta desafíos como la regulación aérea, limitaciones de carga y la necesidad de infraestructuras adecuadas. A medida que la tecnología avanza, se espera que los drones de entrega jueguen un papel cada vez más importante en la cadena de suministro global.

May 12, 2025