En entradas anteriores vimos cómo hay casos en los que la Programación Lineal Entera no es la aproximación más adecuada de cara a la resolución de problemas de cálculo de rutas, planteando la opción del uso de algoritmos metaheurísticos para la obtención de soluciones factibles y en muchos casos próximas a la solución óptima. En esta entrada se realiza un análisis más exhaustivo de cómo se pueden mejorar las soluciones que nos ofrecen estas técnicas metaheurísticas.
Mejora de soluciones: la búsqueda local
Una de las características de las técnicas metaheurísticas, es que no se garantiza la obtención de la solución óptima. Es más, en muchas ocasiones, aunque se encuentre una solución, no se podrá indicar si ésta es óptima, ni cuanto se aleja de la solución óptima.
Por ello, es común intentar mejorar la solución propuesta por una metaheurística realizando una búsqueda local. La búsqueda local se considera una técnica metaheurística per-sé, en la que se parte de una solución factible y se basa en moverse entre distintas soluciones del espacio de búsqueda (soluciones factibles) aplicando cambios locales, hasta que encuentra una solución correspondiente a un máximo/mínimo que puede ser local o global de nuestro problema, o bien, se cumple un tiempo de ejecución predefinido. Resulta importante indicar que no solo se aceptarán cambios que mejoren la bondad de nuestra solución, sino que con una cierta probabilidad, se aceptarán cambios que empeoren la solución en términos de función objetivo, con el propósito de huir de mínimos/máximos locales y explorar otras zonas del espacio de búsqueda.
Búsqueda local y cálculo de rutas
Para el caso del cálculo de rutas, existen unos tipos de búsquedas locales comúnmente utilizadas, conocidas como «2-opt«, «3-opt«, en general “k-opt”. Para introducir estas técnicas, se va a presentar un caso ejemplo:
Supongamos que los puntos de la imagen inferior representan ciudades por las que tiene que pasar una persona, sin pasar dos veces por ninguna y empezando y terminando en su domicilio habitual, representado por el punto 1.
Ejecutando una técnica metaheurística, la mejor solución encontrada es:
Al ser una técnica metaheurística, no tenemos seguridad de que ésta solución sea óptima, por lo que se intentará mejorar la solución propuesta.
Una alternativa común para mejorar esta solución será mediante la búsqueda local conocida como 2-opt, en la cual, se eliminan dos arcos de la solución propuesta y se intercambian entre ellos. Supongamos, que durante la ejecución del algoritmo 2-opt, se seleccionan los arcos que unen los nodos 2-4 y 7-8, y se obtiene que la búsqueda local mejora la solución propuesta por la metaheurística, proporcionando la siguiente ruta:
Otra alternativa no menos útil hubiese sido ejecutar la técnica 3-opt en vez de la 2-opt. En el caso de 3-opt, se intercambian 3 arcos de la solución generando todas las posibles combinaciones. Si durante la ejecución de la búsqueda local, se decidiera que los arcos a intercambiar sean los que unen los nodos 2-4, 7-8 y 1-5, se obtendría:
Conclusiones
- Las técnicas metaheurísticas no aseguran la obtención de la solución óptima, en general, ni siquiera sabremos cómo de lejos se encuentra la solución propuesta de la solución óptima.
- Por ello, es común utilizar algoritmos de búsqueda local para intentar mejorar las soluciones durante un cierto periodo de tiempo.
- Existen búsquedas locales específicas para el cálculo de rutas, conocidas como “k-opt”, que consisten en eliminar k arcos de la solución propuesta y recombinar los segmentos restantes.
- En general cuando se ejecuta una técnica metaheurística, y en particular cuando se ejecuta una búsqueda local, se permiten con cierta probabilidad el “salto” a soluciones aparentemente peores, con el objetivo de huir de los mínimos/máximos locales.
¿Quieres saber más sobre este tipo de problemas y los algoritmos para resolverlos?
Puedes seguirnos en las redes sociales (Linkedin, Twitter, Youtube) para no perderte nada y mantenerte al tanto de futuros eventos o acciones.