Stage M 2 : Algorithme heuristique pour la planification multimodale étudiante 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 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…

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.

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.