Optimización Aplicada a Rutas de Transporte
ARTÍCULO ESCRITO POR
La ciencia al servicio de la logística: Algoritmos heurísticos, metaheurísticos y exactos, y la Optimización de Rutas
La optimización es una rama de la investigación operativa que se encarga de resolver problemas de toma de decisiones. De forma muy resumida podemos decir que la optimización consiste en minimizar o maximizar una función objetivo cuyos valores están restringidos por unas desigualdades.
Dentro de la optimización existen multitud de algoritmos y se pueden clasificar en tres grupos. A continuación veremos en qué consiste esa clasificación y la importancia de elegir el tipo de algoritmo adecuado.
Pero antes de entrar en la clasificación de los algoritmos es importante tener claro el concepto de óptimo. Todos hemos escuchado alguna vez decir que una solución es “más o menos óptima que otra”, sin embargo, es totalmente incorrecto y carece de sentido. Óptimo es el superlativo de bueno, que no puede ser mejor, por tanto, igual que no diríamos que algo es “más mejor” tampoco tenemos que decir que algo es “más óptimo”. Una vez aclarado este concepto ya podemos pasar ver los tipos de algoritmos que existen.
Algoritmos heurísticos
Se basan en reglas empíricas para hallar la solución del problema. Ahora olvidemos, aunque sea por un momento, los problemas tradicionales de rutas o de secuenciación de la producción y vamos a tratar de visualizarlo con un ejemplo.
Supongamos que la solución óptima es la cima de la montaña más alta y veamos hasta donde llegaríamos aplicando un algoritmo heurístico.
Imaginemos que dejamos a alguien en un punto cualquiera del paisaje que se ve en la imagen y su objetivo es alcanzar el punto más alto. Se puede aplicar la regla de que mientras esté subiendo va por buen camino y una vez llegue a un punto donde si da un paso más tiene que bajar, se detiene y esa será la solución.
El problema es que como vemos en la foto hay muchos puntos que cumplen este criterio y, en consecuencia, será fácil que el nuestro no sea el más alto. Por tanto, aunque hemos aplicado una regla que es razonable y mirando alrededor no se ve nada mejor (imaginemos también que a quien hemos dejado explorando sufre de miopía), realmente no tenemos ninguna garantía de que esta sea la mejor solución. Esto mismo sucede cuando por ejemplo aplicamos una búsqueda local, que es una de las heurísticas más conocidas.
Algoritmos metaheurísticos
Literalmente son aquellos que van más allá de los heurísticos, pero… ¿qué quiere decir esto de “ir más allá”?
Siguiendo con el ejemplo anterior, una forma de “ir más allá” es no dejar a una única persona buscando la cima más alta, sino dejar gente repartida por muchos sitios. Si todas estas personas aplicaran la regla vista en el heurístico anterior y la solución fuera la de quien hubiera llegado más alto, seguiríamos sin saber con certeza si la solución obtenida es la mejor, pero sin duda es más probable que sea mejor que con el heurístico. Así es como actúa un algoritmo GRASP, uno de los metaheurísticos por excelencia.
Esto no quiere decir que sea la única forma de “ir más allá”, hay muchas. También podríamos dar algunos pasos más alrededor de un punto, aunque no estemos subiendo, solo para ver si encontramos de nuevo otro camino hacia arriba, idea en la que se basa la Tabu Search. O incluso imitar el recorrido de las hormigas, Ant Colony Algorithm.
De aquí hay que extraer dos ideas clave. La primera es que con estos algoritmos lo habitual será obtener mejores soluciones que con los heurísticos y la segunda es que son más costosos. Como hemos visto, explorando más, lo normal será encontrar un punto que esté a mayor altitud, pero naturalmente esto supondrá que se incremente el coste.
Algoritmos exactos
Son los únicos que garantizan que la solución obtenida es la óptima. Viéndolo así parece que hemos estado perdiendo el tiempo con los algoritmos anteriores, ¿no?
¿Si tenemos algoritmos que nos dan la mejor solución para qué queremos el resto?
Para obtener la respuesta vamos a volver al ejemplo de encontrar la cima más alta. Con los algoritmos anteriores nos deteníamos cuando se alcanzaba un criterio de parada, pero ahora no. Ahora solo pararemos cuando estemos seguros de que no hay ni un solo punto a mayor altitud que el punto de nuestra solución. Pero claro, explorar todo lleva mucho tiempo, y esto mismo es lo que sucede con los algoritmos exactos.
Estos normalmente necesitan mucho más tiempo de lo que podemos o estamos dispuestos a esperar, por eso en muchos casos se opta por los otros tipos de algoritmos.
Habitualmente se emplean modelos matemáticos o directamente algoritmos de ramificación en todas sus variantes.
Aplicación a un problema de rutas de vehículos
Ahora que ya hemos visto los conceptos, veamos como se traduce en un problema cotidiano de gestión de la logística de una empresa.
Supongamos que tenemos un único vehículo con el que hay que servir a 20 clientes. Consideraremos que podemos hacer los repartos a cualquier hora, que el vehículo tiene capacidad suficiente y todos los clientes son igual de prioritarios. Por tanto, solo hay que buscar la ruta más corta para servir a todos, es decir, resolver el TSP. Sencillo, ¿verdad?
Este problema tan simple tiene posibles soluciones. Con esto nos podemos hacer una idea de lo complicado que es un caso real con decenas de vehículos y cientos de clientes a los que servir. Si a esto sumamos que nos podemos encontrar con una flota de vehículos heterogénea, ventanas horarias para servir a los clientes, descansos de conductores, … Es evidente que estamos ante un problema extremadamente complicado y por eso en la mayoría de casos hay que descartar lo métodos exactos.
En cambio, si aplicáramos un heurístico habitual en los problemas de rutas de vehículos como es el Algoritmo de los ahorros, podemos resolver la inmensa mayoría de los problemas de rutas reales en apenas unos pocos segundos.
En caso de querer mejorar la solución siempre le podríamos aplicar una serie de cambios con una Tabu Search o dar cierta aleatoriedad al orden en que se hacen las uniones en el Algoritmo de los ahorros, generando varias soluciones y quedándonos con la mejor. En otras palabras, si no nos gusta la solución, podemos tratar de mejorarla con un metaheurístico.
Conclusión
Hemos clasificado los algoritmos de optimización en tres tipos: heurísticos, metaheurísticos y exactos. Las diferencias más reseñables entre estos grupos son la calidad de la solución y lo costoso que resulta obtenerla.
Cuando vayamos a elegir el tipo de algoritmo lo primero que tendremos que ver es si el problema se puede resolver rápidamente con un algoritmo exacto, ya que entonces no tendría sentido usar el resto.
Pero por desgracia, esto no suele pasar, la inmensa mayoría de los problemas reales de logística y de la cadena de suministro son tan complejos que hacen completamente inviable que se puedan utilizar métodos exactos.
En cuanto a elegir un heurístico o un metaheurístico, salvo en las ocasiones en las que por el conocimiento del problema se pueda obtener una regla que proporcione buenas soluciones, nuestra experiencia nos ha demostrado que lo más recomendable es usar metaheurísticos. La razón principal es, que como hemos visto, los heurísticos son propensos a caer en óptimos locales que pueden estar muy lejos de la mejor solución y con los metaheurísticos este problema se puede evitar.
