Version française Cours doctoraux
- Libellé inconnu,
Cours d'école doctorale : Hanène Mohamed (Modal'X), 1ère partie
Publié le 10 novembre 2020
–
Mis à jour le 26 janvier 2021
Analyse stochastique en temps long de grands systèmes en interaction. L'exemple de systèmes de véhicules en libre service.
Résumé:
Mode écologique de déplacement urbain, les réseaux de véhicules (vélo et auto) en libre partage prennent une importance grandissante dans le développement de modes de transport urbain. L’exploitation de ces systèmes est loin d'être simple, l’un des problèmes les plus cruciaux étant de maintenir les ressources disponibles à l’utilisateur, autant les véhicules que les places libres. Or l’hétérogénéité de la demande ou tout simplement l’aléa déséquilibrent le réseau. Pour pallier cela, il faut bien choisir la taille de la flotte et inciter l’usager à mieux utiliser les ressources disponibles si on veut éviter de relocaliser de manière coûteuse les véhicules. Ainsi, la demande de modèles qualitatifs et quantitatifs est forte de la part des opérateurs publics et privés de ces systèmes pour dimensionner le système et évaluer des politiques incitatives. Ces systèmes peuvent être vus comme de grands réseaux stochastiques, et des modèles et méthodes sont proposés dans ce cadre pour comprendre et analyser le comportement asymptotique de ces grands systèmes, notamment mesurer leur performance à l'équilibre.
Dans ce cours doctoral, je vais présenter deux approches pour l'analyse stochastique de grands systèmes en interaction. La première approche a comme cadre la théorie des files d'attente. En effet, il est remarquable de pouvoir modéliser les systèmes de partage de véhicules par des réseaux de Jackson fermés où les véhicules jouent le rôle de clients (dont le nombre est fixe). Le réseau associé comporte deux types de nœuds: des nœuds à serveur unique décrivant les stations, et des nœuds ayant une infinité de serveurs, représentant les routes entre les stations. Le temps de service y est l’inter-arrivée d’utilisateurs pour les stations, le temps de trajet pour les routes. Dans [1], une analyse détaillée, à l'équilibre, de grands réseaux de Jackson fermés à capacité infinie est proposée. L'application aux systèmes de véhicules en partage à leur stade expérimental précoce dans les années 90 est brièvement examinée. Le comportement asymptotique d'un modèle y introduit est examiné dans [2] quand le nombre de nœuds (stations et routes) est fixe, tandis que le nombre de clients (véhicules) tend vers l'infini. Ces deux articles reposent essentiellement sur la forme produit de la mesure stationnaire explicite d'un tel réseau de Jackson fermé, un résultat standard dans le cas d'une capacité infinie. Néanmoins, cette mesure invariante, bien qu'explicite, exhibe une constante de normalisation dont l'étude asymptotique s'avère lourde. Dans un article plus récent [3], une modélisation plus réaliste des systèmes de véhicules en libre service tenant compte d'une capacité finie des nœuds du réseau est analysée. Il est ainsi démontré, sous des hypothèses légères, que la forme produit de la mesure invariante reste vraie dans ce cas ce qui conduit à l'indépendance asymptotique d’un nombre fini de nœuds, à l'équilibre. Les distributions limites des files d'attente sont ainsi obtenues explicitement.
La seconde approche, plus robuste, est une approche champ-moyen adaptée à des modèles homogènes. Elle nous permettra de nous affranchir de la difficulté d'une étude asymptotique de la constante de normalisation dont dépend la mesure invariante explicite du réseau et nous permettra d'établir le comportement stationnaire de tels grands systèmes en interaction. Je présenterai un article pionnier motivé par les systèmes de vélopartage (Vélib') [4] dans un cadre homogène, un second article [5] dans le même esprit où un modèle hétérogène est étudié via des clusters, ainsi qu'un plus récent [6] motivé par les systèmes d'autopartage où on s'intéresse à l'impact de la possibilité de la réservation de la place (et non de la voiture) sur le comportement asymptotique du système.
[1] G. Fayolle and J.-M. Lasgouttes. Asymptotics and scalings for large product-form networks via the central limit theorem. Markov Process. Related Fields, 2(2):317–348, 1996.
[2] George, D. K. & Xia, C. H. (2010) Asymptotic analysis of closed queueing networks and its implications to achievable service levels. SIGMETRICS Performance Evaluation Review, 38(2):3–5.
[3] Fricker, C. & Tibi, D. (2017). Equivalence of ensembles for large vehicle-sharing models. The Annals of Applied Probability, 27(2), 883-916.
[4] Fricker, C.& Gast, N. (2016). Incentives and redistributions in homogeneous bike-sharing systems with stations of finite capacity. European Journal of Transportation and Logistics, vol. 5, no 3, p. 261-291.
[5] Fricker, C., Gast N.& Mohamed H. (2012). Mean field analysis for inhomogeneous bike sharing systems. In 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymp- totic Methods for the Analysis of Algorithms (AofA’12), Discrete Math. Theor. Comput. Sci. Proc., AQ, pages 365–376.
[6] Bourdais, C., Fricker, C. & Mohamed H. (2020). A mean field analysis of a stochastic model for reservation in car-sharing systems. ACM SIGMETRICS Performance Evaluation Review 48 (2), 18-20
Mode écologique de déplacement urbain, les réseaux de véhicules (vélo et auto) en libre partage prennent une importance grandissante dans le développement de modes de transport urbain. L’exploitation de ces systèmes est loin d'être simple, l’un des problèmes les plus cruciaux étant de maintenir les ressources disponibles à l’utilisateur, autant les véhicules que les places libres. Or l’hétérogénéité de la demande ou tout simplement l’aléa déséquilibrent le réseau. Pour pallier cela, il faut bien choisir la taille de la flotte et inciter l’usager à mieux utiliser les ressources disponibles si on veut éviter de relocaliser de manière coûteuse les véhicules. Ainsi, la demande de modèles qualitatifs et quantitatifs est forte de la part des opérateurs publics et privés de ces systèmes pour dimensionner le système et évaluer des politiques incitatives. Ces systèmes peuvent être vus comme de grands réseaux stochastiques, et des modèles et méthodes sont proposés dans ce cadre pour comprendre et analyser le comportement asymptotique de ces grands systèmes, notamment mesurer leur performance à l'équilibre.
Dans ce cours doctoral, je vais présenter deux approches pour l'analyse stochastique de grands systèmes en interaction. La première approche a comme cadre la théorie des files d'attente. En effet, il est remarquable de pouvoir modéliser les systèmes de partage de véhicules par des réseaux de Jackson fermés où les véhicules jouent le rôle de clients (dont le nombre est fixe). Le réseau associé comporte deux types de nœuds: des nœuds à serveur unique décrivant les stations, et des nœuds ayant une infinité de serveurs, représentant les routes entre les stations. Le temps de service y est l’inter-arrivée d’utilisateurs pour les stations, le temps de trajet pour les routes. Dans [1], une analyse détaillée, à l'équilibre, de grands réseaux de Jackson fermés à capacité infinie est proposée. L'application aux systèmes de véhicules en partage à leur stade expérimental précoce dans les années 90 est brièvement examinée. Le comportement asymptotique d'un modèle y introduit est examiné dans [2] quand le nombre de nœuds (stations et routes) est fixe, tandis que le nombre de clients (véhicules) tend vers l'infini. Ces deux articles reposent essentiellement sur la forme produit de la mesure stationnaire explicite d'un tel réseau de Jackson fermé, un résultat standard dans le cas d'une capacité infinie. Néanmoins, cette mesure invariante, bien qu'explicite, exhibe une constante de normalisation dont l'étude asymptotique s'avère lourde. Dans un article plus récent [3], une modélisation plus réaliste des systèmes de véhicules en libre service tenant compte d'une capacité finie des nœuds du réseau est analysée. Il est ainsi démontré, sous des hypothèses légères, que la forme produit de la mesure invariante reste vraie dans ce cas ce qui conduit à l'indépendance asymptotique d’un nombre fini de nœuds, à l'équilibre. Les distributions limites des files d'attente sont ainsi obtenues explicitement.
La seconde approche, plus robuste, est une approche champ-moyen adaptée à des modèles homogènes. Elle nous permettra de nous affranchir de la difficulté d'une étude asymptotique de la constante de normalisation dont dépend la mesure invariante explicite du réseau et nous permettra d'établir le comportement stationnaire de tels grands systèmes en interaction. Je présenterai un article pionnier motivé par les systèmes de vélopartage (Vélib') [4] dans un cadre homogène, un second article [5] dans le même esprit où un modèle hétérogène est étudié via des clusters, ainsi qu'un plus récent [6] motivé par les systèmes d'autopartage où on s'intéresse à l'impact de la possibilité de la réservation de la place (et non de la voiture) sur le comportement asymptotique du système.
[1] G. Fayolle and J.-M. Lasgouttes. Asymptotics and scalings for large product-form networks via the central limit theorem. Markov Process. Related Fields, 2(2):317–348, 1996.
[2] George, D. K. & Xia, C. H. (2010) Asymptotic analysis of closed queueing networks and its implications to achievable service levels. SIGMETRICS Performance Evaluation Review, 38(2):3–5.
[3] Fricker, C. & Tibi, D. (2017). Equivalence of ensembles for large vehicle-sharing models. The Annals of Applied Probability, 27(2), 883-916.
[4] Fricker, C.& Gast, N. (2016). Incentives and redistributions in homogeneous bike-sharing systems with stations of finite capacity. European Journal of Transportation and Logistics, vol. 5, no 3, p. 261-291.
[5] Fricker, C., Gast N.& Mohamed H. (2012). Mean field analysis for inhomogeneous bike sharing systems. In 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymp- totic Methods for the Analysis of Algorithms (AofA’12), Discrete Math. Theor. Comput. Sci. Proc., AQ, pages 365–376.
[6] Bourdais, C., Fricker, C. & Mohamed H. (2020). A mean field analysis of a stochastic model for reservation in car-sharing systems. ACM SIGMETRICS Performance Evaluation Review 48 (2), 18-20
Mis à jour le 26 janvier 2021