Chemins de fer fédéraux suisses (CFF) · Opérateur ferroviaire · équipe de modélisation SIMBA MOBi
Un planificateur d'activités à l'échelle de la ville qui reproduit le microrecensement suisse sur une pile open-source
Un cadre MILP en temps continu construit avec les CFF à l'EPFL, calibré sur 10 110 emplois du temps réels du microrecensement et exécuté de bout en bout sur une population synthétique lausannoise de 46 970 emplois du temps — sans aucun rapiéçage à base de règles
La prévision de la demande de transport dépend de la simulation de ce que de vraies personnes font réellement pendant la journée, quand elles travaillent, font leurs courses, déjeunent, pas seulement du nombre de voitures sur la route. La plupart des modèles opérationnels trichent sur la couche temporelle avec des heuristiques, et perdent toute leur réalisme dès que quelque chose de disruptif se produit.
Nous avons travaillé avec les CFF et l'EPFL pour construire un véritable modèle d'optimisation pour la dimension temporelle. Un programme mixte décide conjointement de l'emploi du temps quotidien complet de chaque personne, calibré sur des données réelles du microrecensement suisse. Le résultat est une simulation à l'échelle de la ville dont les profils d'activité correspondent aux observations empiriques sans aucun rapiéçage heuristique.
Le défi
Les modèles de transport activity-based traditionnels simulent les décisions séquentiellement, quoi faire, puis quand, puis où, puis comment, ce qui les rend aveugles aux arbitrages. Deux activités en concurrence pour la même heure ? Quarante mille personnes essayant de faire la navette et les courses en même temps ? Les modèles séquentiels devinent ; ils n'optimisent pas.
Les CFF avaient besoin d'un cadre suffisamment réaliste pour alimenter l'affectation de trafic dans MATSim, suffisamment rapide pour simuler des emplois du temps complets pour une ville entière, et suffisamment flexible pour absorber des changements de comportement majeurs comme la montée du télétravail.
Notre démarche
Nous avons transformé la couche temporelle en un véritable problème d'optimisation : les heures de début, durées et séquences d'activités de chaque personne sont décidées conjointement par un programme linéaire mixte avec des paramètres d'utilité estimés à partir des données. Les choix non temporels (où, quoi, comment) restent dans les modèles de choix discret existants des CFF et alimentent l'optimiseur comme entrées fixes.
Nous l'avons déployé sur le solveur open-source SCIP via OR-Tools afin que le pipeline opérationnel ne nécessite pas de licence commerciale, et validé contre le microrecensement suisse sur la sous-population des travailleurs à temps plein de Lausanne.
Le résultat
Livrable : un cadre de planification activity-based calibré et validé qui résout les conflits temporels dans les emplois du temps quotidiens via un MILP maximisant l'utilité, construit sur la pile open-source SCIP / OR-Tools (zéro coût de licence pour solveur commercial). Présenté à STRC 2021 en co-rédaction avec les CFF et l'EPFL, dans le cadre de la collaboration CFF × EPFL en modélisation de la demande financée par Innosuisse (projet 2155006680).
Sur une population synthétique lausannoise de 46 970 emplois du temps, les profils d'activité simulés reproduisent toutes les signatures empiriques du microrecensement suisse, pic matinal du travail, creux du déjeuner, fenêtre de loisirs en soirée, structure multi-tour, sans aucun rapiéçage basé sur des règles. Le cadre calibre 64 paramètres comportementaux sur 10 110 emplois du temps réels du microrecensement et atteint ρ̄² = 0,165.
Plongée technique
Le modèle derrière le résultat.
Le modèle
Chaque individu i a un ensemble fixe d'activités A_i à réaliser dans un budget de 24 heures ξ. Le MILP choisit l'heure de début x_a, la durée τ_a, le temps de trajet tt_a vers l'activité suivante, et un indicateur binaire de séquence z_{ab} (= 1 si a est immédiatement suivie de b). L'objectif est l'utilité totale de l'emploi du temps, une somme de pénalités pour s'écarter des heures de début et durées souhaitées, plus une désutilité de temps de trajet.
Utilité totale de l'emploi du temps. Les activités secondaires sont pénalisées individuellement ; les activités primaires et la maison partagent un budget de durée quotidien.
Pénalité de temps linéaire par morceaux autour de l'heure de début souhaitée x_a*. Asymétrique, être en avance peut coûter plus ou moins que d'être en retard.
Pénalité miroir autour de la durée souhaitée τ_a*. Estimée à partir des données du microrecensement par maximum de vraisemblance.
Cohérence de séquence Big-M. Quand z_{ab} = 1, la paire se réduit à l'égalité x_b = x_a + τ_a + tt_a ; sinon les bornes sont inactives.
Le budget temps remplit exactement la journée de 24 heures. Chaque activité (sauf les points limites aube/crépuscule) a exactement un prédécesseur et un successeur.
Les paramètres de flexibilité β^early, β^late, β^short, β^long sont inconnus par type d'activité. Nous les estimons par maximum de vraisemblance : pour chaque emploi du temps observé dans le microrecensement, nous construisons un choice set compétitif, scorons chaque alternative avec l'utilité ci-dessus, et ajustons les paramètres qui rendent l'emploi du temps observé le plus probable sous un modèle logit. Les paramètres alimentent ensuite le même MILP au moment de la simulation.
Benchmark
Paramètres de flexibilité estimés pour des clusters d'activités sélectionnés (significatifs au niveau 5 %).
| Activité / cluster | β^early | β^late | β^short | β^long |
|---|---|---|---|---|
| travail : début matinal | −0,615 | −0,436 | - | - |
| travail : début d'après-midi | −0,406 | 0 | - | - |
| travail : budget de durée quotidien | - | - | −0,022 | 0 |
| loisirs : déjeuner (sous-tour) | −1,610 | −0,821 | −7,550 | −1,360 |
| loisirs : sous-tour du soir | −0,076 | 0 | −3,060 | −0,692 |
| courses : dans un sous-tour | −0,239 | −0,486 | −5,910 | −0,721 |
| maison : après le travail | −0,073 | −0,596 | - | - |
| maison : budget de durée quotidien | - | - | 0 | −0,354 |
Les nombres négatifs sont des pénalités (perte d'utilité par heure d'écart). Le déjeuner est l'activité la plus rigide, tant pour le décalage horaire que pour le non-respect de la durée souhaitée. Le travail du matin a un horaire de début raide ; le travail de l'après-midi est beaucoup plus flexible. La pénalité maison-tard (β^late = −0,596) capture la préférence bien documentée de rentrer à la maison en début de soirée. Échantillon de 10 110 emplois du temps de travailleurs à temps plein nettoyés, ρ̄² = 0,165, log-vraisemblance améliorée de −57 295,58 à −47 847,37 sur 64 paramètres.
Tiré du dossier
Techniques
- Planification d'activités en temps continu
- Programmation linéaire mixte via OR-Tools / SCIP
- Estimation par maximum de vraisemblance des paramètres d'utilité
- Génération d'ensembles de choix (alternatives probables + aléatoires)
- Couplage d'optimisation MILP avec modèles de choix discret séquentiels
Stack
- Python
- OR-Tools
- SCIP
- Biogeme
- Ray (exécution parallèle)
- Intégration MATSim
Un problème de ce type ?