Cómo SimpliRoute resuelve el problema de Ruteo de Vehículos

El problema de Ruteo de Vehículos

El problema de ruteos de vehículos, conocido como VRP por sus siglas en inglés, es un problema complejo de optimización que tiene como objetivo minimizar los costos de transporte asociados a rutas de reparto.

Qué tan complejo es resolver un VRP depende de las diferentes características o restricciones que deben ser consideradas para resolverlo. Algunas de las variantes del VRP son:

1. VRP con flota heterogénea: Los vehículos que componen la flota son diferentes entre sí.
2. VRP con rutas abiertas: Los vehículos no vuelven al punto de iniciación de rutas.
3. VRP con ventanas de tiempo: Los pedidos tienen que ser entregados dentro de un rango horario predefinido.
4. VRP con Pick up and delivery: Los vehículos, como parte de su ruta, tienen que pasar a los centros de abastecimiento para obtener los paquetes a ser distribuidos.

Aún con todos los avances tecnológicos logrados hoy en día, la alta complejidad de los VRPs no ha permitido encontrar soluciones exactas en tiempos razonables, clasificando a los VRP dentro de los NP-difíciles. Dado lo anterior, los problemas de este tipo se resuelven mediante heurísticas o algoritmos que buscan encontrar la mejor solución posible en un tiempo acotado.

‍

La Solución que Brinda SimpliRoute a tu VRP

El objetivo principal de SimpliRoute es ofrecer a todas aquellas empresas que necesitan resolver su propio VRP, una plataforma online de fácil uso que diseñe rutas eficientes en menos de 15 minutos.

La solución que SimpliRoute propone está basada en un potente algoritmo, el cual es sometido a mejoras continuas tras largos procesos de investigación y desarrollo, que integran la literatura académica más reciente en el área y la formulación propia de nuevas estrategias para mejorar la solución del VRP.

Hoy SimpliRoute brinda soluciones de calidad a 7 variantes de VRP, las cuales pueden presentarse como únicas o como una mezcla entre ellas:

1. Capacidad de Carga: Los vehículos tienen capacidad de carga limitada, ya sea en peso o en volumen. Dado lo anterior, las rutas sólo serán viables si es que cada vehículo soporta la carga a ser distribuida a lo largo de su ruta.
2. Flota Heterogénea: Los vehículos disponibles para realizar el reparto pueden tener distintas características. Por ejemplo, pueden ser de distinto tamaño (distintas capacidades), partir y terminar en lugares distintos, tener distintos horarios de trabajo, etc.
3. Rutas Abiertas: Es posible fijar un punto de fin de ruta por cada vehículo (puede ser el mismo que el inicial, o distinto), o permitir que el algoritmo decida cuál es el mejor lugar para dejar el vehículo una vez que se finaliza la ruta.
4. Zonas Geográficas: Algunas empresas necesitan, por las características de su negocio, asignar sus vehículos a determinadas zonas geográficas. Dada esta necesidad, SimpliRoute ha integrado dentro de sus funcionalidades la opción de permitir asignar un vehículo a una o varias zonas, y también varios vehículos a una misma zona.
5. Habilidades Especiales: Algunas visitas tienen características particulares, que hacen que sólo algunos vehículos puedan ser asignados a éstas, y SimpliRoute permite indicar esta relación por medio de habilidades. Si un pedido está marcado con una habilidad particular, sólo los vehículos que tengan esa habilidad asociada podrán realizar esa visita.
6. Prioridades: Con SimpliRoute se pueden trabajar de forma especial las entregas consideradas como “más importantes”. Por ejemplo, es posible asegurar que los clientes marcados como prioritarios no sean dejados fuera de ruta cuando no sea posible entregar todos los pedidos (ya sea por restricciones de tiempo, capacidad u otros).
7. Ventanas de Tiempo: Algunos clientes sólo pueden ser visitados en determinadas ventanas de tiempo, por lo que el algoritmo está diseñado de tal forma que sea capaz de integrar esta información antes de generar las rutas.

El algoritmo comienza con una solución inicial factible de rutas, la cual es comparada con otra solución factible. Entre la 2 se escoge la que dé mejores resultados, es decir, la que optimice mejor los objetivos definidos (Local Search).

Este proceso se repite miles de veces hasta encontrar la solución más cercana al óptimo posible respetando todas aquellas condiciones que se hayan establecido tanto para los vehículos como para los puntos a ser visitados (las variantes).

Con la heurística de SimpliRoute es posible resolver VRPs para una flota de 100 vehículos y 2.000 clientes en menos de 15 minutos. Pero el desafío no termina ahí, se están probando nuevas e innovadoras técnicas que permitan reducir el tiempo de cálculo a menos de 5 minutos, además de entregar soluciones más personalizadas a las operaciones específicas de quienes optimicen con SimpliRoute.

Si te interesa aprender más de este tema, un buen resumen de métodos de resolución de VRPs son estos dos papers de Braysy y Gendreau:

Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms

Vehicle Routing Problem with Time Windows, Part II: Metaheuristics

‍

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

‍