ROADEF'2001: Résultats de la phase 1

Sommaire

Candidats retenus pour la phase suivante (dans l'ordre alphabétique)

Équipes Junior

Équipes Senior

Tableau des meilleurs résultats (phase 1)

Nota: le tableau junior ne tient pas encore compte des résultat de l'équipe Michelon.

Kmin : meilleure valeur de K trouvée par les participants à ce challenge

Tmin : temps minimum de découverte de cette valeur de K

Vprev : nombre de viols pour K - 1

Vother : Nombre total de viols pour i < K-1

Meilleurs résultats Junior

NOM Kmint Tmin Vprev Vother
fapp01_0200 5 2857 6 298
fapp02_0250 5 73 27 503
fapp03_0300 8 2954 10 919
fapp04_0300 6 ? 1 338
fapp05_0350 11 0 2 1874
fapp06_0500 7 1415 15 1072
fapp07_0600 10 326 1 1685
fapp08_0700 11 0 2 2585
fapp09_0800 7 1350 8 1644
fapp10_0900 11 1 1 4065
fapp11_1000 11 3 3 5107
fapp12_1500 11 2 1 9086
fapp13_2000 11 3 3 11635
fapp14_2500 11 12 117 20936
fapp15_3000 11 5 179 22070
test01_0150 4 41 2 89
test02_0250 7 167 10 422
test03_0400 5 183 ? ?
test04_1250 9 3600 471 16780

Meilleurs résultats Senior

NOM Kmint Tmin Vprev Vother
fapp01_0200 4 1 4 26
fapp02_0250 2 3 7 152
fapp03_0300 7 2 10 483
fapp04_0300 1 106 221 0
fapp05_0350 11 0 1 1014
fapp06_0500 5 21 14 749
fapp07_0600 9 3 22 2088
fapp08_0700 5 9 17 895
fapp09_0800 3 14 41 750
fapp10_0900 6 241 19 1662
fapp11_1000 8 21 8 3294
fapp12_1500 2 1767 3 1019
fapp13_2000 4 864 147 2635
fapp14_2500 5 702 232 5204
fapp15_3000 5 401 195 4178
test01_0150 4 1 2 30
test02_0250 7 2 5 507
test03_0400 4 5 9 193
test04_1250 8 61 31 4152

Nouvelles instances de problémes pour la phase 2

Les résultats de la phase 1 du challenge ont été excellents : pour certaines instances, les valeurs optimales pour k ont été obtenues, avec la preuve de cette optimalité.

Il reste un travail important à faire pour les autres composantes de la fonction de coût : le nombre de contraintes violées au niveau k-1 et aux niveaux inférieurs.

Au vu de ces bons résultats, le jury a décidé de produire pour la base B des instances plus proches de ce qu'on pourrait rencontrer dans la réalité. Ce désir de réalisme se traduit de différentes manières :

  • augmentation de la taille des domaines de ressource en fréquences,
  • augmentation ou diminution du nombre de contraintes CEM et/ou impératives,
  • variation plus faible des relachements de contraintes CEM.

Les nouvelles valeurs limites en taille pour les différentes instances deviennent :

  • nombre de trajets : 3000 (inchangé),
  • nombre de contraintes impératives : moins de 16000,
  • nombre de contraintes CEM : moins de 31000,
  • taille d'un domaine fréquentiel : moins de 500 fréquences.

Ces instances sont à télécharger ici.