Routage dans les grands réseaux de transports multi-modal – MultiMod

Les activités scientifiques et techniques de MultiMod sont organisées comme suit:

WP1 : Algorithmes pour le moteur multimodal.
Concevoir des algorithmes pour le calcul d'itinéraires dans les réseaux routiers ou de PT offrant un bon compromis entre des objectifs contradictoires : offrir un temps de requête court (nécessitant généralement un long pré-calcul), gérer les événements en temps réel et prendre en compte les préférences des utilisateurs. Envisager le calcul d'itinéraires robustes et alternatifs pour faciliter le réacheminement. Étudier la gestion des connexions pédestres pour accélérer le calcul d'itinéraires multimodaux.

WP2 : Solutions pour combiner le covoiturage avec le réseau PT.
Aborder le calcul d'itinéraires mixtes combinant le covoiturage et le PT en concevant des algorithmes plus rapides tout ameliorant la qualité des solutions. Proposer des compromis entre la satisfaction des conducteurs et des voyageurs. Pour ce faire, envisager différentes solutions de trajets en voiture, du détour court jusqu'au point de rencontre, en passant par des itinéraires optimaux passant par des points de rencontre spécifiés (chemin le plus court contraint). Proposer des méthodes pour filtrer efficacement les offres de covoiturage d'intérêt pour un voyageur en fonction de l'évolution du système. Optimiser le remplissage des véhicules sans pénaliser le conducteur par des détours ou des retards excessifs. Une question difficile est ici de faire face à la volatilité des solutions dans le temps.

WP3 : Compagnon de mobilité. Implémenter les algorithmes conçus dans WP1-2 dans une plate-forme intégrant le covoiturage et le réseau PT.

WP4 : Évaluations. Construire des instances de référence réalistes permettant d'évaluer les algorithmes dans une grande variété de situations et de reproduire des expériences. Définir des métriques appropriées pour mesurer les performances des algorithmes en termes de temps de requête, taille mémoire, qualité des solutions, etc.

Les résultats à T+18 portent sur:
1) Intégration de nouvelles contraintes de connexité pour l’accélération de la resolution du problème du voyageur de commerce. Ce problème est au coeur de toutes les variants des problèmes de tournées de véhicules.
2) Conception d’un simulateur temps-réel pour le problème du transport à la demande (TAD) de personnes. Il s’agit d’optimiser le trajet de véhicules tout en maximisant la satisfaction des usagers.
3) Optimisation de l’algorithme Connexion Scan (CSA) pour le calcul rapide d’itinéraire dans les reseaux PT. Travaux sur une meilleure prise en compte du temps reel dans l’algorithme.
4) Etude de complexité des algorithmes de calcul de chemins alternatifs et des k plus courts chemins dissimilaires. Nous travaillons maintenant à la conception de nouveaux algorithmes pour résoudre ces problèmes tout en incluant des contraintes spécifiques (e.g., vélo électrique versus vélo standard).
5) Conception de méthodes basées sur “Embarassingly Parallel Search” pour l’optimisation multicritères. Résultats préliminaires sur le TSP.
6) Construction d’un benchmark d’instances pour tester les algorithmes.

Au cours de la prochaine période, nous allons poursuivre les travaux en cours sur la conception d’algorithmes, et intensifier l’intégration des algorithmes et la réalisation d’expérimentations. Nous allons aussi accentuer nos efforts sur WP2.

Nicolas Isoart, Jean-Charles Régin. Introduction de contraintes structurelles pour la résolution du problème du voyageur de commerce. JFPC, Jun 2019, Albi, France hal.archives-ouvertes.fr/hal-02160046

Duc-Minh Phan, Laurent Viennot. Fast Public Transit Routing with Unrestricted Walking through Hub Labeling. Special Event on Analysis of Experimental Algorithms (SEA2), Jun 2019, Kalamata, Greece
hal.inria.fr/hal-02161283

Nicolas Isoart, Jean-Charles Régin. An adaptive CP method for TSP solving. [Research Report] Université Côte d’Azur. 2019
hal.archives-ouvertes.fr/hal-02165374

Le projet MultiMod vise à améliorer la mobilité des citoyens dans les zones urbaines en leur proposant, grâce à une interface unique permettant d'exprimer leurs préférences, le moyen de transport le plus pratique pour atteindre leurs destinations. En effet, la participation croissante des acteurs et des autorités au déploiement d'une logistique plus responsable et rentable et des progrès réalisés dans les technologies numériques a permis de créer des synergies dans la création de services innovants pour améliorer la mobilité dans les villes. Cependant, les utilisateurs sont confrontés à un grand nombre de solutions qui coexistent à différentes échelles, fournissant des informations complémentaires pour la mobilité des utilisateurs, mais qui rendent très complexe la recherche de l'itinéraire le plus pratique à un instant. Dans ce contexte, le projet MultiMod souhaite proposer des services contextualisés, en reliant les utilisateurs pour faciliter le transport multimodal et combiner tous les modes disponibles (covoiturage planifié/dynamique, transport public (PT), auto-partage, vélo, etc.).

Nous considérons l'utilisation du covoiturage en zones métropolitaines, donc pour des déplacements courts. Cette utilisation permet des itinéraires qui ne sont pas faisable avec PT, d'accéder à des zones à faible couverture PT en rapprochant les utilisateurs de PT (derniers kilomètres), et d’effectuer plus vite certain déplacements lorsque les itinéraires PT sont trop complexes ou peu réguliers (ex: un bus par heure). Dans ce contexte, l’application doit aider le conducteur et le voyageur autant que possible. En particulier, elle doit proposer le point de rencontre, indiquer la durée du détour au conducteur et indiquer au voyageur comment atteindre ce point de rencontre en utilisant PT. Ici, la vitesse de prise de décision (accord entre conducteur et voyageur) devient un problème critique. Aussi, l’application doit fournir toutes les informations nécessaires pour prendre rapidement une décision (c-à-d. en un seul clic).

En outre, l'ère des Smart City s'accompagne de nombreux concepts émergents, pilotés par des acteurs technologiques innovants, qui permettent l'exploitation de données temps réel (ex: bus en retard, embouteillage) mises à disposition par différents acteurs (ex : communautés dans le cadre de projets Open Data, utilisateurs via leurs terminaux mobiles, autorités de surveillance du trafic). Le projet MultiMod utilisera ces informations pour proposer des itinéraires réalisables au moment de la requête. Nos résultats permettront la conception d'un compagnon de mobilité capable non seulement de guider l'utilisateur tout au long de son voyage, y compris quand et comment changer de moyen de transport, mais aussi de proposer des changements d'itinéraire lorsque celui-ci dépasse un certain seuil. L'originalité principale de MultiMod est d’aborder le problème du calcul d’itinéraires dans les très grands réseaux en combinant PT, covoiturage et données temps réel, et en tenant compte des préférences des utilisateurs. Nos résultats amélioreront sensiblement la vie quotidienne des citoyens.

Notre cible pour valider nos solutions est l'Ile-de-France. En effet, Instant-System développe actuellement la nouvelle application "Vianavigo lab" qui remplacera l'application "Vianavigo" pour le réseau PT d'Ile-de-France. Nos résultats seront donc testés à l'échelle et éventuellement intégrés et déployés dans les serveurs de production et les applications mobiles. Les réseaux de Bordeaux et Nice, plus petits, serviront à effectuer des évaluations préliminaires. En effet, Instant System exploite déjà des applications dans ces villes (Boogi Nice, Boogi Bordeaux).
Une remarque importante: les nouvelles fonctionnalités et algorithmes peuvent être déployés en production tous les 4 mois, ce qui permettra à Instant System d’évaluer en conditions réelles et en continue les résultats de MultiMod. C'est une chance pour maximiser l’impact du projet.