Le concours de code en ligne organisé par Axa du 29 avril au 6 mai, « Héros et Métros », a mobilisé près de 200 participants. Dans le cadre des mesures sanitaires, les codeurs avaient pour mission d’optimiser les croisements des travailleurs dans les transports en commun aux heures de pointe. Deux étudiants de l’ESILV ont relevé le challenge et l’un d’entre eux a gagné la dernière phase du concours.
Le Challenge Axa Code a été lancé pour soutenir la recherche épidémiologique à l’Institut Pasteur. Pour chaque participant, AXA s’engagéait à reverser a minima 1€ : 1950 euros au total ont pu être levés grâce aux codeurs inscrits sur la plateforme.
Challenge confinés pour minimiser les croisements dans les transports
À travers cette « dev’ battle », entièrement en ligne, Axa proposait aux codeurs participants de trouver les meilleures options de trajet pour les travailleurs grâce aux algorithmes pour éviter ainsi les contaminations dans les transports. Leur objectif était de déterminer quels travailleurs devront se rendre au travail afin d’assurer le fonctionnement des domaines vitaux, tout en minimisant le nombre de personnes croisées par chacun sur son trajet.
Pour chaque domaine professionnel, les développeurs ont tenu compte d’un quota représentant le nombre minimum de travailleurs nécessaires au bon fonctionnement de ce domaine. Chaque travailleur était associé à 4 attributs : son nom, un domaine professionnel, une liste d’options de trajet aller, et une liste d’options de trajets retour. Chaque option de trajet représentait une liste de moyens de empruntés. Si une personne était choisie pour se rendre sur son lieu de travail, les candidats devaient choisir l’une de ses options pour laquelle chaque moyen de transport comptait un passager supplémentaire.
Le score attribué aux solutions était la somme du nombre de personnes que chaque travailleur aura croisé dans chaque transport qu’il aura pris dans la journée. Si un travailleur croise une même personne dans plusieurs transports au cours de la journée, chacune de leur rencontre augmentait le score final. Le but était de proposer pour chaque jeu de données une solution ayant le score le plus faible possible.
Le challenge a été relevé haut la main par Axel Thevenot et Julien Pytel, deux étudiants en 4ème année, majeure Informatique, objets connectés et sécurité. L’équipe baptisée « Les touristes » a même fait l’objet d’une mention spéciale dans le cadre du concours.
« Les touristes », 22ème place sur 56 en première phase
Organisée le 29 avril, la première phase du concours a réuni 56 participants. À partir de 6 jeux de données de tailles variables, ils avaient 4 heures pour trouver un algorithme d’optimisation des croisements des travailleurs dans les transports en commun, en intégrant les trajets matin et soir de chacun et le quota minimal de salariés pour plusieurs secteurs d’activité. Le but du jeu, était d’assurer un équilibre en affluence entre les stations de transport : plus les travailleurs sont répartis de manière homogène sur les différentes lignes de transports en commun, moins le virus a de chance de se propager, ce qui augmentait le score de la solution.
« On s’est dit qu’on pouvait partir sur un algorithme génétique, quiest basé sur l’observation d’une population d’une génération à l’autre avec des processus de sélection, d’accouplement et de mutation. Cet algorithme nous a permis de faire partie de la première moitié des équipes mais il était encore insuffisant face à la quantité de donnée à traiter dans le temps imparti. » (Julien Pytel, étudiant ESILV)
Les « touristes » – Axel et Julien – ont terminé 22èmes sur 56 équipes qualifiées pour la première phase, mais le challenge était loin de sonner la fin du jeu. Avec de nombreux développeurs qui ont continué à faire tourner leurs algorithmes sur la plateforme même après la fermeture du concours, les organisateurs ont prolongé l’accès jusqu’au 6 mai pour tous ceux qui souhaitaient se re-challenger face à l’équipe gagnante.
L’équipe ESILV, père-fils, gagnante de la dernière phase
Pour la deuxième phase du challenge, la relève a été assurée par Laurent PYTEL, le père de Julien, en remplacement d’Axel, qui avait repris le cours de son stage. Pour développer de nouveaux algorithmes, « les touristes », en version père-fils, ont dressé un état d’art complet de la première phase, tout en ayant à l’esprit l’objectif final : trouver les meilleures formules pour assurer un équilibre en affluence entre les stations de transports.
« L’algorithme se décompose en 2 parties: Le 1er sous algorithme générait une liste de tous les trajets possibles. De manière successive, il retire un par un des trajets, du plus délétère sur le score au moins influent avec de nombreuses règles que nous avions définies. Suite à cela, on obtenait une solution très satisfaisante, nous permettant de nous hisser dans le top 5 du concours, mais c’était encore insuffisant : notre objectif était d’être premiers. Ainsi, nous avons développé un second sous-algorithme pour améliorer nos premières solutions. Ce 2nd sous algorithme teste avec des règles pragmatiques, des permutations individuelles possibles en évaluant leur pertinence; arrivé à un stade, plus de permutation individuelle ne permettait de trouver une meilleure solution, ainsi il réalise une permutation plus ou moins naïve selon les variantes des implémentations, puis repart dans un cycle de type 1. Nous avons étudié nos options de trajets en les triant selon l’affluence dans les gares qu’ils contenaient et pensé nos implémentations d’algorithmes de telle sorte qu’elles soient les plus optimales possibles. » Julien Pytel, étudiant ESILV)
L’algorithme développé par l’équipe père-fils au cours d’une semaine s’est révélé être la formule gagnante grâce à la programmation orientée objet et au multithreading.
« Nous voulions faire ce concours pour pouvoir aider à notre échelle au déconfinement de la population. Alors cet algorithme servira à aider à limiter la propagation du virus dans les transports. Peut-être même il sera celui qui vous aura dit d’aller travailler ou non aujourd’hui, qui sait ? » (Julien Pytel, étudiant ESILV)