Distribución de grupos de 2ª B

En la segunda división B de la liga española hay 80 equipos, divididos en cuatro grupos de 20. Cada año ascienden 4 equipos a segunda división, y descienden 18 a tercera división, y son sustituidos por 4 equipos que descienden de segunda y 18 equipos que ascienden de tercera. Sin embargo, el sistema de play-offs de ascenso hace que la distribución geográfica de los 80 equipos varíe sustancialmente de un año a otro: puede pasar que los 4 equipos que desciendan sean de la misma zona, o que asciendan 4 equipos de una misma zona de tercera. Esto conlleva que a la hora de dividir los equipos en grupos cada año la federación tenga que reunirse, y decidir cuál es la mejor distribución, que puede variar mucho de un año a otro al poder variar los equipos que componen la división.

El sistema actual para dividir los grupos es sencillo. Cada federación territorial propone la división que más le conviene, por ejemplo tratando de minimizar los viajes largos de sus equipos, y después se votan todas las opciones, y la que más consenso tenga es la que sale elegida. Como esto tiene poco interés desde un punto de vista matemático vamos a intentar formalizar el problema.

Los criterios que se suelen aducir son de lo más variado. Por un lado tenemos el obvio: distancia. Será mejor una distribución de grupos en la que los equipos viajen menos. Especialmente delicados son los viajes de más de ~300km, ya que suele ser difícil ir y volver el mismo día, lo que implica tener que pernoctar, con el gasto que eso suele suponer a los clubs. Pero por otro lado ningún equipo quiere estar en un grupo diferente a sus vecinos, ya que los viajes cortos además de ser baratos permiten una gran afluencia de aficionados. Por motivos más sentimentales que prácticos muchos equipos quieren también estar en el mismo grupo que otros equipos de su comunidad, aunque estén muy alejados, y ya ni hablar de la provincia: es impensable que dos equipos de la misma provincia no estén en el mismo grupo. Algunos equipos también quieren evitar a los más fuertes, pero en esta división de transición las plantillas varían mucho de un año a otro, por lo que es difícil saber a priori quiénes serán los rivales a batir. Otros criterios incluyen no obligar a un equipo concreto a hacer muchos viajes largos, aunque al tener los otros equipos viajes más cortos se compense. O incluso compensar el hecho de que anteriormente unos determinados equipos hayan hecho viajes más largos, poniéndoles ese año viajes más cortos.

Como es imposible tener en cuenta todos los criterios, vamos a simplificar el problema todo lo que podamos. Tenemos 80 equipos (nodos, vértices, patatas… 80 cosas). Y los situamos en un grafo completo etiquetado. Es decir, por cada pareja de equipos hay un coste asociado. Ese coste puede ser, por ejemplo, la distancia entre ellos. Puede ser distancia en línea recta o por carretera, eso da igual. Nuestro objetivo sería dividir los 80 equipos en cuatro grupos de 20 equipos, de forma que la suma de los costes asociados a cada pareja de equipos en el mismo grupo sea lo menor posible. Dicho de otra forma, que el viaje medio que tenga que hacer un equipo sea lo más corto posible. Con esta simplificación de momento no podemos tener en cuenta que ningún equipo quede especialmente perjudicado, ya que lo que se mira de minimizar es la suma global, y no la suma de ninguno en concreto, o la suma del equipo que viaje más. Sin embargo sí podemos intentar que los equipos de la misma provincia estén en el mismo grupo: basta con aumentar el coste entre dos equipos que sean de provincias diferentes.

Ya tenemos el problema formalizado. Ya sólo falta hacer un programa que lo resuelva… ups… parece (aunque no lo he demostrado) que es NP-difícil. Podríamos probar todas las distribuciones, pero hay demasiadas: {80\choose 20, 20, 20, 20}/4!={80!\over (20!)^44!}\approx 8.51\cdot 10^{43}. Usando el superordenador más potente del mundo tardaríamos 3.570 millones de veces la edad del universo en considerarlas todas. Parece que no es factible. Sin embargo hay algoritmos heurísticos que dan soluciones buenas, y cuando por mucho que busques no encuentras ninguna mejor esto da un indicio (aunque no una demostración) de que la solución encontrada es óptima. Por lo tanto a partir de ahora, cada vez que leáis “Esta es la mejor solución posible”, en realidad deberíais leer “Esta es la mejor solución que he encontrado, pero no he podido demostrar que no haya ninguna mejor. Apostaría dinero, bastante dinero, a que es la mejor, pero tampoco me jugaría el brazo derecho”. Avisados estáis.

Utilizaremos un algoritmo de búsqueda local. En mi caso utilizo el Hill Climbing, que consiste en lo siguiente. Te ponen en un lugar aleatorio de un terreno, y tienes que llegar al punto más alto. Pero hace mucha niebla, y sólo puedes ver el terreno a un metro alrededor de ti. Así que lo que haces es ir hacia el punto más alto a un metro a la redonda y repetir el proceso. Dicho proceso acabará cuando llegues a un punto tal que no puedas subir más dando solo un paso, es decir, un máximo local. El problema es que puede que dicho máximo local sea una pequeña colina al lado de una montaña enorme a la que querías llegar pero no has visto. Así que lo que tienes que hacer es repetir el procedimiento empezando en muchos puntos diferentes. Cabe pensar que en una de esas ocasiones te pondrán lo suficientemente cerca de la montaña para que yendo lo más arriba que puedas a cada momento la acabes escalando.

En realidad mi algoritmo consiste en una pequeña modificación del Hill Climbing llamada Simulated Annealing. En realidad la única diferencia con este algoritmo es que empiezas en el terreno habiéndote ventilado una botella de tequila, por lo que al principio avanzarás un poco hacia cualquier lado al azar, pero según se te vaya pasando la borrachera cada vez irás viendo mejor cuál es el punto más alto, y al final el algoritmo se comporta como un Hill Climbing normal, llegando al punto más alto al que puedas llegar en el momento en el que ya estabas totalmente sereno. Que este algoritmo sea mejor o no depende mucho del problema, pero en este caso me ahorraba unos segundos, así que decidí implementarlo.

Traducido a equipos, mi algoritmo empieza con una distribución al azar, y va intercambiando parejas de equipos, quedándose con el intercambio que reduce más el tiempo total de viaje. Cuando ningún intercambio de equipos da lugar a una mejora hemos llegado a un máximo local. Después probamos con otras distribuciones iniciales, hasta que hayamos alcanzado un número n de veces (por ejemplo 5) la mejor distribución hasta ahora sin poder mejorarla. Esto me hace estar bastante convencido de que la distribución es óptima. Respecto al tiempo, a cada paso del algoritmo hay que revisar todas las parejas de equipos, y después de intercambiarlas calcular el nuevo coste. Con un precálculo consigo hacer esto último en tiempo constante, por lo que el coste total es de O(n^2) por cada operación, y como suele haber un número lineal de operaciones antes de que converja el coste total ronda a O(n^3) por cada búsqueda local, lo cual es algo menos de un segundo. Repetimos el algoritmo cerca de 100 veces hasta convencernos de que el máximo local es global, por lo que el tiempo total que tarda es de alrededor de un minuto. Bastante menos que la miles de millones de veces la edad del universo que tarda el algoritmo de probar todas las combinaciones.

Falta entonces definir los costes. En una primera versión utilizaba la distancia en línea recta, que aproxima bastante bien lo que queremos. Pero es más correcto si usamos la distancia por carretera, por ejemplo la que da Google Maps. Así que he usado la API de Google Distance Matrix para calcular la distancia entre cualquier par de ciudades de equipos que juegan en segunda B. Como puede haber hasta 80*80=6.400 distancias, y la versión gratuita sólo permite 2.500 consultas al día, llevo varios días calculando las distancias entre todos los equipos que podrían haber quedado en 2ª B, y guardo las de años anteriores. Además, para imprimir los mapas uso la API de Google Static Maps, que aunque sólo genera imágenes de mapas, y no permite interactuar con ellas, los límites son muy generosos.

Un último detalle es que los equipos canarios los sitúo en Madrid, ya que es el lugar hacia donde hay más vuelos desde Canarias, y la federación siempre los pone ahí. Para los demás, incluyendo los equipos baleares y el Melilla, uso la distancia de Google Maps, que normalmente incluye viajes en barco si es necesario. Ya tenemos todos los ingredientes para ejecutar nuestro programa. La distribución que minimiza la distancia total es la siguiente:

dist1

El viaje medio es de 285.68km, y en principio, cualquier variación de esto provocará viajes más largos de media. Sin embargo es fácil de ver que se consiguen viajes más cortos gracias a formar un grupo muy concentrado (el II presumiblemente, el verde), y perjudicar a otros, como el Mérida, que tiene que hacer viajes muy largos. De hecho hay una gran diferencia entre los equipos que viajan menos (116km el Bilbao Athletic, 117km el Amorebieta, 118km el Barakaldo…) y los que viajan más (466km el Melilla, inevitable, 464km el Mérida, 439km el Boiro, 420km el Racing de Ferrol…). Además algunas provincias están separadas en varios grupos, lo que no es del todo deseable. Vamos a intentar poner al Mérida con los extremeños, al Jumilla con los murcianos, y a los asturianos juntos. Para eso pondremos una penalización de cada vez que un equipo tenga que viajar fuera de su provincia. Con 100km de penalización el resultado es el mismo. Con 500km la única diferencia es que el que va al grupo III no es el Jumilla sino el Albacete, que tiene a menos en su provincia, y el viaje medio sube a 286km. Tenemos que subir la penalización a 2.000km para que nos junte a los equipos de la misma provincia. El resultado es el siguiente:

dist2

En este caso llevamos al Lleida, el único de su provincia, al grupo II, y completamos el grupo III con los albaceteños. Queda un sitio en el que puede ir el Mérida, lo que permite reagrupar a los asturianos. Como contrapartida el viaje medio sube ligeramente hasta los 288.56km, es decir, tres km más, y la comunidad castellano-manchega queda dividida en tres grupos. Debido a los viajes a Lleida, los equipos con viajes más cortos (los vascos) tienen ahora viajes algo más largos (unos 10km más de media cada uno), mientras que los que tienen viajes más largos los ven acortados (unos 20km los gallegos, por el cambio del Mérida por el Lealtad asturiano, y cerca de 60km el Mérida por ahorrarse los viajes a Galicia). Por lo que aunque el viaje medio sea algo más largo, los viajes están más equilibrados. Otro de los criterios históricos consiste en meter equipos de la misma comunidad autónoma en el mismo grupo, dentro de lo posible. A ver qué pasaría si penalizáramos el cambio de comunidad autónoma con 100km.

dist3

No parece una gran mejora. El Lleida tiene que ir en el grupo III porque hay muchos catalanes, pero sólo hay cuatro castellano-manchegos, por lo que la penalización de separarlos es pequeña. Por contra el viaje medio bajaría un poco, a los 287km. Vamos a probar subiendo la penalización a 500km.

dist4

Puede que esto se parezca más a lo que se acabe decidiendo. El viaje medio sube a 289.36km, cuatro más que el óptimo, pero la única comunidad autónoma que se separa es la castellano-leonesa, lo cual parece casi inevitable. Si aumentamos la penalización a los 2.000km, separaríamos en su lugar la comunidad de Castilla-la Mancha, que tiene menos equipos y la penalización es menor, dando lugar a la siguiente distribución:

dist5

Aparte de lo feo que queda ver tres equipos tan juntos en grupos diferentes, el viaje medio sube a 293km, perjudicando especialmente al Socuéllamos, cuyos viajes serían de 457km de media por tener que ir hasta Galicia. ¿Es posible evitar todo tipo de división entre comunidades autónomas, por largos que sean los viajes? Probemos con 5.000km de penalización.

dist6

Parece que sí que es posible juntarlos a todos, pero el problema es que el viaje medio sube drásticamente hasta los 304km (20 más que el mínimo), y que el Mensajero no estaría con los madrileños, sino que pasaría al grupo I con los gallegos. Si forzamos a que el equipo canario esté siempre con los madrileños la solución es sencilla: lo intercambiamos por el Logroñés, único equipo riojano, quedando así:

dist7

El viaje medio, sin embargo, sube hasta los 308.92km. Los equipos con viajes más cortos siguen siendo los vascos, con poco menos de 200km de media, mientras que los extremeños serían los más perjudicados, con viajes de más de 500km. De hecho los viajes del Mérida son de media 30km más largos que en la distribución óptima, cuando estaba separado de los otros extremeños. Muy pocos equipos salen beneficiados con esta distribución, pero dado que todas las comunidades autónomas están juntas, es muy probable que acabe siendo la distribución elegida.

Se puede ejecutar el programa en este enlace, variando parámetros. De momento se permite variar la penalización por cambiar de provincia o comunidad autónoma, pero estoy abierto a sugerencias. El tiempo de ejecución varía entre menos de un minuto y más de cinco, según los parámetros, así que paciencia.