La importancia de la optimización de rutas – Entrevista Alfredo García Hernández-Díaz – Los maestros del transporte

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. la optimización de rutas

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

Ya me concedió una entrevista titulada “La matemática de bicicleta” que podrás leer pinchando en el enlace.

¿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 adpatativos, 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.

Actualmente son muchas las empresas que están pensando en dar el salto e iniciar un proceso de transformación digital así como la digitalización o automatización de sus procesos.

 Con qosITconsulting también asesoramos a grandes empresas en aspectos tecnológicos y otros trasversales (CRM, ERP…) que más tarde o más temprano se solapan con los problemas de optimización de rutas que hemos tratado en este post.

Muchisimas gracias por la entrevista Alfredo. Estoy seguro que a mis lectores les gustará mucho.

 

Ahora te animo a ti a comentar qué te parece y si tienes cualquier pregunta estaremos encantados de responderlas.

Opt In Image
¿Quieres saber más sobre Movilidad?
¡Estás en el lugar indicado!

Únete al grupo de Movilidad y Transporte y forma parte de la red que sigue creciendo en España y Latinoamérica.  Sólo por suscribirte recibirás contenidos GRATUITOS sobre Movilidad Sostenible y Sistemas de Transporte.