Archivo de la etiqueta: novedades

Golden Ball meta-heuristic o cómo fútbol y la planificación de rutas tienen mucho que ver

ENEKO OSABA. Profesor de Estadística y estudiante de doctorado en DeustoTech Mobility

FERNANDO DÍAZ. Profesor del Departamento de Telecomunicaciones

¿Es posible unir el mundo del fútbol con la planificación de rutas de vehículos? A simple vista son dos conceptos que nada tienen que ver, pero con un poco de imaginación es posible. Siendo conscientes de que es algo difícilmente asimilable en un primer momento, comencemos por lo más simple.

GoldenBall1
El Golden Ball es una técnica especialmente diseñada para la resolución de problemas de planificación de rutas. Un problema muy conocido dentro de este campo es el problema del viajante, o TSP, en el que contamos con un número de ciudades repartidas aleatoriamente, y en el que el objetivo consiste en encontrar una ruta que minimice la distancia recorrida visitando cada ciudad una sola vez.
A priori el TSP parece un problema de fácil resolución. En una instancia en la que contáramos con tan solo cinco estaciones, por ejemplo, estoy seguro que la mayoría de vosotros sería capaz de encontrar «a ojo» la ruta óptima. Ahora os propongo un ejercicio más complicado… Intentad encontrar la ruta óptima para una instancia de más de 50 ciudades.
Resulta más complicado, ¿verdad? Teniendo en cuenta que el número total de rutas posibles es mucho mayor que tres trillones de trillones (que se dice pronto), es más que probable que en toda nuestra vida no fuéramos capaces de obtener la solución óptima.
Para resolver este tipo de problemas hay que hacer uso de técnicas, o algoritmos, especialmente diseñados para ello. En la literatura pueden encontrarse múltiples técnicas de este tipo para resolver todo tipo de problemas de planificación de rutas. Algunos de
estos algoritmos son el algoritmo genético (AG), o la optimización por abejas artificiales (OAA). Cada una de las técnicas se basa en diferentes conceptos, o metáforas, como por ejemplo la evolución del ser humano, en el caso del AG; o el ejercicio que realizan
las abejas en busca de fuentes de alimento, en el caso del OAA.

GoldenBall.TSP, mapa despues

Pese a que existen muchísimos algoritmos de este tipo, es interesante mencionar que la gran mayoría de ellos tienen un aspecto en común. Todos ellos trabajan sobre posibles soluciones del problema, las cuales se van modificando y evaluando a lo largo de la ejecución del algoritmo. En el caso del TSP, las técnicas trabajan con posibles rutas, las cuales se van modificando con la intención de mejorarlas progresivamente.

Con todo esto, el Golden Ball es una técnica que se basa en la metáfora del fútbol para resolver problemas de diferente índole, entre los cuales destacamos los problemas de planificación de rutas. Centrándonos en el TSP, el Golden Ball, al igual que muchas técnicas existentes, trabaja con un conjunto de soluciones (es decir, rutas) aleatoriamente creadas.

GoldenBall.TSP, satelite despues
Estos son los conceptos básicos en los que se basa la técnica Golden Ball. Hasta ahora, ha gozado de reconocimiento científico, habiendo sido publicada en dos revistas científicas y en un congreso. Además de esto, somos conscientes de que un grupo de investigación tailandés se ha interesado en nuestra técnica, y ya está trabajando sobre la misma, con la intención de realizar varias publicaciones al respecto.

Por lo tanto, a la pregunta «¿Es posible unir el fútbol con la planificación de rutas de vehículos?» hay que contestar que sí: sí es posible. Y no veáis lo gratificante que es unir uno de tus mayores hobbies con tu inquietud científica. ¡Es algo que realmente aconsejamos!

Seguir leyendo Golden Ball meta-heuristic o cómo fútbol y la planificación de rutas tienen mucho que ver