Le projet ReCHor
CS-108
1. Introduction
Le projet de cette année, nommé ReCHor, consiste à écrire un programme de recherche d'horaire de transport public en Suisse, afin de trouver comment se déplacer de manière optimale d'un arrêt de départ à un arrêt d'arrivée, à une date et une heure de voyage données.
Une fois terminé, ReCHor pourra effectuer le même genre de recherches que des sites comme cff.ch, search.ch ou encore bahn.de, et proposera généralement des résultats similaires, avec parfois des différences mineures dues aux particularités des algorithmes de recherche utilisés. Il faut noter que ReCHor effectue la recherche sur des données horaires préalablement téléchargées sur l'ordinateur sur lequel il fonctionne, et ne nécessite donc aucune connexion Internet. Ces données sont obtenues à partir de l'horaire officiel des transports publics suisses.
Tout comme les sites susmentionnés, ReCHor effectue une recherche qui tente d'optimiser simultanément plusieurs critères, en l'occurrence les heures de départ et d'arrivée, et le nombre de changements.
La figure 1 ci-dessous montre une copie d'écran de la version finale de ReCHor. On y voit les relations proposées par le programme pour aller de l'arrêt Ecublens VD, EPFL — l'arrêt du métro m1 à l'EPFL — à l'arrêt Gruyères, le 18 février 2025 à 16h00. La partie gauche de l'interface montre la totalité des relations trouvées ce jour-là, tandis que la partie droite montre les détails de la relation sélectionnée.
En effectuant la même recherche sur les sites mentionnés plus haut, on constate qu'ils proposent des relations similaires mais avec parfois des différences insignifiantes. Par exemple, pour la relation sélectionnée (départ à 16h13), cff.ch propose d'effectuer le trajet de Renens à Lausanne avec le RE 33 (départ à 16h24, arrivée à 16h29) plutôt qu'avec le R 4 (départ à 16h26, arrivée à 16h33) comme ReCHor. Cela n'a toutefois aucun impact sur la suite du trajet.
Les relations proposées par ReCHor sont ce que l'on appelle « Pareto-optimales » pour les critères d'optimisation utilisés. Cela signifie que si une relation proposée est meilleure qu'une autre selon un critère, alors elle est forcément moins bonne selon au moins un autre critère. Ainsi, la relation partant à 15h55, proposée juste avant celle partant à 16h13, est meilleure que celle de 16h13 du point de vue des changements — car elle n'en nécessite que 3 plutôt que 4. Elle est donc forcément moins bonne selon un autre critère, en l'occurrence l'heure de départ. Un utilisateur de ReCHor désirant arriver à Gruyères à 17h57 devra donc décider s'il veut partir plus tôt mais changer moins souvent, ou partir plus tard et changer plus souvent.
Au bas de la partie droite de l'interface de ReCHor se trouvent deux boutons permettant respectivement de visualiser la relation choisie sur une carte, et de l'exporter au format iCalendar.
La visualisation sur une carte est faite sur une instance du programme uMap mise à disposition par la branche suisse du projet OpenStreetMap. La figure 2 ci-dessous montre une copie d'écran de la relation sélectionnée plus haut une fois visualisée dans uMap. Comme on le voit, la ligne brisée bleue représentant le trajet est relativement peu précise, car elle ne relie entre eux que les arrêts auxquels les différents moyens de transport utilisés s'arrêtent effectivement. Néanmoins, elle permet de se faire une idée du trajet.
L'exportation d'une relation au format iCalendar permet de l'importer par la suite dans la plupart des calendriers électroniques. Par exemple, une fois importée dans l'application Calendar de macOS, la relation ci-dessus ressemble à ceci :
2. Organisation
Le projet se fait par groupes de 2 personnes au maximum. La formation de ces groupes est libre et peut changer au cours du semestre, pour peu que les directives concernant le plagiat soient respectées. En particulier, si deux personnes ayant travaillé en commun se séparent, elles doivent se partager le code et ne peuvent chacune l'emporter en totalité de leur côté.
La mise en œuvre du projet est découpée en 12 étapes hebdomadaires, regroupées en trois parties :
- les étapes 1 à 6,
- les étapes 7 à 11,
- l'étape 12, qui est optionnelle.
La première partie est très guidée, afin de vous permettre de bien démarrer, tandis que la seconde l'est moins, la troisième étant (presque) totalement libre.
3. Notation
Un total de 500 points est attribué durant le semestre, répartis ainsi :
- projet : 300 points,
- examen intermédiaire : 75 points,
- examen final : 125 points.
Les 300 points attribués au projet sont répartis de la manière suivante :
- rendus testés : 100 points (20 points par rendu),
- rendu intermédiaire : 90 points,
- rendu final : 90 points,
- test final : 20 points.
Un rendu testé est un rendu qui est évalué automatiquement au moyen de tests. Il y a cinq rendus de ce type au cours du semestre, un pour chacune des étapes 2 à 6. Le nombre de points obtenus à un rendu testé est proportionnel au nombre de tests passés avec succès.
Le rendu intermédiaire, qui concerne les étapes 1 à 6, et le rendu final, qui concerne les étapes 7 à 11, sont quant à eux évalués par lecture de votre code, et les points attribués en fonction de la qualité du programme. L'efficacité, la concision et l'élégance du code sont prises en compte dans cette évaluation.
Le test final consiste en un test non automatisé — contrairement au test des étapes 2 à 6 — du bon fonctionnement du projet terminé.