Proposition de thèse 2009 - Habbas, Khadraoui

Lita

Description

Sujet de thèse proposé par Zineb Habbas et Djamel Khadraoui I) Intitulé du sujet : Contribution à la résolution des problèmes de robustesse dans les réseaux dynamiques multi-modaux et multi-objectifs. II) Unité de recherche : Laboratoire LITA-UFR-MIM, Université Paul Verlaine-Metz Équipe d'accueil : Algorithmes et optimisation III) Domaine scientifique principal de la thèse : Le domaine scientifique est celui d'algorithmes de plus courts chemins dans les graphes dynamiques, l'optimisation multi-objectif, l'optimisation combinatoire, la théorie des graphes, les algorithmes de chemins robustes. IV) Domaine scientifique secondaire : Le domaine secondaire couvre les aspects d'algorithmique parallèle ou distribuée, les politiques de transports, la multi-modalité et l'aspect temps réel. V) Nom, prénoms et couriels du Directeur de thèse Directeur Zineb Habbas e-mail [e-mail] Co-encadrant Djamel Khadraoui e-mail [e-mail] VI) Sujet de thèse : VI.1) Contexte de travail Le problème de plus court chemin est un problème très classique en théorie des graphes. L'algorithme le plus répandu pour le résoudre est celui de Dijkstra. Cet algorithme suppose que les arêtes sont pondérées par des valeurs positives ou nulles. Il existe aussi toute une variante d'algorithmes calculant les plus courts chemins partant de n'importe quel noeud s à n'importe quel noeud d ou d'un noeud s à tout noeud. Certains ...

Informations

• Publié par: Abbu
• Nombre de lectures: 61
• Langue: Français

Extrait

      Sujet de thèse proposé par Zineb Habbas et Djamel Khadraoui     I) Intitulé du sujet : problèmes de robustesse dans les réseauxContribution à la résolution des dynamiques multi-modaux et multi-objectifs.       I É I q ) u   i U pe n   i d t 'a é de recherch h e m : P ét lualreVenia-MFR, IMivUnsier-Metz    noitt  eessamitiop aL -UTALIe irtorabo ccueil : Algorit     III) Domaine scientifique principal de la thèse :Le domaine scientifique est celui d'algorithmes de plus courts chemins dans les graphes dynamiques, l'optimisation multi-objectif, l'optimisation combinatoire, la théorie des graphes, les algorithmes de chemins robustes.   IV) Domaine scientifique secondaire :Le domaine secondaire couvre les aspects d'algorithmique parallèle ou distribuée, les politiques de transports, la multi-modalité et l'aspect temps réel.   V) Nom, prénoms et couriels du Directeur de thèse   Directeur Zineb Habbas e-mail [e-mail]

Co-encadrant Djamel Khadraoui [e-mail]

  VI) Sujet de thèse :   VI.1) Contexte de travail  Le problème de plus court chemin est un problème très classique en théorie des graphes. L'algorithme le plus répandu pour le résoudre est celui de Dijkstra. Cet algorithme suppose que les arêtes sont pondérées par des valeurs positives ou nulles. Il existe aussi toute une variante d'algorithmes calculant les plus courts chemins partant de n'importe quel noeud s à n'importe quel noeud d ou d'un noeud s à tout noeud. Certains algorithmes peuvent s'exécuter en un temps polynomial. Dans cette thèse nous intéressons aux algorithmes de plus courts chemins dans des graphes dynamiques, des graphes dont la pondération des arêtes et paramétrée par une fonction faisant intervenir le temps par exemple. Kauffman et Smith ont montré que si la pondération respecte la règle dite FIFO alors l'algorithme de Dijstra classique détermine un chemin optimal. Par contre dans le cas où cette condition n'est pas satisfaite le problème devient NP-difficile. Beaucoup de travaux dans la littérature portent sur le calcul de chemins dans des graphes dynamiques. Dans ces graphes la fonction de pondération peut être elle même mise à jour, le problème qui se pose alors est de reconstruire rapidement un chemin optimal et ce sans relancer le calcul du plus court chemin depuis le début. Par ailleurs Roditty et Zwick ont montré que si on autorise uniquement des suppressions d'arêtes, le problème de plus court chemin avec une seule source dans un graphe dynamique devient aussi dur que celui du plus court chemin entre paire de noeuds dans un graphe statique. Parmi les graphes dynamiques il existe les graphes dits stochastiques régis par une règle de

probabilité et où le poids d'une arête répond à une loi de probabilité. Le calcul du plus court chemin se ramène à celui de l'espérance mathématique. D'autres graphes rentrent aussi dans ce cadre. Ce sont les graphes multi-critères qui ajoutent une difficulté supplémentaire au problème du plus court chemin. Dans les graphes dynamiques les problèmes de plus court chemin doivent être robustes. De nombreuses recherches ont été menées pour rendre les algorithmes de plus court chemin tolérants aux changements de topologie, c'est à dire qui peuvent rapidement réadapter la solution courante vers une solution proche de l'optimale. C'est un sujet complexe et c'est dans ce contexte que s'inscrit cette thèse.   VI.2 ) Sujet à réaliser Le sujet à réaliser est de contribuer à la recherche d'algorithmes efficaces pour calculer des plus courts chemins robustes ou tolérants aux pannes, aux perturbations dans les réseaux. Ces algorithmes doivent être appliqués et validés pour le problème de transport multi-modal et multi- objectif. Cette thèse s'inscrit dans le cadre d'un projet Européen Interreg-IVB Europe NWE en cours de préparation. Il a donc un enjeu à la fois académique et scientifique mais aussi un enjeu industriel dans le cadre de transfert technologique.   Le plan à suivre serait le suivant: ●  Faire une étude exhaustive de l'état de l'art sur le problème de robustesse de graphes dynamiques.   ●  Se baser sur les algorithmes de théorie des graphes, des CSP, pour proposer des algorithmes efficaces et robustes et les tester sur des données académiques.   ● Valider ces algorithmes sur le problème de transport multi-modal, multi-objectif et temps réel.