Optimización de Rutas

Planificación de rutas optimizada
La planificación de rutas, de forma muy general, se puede definir como la asignación de recursos a unos puntos a lo largo del tiempo.
Un ejemplo muy habitual de este tipo de problemas es una empresa que dispone de una flota de vehículos (sus recursos) y tiene que entregar una serie de pedidos a unos clientes (los puntos a visitar). La solución del problema será asignar a los clientes el vehículo con el que se les hará la entrega e indicar cuando se hará esa entrega. Es fácil entender que hay muchas posibilidades de resolver este problema, o de repartir los clientes entre los distintos vehículos y de ordenarlos dentro de cada vehículo, pero hacerlo de una u otra forma puede suponer una gran diferencia. Realizar una planificación de rutas optimizada supone un gran ahorro de km, tiempo y coste, además de la satisfacción de nuestros clientes.
¿Por qué es importante hacer una planificación optimizada?
Para responder a esta pregunta nos basaremos en un ejemplo extraído de un Webinar de Rubén Ruiz para ITI.
El ejemplo consiste en encontrar la forma de visitar 20 ciudades recorriendo la menor distancia posible. A esto se le llama resolver un TSP o problema del viajante.
En principio parece bastante sencillo o al menos mucho más sencillo que los que tienen que resolver la mayoría de empresas en su operativa diaria. Sin embargo, no lo es tanto, ya que hay nada menos que 2.430.000.000.000.000.000 posibles soluciones.
Una forma lógica de resolver este problema, y que es habitual utilizar cuando no se dispone de software específico para la optimización de rutas, es partir de un punto y moverse al punto o vecino más cercano. Por ejemplo, si partimos de Málaga iríamos primero a Sevilla, después a Córdoba, Badajoz … y seguiríamos así hasta construir toda la ruta. Aplicando la misma lógica, si partimos de Valencia, el vecino más cercano es Castellón, y de ahí, entre los restantes el más próximo es Alicante, Albacete, etc.
Solo mirando el mapa ya se puede apreciar que, aunque el criterio que se ha seguido es muy razonable, la solución tiene bastante margen de mejora. Veamos de cuánto es esta mejora aplicando software de optimización de rutas.
Con la ayuda de algoritmos de optimización, obtenemos la solución óptima, es decir, la ruta más corta para visitar todas las ciudades. Pasando de una ruta de 5.244 Km a una de tan solo 3.946 Km, esto es, hemos conseguido reducir la distancia a recorrer un 25%.
Con esto queremos resaltar la gran importancia que tiene usar herramientas de optimización de rutas, ya que los beneficios que se pueden obtener son enormes. Es más, hemos visto un ejemplo exageradamente simple, así que es fácil imaginar lo que se puede conseguir cuando hay que generar rutas para toda una flota de vehículos y cientos de puntos que visitar, donde ni siquiera encontrar una solución es fácil a ‘simple vista’.
¿Dónde se utiliza la planificación de rutas?
Normalmente cuando se piensa en planificación de rutas nos vienen a la cabeza ejemplos como el anterior, donde uno o varios vehículos tienen que entregar unos pedidos a varios clientes.
Sin embargo, hay muchas más aplicaciones y para sectores muy diversos. Aquí os dejamos algunos ejemplos:
Vending
Todos hemos visto y utilizado las máquinas expendedoras que hay repartidas por las ciudades y en muchos edificios públicos. Abastecer a estas máquinas de los artículos necesarios da como resultado un problema de optimización de rutas con algunas particularidades especiales.
- Los puntos de entrega pueden estar muy próximos entre sí, lo que genera rutas muy cortas en distancia, pero con muchas paradas, donde el tiempo de reposición cobra mayor importancia en detrimento del tiempo de tránsito.
- Que haya tantas paradas lo convierte en un problema tremendamente costoso de resolver en cuanto a coste computacional se refiere.
- Se busca sectorizar los puntos de entrega, para cubrir cada día una zona y así evitar desplazamientos innecesarios.
Rutas de pasajeros a demanda
Este problema se aplica especialmente en las zonas rurales, donde hay pueblos por los que el autobús solo pasa si el usuario lo pide.
Este problema tiene la peculiaridad de que las rutas se va creando a medida que van llegando las peticiones. Además, también puede darse el caso de que el usuario demande una hora de paso. Esto supone que la ruta óptima ya no sea la que menos distancia recorre, sino la que pueda atender a más usuarios.
Rutas escolares o de trabajadores
Son las rutas en las que se recoge a los estudiantes o a los trabajadores para llevarlos al colegio o al trabajo respectivamente. Y como no también aparecen algunas restricciones particulares para este tipo de problemas:
- Evitar que alguno de los pasajeros esté demasiado tiempo de trayecto. Por ejemplo, si un trabajador empieza su jornada a las 8:00 no querrá que el autobús lo recoja a las 6:00, por mucho que le digamos que esa ruta es óptima en Km.
- También hay restricciones con la distancia de la parada al domicilio. Naturalmente, agrupar a muchos usuarios en una parada reduce tiempo y Km. Sin embargo, esto genera conflictos si por ejemplo a un trabajador lo recogen en la puerta de casa y el otro ha tenido que andar 2 km hasta allí.
Podríamos seguir añadiendo ejemplos a la lista, como servicios de recogida de basuras, recogida de paquetes tanto a empresas como a domicilio, y un largo etc. que la haría interminable. Pero más que con los ejemplos, con lo que nos tenemos que quedar es con la idea de que hay muchas aplicaciones y cada una tiene sus peculiaridades.
Conclusión
La planificación de rutas tiene muchas y muy diversas aplicaciones. Además, cada caso tiene sus características particulares, lo que supone que lo que es bueno para un sector y un problema determinado, no tenga que serlo necesariamente para otro.
Por otro lado, están de sobra probados los beneficios que se pueden obtener si se optimiza la planificación de las rutas, por tanto, no hacerlo sería perder una ventaja muy valiosa respecto a la competencia.
Por último, queda recomendar a quien se decida a hacerlo, que lo haga con la ayuda de un profesional que le guie en el análisis de su problemática y le ayude a encontrar la herramienta que mejor se adapte a sus necesidades.