Th
Forum 'Emplois' - Sujet créé le 2013-03-20
Sujet: Modèles et algorithmes pour un guidage optimal des usagers dans les réseaux de transport.
Laboratoire: COSYS-GRETTIA
Spécialité de la thèse: Mathématiques appliquées, Recherche opérationnelle.
Résumé:
Les problèmes de guidage optimal des usagers dans les réseaux de transport connaissent un regain d'intérêt particulier ces dernières années. Cela est dû principalement au développement rapide des nouvelles technologies d'information et de communication (NTIC) appliquées au transport. Ce développement a rendu possible et même nécessaire le développement d'applications informatiques temps-réel mobile et/ou GPS, où des algorithmes adaptatifs donnent des solutions optimales, mises à jours en fonction de l'état du trafic, et avec de meilleures garanties en terme de fiabilité, de robustesse et de risque, comparées aux solutions à priori.
Le guidage optimal dans les réseaux de transport à de variables conditions de trafic est un problème difficile à résoudre à cause de la nature stochastique du temps de parcours sur les liens du réseau. Les décisions des usagers reflètent leurs attitudes envers le risque. Un usager peut : 1) choisir un chemin court en moyenne (minimiser l'espérance du temps de parcours), 2) choisir un chemin fiable (minimiser la variance du temps de parcours, par exemple), 3) choisir un chemin robuste (un chemin dont le temps de parcours est peu sensible à des perturbations, et résiste à la détérioration de l'état du trafic sur le réseau), et 4) choisir un chemin "flexible" (un chemin qui admet des détours à temps de parcours acceptables, en cas d'événements imprévus comme des accidents, des travaux, etc.)
Une des formulations classiques du problème de guidage optimal est celle du Least Expected Time (LET) (Loui 1983). Plusieurs algorithmes efficaces ont été proposés pour résoudre cette formulation (Fu and Rilett 1998, Miller-Hooks and Mahmassani 2000, Waller and Ziliaskopoulos 2002). Cependant, dans plusieurs configurations, les solutions LET ne sont pas garanties d'être fiables. Une définition intéressante d'un chemin optimal fiable (stochastic on time arrival: SOTA) a été donnée par Frank (Frank 1969). Cette formulation a permis l'obtention de solutions adaptables satisfaisantes en terme de fiabilité. On cite notamment les travaux basés sur le contrôle optimal et la programmation dynamique stochastiques (Fan and Nie 2006). Plusieurs algorithmes sous la forme SOTA ont été récemment proposés par Samaranayake et al. (2011), ainsi que des résultats expérimentaux utilisant des données du projet Millennium.
L'objet de la thèse est d'explorer le problème du guidage optimal dans les réseaux de transport sous ses différents aspects (fiabilité, robustesse, risque, etc.), dans le but de proposer des modèles et algorithmes adéquats, pouvant donner suite au développement d'applications informatiques utilisables par les usagers. Nous proposons d'explorer plus particulièrement les approches basées sur le contrôle optimal et la programmation dynamique stochastiques.
Le déroulement du travail de thèse est le suivant:
• Analyse bibliographique,
• Sélection et recherche de modèles de trafic adéquats aux problèmes du
guidage optimal des usagers,
• Proposition d'algorithmes efficaces de guidage optimal,
• Implémentation, tests, et validation.
Références:
1. S. Samaranayake, S. Blandin, A.Bayen, A tractable class of algorithms for reliable routing in stochastic networks, Transportation Research Part C, 2011.
2. Fan, Y., Nie, Y. Optimal routing for maximizing travel time reliability. Networks and Spatial Economics 3 (6), 333–344. 2006.
3. Chancelier, J-P. De Lara, M. De Palma, A. Risk aversion, road choice, and the one-armed bandit problem. in Transportation science. Vol. 41, No. 1. 2007.
4. E. Crisostomi, S. Kirkland, R. Shorten, Robust and risk-averse routing algorithms in road networks. 18th IFAC World Congress. 2011.
5. Maaike Snelder, Designing Robust Road Networks. A general design method applied to the Netherlands, PhD thesis, Netherlands TRAIL Research School, 2010.
6. Hofleitner, R. Herring and A. Bayen, Probability distributions of travel times on arterial networks: a traffic flow and horizontal queuing theory approach, TRB 2012.
7. Miller-Hooks, E., Mahmassani, H. Least expected time paths in stochastic, time-varying transportation networks. Transportation Science 34 (2), 198–215. 2000.
8. Fu, L., Rilett, L., 1998. Expected shortest paths in dynamic and stochastic traffic networks. Transportation Research Part B 32 (7), 499–516.
9. Loui, R., Optimal paths in graphs with stochastic or multidimensional weights. Communications of the ACM. 26 (9), 670–676. 1983.
10. Waller, S., Ziliaskopoulos, A. On the online shortest path problem with limited arc cost dependencies. Networks 40 (4), 216–227. 2002.
11. Frank, H. Shortest paths in probabilistic graphs. Operations Research 17, 583–599. 1969.
12. Bertsekas, D. Dynamic Programming and Optimal Control. Athena Scientific. 2005.
Mots-clefs : Guidage adaptatif, guidage stochastique, choix de route,
affectation du trafic, fiabilité, risque, robustesse.
Contact FARHI Nadir e-mail: nadir.farhi@ifsttar.fr
Laboratoire: COSYS-GRETTIA
Spécialité de la thèse: Mathématiques appliquées, Recherche opérationnelle.
Résumé:
Les problèmes de guidage optimal des usagers dans les réseaux de transport connaissent un regain d'intérêt particulier ces dernières années. Cela est dû principalement au développement rapide des nouvelles technologies d'information et de communication (NTIC) appliquées au transport. Ce développement a rendu possible et même nécessaire le développement d'applications informatiques temps-réel mobile et/ou GPS, où des algorithmes adaptatifs donnent des solutions optimales, mises à jours en fonction de l'état du trafic, et avec de meilleures garanties en terme de fiabilité, de robustesse et de risque, comparées aux solutions à priori.
Le guidage optimal dans les réseaux de transport à de variables conditions de trafic est un problème difficile à résoudre à cause de la nature stochastique du temps de parcours sur les liens du réseau. Les décisions des usagers reflètent leurs attitudes envers le risque. Un usager peut : 1) choisir un chemin court en moyenne (minimiser l'espérance du temps de parcours), 2) choisir un chemin fiable (minimiser la variance du temps de parcours, par exemple), 3) choisir un chemin robuste (un chemin dont le temps de parcours est peu sensible à des perturbations, et résiste à la détérioration de l'état du trafic sur le réseau), et 4) choisir un chemin "flexible" (un chemin qui admet des détours à temps de parcours acceptables, en cas d'événements imprévus comme des accidents, des travaux, etc.)
Une des formulations classiques du problème de guidage optimal est celle du Least Expected Time (LET) (Loui 1983). Plusieurs algorithmes efficaces ont été proposés pour résoudre cette formulation (Fu and Rilett 1998, Miller-Hooks and Mahmassani 2000, Waller and Ziliaskopoulos 2002). Cependant, dans plusieurs configurations, les solutions LET ne sont pas garanties d'être fiables. Une définition intéressante d'un chemin optimal fiable (stochastic on time arrival: SOTA) a été donnée par Frank (Frank 1969). Cette formulation a permis l'obtention de solutions adaptables satisfaisantes en terme de fiabilité. On cite notamment les travaux basés sur le contrôle optimal et la programmation dynamique stochastiques (Fan and Nie 2006). Plusieurs algorithmes sous la forme SOTA ont été récemment proposés par Samaranayake et al. (2011), ainsi que des résultats expérimentaux utilisant des données du projet Millennium.
L'objet de la thèse est d'explorer le problème du guidage optimal dans les réseaux de transport sous ses différents aspects (fiabilité, robustesse, risque, etc.), dans le but de proposer des modèles et algorithmes adéquats, pouvant donner suite au développement d'applications informatiques utilisables par les usagers. Nous proposons d'explorer plus particulièrement les approches basées sur le contrôle optimal et la programmation dynamique stochastiques.
Le déroulement du travail de thèse est le suivant:
• Analyse bibliographique,
• Sélection et recherche de modèles de trafic adéquats aux problèmes du
guidage optimal des usagers,
• Proposition d'algorithmes efficaces de guidage optimal,
• Implémentation, tests, et validation.
Références:
1. S. Samaranayake, S. Blandin, A.Bayen, A tractable class of algorithms for reliable routing in stochastic networks, Transportation Research Part C, 2011.
2. Fan, Y., Nie, Y. Optimal routing for maximizing travel time reliability. Networks and Spatial Economics 3 (6), 333–344. 2006.
3. Chancelier, J-P. De Lara, M. De Palma, A. Risk aversion, road choice, and the one-armed bandit problem. in Transportation science. Vol. 41, No. 1. 2007.
4. E. Crisostomi, S. Kirkland, R. Shorten, Robust and risk-averse routing algorithms in road networks. 18th IFAC World Congress. 2011.
5. Maaike Snelder, Designing Robust Road Networks. A general design method applied to the Netherlands, PhD thesis, Netherlands TRAIL Research School, 2010.
6. Hofleitner, R. Herring and A. Bayen, Probability distributions of travel times on arterial networks: a traffic flow and horizontal queuing theory approach, TRB 2012.
7. Miller-Hooks, E., Mahmassani, H. Least expected time paths in stochastic, time-varying transportation networks. Transportation Science 34 (2), 198–215. 2000.
8. Fu, L., Rilett, L., 1998. Expected shortest paths in dynamic and stochastic traffic networks. Transportation Research Part B 32 (7), 499–516.
9. Loui, R., Optimal paths in graphs with stochastic or multidimensional weights. Communications of the ACM. 26 (9), 670–676. 1983.
10. Waller, S., Ziliaskopoulos, A. On the online shortest path problem with limited arc cost dependencies. Networks 40 (4), 216–227. 2002.
11. Frank, H. Shortest paths in probabilistic graphs. Operations Research 17, 583–599. 1969.
12. Bertsekas, D. Dynamic Programming and Optimal Control. Athena Scientific. 2005.
Mots-clefs : Guidage adaptatif, guidage stochastique, choix de route,
affectation du trafic, fiabilité, risque, robustesse.
Contact FARHI Nadir e-mail: nadir.farhi@ifsttar.fr