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 CESI

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…

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.

CESI est une école d'ingénieurs qui fait de la promotion sociale par l'excellence un modèle de réussite. Rejoignez un environnement stimulant où l'esprit d'équipe, la diversité des projets et l'autonomie ne font qu'un. Découvrez une école qui a su développer un modèle unique et se donne les moyens au quotidien de relever les grands défis de l'époque. Nos 25 campus, 28 000 étudiants, 8000 entreprises partenaires et 106 000 alumni témoignent de l'impact de CESI au niveau national.

CESI accompagne ses étudiants en utilisant des méthodes innovantes de pédagogie active. L'établissement forme avec rigueur les futurs ingénieurs, techniciens et managers, dans les secteurs suivants : l'Industrie & l'Innovation, le BTP, l'Informatique et le Numérique et le Développement Durable. Parallèlement, CESI concrétise son engagement dans la Recherche à travers des activités menées au sein de son Laboratoire d'Innovation Numérique, CESI LINEACT.

Les partenariats établis avec 130 universités à travers le globe, attestent de l'engagement international de CESI. Ces liens privilégiés offrent aux élèves ingénieurs une mobilité sortante et entrante à l'échelle internationale, façonnée notamment par des stages obligatoires faisant partie intégrante de leur cursus.