SafeRoute

Fait par Gillesto

⚠️ Avertissement d'usage. Le score de risque est une densité statistique de crimes passés (Police UK, SAPS). Il ne prédit pas un crime et ne garantit pas la sécurité d'un trajet : il aide à comparer des itinéraires, il ne remplace pas le jugement de la personne qui se déplace. Les sources sont anonymisées et biaisées par le signalement (voir docs/donnees.md).

Qu'est-ce que SafeRoute ?

SafeRoute est une bibliothèque Python de routage piéton sûr qui calcule simultanément trois itinéraires entre deux points d'une ville, en optimisant des objectifs contradictoires :

Le moteur de calcul est écrit en Rust (recherche multi-objectif ε-approximée) et exposé à Python via PyO3/maturin ; le scoring KDE est en Python (numpy/scipy). Les données de criminalité proviennent de sources officielles : Police UK API pour Londres et SAPS pour Le Cap — ou les vôtres, pour n'importe quelle ville (engine.load_graph(graphe_osmnx, crimes)).

Pourquoi SafeRoute ?

Les applications de navigation classiques (Google Maps, Waze) optimisent uniquement la distance ou le temps. SafeRoute résout un problème différent : comment rentrer chez soi en sécurité ?

La formule de coût intègre trois dimensions :

C = w₁ · Distance + w₂ · Risque − w₃ · Familiarité

• Risque : densité criminelle sur chaque segment de rue, calculée par KDE gaussien à partir des données historiques de criminalité géolocalisées (bande passante réelle en mètres)
• Familiarité : les rues que vous empruntez régulièrement sont mémorisées et cumulées (total_familiarity). Elle n'influence pas le choix des trois itinéraires (voir limites connues).
• Algorithme : recherche à étiquettes biobjectif de type NAMOA*, inspirée de A*pex (Zhang et al., ICAPS 2022), avec bornes inférieures exactes et élagage ε. Garantie vérifiée par les tests contre un calcul exhaustif : chaque solution Pareto-optimale exacte est couverte à (1+ε) près (eps=0.1 → 10 %). Elle ne reprend pas le regroupement en « paires apex » de l'article.

Installation

# Bibliothèque seule (calcul d'itinéraires)
pip install saferoute

# Avec le serveur REST FastAPI
pip install "saferoute[api]"

Rust n'est pas requis : le wheel PyPI contient le binaire Rust précompilé (wheel abi3 : Windows, Linux et macOS, Python ≥ 3.10). Sans wheel pour votre plateforme, pip compile les sources et exige alors une chaîne Rust. Cartes et graphiques (notebook de démonstration) : pip install "saferoute[viz]".

Exemple concret : trouver le chemin le plus sûr à Londres

from saferoute import SafeRouteEngine
from saferoute.exceptions import SafeRouteError

# 1. Initialiser le moteur (eps=0.1 → approximation à 10% de l'optimal)
engine = SafeRouteEngine(eps=0.1)

# 2. Charger la ville — utilise le cache local si disponible,
#    télécharge OSMnx + données de criminalité sinon (~5 min la première fois)
engine.load_city("london")

# 3. Convertir des coordonnées GPS en identifiants de nœuds OSM
#    Départ : Gare de London Bridge
source = engine.nearest_node(lat=51.5055, lon=-0.0873)
#    Arrivée : Borough Market
target = engine.nearest_node(lat=51.5055, lon=-0.0910)

# 4. Calculer les 3 itinéraires Pareto-optimaux
try:
    pareto = engine.compute_routes(source, target)
except SafeRouteError as e:
    print(f"Erreur : {e}")
    raise

# 5. Comparer les résultats
print(f"Plus court  : {pareto.shortest.total_distance_m:.0f}m "
      f"en {pareto.shortest.estimated_time_min:.1f} min "
      f"(risque={pareto.shortest.total_risk:.3f})")

print(f"Plus sûr    : {pareto.safest.total_distance_m:.0f}m "
      f"en {pareto.safest.estimated_time_min:.1f} min "
      f"(risque={pareto.safest.total_risk:.3f})")

print(f"Équilibré   : {pareto.balanced.total_distance_m:.0f}m "
      f"en {pareto.balanced.estimated_time_min:.1f} min "
      f"(risque={pareto.balanced.total_risk:.3f})")

# Exemple de sortie typique :
# Plus court  : 380m en 5.7 min (risque=0.847)
# Plus sûr    : 510m en 7.7 min (risque=0.112)
# Équilibré   : 430m en 6.5 min (risque=0.341)

# 6. Enregistrer le trajet effectué pour améliorer les recommandations futures
#    (les rues empruntées régulièrement voient leur coût réduit)
engine.record_trip(pareto.balanced.path)

Utiliser l'API REST

# Démarrer le serveur
uvicorn saferoute.api.main:app --reload
# → Documentation interactive : http://localhost:8000/docs

# Charger une ville
curl -X POST http://localhost:8000/api/v1/load-city \
     -H "Content-Type: application/json" \
     -d '{"city": "london"}'

# Calculer les 3 itinéraires
curl -X POST http://localhost:8000/api/v1/route \
     -H "Content-Type: application/json" \
     -d '{
       "city": "london",
       "source_node": 123456789,
       "target_node": 987654321,
       "eps": 0.1
     }'

Réponse JSON consommable directement par React ou Flutter :

{
  "city": "london",
  "shortest": {
    "path": [123456789, 111, 222, 987654321],
    "total_distance_m": 380.0,
    "distance_km": 0.38,
    "total_risk": 0.847,
    "estimated_time_min": 5.7,
    "comfort_score": 0.17,
    "route_type": "shortest"
  },
  "safest": { "..." : "..." },
  "balanced": { "..." : "..." }
}

Performance mesurée

Mesures réelles et rejouables (python benchmarks/run.py --city london), portable 8 cœurs logiques / 15,8 Go, Windows 11, Python 3.13 (détail, méthode et limites : docs/benchmarks.md).

La promesse « < 2 secondes sur Londres » des versions précédentes n'est vraie ni en général ni pour les trajets longs : elle l'est pour les trajets de moins de ~4 km et la médiane des 4–10 km. Une requête trop complexe s'arrête avec SearchBudgetExceededError (jamais un crash) ; augmenter eps (0,3) aide.

Villes supportées

Architecture

SafeRoute/
├── src/
│   ├── saferoute/          ← Package Python
│   │   ├── engine.py       ← Orchestrateur principal
│   │   ├── exceptions.py   ← SafeRouteError, GraphNotLoadedError, ...
│   │   └── api/            ← Serveur FastAPI (optionnel)
│   └── rust/               ← Core de calcul Rust
│       └── src/
│           ├── algorithms/ ← A*pex + frontière de Pareto
│           ├── graph/      ← Structures Node, Edge, Graph
│           └── scoring/    ← KDE gaussien
└── tests/                  ← 170 tests Python + 64 tests Rust

Protocole Python ↔ Rust : Python convertit le graphe enrichi (OSMnx + scores KDE + familiarité) en colonnes numpy, une seule fois ; Rust reçoit les octets bruts (PyGraph.from_arrays, sans JSON) et valide le graphe. Quand la familiarité change, seuls les arcs modifiés sont renvoyés (update_familiarity). Rust exécute la recherche (GIL relâché) et retourne les routes → Python les convertit en dataclasses.

Limites connues

• La familiarité ne modifie pas le choix des routes : elle est cumulée et rapportée, mais n'entre ni dans la dominance de Pareto ni dans la sélection de shortest / safest / balanced.
• safest minimise le risque seul : sur un trajet de 7 km à Le Cap, il peut atteindre ~25 km.
• Le défaut de bande passante (Silverman, 740–800 m) sur-lisse : en évaluation temporelle sur Londres (test sur 2 mois jamais vus), il n'atteint que AUC 0,536 (hasard = 0,5), contre 0,663 avec SafeRouteEngine(bandwidth_m="auto"). Utilisez "auto" ; voir docs/benchmarks.md.
• Le cache d'origine de Londres n'avait pas de date et sous-échantillonnait les crimes (voir ci-dessous) ; benchmarks/download_dated_london.py télécharge des crimes datés (fetch_london_crimes conserve le mois).
• Les crimes de Londres sont ancrés sur des points de rue : plusieurs crimes réels partagent les mêmes coordonnées (voir validate_crimes(..., deduplicate=False)).
• Le graphe d'une grande ville occupe plusieurs Go de RAM ; le chargement du graphml est lent (4 min pour Londres) et est le goulot d'étranglement du démarrage.

Documentation complète

https://gillesto66.github.io/SafeRoute/

Développement

# Prérequis : Rust (https://rustup.rs)
git clone https://github.com/Gillesto66/SafeRoute.git
cd SafeRoute
pip install -e ".[dev,api]"           # compile aussi le core Rust (maturin)

# Tests (CI=true : l'absence du module natif devient un échec au lieu d'un test sauté)
CI=true python -m pytest tests/ -q    # tests Python
cargo test --workspace                # tests Rust : aucun Python requis

# Wheel construit, installé dans un environnement vierge
python -m maturin build --release --out dist && python scripts/smoke_wheel.py dist

Voir CONTRIBUTING.md pour le guide complet.

Licence

MIT — voir LICENSE