Projet : Réseau de transport en commun

La problématique

Dans ce projet, vous allez devoir réaliser une application Python permettant de rechercher un itinéraire entre deux arrêts du réseau de transports en commun de la ville de Toulouse (Tisseo).

Afin d'y parvenir, vous devrez réaliser un graphe orienté pondéré où les sommets correspondent aux arrêts, et les arcs correspondent à un trajet entre deux arrêts (à pied ou en transports en commun), et dont leur poids correspond à la durée en seconde entre ces deux arrêts.

Vous êtes libres de choisir l'implémentation de votre choix pour réaliser ce graphe.

Vous devrez ensuite appliquer l'algorithme du plus court chemin de Dijkstra afin de répondre à la problématique.

Les ressources

Afin de vous aider à réaliser le réseau, un fichier GTFS¹ vous est fourni. C'est un fichier standard dans les services de transports en commun, que vous pourrez retrouver pour chaque réseau. Ainsi, votre travail pourra en théorie être facilement transposable d'un réseau à un autre.

Télécharger le GTFS

Ce fichier GTFS est un simple dossier ZIP contenant plusieurs fichiers. Malgré leur extension, tous les fichiers sont rédigés au format CSV. La documentation complète de chaque fichier est à retrouver sur ce site. Une description de certains fichiers est fournie ci-dessous pour vous aider à démarrer :

Le fichier stops.txt contient la liste des arrêts. Pour regrouper tous les arrêts du même nom, un arrêt parent est créé, et son identifiant débute par SA. Il est possible de retrouver l'arrêt parent d'un arrêt depuis la colonne parent_station. De plus, le fichier transfers.txt permet d'indiquer les transfers possibles à pied entre deux arrêts du même parent (utile pour les transfers).
Le fichier routes.txt contient la liste des lignes. Chaque ligne possède plusieurs trajets dans trips.txt. Pour simplifier, on ne travaillera que sur deux trajets par ligne (un dans chaque sens).
Le fichier stop_times.txt indique pour chaque trajet l'heure d'arrivée et de départ à chaque arrêt de ce trajet.

Comment y parvenir ?

Vous devrez donc débuter par la construction de ce réseau en Python. Avant de vous lancer dans la programmation, il est important de comprendre le fonctionnement de ces fichiers en réalisant des schémas (et pourquoi pas des graphes).

Commencez donc par réaliser un graphe sur papier des trajets possibles depuis la station Esquirol. Ce sera l'occasion de se poser la question des informations à noter dans les sommets et sur les arcs.

Une fois que cette prise en main est parfaite, et que vous savez comment vous allez représenter votre graphe, vous pourrez passer à l'extraction des données dans Python.

Ouvrir un fichier au format CSV

Le code ci-dessous permet d'ouvrir le fichier stop_times.txt (placé dans le même dossier) et d'enregistrer ses informations dans un objet de type DataFrame. Un DataFrame est une sorte de tableur du module pandas qui nous permettra bien plus d'opérations qu'une simple liste, et surtout une meilleure efficacité.

import pandas as pd

stop_times = pd.read_csv("stop_times.txt", sep=',', header=0, dtype={
    "trip_id": int,
    "arrival_time": str,
    "departure_time": str,
    "stop_id": str,
    "pickup_type": int,
    "drop_off_type": int,
    "stop_sequence": int,
    "shape_dist_traveled": float,
    "timepoint": int,
    "stop_headsign": str
})

# Voici comment récupérer les lines du CSV dont la colonne stop_id vaut une valeur donnée
liste_trajets = stop_times[stop_times["stop_id"] == "stop_point:SP_3480"]

# L'objet liste_trajets est également un DataFrame de Pandas. On peut donc
# appliquer encore un filtre, ou bien parcourir ses valeurs :

for index, trajet in liste_trajets.iterrows():
    # Le .iterrows permet d'indiquer qu'on veut itérer sur les lignes.

    # On affiche ensuite l'heure de départ de chaque trajet
    print(trajet["departure_time"])

Ce projet a également pour but de vous apprendre à découvrir de nouveaux modules Python. Ainsi, une documentation express vous est fournie au format PDF.

Vous devrez utiliser cette documentation, et quelques recherches sur le web, afin de créer un graphe contenant notre réseau de transports en commun.

Une fois le graphe réalisé, demandez à l'utilisateur d'entrer deux arrêts, et proposez-lui un itinéraire entre ces deux arrêts.

Quel est le travail attendu ?

Vous devrez rendre un document PDF expliquant votre démarche, votre implémentation, et toutes les étapes que vous aurez mises au point. Il vous faudra également détailler les étapes clés des algorithmes utilisés dans votre programme Python.

Afin de vous séparer les tâches, vous pouvez définir les rôles suivants :

Responsable des données :
- Tâches principales :
  - Comprendre et extraire les données des fichiers GTFS.
  - Utiliser Pandas pour manipuler les données et créer les premières structures de base.
- Compétences nécessaires :
  - Bonne maîtrise des formats CSV et de leur manipulation avec Python.
  - Capacité à comprendre les relations entre les différents fichiers GTFS.
Architecte du graphe
- Tâches principales :
  - Concevoir la structure du graphe en Python.
  - Traduire les données extraites en un graphe orienté pondéré représentant le réseau de transport.
  - Définir les méthodes pour ajouter des éléments dans le graphe.
- Compétences nécessaires :
  - Connaissance des graphes et des algorithmes associés.
  - Maîtrise de la manipulation de structures complexes en Python, comme les dictionnaires.
Développeur d'algorithmes
- Tâches principales :
  - Implémenter l'algorithme de Dijkstra pour trouver le plus court chemin entre deux arrêts.
  - Assurer une bonne intégration de l'algorithme avec le graphe construit.
  - Tester et valider les résultats avec des scénarios réalistes, en utilisant des données réelles extraites du GTFS.
- Compétences nécessaires :
  - Connaissance des algorithmes de graphes, notamment Dijkstra (mais pas que).
  - Capacité à optimiser le code pour garantir une exécution fluide même avec des données volumineuses.

General Transit Feed Specification ↩