Depuis plusieurs années, nous utilisons RAPTOR pour calculer nos itinéraires en transport en commun. RAPTOR permet de trouver l'arrivé au plus tôt pour chaque point d'arrêt du réseau en fonction du nombre de correspondances. Les alternatives proposés n'étaient pas suffisament diversifiées. Certaines correspondances étaient également mal choisi. C'est pourquoi nous avons développé un algorithme permettant de choisir les solutions intéressantes parmis tous les itinéraires implicites fournis par RAPTOR.
Les entrées de l'arlgorithme de calcul sont deux ensembles de points d'arrêts avec leur durée d'accès : un ensemble pour le départ, et un ensemble pour l'arrivé. Par exemple, supposons que nous souhaitons partir du point A pour aller au point B. Les numéros sont des points d'arrêts.
1 2 3 7 8
A 6 B 9
5 4 10
Ce qui nous donnerait:
- départ: 1->27min, 2->15min, 3->12min, 4->6min, 5->21min, 6->18min
- arrivé: 6->21min, 7->18min, 8->9min, 9->9min, 10->6min
Pour un itinéraire de A à B en partant après 8h, nous donnons alors à RAPTOR les heures de début au plus tôt aux points d'arrêt accessible de A: 1->8h27, 2->8h15, 3->8h12, 4->8h06, 5->8h21, 6->8h18. RAPTOR calcule alors les arrivés au plus tôt en fonction du nombre de correspondances. Pour ce qui nous intéresse, cela donnerait:
- 6: 8h32 avec 0 correspondance, 8h23 en 1 correspondance
- 7: 10h29 en 2 correspondances
- 8: pas de solution
- 9: 8h15 en 2 correspondances
- 10: 8h37 en 1 correspondances
L'arrivé au plus tôt au point B est donc à 8h24 avec 2 correspondances en arrivant au point d'arrêt 9. L'arrivé avec le moins de correspondance est à 8h53 en 0 correspondance en descendant au point d'arrêt 6. Les itinéraires sont recomposés en prenant les véhicules qui ont été utilisés pour trouver les horaires d'arrivées.
Voir http://confluence.canaltp.fr/pages/viewpage.action?pageId=3769232#Lecalculd%27itin%C3%A9raire-calcul_horaireAlgorithmehoraire%28oualgorithmeli%C3%A9autransportencommun%29 partie Minimisation du temps d'attente
problèmes : troisième passe, ligne en Y, alternatives minimisant la marche à pied.
RAPTOR calcule l'arrivé au plus tôt aux points d'arrêt en fonction du nombre de correspondances. Pour reconstruire l'itinéraire, nous notons les différentes montées et descentes de véhicules qui ont permis de trouver ces temps. Mais il existe d'autres itinéraires permettant d'arriver au plus tôt que celui noté par l'algorithme. Pour diversifier les solutions, nous construisons grâce à un algorithme énumératif tous les itinéraires validant les arrivées au plus tôt calculé par RAPTOR. Ainsi, nous n'avons plus un itinéraire, mais un grand nombre d'itinéraires candidats.
Pour sélectionner les itinéraires pertinants, nous utilisons un filtre multiobjectif. Nous ne gardons que les solutions non dominées sur le triplet d'objectifs suivant:
- horaire: minimiser l'heure d'arrivé. À heure d'arrivé égale, maximiser l'heure de départ. À heure de départ égale, maximiser le plus petit temps d'attente (pour proposer un itinéraire plus robuste).
- correspondance: minimiser le nombre de correspondance.
- marche: minimiser le temps de marche (incluant le temps de marche dans les correspondances) pénalisé de 2 minutes par correspondance (pour ne pas proposer de prendre un bus pour un arrêt pour gagner quelques secondes de marche à pied).
Ces objectifs permettent de sélectionner des itinéraires crédibles et intéressants.
Faire une énumération exhastive de la sorte n'est pas sans risque. En effet, il peut y avoir plusieurs millions de solutions candidates pour en garder au final moins de 10. Il est donc important de minimiser au maximum le nombre de solutions explorées tout en conservant les solutions optimales. Pour cela, nous avons optimisé la méthode de branchement pour limiter le nombre de solutions explorées. Nous avons également mis en place des bornes pour arrêter l'exploration lorsqu'aucune solution intéressante n'existe dans le sous-espace courant.
Cette nouvelle méthode nous permet de proposer environ 3 fois plus d'alternatives d'itinéraires (bien que ce chiffre soit très variable suivant les cas). Les solutions proposées permettent de mettre en relief le réseau de transport, mettant en avant des solutions proposant différents niveaux de marche à pied.
Les optimisations de temps de calcul permettent d'avoir ces meilleurs résultats dans un temps comparable à l'ancienne version. Certains cas problématiques ont été protégés par des gardes fous.
Certaines alternatives crédibles minimisant la marche à pied sont encore masquées. Des travaux dans cette direction peuvent permettre d'améliorer encore plus la diversité des itinéraires.