Recherche de voyages optimaux

ReCHor – étape 7

1. Introduction

Le but principal de cette étape est d'écrire l'algorithme central du projet, qui recherche les voyages optimaux permettant de se rendre à un arrêt d'arrivée donné, un jour donné. Son but secondaire est d'écrire une classe permettant de stocker les données horaires dans ce que l'on nomme un cache, afin d'éviter de les recharger trop fréquemment.

2. Concepts

2.1. Algorithme CSA

Afin de calculer les voyages optimaux, nous utiliserons l'algorithme CSA1 (connection scan algorithm). Comme son nom le suggère, il effectue la recherche de voyages en parcourant la totalité des liaisons à l'horaire.

Cet algorithme se base sur l'observation que, si une liaison est ajoutée à un horaire mais qu'elle part avant toutes les liaisons existantes, alors les seuls voyages optimaux que son ajout peut affecter sont ceux partant de la gare de départ de cette liaison, ou d'une gare dont on peut y parvenir à pied.

Par exemple, admettons qu'aucune liaison ne parte avant 8h du matin, et que nous ayons établi le profil de tous les voyages optimaux permettant de se rendre de n'importe quelle gare de Suisse à Gruyères. Imaginons maintenant qu'une nouvelle liaison soit ajoutée à l'horaire, et parte de Renens à 7h59 pour arriver à Lausanne à 8h04. Il devrait être clair que cet ajout ne peut, au mieux, qu'améliorer les voyages optimaux partant de Renens ou d'une gare depuis laquelle il est possible de marcher jusqu'à celle de Renens. Aucun autre voyage optimal ne peut être affecté, car la nouvelle liaison part avant toutes les autres et n'est donc pas atteignable depuis une ancienne liaison.

Dès lors, on peut déterminer la totalité des voyages optimaux permettant de se rendre à une destination donnée en partant d'un horaire vide auquel on ajoute petit à petit toutes les liaisons, par heure de départ décroissante. Ce faisant, on garde à jour l'ensemble des voyages optimaux actuels.

Comme nous l'avons vu, l'information concernant les voyages optimaux est stockée dans les frontières de Pareto des critères d'optimisation attachées aux gares. Lors de l'exécution de l'algorithme, ce sont donc ces frontières de Pareto qui sont mises à jour au fur et à mesure de l'ajout des liaisons. De plus, des frontières de Pareto associées aux différentes courses sont tenues à jour de manière identique, pour des raisons expliquées plus bas.

Pour chaque liaison ajoutée à l'horaire, l'algorithme CSA commence par déterminer la frontière de Pareto des voyages optimaux de la liaison elle-même, en utilisant le fait qu'une personne l'empruntant n'a que trois manière de continuer son voyage :

  1. elle peut descendre à la fin de la liaison et marcher jusqu'à la destination finale, pour peu que celle-ci soit atteignable à pied depuis là,
  2. elle peut rester dans le véhicule afin de continuer avec la prochaine liaison de la même course (s'il y en a une),
  3. elle peut changer de véhicule à la fin de la liaison.

Une fois que la frontière de Pareto des voyages optimaux de la liaison a été déterminée, elle peut être utilisée pour mettre à jour les frontières de Pareto de :

  • la course à laquelle appartient la liaison, et
  • toutes les gares depuis lesquelles il est possible de marcher pour atteindre la gare de départ de la liaison — y compris la gare de départ elle-même.

Lorsque toutes les liaisons ont été ajoutées, l'algorithme se termine, son résultat étant les frontières de Pareto des voyages optimaux des gares.

2.1.1. Version de base

La version de base de l'algorithme CSA ne contient aucune optimisation et se contente de calculer les frontières de Pareto des voyages optimaux permettant de rejoindre la destination depuis n'importe quelle gare, sans calculer l'information auxiliaire nécessaire à l'extraction des voyages. Elle est présentée ci-dessous sous forme de pseudo-code dans lequel :

  • dst est l'arrêt de destination,
  • dep(x) / arr(x) est l'arrêt de départ/arrivée de la liaison ou du changement x,
  • h_dep(x) / h_arr(x) est l'heure de départ/arrivée de la liaison ou du tuple x,
  • chg(t) est le nombre de changements du tuple t,
  • trp(l) est la course de la liaison l,
  • dur(c) est la durée du changement c.

Bien entendu, les liaisons parcourues par l'algorithme sont celles du jour de voyage choisi. 

 1: p = profil vide
 2: 
 3: pour chaque liaison l par heure de départ décroissante:
 4:   f = frontière de Pareto vide
 5: 
 6:   // Option 1: marcher de l'arrivée de l à la destination
 7:   s'il existe un changement c de arr(l) à dst:
 8:     ajouter à f le tuple (h_arr(l) + dur(c), 0)
 9: 
10:   // Option 2: continuer avec la liaison suivante
11:   ajouter à f tous les tuples de p[trp(l)]
12: 
13:   // Option 3: changer de véhicule à la fin de l
14:   pour tous les tuples t de p[arr(l)]:
15:     si h_dep(t) >= h_arr(l):
16:       ajouter à f le tuple (h_arr(t), chg(t) + 1)
17: 
18:   // Mise à jour de la frontière de la liaison
19:   ajouter à p[trp(l)] tous les tuples de f
20: 
21:   // Mise à jour des frontières des gares
22:   pour tous les changements c arrivant à dep(l):
23:     d = h_dep(l) - dur(c)
24:     pour tous les tuples t de f:
25:       ajouter à p[dep(c)] le tuple (d, h_arr(t), chg(t))

Le résultat de l'algorithme est le profil p, qui contient les frontières de Pareto des voyages optimaux pour toutes les gares et toutes les courses. Comme nous l'avons vu, seules celles associées aux gares sont nécessaires pour reconstruire ensuite les voyages optimaux, mais des informations additionnelles doivent être associées à leurs tuples.

2.1.2. Informations associées

Pour pouvoir extraire les voyages à partir d'un profil, il faut qu'à chaque tuple d'une frontière de Pareto de gare soient associés :

  • l'identité de la première liaison de la première étape du voyage,
  • le nombre d'arrêts intermédiaires de la première étape du voyage.

Pour mémoire, dans notre mise en œuvre, ces informations sont empaquetées dans la charge utile du tuple auquel elles sont associées.

Afin de pouvoir déterminer ces informations pour les tuples des frontières des gares, il est nécessaire d'associer aux tuples des frontières des courses l'identité de la liaison de la course en question à laquelle il faut en descendre. Cette liaison est facile à déterminer : lorsqu'on termine à pied après la liaison l (ligne 8), ou lorsqu'on change de véhicule à la fin de l (ligne 16), cette liaison est simplement l.

Grâce à cette information associée aux frontières des courses, on peut calculer l'information à associer aux tuples lors de la mise à jour des frontières des gares (ligne 25), puisque :

  • la première liaison de la première étape du voyage est simplement la liaison l,
  • le nombre d'arrêts intermédiaires est la différence entre la position, dans la course, de la liaison à laquelle il faut descendre de la course, et la liaison l.

2.1.3. Optimisations

L'algorithme de base peut être optimisé de deux manières.

Premièrement, avant d'effectuer les mises à jour des frontières de Pareto de la course et des gares, si la frontière f est vide, on peut passer directement à la liaison suivante.

Deuxièmement, la mise à jour des frontières des gares n'a pas besoin d'être faite si tous les tuples de la frontière f, augmentés de l'heure de départ de la liaison l, sont dominés par au moins un tuple de la frontière de la gare de départ de l. En effet, on sait dans ce cas que la frontière f n'aurait aucun impact sur celles des gares depuis lesquelles il est possible de marcher jusqu'à la gare de départ de l, même si le temps de marche était nul.

2.2. Mémoire cache

En informatique, on nomme mémoire cache (cache memory), ou simplement cache, une mémoire dans laquelle on stocke une (copie d'une) donnée fréquemment utilisée, pour éviter de devoir la recalculer à chaque utilisation.

Dans ce projet, nous utiliserons un cache pour accélérer l'accès aux données horaires qui dépendent du jour, c.-à-d. les courses et les liaisons. Comme nous l'avons vu à l'étape précédente, ces données sont chargées — ou, plus exactement, « mappées » en mémoire — à chaque utilisation. Or il est très probable que les données horaires du même jour soient nécessaires plusieurs fois de suite, et en les plaçant dans un cache on évite leur rechargement — ou « re-mappage » en mémoire — ce qui peut améliorer considérablement les performances du programme.

Le cache que nous utiliserons est particulièrement simple, puisqu'il ne mémorise que les données horaires d'un seul jour. On aurait pu imaginer un cache plus sophistiqué, mémorisant les données des n derniers jours, mais étant donné la manière dont le programme est généralement utilisé, cela ne s'avère pas utile.

3. Mise en œuvre Java

Cette étape est la première de la seconde partie du projet, durant laquelle vous serez plus libres et moins guidés que durant la première.

En particulier, vous avez maintenant le droit de modifier ou augmenter l'interface publique des classes et interfaces proposées, pour peu bien entendu que vous ayez une bonne raison de le faire. Pour faciliter la correction, nous vous demandons néanmoins de respecter les noms de paquetages et de classes, interfaces, enregistrements et types énumérés donnés.

D'autre part, nous nous attendons à ce que vous lisiez et compreniez la documentation des parties de la bibliothèque Java que vous devez utiliser.

3.1. Enregistrement Router

L'enregistrement Router du sous-paquetage journey, public et immuable, représente un « routeur », c.-à-d. un objet capable de calculer le profil de tous les voyages optimaux permettant de se rendre de n'importe quelle gare du réseau à un gare d'arrivée donnée, un jour donné. Il possède un seul attribut, de type TimeTable, qui contient les données horaires à utiliser.

En dehors des méthodes ajoutées automatiquement par Java aux enregistrements, Router possède une seule méthode publique, nommée p. ex. profile, qui prend en arguments :

  • la date pour laquelle les voyages optimaux doivent être calculés,
  • l'identité de la gare de destination,

et retourne le profil de tous les voyages optimaux permettant de se rendre de n'importe quelle gare du réseau à celle de destination, le jour donné. Cette méthode utilise bien entendu l'algorithme CSA décrit plus haut.

3.1.1. Conseils de programmation

  1. Organisation

    L'algorithme CSA n'est pas trivial à mettre en œuvre, et pour cette raison il est fortement conseillé de procéder par étapes, ainsi :

    1. commencer par la version de base, sans gestion de la charge utile permettant d'extraire les voyages, ni optimisations,
    2. tester cette version en vérifiant, par exemple, que dans le profil pour se rendre à Gruyères un mardi, la frontière associée à l'arrêt Ecublens VD, EPFL comporte bien les tuples correspondants aux voyages visibles sur la figure 1 de l'introduction au projet,
    3. augmenter cette mise en œuvre pour qu'elle gère la charge utile,
    4. tester cette nouvelle mise en œuvre en extrayant des voyages du profil obtenu et en les comparant aux résultats attendus,
    5. augmenter encore la mise en œuvre pour lui ajouter les optimisations, et vérifier que cela n'a pas d'impact sur le profil généré.

    En procédant ainsi, vous augmentez vos chances d'obtenir assez un code correct en un temps raisonnable.

  2. Arrêts « marchables »

    Pour chaque liaison qu'il examine, l'algorithme CSA doit tout d'abord déterminer s'il existe un changement allant de l'arrivée de la liaison à la destination finale.

    Ce test pourrait bien entendu se faire en appelant minutesBetween, mais sachant qu'il doit être fait pour chacune des ~3 millions de liaisons, une technique plus rapide doit être utilisée.

    Nous vous proposons donc d'utiliser un tableau indexé par les gares et contenant, à un index donné, le temps de marche entre la gare correspondante et la destination, ou -1 si le trajet n'est pas faisable à pied. Ce tableau peut être créé avant de commencer à parcourir les liaisons, et grâce à lui, le test susmentionné est très rapide.

  3. Parcours des liaisons

    L'algorithme CSA parcourt les liaisons par ordre décroissant d'heure de départ. Dans les données que nous utilisons, les liaisons sont déjà triées de la sorte, donc il suffit de les parcourir par ordre croissant d'index.

3.2. Classe CachedTimeTable

La classe CachedTimeTable du sous-paquetage timetable, publique et immuable, implémente TimeTable et représente un horaire dont les données qui dépendent de la date — les courses et les liaisons — sont stockées dans un cache. De la sorte, si ces données sont demandées plusieurs fois de suite pour une seule et même date, elles ne sont pas rechargées à chaque fois.

CachedTimeTable offre un constructeur prenant en argument l'horaire, de type TimeTable, dont les courses et liaisons doivent être stockées dans un cache. Nous appellerons cet horaire l'horaire sous-jacent (underlying timetable).

En dehors de ce constructeur, CachedTimeTable n'offre que les méthodes publiques de l'interface TimeTable.

3.2.1. Conseils de programmation

  1. Représentation du cache

    CachedTimeTable garde en cache au plus une valeur de type Connections et une de type Trips, stockées dans des attributs qui peuvent être vides (null).

    Initialement, ces attributs sont null, mais au premier appel à la méthode tripsFor ou connectionsFor, les données sont tout d'abord obtenues de l'horaire sous-jacent, puis stockées dans l'attribut correspondant — le cache. Bien entendu, la date à laquelle ces données correspondent doit également être mémorisée dans un attribut.

    Lors des appels suivants aux méthode tripsFor ou connectionsFor, si les données horaires demandées sont celles qui sont déjà dans le cache — c.-à-d. stockées dans les attributs —, alors elles sont simplement retournées, sans aucun appel à une méthode de l'horaire sous-jacent. Par contre, si la date passée en argument à tripsFor ou connectionsFor n'est pas la même que celle passée à l'appel précédent, alors les données sont obtenues de l'horaire sous-jacent et stockées dans les attributs à la place des anciennes.

    De la sorte, toute séquence d'appels aux méthodes tripsFor ou connectionsFor avec la même date en argument ne nécessite qu'un seul chargement — ou « mappage » en mémoire — des données.

  2. Délégation

    Toutes les méthodes de CachedTimeTable, à l'exception de connectionsFor et tripsFor, ne font rien d'autre qu'appeler la même méthode sur l'horaire sous-jacent, en retournant son éventuelle valeur de retour.

    En programmation orientée-objets, cette technique consistant à demander à un objet d'effectuer une tâche à la place d'un autre se nomme souvent délégation (delegation). Étant donné que la délégation est fréquemment utilisée, IntelliJ permet de générer le code des méthodes qui délèguent leur tâche à un autre objet. Pour utiliser cette possibilité, il vous suffit de :

    • déclarer l'attribut contenant l'horaire sous-jacent auquel les différentes tâches (méthodes) vont être déléguées,
    • placer votre curseur dans la classe, à l'endroit où les méthodes de délégation devraient apparaître,
    • ouvrir le menu Code, choisir Generate… puis Delegate Methods…, sélectionner l'objet auquel déléguer les méthodes (l'horaire sous-jacent), puis les méthodes qu'IntelliJ doit générer.

3.3. Tests

Pour tester votre calcul de voyages optimaux, vous pouvez écrire un programme similaire à celui ci-dessous pour afficher l'événement iCalendar correspondant à un voyage optimal. Avec les données horaires de la semaine 14, ce programme devrait afficher un événement très similaire à celui de la §2.1.8 de l'étape 2. 

static int stationId(Stations stations, String stationName) {
  // … laissé en exercice
}

public static void main(String[] args) throws IOException {
  long tStart = System.nanoTime();

  TimeTable timeTable =
    new CachedTimeTable(FileTimeTable.in(Path.of("timetable")));
  Stations stations = timeTable.stations();
  LocalDate date = LocalDate.of(2025, Month.APRIL, 1);
  int depStationId = stationId(stations, "Ecublens VD, EPFL");
  int arrStationId = stationId(stations, "Gruyères");
  Router router = new Router(timeTable);
  Profile profile = router.profile(date, arrStationId);
  Journey journey = JourneyExtractor
    .journeys(profile, depStationId)
    .get(32);
  System.out.println(JourneyIcalConverter.toIcalendar(journey));

  double elapsed = (System.nanoTime() - tStart) * 1e-9;
  System.out.printf("Temps écoulé : %.3f s%n", elapsed);
}

En plus de l'évènement iCalendar, ce programme affiche le temps nécessaire à son exécution. Sur un MacBook Pro de 2020, ce temps se situe généralement autour des 2½ secondes, et si vous obtenez un résultat du même ordre de grandeur sur votre ordinateur, vous pouvez raisonnablement en conclure que votre programme n'a pas de gros problème de performance.

Bien entendu, vous pouvez également calculer les voyages optimaux entre des gares différentes, et comparer vos résultats avec ceux d'un site comme celui des CFF.

Finalement, vous pouvez aussi essayer de calculer le même profil que celui fourni à l'étape 6, le stocker dans un fichier textuel de format identique, et ensuite comparer le contenu des deux fichiers. IntelliJ permet de faire facilement de telles comparaison : il suffit de sélectionner les deux fichiers à comparer, puis à sélectionner Compare files… dans le menu contextuel.

Faites toutefois attention au fait qu'il pourrait y avoir des différences non significatives dues à la manière dont la méthode add de votre classe ParetoFront.Builder gère le cas où on ajoute un tuple déjà présent dans la frontière en cours de construction. Le corrigé du projet, utilisé pour générer le profil de référence, conserve l'ancien tuple et sa charge utile, en ignorant le nouveau. Si votre mise en œuvre remplace le tuple existant par le nouveau — ce qui est aussi valide, bien que moins efficace — alors vous pourriez obtenir un profil différent mais néanmoins correct.

4. Résumé

Pour cette étape, vous devez :

  • écrire les classes Router et CachedTimeTable selon les indications donnés plus haut,
  • tester votre code,
  • documenter la totalité des entités publiques que vous avez définies.

Vous n'avez pas l'obligation de rendre cette étape avant le rendu final, mais nous vous conseillons néanmoins de le faire afin de sauvegarder votre travail.

Notes de bas de page

1

Cet algorithme est décrit dans un article du même nom disponible en ligne. Il n'est absolument pas nécessaire de lire cet article, mais les personnes décidant de le faire devront prêter attention au fait qu'il comporte malheureusement de nombreuses erreurs.