Route Planning — M1 Structures de données avancées

Ce projet implémente un moteur de calcul d’itinéraires sur graphe routier, avec pour objectif de comparer différentes méthodes de plus court chemin dans un contexte réaliste.

Il s’inscrit dans le cadre du projet de M1 « Structures de données avancées ».

---

Objectif du projet

Le but n’est pas uniquement d’implémenter des algorithmes, mais de comprendre et mesurer les compromis entre différentes approches.

Nous cherchons notamment à répondre aux questions suivantes :

• Qu’est-ce qui permet d’accélérer les requêtes ?
  • heuristique (A*)
  • prétraitement (ALT, CH)
  • structure mémoire (CSR)
• Quel est le coût de ces accélérations ?
  • mémoire supplémentaire
  • temps de prétraitement
• Les gains sont-ils stables selon le type de requête ?
  • courtes distances
  • distances moyennes
  • longues distances

---

Algorithmes étudiés

Dijkstra (baseline)

• Algorithme de référence
• Correct mais lent sur gros graphes
• Utilisé pour valider les résultats

---

A*

• Ajout d’une heuristique (distance haversine)
• Réduction du nombre de sommets explorés
• Gain significatif sur les requêtes

---

ALT (A* + landmarks)

• Heuristique améliorée via des points repères
• Prétraitement : distances vers/depuis les landmarks
• Implémentation avec sélection farthest-first

---

CH (Contraction Hierarchies)

• Méthode basée sur un prétraitement lourd
• Ajout de raccourcis (shortcuts)
• Requêtes extrêmement rapides

---

Données et modélisation

Le réseau routier est modélisé comme un graphe orienté pondéré :

• sommet = intersection
• arête = segment de route
• poids = distance

Les données proviennent de OpenStreetMap (Île-de-France) :

Disponible sur ce lien : https://download.geofabrik.de/europe/france/ile-de-france.html

Format requis : .osm.pbf

(nécessaire de changer le chemin/nom du fichier dans src/loadData.py ligne 18 !)

---

Représentation du graphe

Le graphe est stocké en CSR (Compressed Sparse Row) :

• tableaux contigus
• accès rapide aux voisins
• meilleure locality cache
• faible empreinte mémoire

---

Méthodologie expérimentale

Génération des requêtes

• paires (source, cible) générées aléatoirement
• distances calculées avec Dijkstra
• classification en :
  • SHORT
  • MEDIUM
  • LONG

Classification basée sur la distance réelle

---

Mesures collectées

Pour chaque algorithme :

• temps par requête (moyenne, p50, p95)
• débit (requêtes/s)
• nombre de sommets explorés (settled)
• nombre de relaxations
• mémoire utilisée
• coût de prétraitement (ALT, CH)

---

Validation

• comparaison systématique avec Dijkstra
• tolérance sur flottants
• vérification de la correction des résultats

---

Structure du projet

. ├── src/ │ ├── loadData.py │ ├── loadSubsetGeo.py │ ├── benchmark.c │ ├── plotBenchmark.py │ └── ... ├── include/ ├── dataset/ ├── results/ ├── runAll.sh └── readMe.md

---

Exécution

1. Télécharger les données

Télécharger le fichier .osm.pbf depuis :

https://download.geofabrik.de/europe/france/ile-de-france.html

---

2. Lancer le pipeline complet

#si permission refuser, lancer la commande ci-dessous avant
#chmod +x runAll.sh
#forcer bash et non ./ qui peut utiliser un shell different 
bash runAll.sh

Ce script :

• vérifie / installe les dépendances
• génère le graphe
• extrait un sous-graphe
• compile le benchmark C
• exécute les algorithmes
• génère les résultats et graphiques

---

📊 Résultats

Les résultats sont stockés dans :

result/

Fichiers

• benchmark_summary.csv → statistiques
• benchmark_queries.csv → résultats détaillés

Graphiques

• temps moyen par type de requête
• sommets explorés
• temps vs distance
• mémoire utilisée

---

Résultats typiques

• Dijkstra explore presque tout le graphe
• A* réduit fortement l’exploration
• ALT dépend du choix des landmarks
• CH offre les meilleures performances en requête

---

Installation requise

Dépendances système

Assurez-vous d’avoir installé :

• python3
• pip
• gcc
• osmium (pour le traitement des données OpenStreetMap)

Sur macOS (via Homebrew) :

brew install osmium-tool

Sur Linux (Ubuntu/Debian)

sudo apt update
sudo apt install osmium-tool build-essential python3 python3-pip

Dépendances Python

Les bibliothèques suivantes sont nécessaires :

• numpy
• pandas
• matplotlib

Installation :

pip3 install numpy pandas matplotlib

Données nécessaires

Le projet nécessite un fichier OpenStreetMap :

https://download.geofabrik.de/europe/france/ile-de-france.html

Télécharger le fichier :

ile-de-france-latest.osm.pbf

et le placer dans le dossier :

dataset/

---