Stage M 2 : Algorithme heuristique pour la planification multimodale étudiante 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 du stage est de remplacer l’usage exclusif d’algorithmes exacts de type McRAPTOR, trop coûteux en temps de calcul pour un usage opérationnel, par des heuristiques et métaheuristiques capables de produire rapidement des trajets étudiants multimodaux de bonne qualité sur des graphes time-expanded. Le but n’est pas de garantir systématiquement l’optimalité, mais d’obtenir des solutions proches de l’optimum sur plusieurs objectifs (temps de trajet, nombre de transferts, fiabilité, part de mobilité douce) avec un gain marqué en temps de calcul. 

Le travail reposera d’abord sur un découpage du réseau en zones pertinentes afin de restreindre l’exploration aux sous-graphes réellement utiles entre une origine et une destination, en ne conservant que les lignes de transport et les arcs pertinents. À partir de cette réduction, plusieurs familles de méthodes seront développées et testées (recherche locale, Tabou, VNS, PSO, ACO) pour explorer efficacement l’espace des trajets tout en contrôlant le compromis entre rapidité et qualité. 

Les algorithmes seront évalués sur des données réelles de Strasbourg, Toulouse et Lyon, en comparant leurs performances à RAPTOR et McRAPTOR en termes de temps médian par requête, facteur d’accélération et perte relative sur les objectifs. Les méthodes les plus convaincantes seront intégrées dans l’outil Mon Trajet Vert, avec scripts d’expériences et documentation technique pour assurer la reproductibilité 

Projet de stage

Contexte scientifique 

Ce stage s’inscrit dans le cadre du programme Mon Trajet Vert 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 

Le stage vise à concevoir, implémenter et évaluer des heuristiques et métaheuristiques pour accélérer la planification multimodale étudiante sur graphes time-expanded, en s’appuyant sur RAPTOR comme base algorithmique de référence. L’enjeu principal est d’obtenir, pour des réseaux réels de grande taille, des trajets multiobjectifs (temps, transferts, fiabilité, part de mobilité douce) calculés en temps compatible avec un usage opérationnel dans Mon Trajet Vert, tout en maintenant un écart contrôlé avec les solutions exactes fournies par McRAPTOR. 

L’approche reposera sur des stratégies de recherche ciblées qui évitent l’exploration exhaustive du graphe. Dans un premier temps, un découpage spatial du graphe en zones sera mis en place afin de restreindre l’exploration aux sous-ensembles pertinents reliant la zone de départ à la zone d’arrivée et aux lignes associées. Ce découpage initial sera affiné en collaboration avec un autre stage dédié à l’identification automatique de zones pertinentes et de nœuds ou lignes influents du réseau, dont les résultats viendront alimenter les méthodes développées ici. 

Sur cette base, plusieurs types d’algorithmes seront conçus et comparés : recherche locale, Tabou, VNS, PSO, ACO, entre autres. L’objectif est de calibrer ces méthodes pour équilibrer vitesse de calcul, stabilité de la fiabilité et qualité multiobjectif des trajets, tout en maîtrisant la consommation mémoire. 

L’évaluation sera menée sur les réseaux de Strasbourg, Toulouse et Lyon à partir de données GTFS enrichies (événements, transferts piéton et vélo) et de jeux de requêtes dérivés d’emplois du temps étudiants. Les performances seront analysées selon le temps médian par requête, le facteur d’accélération, l’écart aux solutions de référence McRAPTOR sur chaque objectif, la robustesse temporelle et l’empreinte mémoire. 

Les méthodes retenues seront intégrées dans Mon Trajet Vert sous forme de modules réutilisables, accompagnées de scripts d’expériences, de jeux d’essai et d’une documentation technique et expérimentale permettant la reproductibilité et l’extension ultérieure du travail. 

Antériorité du sujet dans le laboratoire : 

Des recherches menées au sein du laboratoire ont produit une modélisation time-expanded et une extension de RAPTOR intégrant la marche, le vélo personnel et le vélo partagé, avec une métrique de fiabilité, appliquées à Strasbourg et Toulouse. Ces travaux, soutenus par un état de l’art complet, constituent la base de l’étude des heuristiques et métaheuristiques. 

À ce jour, aucune exploration systématique des approches heuristiques n’a été menée pour la planification multimodale sur graphes time-expanded. De même, la question de la réduction pertinente de la taille du graphe, par découpage spatial ou filtrage des lignes de transport utiles, reste très peu étudiée dans la littérature. Ces lacunes motivent directement les travaux proposés dans ce stage. 

Programme de travail 

M1 : Mise en place de l’environnement de développement et définition du protocole d’évaluation. Première implémentation du découpage arbitraire du graphe en zones et des structures de données associées. 

M2–M3 : Conception et implémentation des premières heuristiques de planification et méthodes de recherche locale pour la sélection des trajets pertinents. Premières expérimentations et ajustements. 

M3–M4 : Développement et calibration des approches populationnelles (PSO, ILS, VNS, Tabou, colonies de fourmis). Analyse comparative des performances et robustesse. 

M4–M5 : Validation sur petits cas avec solutions exactes issues de RAPTOR pour bornes et vérification de la qualité des résultats. 

M5–M6 : Expérimentations à grande échelle sur Strasbourg, Toulouse et Lyon, analyse des performances, rédaction du rapport et intégration dans Mon Trajet Vert. 

Production scientifique/technique attendue : 

Code reproductible, scripts d’expériences, tableaux et figures de performance, 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. 

Positionnement dans les thématiques de recherche du laboratoire : 

Le sujet relève de l’équipe Ingénierie et Outils Numériques, avec un ancrage en modélisation, optimisation et analyse de données pour systèmes cyber physiques appliqués à la Ville du Futur. La planification multimodale étudiante s’inscrit dans la mobilité durable à l’échelle campus. Le stage contribue au développement d’outils d’aide à la décision, en améliorant la performance des calculs sur graphes time-expanded et en assurant des garanties d’exactitude et de fiabilité, conformément aux objectifs d’une recherche appliquée transférable aux acteurs campus. 

Compétences scientifiques et techniques : 

• Algorithmes et optimisation combinatoire sur graphes 
  Python pour l’optimisation expérimentale 
  Notions de GTFS et graphes temporels 
  Rigueur expérimentale et reproductibilité 

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 

Abdellaoui R., Caillard S., Foucras M., Baudry D. (2025). Multimodal Route Planning Integrating Soft Mobility: A Real-World Case Study for Student Mobility. VEHITS 2025. 
Delling D., Pajor T., Werneck R. F. (2015). Round-Based Public Transit Routing. Transportation Science 49(3):591–604. 
Bast H., Funke S., Matijevic D., Sanders P., Schultes D. (2014). Route Planning in Transportation Networks. MSR-TR-2014-4. 
Dorigo M., Stützle T. (2004). Ant Colony Optimization. MIT Press. 
Kennedy J., Eberhart R. (1995). Particle Swarm Optimization. Proc. IEEE Int. Conf. on Neural Networks. 
Glover F., Laguna M. (1997). Tabu Search. Kluwer. 
Ropke S., Pisinger D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science 40(4):455–472. 
Hoos H., Stützle T. (2004). Stochastic Local Search. Morgan Kaufmann.