Pour la deuxième année consécutive, Domloup se retrouve en Nationale 3 dans un groupe incroyable. En 2014 déjà dans un groupe qui allait jusqu'à Orléans, en 2015 avec quatre équipes Parisiennes. L'occasion de réfléchir sur la manière dont sont constitués les groupes des championnats...
La répartition d'un certain nombre d'équipes dans un certain nombre de groupes n'est pas un problème simple : il s'agit d'un problème de géométrie, dont la complexité devient très importante dès que le nombre d'équipes et de groupes augmente, et pour lequel la recherche pratique d'une solution optimale se heurte à ce qu'on appelle en mathématique la NP-complétude (de manière simple, il y a tellement de solutions possibles que même un ordinateur prendrait trop de temps pour la trouver). L'informatique peut néanmoins aider à trouver une solution meilleure que celle que l'on pourrait bâtir « à la main», ce que nous allons montrer dans cet article.
Une solution sera jugée d'autant meilleure qu'une autre si l'ensemble des déplacements nécessaires pour un championnat toutes rondes dans chaque groupe est moindre.
Pour refléter la réalité des déplacements des joueurs, les distances prises en compte seront les distances routières :
- Les lieux de jeu des 180 équipes sont définis par leurs coordonnées (latitude et longitude)
- L'API Google Directions permet de calculer simplement les distances routières entre tous ces points.
Il est alors facile de calculer les distances nécessaires aux déplacements.
1. La répartition manuelle
1.a) Composition des groupes
Prenons par exemple la répartition actuelle des 180 clubs dans les 18 groupes de Nationale 3 (source : site de la Fédération) :
|
|
|
|
||||||||
|
|
|
|
||||||||
|
|
|
|
||||||||
|
|
|
|
||||||||
|
|
1.b) Répartition géographique
Cliquer sur l'image pour agrandir ou télécharger au format KML
1.c) Déplacements nécessaires
Les distances des déplacements dans chacun des groupes sont les suivantes :
| Groupe | Déplacements (km) |
|---|---|
| G : Domloup / Mantes en Yvelines | 17046 |
| E : Les Sables-d'Olonne / Chateauroux | 15981 |
| P : Gueugnon / Epinal | 13613 |
| A : Gap / Monaco 2 | 13584 |
| F : Brest Usam 2 / Getigne | 12673 |
| D : Marennes Oleron / Pau Sarrailh | 12511 |
| C : Cahors / Frontignan | 11226 |
| Q : Couzon / Grenoble 3 | 11128 |
| H : Saint-Thomas - le Havre / Ecouen | 10164 |
| N : Reims Echec et Mat / Sarreguemines | 9507 |
| M : Boulogne-sur-Mer / Feignies | 8793 |
| R : Oyonnax-Dortan 2 / Eybens 2 | 8621 |
| B : Montpellier 3 / Echiquier Marseillais 1872 | 8135 |
| I : Nogent le Roi / Echiquier du Gatinais - Amilly | 7409 |
| L : Cergy-Pointoise / Saint-Quentin 2 | 5749 |
| O : Saverne / Mulhouse Philidor 4 | 5031 |
| K : Maisons-Laffitte / Fontainebleau Avon 2 | 2755 |
| J : Rueil-Malmaison 2 / Melun | 2463 |
| Total | 176389 |
Il faut considérer pour des équipes de 8 joueurs comme en Nationale 3 que deux voitures en moyenne sont nécessaires pour chaque déplacement. Dès lors, on s'aperçoit que les déplacements de ce seul championnat représentent près de huit tours du monde, et on se dit qu'il peut être intéressant de réfléchir à la manière dont ces groupes sont constitués, et qu'une économie même minime sera intéressante.
Allons-y donc et faisons confiance à l'ordinateur...
2. Répartition naïve
Compte tenu de la complexité du problème, l'objectif n'est pas de trouver la meilleure solution mais une meilleure solution ; en d'autres mots, trouver une méthode (un algorithme) pour constituer les groupes et espérer que la solution sera meilleure que celle proposée par la Fédération.
Nous itérons donc de manière « naïve » :
Tant qu'il reste des clubs :
- prendre le club le plus éloigné de ses voisins (celui dont la distance à ses vingt plus proches voisins est la plus importante) ;
- lui associer les 9 clubs les plus proches et constituer un groupe.
Cette solution naïve donne les résultats ci-dessous.
2.a) Composition des groupes
|
|
|
|
||||||||
|
|
|
|
||||||||
|
|
|
|
||||||||
|
|
|
|
||||||||
|
|
2.b) Répartition géographique
Cliquer pour agrandir ou télécharger au format KML
2.c) Déplacements nécessaires
| Groupe | Déplacements (km) |
|---|---|
| D : Chateauroux / Carcassonne 2 | 19825 |
| J : C.E. Thur Thann / Chambery | 17280 |
| B : Le Mans / Marennes Oleron | 15452 |
| E : Agneaux Saint-Lo 2 / Maisons-Laffitte | 13198 |
| C : Mont-de-Marsan / Muret | 12921 |
| A : Brest Usam 2 / Gorges Clisson | 12348 |
| I : Couzon / Bourgoin-Jallieu | 11887 |
| H : Lyon 64 / Marseille Echecs 2 | 11677 |
| F : Echiquier Marseillais 1872 / Monaco 2 | 9474 |
| N : Montreuil / Feignies | 9405 |
| M : Abbeville / Aulnoye | 9258 |
| G : Beziers / Martigues | 8348 |
| K : Hoenheim / Roi Blanc Montbeliard | 7819 |
| P : Nogent le Roi / Echiquier du Gatinais - Amilly | 7701 |
| L : Thionville / Mundolsheim 2 | 7657 |
| O : Arcueil / Recy | 4115 |
| R : Cergy-Pointoise / Sevres - Ville-d'Avray | 1721 |
| Q : Clichy 4 / Yerres | 1295 |
| Total | 181383 |
2.d) Analyse
La solution trouvée n'est de manière évidente pas optimale :
- Le kilométrage total est supérieur à celui de la solution de la Fédération (181383 contre 176389 précédemment), mais reste du même ordre de grandeur (+2,8%) ;
- La méthode a un défaut intrinsèque : elle isole des clubs proches de ses voisins car elle les considère comme non prioritaires.
L'essai est néanmoins très encourageant et on sent bien qu'il suffirait de corriger les défauts de la méthode pour obtenir rapidement une meilleure solution...
3. Optimisation de la répartition
Nous allons améliorer la répartition naïve ci-dessus en procédant de la sorte :
Tant qu'une optimisation est possible :
- Classer tous les clubs par ordre décroissant de leur distance aux autres équipes de leur groupe (on obtient ainsi en premier les clubs les plus excentrés), et pour chacun d'entre eux :
- Considérer tous les échanges un à un avec les clubs des autres groupes et calculer la différence de kilométrage total avant et après échange ;
- Si aucun gain n'a été trouvé :
- Arrêter (considérer qu'il n'y a plus d'optimisation possible) ;
- Sinon (des gains sont possibles) :
- Prendre le meilleur gain et effectuer l'échange.
- Rechercher une nouvelle optimisation.
Dans le cas présent, les échanges suivants sont effectués :
| Itération | Club excentré | Echange | Gain (km) |
|---|---|---|---|
| 1 | Carcassonne 2 (groupe D) | Bordeaux A.S.P.O.M. (groupe C) | 3745 |
| 2 | Marseille Echecs 2 (groupe H) | Monteux (groupe G) | 781 |
| 3 | Chateauroux (groupe D) | Marennes Oleron (groupe B) | 1449 |
| 4 | Chambery (groupe J) | Geugnon (groupe I) | 570 |
| 5 | Creon (groupe C) | Castelsarrrasin 2 (groupe D) | 3593 |
| 6 | Cahors (groupe D) | Mont-de-Marsan (groupe C) | 1333 |
| 7 | Feignies (groupe N) | Abbeville (groupe M) | 1104 |
| 8 | C.E. Thur Thann (groupe J) | Roi Blanc Montbeliard (groupe K) | 1347 |
| 9 | Sundgau Echecs - Altkirch (groupe J) | Belfort (groupe K) | 769 |
| 10 | Mulhouse Philidor 4 (groupe J) | Epinal (groupe K) | 364 |
| 11 | Maisons-Laffitte (groupe E) | Abbeville (groupe N) | 1154 |
| 12 | Recy (groupe O) | Montreuil (groupe N) | 1094 |
| 13 | Chambery (groupe I) | Lyon Olympique Echecs 2 (groupe H) | 1131 |
| 14 | Bourgoin-Jallieu (groupe I) | Lyon 64 (groupe H) | 892 |
| 15 | Sainte Foy Echecs (groupe H) | Genas (groupe I) | 293 |
| 16 | Maisons-Laffitte (groupe N) | Asnieres 64 (groupe R) | 288 |
| 17 | Asnieres 64 (groupe N) | Saint-Georges (groupe O) | 51 |
| 18 | Yerres (groupe Q) | Asnieres 64 (groupe O) | 215 |
| 19 | Sevres - Ville-d'Avray (groupe R) | Asnieres 64 (groupe Q) | 126 |
| 20 | Sceaux (groupe Q) | Lutece Echecs 2 (groupe O) | 7 |
| 21 | Sceaux (groupe O) | Tour Blanche 3 - Paris (groupe Q) | 17 |
| 22 | Arcueil (groupe O) | Tour Blanche 2 - Paris (groupe Q) | 87 |
| 23 | Club 608 2 - Paris (groupe Q) | Lutece Echecs 3 (groupe O) | 11 |
| 24 | Club 608 3 - Paris (groupe Q) | S.C.P.O. Paris (groupe O) | 27 |
| 25 | Puteaux (groupe R) | Clichy 4 (groupe Q) | 8 |
3.a) Composition des groupes
|
|
|
|
||||||||
|
|
|
|
||||||||
|
|
|
|
||||||||
|
|
|
|
||||||||
|
|
3.b) Répartition géographique
Cliquer pour agrandir ou télécharger au format KML
3.c) Déplacements nécessaires
| Groupe | Déplacements (km) |
|---|---|
| J : Epinal / Oyonnax-Dortan 2 | 15586 |
| B : Les Sables-d'Olonne / Chateauroux | 15094 |
| E : Agneaux Saint-Lo 2 / Abbeville | 13616 |
| D : Couzeix / Mont-de-Marsan | 13380 |
| A : Brest Usam 2 / Gorges Clisson | 12348 |
| H : Chambery / Monteux | 10284 |
| I : Couzon / Meximieux | 9817 |
| C : Pau Sarrailh / Cahors | 9604 |
| F : Echiquier Marseillais 1872 / Monaco 2 | 9474 |
| G : Beziers / Marseille Echecs 2 | 8970 |
| N : Ecouen / Recy | 8889 |
| M : Boulogne-sur-Mer / Feignies | 8793 |
| P : Nogent le Roi / Echiquier du Gatinais - Amilly | 7701 |
| L : Thionville / Mundolsheim 2 | 7657 |
| K : Hoenheim / Sundgau Echecs - Altkirch | 6207 |
| R : Echiquier de Cergy / Rueil-Malmaison 2 | 1567 |
| O : Tour Blanche 2 - Paris / Yerres | 1029 |
| Q : Puteaux / Sceaux | 912 |
| Total | 160928 |
3.d) Analyse
Les échanges ont permis de corriger toutes les anomalies de la méthode naïve utilisée pour contituer les groupes initialement.
La méthode diminue globalement le nombre de kilomètres à effectuer de manière importante, pour tous les groupes :
| Groupe |
Répartition manuelle |
Répartition informatique |
Gain |
|---|---|---|---|
| 1 | 17046 | 15586 | -9% |
| 2 | 15981 | 15094 | -6% |
| 3 | 13613 | 13616 | 0% |
| 4 | 13584 | 13380 | -2% |
| 5 | 12673 | 12348 | -3% |
| 6 | 12511 | 10284 | -22% |
| 7 | 11226 | 9817 | -14% |
| 8 | 11128 | 9604 | -16% |
| 9 | 10164 | 9474 | -7% |
| 10 | 9507 | 8970 | -6% |
| 11 | 8793 | 8889 | +1% |
| 12 | 8621 | 8793 | +2% |
| 13 | 8135 | 7701 | -6% |
| 14 | 7409 | 7657 | +3% |
| 15 | 5749 | 6207 | +7% |
| 16 | 5031 | 1567 | -221% |
| 17 | 2755 | 1029 | -168% |
| 18 | 2463 | 912 | -170% |
| Total | 176389 | 160928 | -10% |
Conclusion
L'application de la méthode décrite ci-dessus est simple, elle s'appuie sur le kilométrage réel et diminue de 10% l'ensemble des déplacements sur le territoire.
L'économie globale, pour le seul championnat de Nationale 3 représente :
- 15461 kilomètres de déplacement de club à club
- environ 30000 kilomètres effectués (moyenne de deux véhicules par équipe) ;
- 1800 litres et 3000€ d'essence (6l./100km)
- 2400 heures de joueurs d'échecs passées inutilement sur la route, soit plus de 600 parties en 1h30 + 30 sec./cp
Appliquée à l'ensemble des championnats de la Fédération, on peut probablement gagner un tour du monde...
Avis : le programme est à disposition de la Fédération !
Ajout 24 juin 2014 : suite à un échange avec Gérard Hernandez, rendez-vous est pris pour l'optimisation des groupes des interclubs adultes de la Fédération pour la saison 2016 ;-)
Autres exemples
Nationale 4 jeunes Bretagne 2015 (prévision juin 2014)
Nationale 2 jeunes 2015 (prévision juin 2014)
Nationale 4 adultes Bretagne 2015
Répartition manuelle
Répartition informatique
Comparaison des distances parcourues (gain : 19%)
| Répartition manuelle | 12950 |
|---|---|
| C : Queven / Domloup B | 5056 |
| A : Concarneau / Guingamp B | 4260 |
| B : Saint-Brieuc / Vitre | 3634 |
| Répartition informatique | 10892 |
|---|---|
| C : Dinard / Sainte-Anne-d'Auray | 5469 |
| A : Lesneven / Queven | 4100 |
| B : Guichen / Vitre | 1323 |
Commentaires
Olivier Rousse
mar, 06/24/2014 - 23:12
Permalien
Y a trop d'informaticiens à Domloup !!!
Et des tordus !!! Vous essayez de nous faire croire que 3 ou 4 modestes individus pourraient trouver des solutions simples, efficaces et censées et ce mieux qu'une floppée de personnes qu'ont que ça à faire de leurs journées (ou presque). Nan, vous êtes pas crédible les gars...
Si en fait !!! et démontré par A + B (ah ces informaticiens fous!!!)
La démonstration étant (habilement) faite, le plus dur est de convaincre la fédération et si la fédération d'échecs est comme la majorité des fédérations sportives alors bon courrage :-) mais vous avez peut être un logiciel pour ça ;-)
En tout cas, bravo, c'était bien vu. Finalement je suis pas si mécontent de ne pas avoir été retenu en N3... car ancien francilien, j'ai plus franchement envie de remettre les pieds dans ce secteur paradisiaque de France... D'avance bonnes balades ;-)
Captain Olive