offre-th
Forum 'Emplois' - Sujet créé le 2007-09-17
Appel d'offre à candidature pour bourse de thèse en RO: à diffuser auprès des étudiants intéressés.
Sujet de thèse Bourse LIMOS Ministère, 3ans, UMR CNRS 6158.
Titre: Modèles de flots temporisés et application à la conception d'outils décisionnel pour des systèmes réactifs d'aide à la mobilité.
Responsables de la Thèse: Alain QUILLIOT, PR, Philippe LACOMME, MC 27,
alain.quilliot@isima.fr, 04 73 40 50 04
Nom du Directeur d'Unité : Alain QUILLIOT
Financement: Bourse sur 3 ans du Ministère de la Recherche
Début: 1° Novembre 2007
Descriptif du Sujet.
I. Contexte Général.
Le projet qui est proposé contient une partie fondamentale et une partie appliquée. La partie fondamentale, qui renvoie à un projet ANR en phase de démarrage, concerne des modèles de flots temporisés qui visent à permettre de gérer simultanément ordonnancement et affectation de ressource dans des problèmes de planification ou de synthèse de réseaux. La partie appliquée concerne le pilotage en temps réel ou légèrement différé de flottes de transports flexibles. Il relève de ce que l'on nommera "Recherche Opérationnelle Embarquée", soit de l'application de méthodes algorithmiques fine à la gestion de systèmes fortement mobiles. Le projet s'inscrit, à ce niveau appliqué, dans un des projets de la Fédération de Recherche T.I.M.S : Technologies de l'Information, de la Mobilité et de la Sûreté, FR CNRS 2856, sur l'Ingéniérie de la Mobilité.
Le LIMOS dispose de compétences en Recherche Opérationnelle, (méthodes polyédrales, synthèse de réseaux, ordonnancement et Simulation), ainsi que dans le domaine des systèmes embarqués, et évolue dans un environnement régional (Fédération TIMS, partenariat avec le CEMAGREF) préoccupé par les problèmes liés à l'Ingénierie de la Mobilité. Ce projet combine ces savoir-faire selon une forme de pluridisciplinarité.
II. La Problématique Applicative de la Mobilité Réactive.
On s'intéresse ici à la perspective de nouveaux services de transport (fret, personnes ciblées, desserte de zones rurales, sites dédiés, véhicules autonomes), pilotés de façon à réagir à une demande fluctuante dans le temps, selon une logique qui combine service individualisé et mutualisation (minibus, navettes, ...). On pourra se référer, à tire indicatif, aux problématique dites du Dial for Ride et du Half Truck Load.
Le projet dont il est question ici porte dès lors sur la conception d'outils informatique pour le suivi et de contrôle en temps réel d'une flotte de véhicules, son mode de supervision et son mode de communication avec l'usager cible. Ces outils vont mettre en jeu des techniques de communication mobile, sur lesquelles s'appuiera un noyau décisionnel proprement dit, c'est à dire un ensemble de procédures qui effectueront le routage des véhicules et l'affectation des demandes sur ces véhicules en vue d'une bonne mutualisation de la ressource véhicule entre ces demandes. Ce projet, qui inclut une forme de pluridisciplinarité, relève dès lors de ce que l'on peut considérer comme de la Recherche Opérationnelle Embarquée.
II.1. Le suivi et le contrôle de la flotte en temps réel.
Deux modes de fonctionnement principaux sont à envisager:
* Un mode de fonctionnement supervisé: l'usager communique avec un superviseur, par téléphone (signal parlé) ou via une borne (signal tactile). Ce superviseur, qui dispose d'une vision sur l'état du système refuse ou accepte la demande. Dans ce dernier cas, il peut commander le déroutage d'un des véhicules, un calcul de synchronisation, et une évaluation de la fenêtre de temps qui verra la transaction s'effectuer. Puis il transmet sa proposition aux véhicules concernés et au demandeur.
* Un mode de fonctionnement non supervisé: l'usager communique avec l'ensemble des véhicules, ou, si l'on envisage un filtrage, avec ceux qui se trouvent à un certain niveau de proximité de lui. Ceux-ci se concertent alors avant de lui transmettre une réponse.
Dans tous les deux cas, doivent être analysés:
* La nature des dispositifs de communication, et de calcul embarqués sur les véhicules;
* La nature des dispositifs de communication et de calcul qui sont centralisés;
* La nature de l'intervention humaine par rapport à ces dispositifs;
* Les délais de réponse imposés à l'ensemble, suivant l'origine des demandes.
II.2. Le Décisionnel et son Evaluation.
A un instant donné t, certains parmi les véhicules sont à l'arrêt, et localisés en différents points du réseau de transit, et d'autres sont en circulation, engagés sur différents parcours et porteurs de charges. Un paquet de demandes de transports est alors formulé. Chacune de ces demandes est synthétisée par un couple (o, d) de points origine/destination, et par une estimation des dates de départ et d'arrivée souhaitées par le demandeur.
La décision à prendre porte alors sur deux points:
* La prise en compte des différentes demandes: il faut de décider si une demande est acceptée ou non, et, dans le cas positif, quels véhicules s'en acquittent, modulo quelles modification de leur parcours courant et selon quels mécanismes de synchronisation.
* Le repositionnement des véhicules oisifs.
L'évaluation des solutions proposées, en termes économique et en termes de qualité du service offert, passe alors par la simulation à évènements discrets.
III. Les Points Fondamentaux de l'Etude.
III.1. L'Algorithmique du Routage Dynamique et de l'Allocation de Charges.
Le premier niveau de décision évoqué ci-dessus, c'est à dire celui de prise en compte des différentes demandes, est essentiellement combinatoire. Le point dur consiste à concilier qualité de service (vitesse /fiabilité de l'acheminement, respect des contraintes temporelles), avec un impératif de mutualisation.
Le deuxième niveau de décision, c'est à dire celui du repositionnement des véhicules oisifs, est de nature probabiliste et multicritère: pour une distribution de la demande dans le temps et l'espace de la demande, il faut chercher à replacer les véhicules qui ne sont pas en trajectoire actives et qui sont néanmoins en service de façon à les rapprocher de la demande prévisible.
La réponse à ces problèmes de décision doit être dans tous les cas fournie de façon rapide, ce terme pouvant se décliner de façon plus ou moins exigeante suivant le contexte.
Une analyse statique du problème conduit à introduire une notion de Flot et Multiflot Temporises et à travailler sur un modèle type CFA: Capacitated Flow Assignment, qui met en jeu un multiflot flot véhicule F et un multiflot routage f, couplés par une contrainte de capacité et contraints par des contraintes temporelles:
{ Trouver, dans le réseau G, un multiflot (entier) F et un multiflot (fractionnaire) f, tels que:
F domine f en un certain sens (capacités); (* Contraintes de Couplage*)
F et f sont temporisables de façon à définir des déplacements compatibles avec les contraintes de fenêtre de temps; (*Contraintes Temporelles*)
F et f minimisent un coût C(F) (coût d'infrastructure) + P(f) (coût de Qualité des routages)}.
Cette classe de modèle est apparue très régulièrement dans les applications de la Recherche Opérationnelle aux Télécommunications (problèmes de dimensionnement et de routage). Ce qui constitue ici un élément nouveau et fortement complexifiant est la présence des contraintes temporelles, qui font se rapprocher ce formalisme de type CFA caractéristique des modèles de Synthèse de Réseaux des modèles de conception de tournées ou d'ordonnancements. L'intérêt de ce type de modèle est qu'il permet de se raccrocher aux outils hérités du formalisme PLNE, soulevant dès lors plusieurs questions théoriques :
- caractérisation des contraintes (coupes polyédrales) sur l'objet principal F qui permettront d'éliminer les contraintes temporelles;
- définition de mécanismes d'agrégation et de coupes qui permettront de remplacer les composants des différents multiflots par des objets flots ou multiflots agrégés).
L'analyse dynamique du problème consiste à tenir du compte du fait que les demandes de routage arrivent à la volée, requérant des réponses en temps réel ou légèrement différé. Les règles de décision induites doivent alors dériver de l'analyse effectuée au niveau statique.
III.2. L'Evaluation des Performances du Noyau Décisionnel.
L'évaluation des solutions proposées pour le problème décisionnel passe donc par la simulation à évènements discrets, s'appuyant sur:
- une représentation probabiliste des demandes, dans le temps et dans l'espace ;
- une représentation de l'état du système ;
- la description des procédures décisionnelles objet de l'évaluation.
On évaluera le système en considérant qu'il fonctionne en mode supervisé et en posant des hypothèses sur les délais moyens de communication, puis en prenant en compte:
- le mode de fonctionnement du système (supervisé, non supervisé);
- le détail des protocoles de communications entre usager, véhicules et superviseur.
III.3. L'Analyse des Modes de Communication et de Supervision Adaptés à une Mise en Œuvre Opérationnelle.
Il s'agit dès lors d'identifier, parmi les dispositifs de communication mobile inter-véhicules, véhicules/usagers et usagers/superviseur, actuellement disponibles, quels sont ceux qui sont les mieux adaptés à la mise en œuvre opérationnelle du noyau décisionnel évoqué en III.1, et le mode de supervision qui en découle : la réponse à ces questions dépendra en grande partie du contexte applicatif, et des échelles de temps et d'espace par rapport auxquelles s'inscrit le système considéré (échelle géographique, niveau de réactivité).
IV. Le Plan de Travail de l'Etudiant.
Le travail de l'étudiant se focalisera principalement sur la conception et l'évaluation du noyau décisionnel et sur son articulation avec des hypothèses et un contexte de communication mobile donné. Plus précisément :
1° partie : 6 mois.
Seront étudiées (études « bibliographique »), les systèmes existants ou récemment expérimentés (Telebus à BERLIN, repositionnement des ambulances à MONTREAL...), ainsi que les travaux déjà réalisés au plan académique sur le Dial for Ride et le Half Truck Load (CRT et GERAD MONTREAL, Centre des Transports à LISBONNE,
Sujet de thèse Bourse LIMOS Ministère, 3ans, UMR CNRS 6158.
Titre: Modèles de flots temporisés et application à la conception d'outils décisionnel pour des systèmes réactifs d'aide à la mobilité.
Responsables de la Thèse: Alain QUILLIOT, PR, Philippe LACOMME, MC 27,
alain.quilliot@isima.fr, 04 73 40 50 04
Nom du Directeur d'Unité : Alain QUILLIOT
Financement: Bourse sur 3 ans du Ministère de la Recherche
Début: 1° Novembre 2007
Descriptif du Sujet.
I. Contexte Général.
Le projet qui est proposé contient une partie fondamentale et une partie appliquée. La partie fondamentale, qui renvoie à un projet ANR en phase de démarrage, concerne des modèles de flots temporisés qui visent à permettre de gérer simultanément ordonnancement et affectation de ressource dans des problèmes de planification ou de synthèse de réseaux. La partie appliquée concerne le pilotage en temps réel ou légèrement différé de flottes de transports flexibles. Il relève de ce que l'on nommera "Recherche Opérationnelle Embarquée", soit de l'application de méthodes algorithmiques fine à la gestion de systèmes fortement mobiles. Le projet s'inscrit, à ce niveau appliqué, dans un des projets de la Fédération de Recherche T.I.M.S : Technologies de l'Information, de la Mobilité et de la Sûreté, FR CNRS 2856, sur l'Ingéniérie de la Mobilité.
Le LIMOS dispose de compétences en Recherche Opérationnelle, (méthodes polyédrales, synthèse de réseaux, ordonnancement et Simulation), ainsi que dans le domaine des systèmes embarqués, et évolue dans un environnement régional (Fédération TIMS, partenariat avec le CEMAGREF) préoccupé par les problèmes liés à l'Ingénierie de la Mobilité. Ce projet combine ces savoir-faire selon une forme de pluridisciplinarité.
II. La Problématique Applicative de la Mobilité Réactive.
On s'intéresse ici à la perspective de nouveaux services de transport (fret, personnes ciblées, desserte de zones rurales, sites dédiés, véhicules autonomes), pilotés de façon à réagir à une demande fluctuante dans le temps, selon une logique qui combine service individualisé et mutualisation (minibus, navettes, ...). On pourra se référer, à tire indicatif, aux problématique dites du Dial for Ride et du Half Truck Load.
Le projet dont il est question ici porte dès lors sur la conception d'outils informatique pour le suivi et de contrôle en temps réel d'une flotte de véhicules, son mode de supervision et son mode de communication avec l'usager cible. Ces outils vont mettre en jeu des techniques de communication mobile, sur lesquelles s'appuiera un noyau décisionnel proprement dit, c'est à dire un ensemble de procédures qui effectueront le routage des véhicules et l'affectation des demandes sur ces véhicules en vue d'une bonne mutualisation de la ressource véhicule entre ces demandes. Ce projet, qui inclut une forme de pluridisciplinarité, relève dès lors de ce que l'on peut considérer comme de la Recherche Opérationnelle Embarquée.
II.1. Le suivi et le contrôle de la flotte en temps réel.
Deux modes de fonctionnement principaux sont à envisager:
* Un mode de fonctionnement supervisé: l'usager communique avec un superviseur, par téléphone (signal parlé) ou via une borne (signal tactile). Ce superviseur, qui dispose d'une vision sur l'état du système refuse ou accepte la demande. Dans ce dernier cas, il peut commander le déroutage d'un des véhicules, un calcul de synchronisation, et une évaluation de la fenêtre de temps qui verra la transaction s'effectuer. Puis il transmet sa proposition aux véhicules concernés et au demandeur.
* Un mode de fonctionnement non supervisé: l'usager communique avec l'ensemble des véhicules, ou, si l'on envisage un filtrage, avec ceux qui se trouvent à un certain niveau de proximité de lui. Ceux-ci se concertent alors avant de lui transmettre une réponse.
Dans tous les deux cas, doivent être analysés:
* La nature des dispositifs de communication, et de calcul embarqués sur les véhicules;
* La nature des dispositifs de communication et de calcul qui sont centralisés;
* La nature de l'intervention humaine par rapport à ces dispositifs;
* Les délais de réponse imposés à l'ensemble, suivant l'origine des demandes.
II.2. Le Décisionnel et son Evaluation.
A un instant donné t, certains parmi les véhicules sont à l'arrêt, et localisés en différents points du réseau de transit, et d'autres sont en circulation, engagés sur différents parcours et porteurs de charges. Un paquet de demandes de transports est alors formulé. Chacune de ces demandes est synthétisée par un couple (o, d) de points origine/destination, et par une estimation des dates de départ et d'arrivée souhaitées par le demandeur.
La décision à prendre porte alors sur deux points:
* La prise en compte des différentes demandes: il faut de décider si une demande est acceptée ou non, et, dans le cas positif, quels véhicules s'en acquittent, modulo quelles modification de leur parcours courant et selon quels mécanismes de synchronisation.
* Le repositionnement des véhicules oisifs.
L'évaluation des solutions proposées, en termes économique et en termes de qualité du service offert, passe alors par la simulation à évènements discrets.
III. Les Points Fondamentaux de l'Etude.
III.1. L'Algorithmique du Routage Dynamique et de l'Allocation de Charges.
Le premier niveau de décision évoqué ci-dessus, c'est à dire celui de prise en compte des différentes demandes, est essentiellement combinatoire. Le point dur consiste à concilier qualité de service (vitesse /fiabilité de l'acheminement, respect des contraintes temporelles), avec un impératif de mutualisation.
Le deuxième niveau de décision, c'est à dire celui du repositionnement des véhicules oisifs, est de nature probabiliste et multicritère: pour une distribution de la demande dans le temps et l'espace de la demande, il faut chercher à replacer les véhicules qui ne sont pas en trajectoire actives et qui sont néanmoins en service de façon à les rapprocher de la demande prévisible.
La réponse à ces problèmes de décision doit être dans tous les cas fournie de façon rapide, ce terme pouvant se décliner de façon plus ou moins exigeante suivant le contexte.
Une analyse statique du problème conduit à introduire une notion de Flot et Multiflot Temporises et à travailler sur un modèle type CFA: Capacitated Flow Assignment, qui met en jeu un multiflot flot véhicule F et un multiflot routage f, couplés par une contrainte de capacité et contraints par des contraintes temporelles:
{ Trouver, dans le réseau G, un multiflot (entier) F et un multiflot (fractionnaire) f, tels que:
F domine f en un certain sens (capacités); (* Contraintes de Couplage*)
F et f sont temporisables de façon à définir des déplacements compatibles avec les contraintes de fenêtre de temps; (*Contraintes Temporelles*)
F et f minimisent un coût C(F) (coût d'infrastructure) + P(f) (coût de Qualité des routages)}.
Cette classe de modèle est apparue très régulièrement dans les applications de la Recherche Opérationnelle aux Télécommunications (problèmes de dimensionnement et de routage). Ce qui constitue ici un élément nouveau et fortement complexifiant est la présence des contraintes temporelles, qui font se rapprocher ce formalisme de type CFA caractéristique des modèles de Synthèse de Réseaux des modèles de conception de tournées ou d'ordonnancements. L'intérêt de ce type de modèle est qu'il permet de se raccrocher aux outils hérités du formalisme PLNE, soulevant dès lors plusieurs questions théoriques :
- caractérisation des contraintes (coupes polyédrales) sur l'objet principal F qui permettront d'éliminer les contraintes temporelles;
- définition de mécanismes d'agrégation et de coupes qui permettront de remplacer les composants des différents multiflots par des objets flots ou multiflots agrégés).
L'analyse dynamique du problème consiste à tenir du compte du fait que les demandes de routage arrivent à la volée, requérant des réponses en temps réel ou légèrement différé. Les règles de décision induites doivent alors dériver de l'analyse effectuée au niveau statique.
III.2. L'Evaluation des Performances du Noyau Décisionnel.
L'évaluation des solutions proposées pour le problème décisionnel passe donc par la simulation à évènements discrets, s'appuyant sur:
- une représentation probabiliste des demandes, dans le temps et dans l'espace ;
- une représentation de l'état du système ;
- la description des procédures décisionnelles objet de l'évaluation.
On évaluera le système en considérant qu'il fonctionne en mode supervisé et en posant des hypothèses sur les délais moyens de communication, puis en prenant en compte:
- le mode de fonctionnement du système (supervisé, non supervisé);
- le détail des protocoles de communications entre usager, véhicules et superviseur.
III.3. L'Analyse des Modes de Communication et de Supervision Adaptés à une Mise en Œuvre Opérationnelle.
Il s'agit dès lors d'identifier, parmi les dispositifs de communication mobile inter-véhicules, véhicules/usagers et usagers/superviseur, actuellement disponibles, quels sont ceux qui sont les mieux adaptés à la mise en œuvre opérationnelle du noyau décisionnel évoqué en III.1, et le mode de supervision qui en découle : la réponse à ces questions dépendra en grande partie du contexte applicatif, et des échelles de temps et d'espace par rapport auxquelles s'inscrit le système considéré (échelle géographique, niveau de réactivité).
IV. Le Plan de Travail de l'Etudiant.
Le travail de l'étudiant se focalisera principalement sur la conception et l'évaluation du noyau décisionnel et sur son articulation avec des hypothèses et un contexte de communication mobile donné. Plus précisément :
1° partie : 6 mois.
Seront étudiées (études « bibliographique »), les systèmes existants ou récemment expérimentés (Telebus à BERLIN, repositionnement des ambulances à MONTREAL...), ainsi que les travaux déjà réalisés au plan académique sur le Dial for Ride et le Half Truck Load (CRT et GERAD MONTREAL, Centre des Transports à LISBONNE,