Stage M 2 : Segmentation et simplification du réseau de mobilité urbaine d’une ville pour l’optimisation des trajets à l’aide de graphes H/F

Intégrer Linéact au sein de CESI pour un stage de recherche serait une formidable opportunité de contribuer à des projets innovants, tout en approfondissant mes compétences dans un environnement à la pointe de la transformation numérique et de l’industrie 4.0.

Travaux de Recherche

Sujet de stage résumé

L’objectif de ce stage est de réduire la complexité des graphes multimodaux issus de la modélisation time-expanded afin d’accélérer les algorithmes de planification multimodale exacts et métaheuristiques. Le stagiaire appliquera des méthodes d’analyse de réseaux complexes pour identifier les communautés de nœuds fortement interconnectés (zones cohérentes du réseau urbain), puis en extraire le backbone, c’est-à-dire les nœuds et liens les plus structurants du réseau. Les sous-graphes résultants serviront de support aux algorithmes afin de réduire le temps de calcul tout en maintenant la qualité et la fiabilité des trajets. Les tests seront menés sur Strasbourg et Toulouse avec des données réelles. 

Projet de stage

Contexte scientifique 

Ce stage s’inscrit dans le cadre du programme MobE porté par CESI. Ce programme vise à comprendre et optimiser la mobilité du public étudiant en faveur des économies d’énergie et à engager les établissements d’enseignement supérieur dans une transformation de la mobilité du public étudiant via une approche intégrée d’analyse, d’apports méthodologiques et de diffusion large auprès des étudiants et des établissements d’enseignement supérieur. 

Nous cherchons à réduire l'empreinte carbone des déplacements étudiants tout en proposant des alternatives efficientes basés notamment sur la mobilité douce (marche, vélo, trottinette…) mais aussi tout moyen de mobilité, collectif ou individuel, contribuant à une baisse des émissions de CO2 (tel que les transports en commun ou le covoiturage). 

Le Programme s’articule autour des axes suivants : 

• Analyser et comprendre les leviers motivationnels de mobilité des étudiants puis imaginer les mobilités de demain de manière participative avec plus de 5 000 étudiants 

• Organiser des évènements de proximité sur le sujet de la mobilité dans les établissements d’enseignement supérieur avec des actions de terrain telles que la mise en place d’une communication adaptée au public jeune, de challenges de la mobilité, des challenges des ambassadeurs de mobilité.  

• Accompagner la démarche d’établissements d’enseignement supérieur dans l’optimisation des mobilités étudiantes : 20 établissements impliqués directement pour établir leur diagnostic et 4 à 6 pilotes pour engager des plans de mobilité campus à l’aide des données et outils numériques. 

• Pérenniser l’engagement des établissements d’enseignement supérieur dans la démarche de mobilité économe des étudiants en mettant à disposition l’ensemble de la synthèse, des analyses ainsi que des outils méthodologiques.  

Sujet de stage 

Avec l’essor des systèmes de transport multimodaux et la croissance continue des réseaux de mobilité urbaine, les graphes représentant ces réseaux deviennent extrêmement denses et complexes. Dans le cadre du projet Mon Trajet Vert, la modélisation dite graphe time-expanded permet de représenter finement les événements temporels et les correspondances entre différents modes de transport (piéton, vélo, transports en commun, covoiturage). Cependant, cette représentation engendre des graphes de très grande taille, rendant les algorithmes de planification ou d’optimisation métaheuristique particulièrement coûteux en temps de calcul et en mémoire. 

Afin de pallier ces limitations, ce stage propose d’explorer l’apport des outils d’analyse issus des réseaux complexes pour réduire la taille et la redondance structurelle des graphes multimodaux, tout en préservant leurs propriétés essentielles de connectivité et de fiabilité. Plus précisément, le travail consistera à découper le graphe multimodal en sous-graphes cohérents à l’aide d’algorithmes de détection de communautés (tels que Louvain, Leiden ou Infomap) [1-3], permettant d’isoler des zones urbaines fortement interconnectées. À l’intérieur de chaque sous-graphe, une extraction de backbone [4-7] sera ensuite réalisée afin d’identifier les nœuds et arêtes les plus influents selon diverses mesures de centralité (betweenness, degree, closeness, eigenvector), tout en supprimant les éléments moins pertinents pour la recherche de trajets. 

Le résultat de cette double réduction (communautaire et structurelle) permettra d’obtenir une version allégée du graphe multimodal, qui servira de base à l’exécution des algorithmes exacts et métaheuristiques développés dans le projet. Ces algorithmes visent à générer rapidement des chemins multimodaux optimaux. L’intégration du module de réduction topologique proposé aura pour objectif principal d’accélérer la convergence de ces approches tout en conservant la qualité et la fiabilité des solutions obtenues. L’évaluation se fera sur les graphes multimodaux des villes de Strasbourg et Toulouse, en utilisant les données GTFS. Les métriques d’analyse incluront notamment le temps de calcul moyen par requête ainsi que l’empreinte mémoire. 

À travers ce travail, le stagiaire contribuera à la mise au point d’un cadre méthodologique innovant combinant l’analyse de réseaux complexes et les techniques d’optimisation métaheuristique pour la planification multimodale. Ce cadre ouvre la voie à une planification plus efficace et plus scalable, applicable à plusieurs villes et contextes de mobilité durable. 

Antériorité du sujet dans le laboratoire 

Le laboratoire a développé une modélisation time-expanded et une extension de RAPTOR pour la planification multimodale. Les travaux de Rekia Abdellaoui portent exclusivement sur des algorithmes exacts intégrant les transports publics et les mobilités douces et actives, privées et partagées (vélo, trottinettes). La nouveauté introduite ici réside dans l’usage des outils d’analyse de réseaux complexes pour réduire la taille des graphes multimodaux tout en préservant leur structure essentielle. 

Programme de travail 

Production scientifique/technique attendue

·        E.B : Etude bibliographique

·        C.S : Implémentation du code source du framework avec des tests sur la ville de Strasbourg, puis sur d'autres villes, telles que Rouen, Toulouse, etc.

·        L.R : Rapport de stage

Contexte

Présentation du laboratoire

CESI LINEACT (UR 7527), Laboratoire d'Innovation Numérique pour les Entreprises et les Apprentissages au service de la Compétitivité des Territoires, anticipe et accompagne les mutations technologiques des secteurs et des services liés à l’industrie et au BTP. La proximité historique de CESI avec les entreprises est un élément déterminant pour nos activités de recherche, et a conduit à concentrer les efforts sur une recherche appliquée proche de l’entreprise et en partenariat avec elles. Une approche centrée sur l’humain et couplée à l’utilisation des technologies, ainsi que le maillage territorial et les liens avec la formation, ont permis de construire une recherche transversale ; elle met l’humain, ses besoins et ses usages, au centre de ses problématiques et aborde l’angle technologique au travers de ces apports. 

Sa recherche est organisée selon deux équipes scientifiques interdisciplinaires et plusieurs domaines applicatifs. 

L’équipe 1 "Apprendre et Innover" relève principalement des Sciences cognitives, Sciences sociales et Sciences de gestion, Sciences et techniques de la formation et celles de l’innovation. Les principaux objectifs scientifiques visés sont la compréhension des effets de l'environnement, et plus particulièrement des situations instrumentées par des objets techniques (plateformes, ateliers de prototypage, systèmes immersifs...) sur les processus d'apprentissage, de créativité et d’innovation. 

L’équipe 2 "Ingénierie et Outils Numériques" relève principalement des Sciences du Numérique et de l'Ingénierie. Les principaux objectifs scientifiques portent sur la modélisation, la simulation, l’optimisation et le pilotage de composants, systèmes et processus complexes et des interactions Humains-systèmes dans des systèmes cyber-physiques et jumeaux numériques. 

Ces deux équipes développent et croisent leurs recherches dans les domaines applicatifs de l'Industrie du Futur, de la Ville du Futur et des services numériques, soutenues par des plateformes de recherche, principalement celle de Rouen dédiée à l’Usine du Futur et celles de Nanterre dédiée à l’Usine et au Bâtiment du Futur. 

Ces deux thèmes développent et croisent leurs recherches dans les deux domaines applicatifs de l'Industrie du Futur et de la Ville du Futur, soutenues par des plateformes de recherche, principalement celle de Rouen dédiée à l’Usine du Futur et celles de Nanterre dédiée à l’Usine et au Bâtiment du Futur. 

Positionnement dans les thématiques de recherche du laboratoire

Ce stage s’inscrit dans l’équipe Ingénierie et Outils Numériques du CESI LINEACT, relevant de la modélisation, optimisation et analyse de données pour la Ville du Futur.
Il contribue au développement d’outils d’aide à la décision pour la mobilité durable, en intégrant les méthodes d’analyse de réseaux complexes dans les processus d’optimisation multimodale.

Compétences scientifiques et techniques : 

• Connaissance en théorie des graphes et réseaux complexes.

• Python (NetworkX, iGraph, PyTorch Geometric souhaité).

• Optimisation métaheuristique

Compétences relationnelles :

• Etre autonome, avoir un esprit d’initiative et de curiosité,

• Savoir travailler en équipe et avoir un bon relationnel,

• Etre rigoureux

• Communiquer efficacement avec son encadrant

Gratification à 15% du plafond horaire de la Sécurité Sociale

Date de début : Février 2026

Votre candidature devra comporter :

• Un Curriculum-Vitae ;

• Une lettre de motivation pour le sujet ;

• Notes du parcours (Licence ou autre) et du master en cours ; 

• Lettres de recommandation si disponibles.  

Références 

[1] Khawaja, F. R., Zhang, Z., Memon, Y., & Ullah, A. (2024). Exploring community detection methods and their diverse applications in complex networks: a comprehensive review. Social Network Analysis and Mining, 14(1), 115.

[2] Magnani, M., Hanteer, O., Interdonato, R., Rossi, L., & Tagarelli, A. (2021). Community detection in multiplex networks. ACM Computing Surveys (CSUR), 54(3), 1-35.

[3] Santos, G. G., Lakhotia, K., & De Rose, C. A. (2024, March). Towards a Scalable Parallel Infomap Algorithm for Community Detection. In 2024 32nd Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP) (pp. 116-123). IEEE.

[4] Ghalmane, Z., Brahmia, M. E. A., Zghal, M. (2023). Road networks: A new filtering approach to extract backbones using community structure.

[5] Ghalmane, Z., Cherifi, C., Cherifi, H., & El Hassouni, M. (2021). Extracting modular-based backbones in weighted networks. Information Sciences, 576, 454-474.

[6] Ghalmane, Z., Cherifi, C., Cherifi, H., & El Hassouni, M. (2020). Extracting backbones in weighted modular complex networks. Scientific Reports, 10(1), 15539.

[7] GHALMANE, Z., & Zghal, M. (2023). Road networks: A new filtering approach to extract backbones using community structure.