La importancia de la optimización de rutas

La importancia de la optimización de rutas

Esta vez estará con nosotros Alfredo García Hernández-Díaz, Catedrático (acreditado) del Departamento de Economía, Métodos Cuantitativos e Historia Económica de la Universidad Pablo de Olavide.

Con más de 50 trabajos publicados y con experiencia en diversos proyectos de I+D+i del Ministerio de Ciencia e Innovación y de la Junta Andalucía, hoy explicará y detallará algunas ideas sobre la importancia de la optimización de rutas.

CURSO PRESENCIAL EN MADRID EN GESTIÓN DE FLOTAS DE VEHÍCULOS

CURSO PRESENCIAL EN MADRID EN GESTIÓN DE FLOTAS DE VEHÍCULOSLa Asociación Española del Transporte (aetransporte.org) Y Advanced Fleet Management Consulting organizan el “Curso para la Gestión de flotas de vehículos” con el fin de formar a los profesionales en gestión de flotas a tomar una visión global y conocer todas las actividades y factores clave involucrados en la gestión de una flota de vehículos. El curso es único en España y presenta un enfoque innovador para la gestión de flotas de vehículos.

Curso en gestión de flotas-Madrid Mayo 2017

¿En qué consiste y por qué es importante la optimización de rutas?

La optimización de rutas de vehículos consiste en definir la planificación óptima (de menor coste o de mayor nivel de servicio, o de menor riesgo…) para nuestra flota de vehículos. Dicha planificación consiste en determinar, para cada vehículo de la flota, el conjunto de nodos (o clientes) a los que visitar así como el orden en que deben ser visitados.

En función de las características del problema a veces también se debe determinar la hora de inicio y finalización de la ruta, los tiempos de descanso del conductor, la ruta a seguir entre cada par de clientes, etc.

La optimización en general surge para gestionar la escasez de recursos de la manera más eficiente posible. Para el caso concreto de las rutas, disponemos de un número finito de vehículos, conductores, horas de trabajo, presupuesto, etc a la que queremos sacarle el mayor rendimiento posible.

Habitualmente un equipo de personas con más o menos experiencia planifica las rutas “a ojo” basándose en su experiencia previa. Lo que quizás no saben es que la planificación que han organizado es altamente probable que esté muy lejos de la óptima pues son tantas las decisiones que deben tomar que un humano no puede contemplarlas y analizarlas todas. Veamos un pequeño ejemplo.

Supongamos que disponemos de un solo vehículo con el que debemos visitar a, por ejemplos, 20 clientes. La mayoría de las personas desconocen que existen 2.432.902.008.176.640.000 de alternativas para visitarlos (factorial de 20).

Como decía, ¿quién nos garantiza que la ruta que hemos seleccionado manualmente es la más eficiente, corta o barata? ¿Cuánto tiempo, dinero, recursos estamos perdiendo al no haber seleccionado la mejor de las planificaciones?

Nosotros estamos especializados en el desarrollo de algoritmos (metaheurísticos), ad hoc para cada problema, capaces de generar en pocos minutos millones de soluciones de gran calidad. Bastaría con seleccionar la mejor planificación de todas las evaluadas para obtener una planificación difícilmente mejorable.

Es importante notar que las rutas no tienen que ser necesariamente para vehículos. El mismo ejemplo valdría para redes eléctricas, de antenas, de sensores u otras redes de comunicación.

¿Qué técnicas se utilizan en la optimización de rutas?

Son muchas y variadas pues depende de la dificultad del problema entre manos. Antiguamente, cuando la capacidad de los ordenadores era muy limitada, se usaba la Programación Lineal y el Método del Simplex pero éste tenía grandes problemas para resolver problemas de tamaño medio.

Si a esto añadimos que muchos de los problemas reales no son lineales, nos encontrábamos con grandes problemas para abordarlos.

Hoy en día, debido a los avances en computación, capacidad de cálculo, almacenamiento y tratamiento de datos, etc. han ganado en popularidad y eficacia los algoritmos metaheurísticos aunque los matheuristics (híbridos de algoritmos exactos con metaheurísticos) también están funcionando muy bien:

  • Metaheurísticos. Hay una gran variedad de algoritmos metaheurísticos para la optimización de rutas. Desde los clásicos algoritmos genéticos hasta los más modernos (esquemas auto adaptativos, matheuristics o algoritmos basados en descomposición) pasando por otros más o menos popular como la búsqueda tabú, búsqueda dispersa, cúmulo de partículas, colonia de hormigas, grasp, entornos variables, meméticos, etc.
  • Exactos. Los algoritmos exactos son capaces de encontrar la solución óptima aunque a veces el “precio” que hay que pagar es alto pues el tiempo que requieren es inviable para la empresa. Mencionamos la Programación Dinámica o el famoso Branch&Bound y todos sus variantes. Su uso es muy extendido y de gran utilidad en ciertos escenarios de escala media.
  • Matheuristics. Más recientemente se están intentando aprovechar las fortalezas de unos y otros para crear soluciones híbridas de mucha potencia. Así, nos podríamos encontrar con metaheurísticos con operadores exactos o algoritmos exactos que se robustecen con procesos o soluciones encontradas con metaheurísticos en poco tiempo.
Cuéntanos alguna anécdota histórica de la importancia de la optimización de rutas

Una de las primeras referencias documentada es de 1856 del matemático irlandés Sir William Rowan Hamilton y por el matemático británico Thomas Penyngton Kirkman donde se estudió el (ahora) famoso Travelling Salesman Poblem (TSP).

En el TSP, un número de ciudades tiene que ser visitado por un vendedor que debe volver a la misma ciudad desde la que comenzó, y cada ciudad tiene que ser visitada exactamente una vez. Se trataba de construir la ruta que minimizase la distancia total recorrida.

Posteriormente surgen otros trabajos que profundizan o generalizan el TSP original. Estas generalizaciones (como el TSP múltiple, donde se permite que más de un vendedor se utilice en la solución, así como la consideración de otras restricciones como capacidad, distancia y/o ventana de tiempo) son las primeras aproximaciones a los actuales Vehícle Routing Problems (VRP).

Se podría decir que la primera investigaciones teórica y aplicaciones prácticas en el campo de los VRPs comenzaron en 1959 con el trabajo de Dantzig y Ramser titulado Truck Dispatching Problem, donde se comenta: “….optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations supplied by the terminal“.

Utilizando un método basado en una formulación de programación lineal y mediante cálculos manuales obtuvieron una solución casi óptima con cuatro rutas para un problema con doce estaciones de servicio.

Los autores comentaron: “No practical application of the method has been made as yet“. Desde entonces el interés en este problema no ha parado de crecer más aún teniendo en cuenta la relevancia para un sector con tanto peso como la Logística.

Habla de un caso practico que hayas hecho

Actualmente, en colaboración con qosITconsulting, estamos trabajando para una empresa líder en el mundo en el sector del retail. Esta empresa recorre millones de kilómetros diarios en toda Europa y supone uno de sus principales costes operativos.

Estamos desarrollando desde cero una solución única en el mundo capaz de realizar una planificación integral de todas las operaciones de los diferentes centros de servicio de la empresa.

Dicha herramienta es capaz de trabajar con flotas heterogéneas, tamaño de flota variable, ventanas de tiempo, descansos de los conductores para cada día y entre días y un esquema de costes asociados (fijos y variables).

Todo ello integrado en la nube con herramientas de business intelligence para dar soporte en la toma de decisiones respecto al tamaño de flota de más adecuado, si es recomendable posponer alguna tarea o no y el impacto en los costes y otras recomendaciones de gran interés para el cliente.

Esta herramienta va a suponer un cambio radical en la operativa de las cientos de plantas que posee la empresa en toda Europa y les facilitará el trabajo enormemente, minimizando los riesgos del proceso, optimizando los costes y en definitiva  ofreciendo un mejor nivel de servicio. Todo ello ayuda también a posicionar a la empresa frente a la competencia.

Para nuestros amigos de América Latina, ¿por dónde aconsejas que se empiece?

Lo primero que recomendaría a los directores de operaciones, logística y planificación es que se sienten con expertos en optimización de procesos para que les ayuden a detectar todos aquellos procesos susceptibles de ser optimizables.

Es un ejercicio muy útil. Esa intensa reflexión donde se evalúan criterios, restricciones, objetivos, métricas, etc. y sobre todo los riesgos en sus procesos ayuda a conocer tus procesos internos, tu operativa diaria, el nivel o calidad de tus datos y lo más importante, si esto te supondría algún ahorro o mejora en tus servicios.

Estas reuniones, aunque luego no se ejecute ningún proyecto, aportan mucho más valor del que generalmente se cree.

También recomendaría que se guardasen datos históricos de todos los procesos, que los ordenen y estructuren. Son muy necesarios para poder validar posteriormente si las herramientas y soluciones funcionan o no.

0a893e5

Julián Sastre González

Soy Consultor con experiencia en mas de 20 países y he participado en el desarrollo de muchos proyectos de éxito. Ademas de con grandes grupos, trabajo como asesor para organismos multilaterales como el Banco Interamericano de Desarrollo.

Blog

Únete a mi página de Facebook y LinkedIn, cada semana publicamos posts, conferencias, congresos, artículos científicos, noticias y tecnología relacionados con la gestión de flotas de vehículos, espero tu visita, gracias.

imagenes-de-facebook-logo-4 Página de Facebook 768px-LinkedIn_logo_initialsPágina de LinkedIn

tank_110405_21Conoce nuestro programa para reducir en un 20% el consumo de combustible de una flota de vehículos 

Reducción del consumo de combustible

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *