Calcul de k plus courts chemins dans de grands graphes multimodaux et dépendant du temps.

L'objectif est d'etablir une methode de calcul de k plus courts chemins contraints par un langage regulier partant a un horaire donne dans de grands multigraphes multimodaux dependant du temps et respectant la condition FIFO. Soient n et m le nombre de noeuds et d'arcs du graphe; un chemin est une sequence d'arcs adjacents deux a deux. Bien que pour le cas classique du calcul de k plus courts chemins non contraints sur des graphes monomodaux statiques, des methodes de resolution (Eppstein 94 et ameliorations) tres efficaces (O(m + n*log(n) + k) en temps) existent, ces approches sont difficilement utilisables dans notre cas car elles se basent sur un precalcul en parcours arriere. Nous proposons un algorithme a fixation d'etiquettes pour le calcul des k plus courts chemins multimodaux dependant du temps. La difficulte de la resolution vient de ce qu'aucune regle de dominance ne peut s'appliquer, rendant tout parcours en largeur naif prohibitif. Nous introduisons donc une regle de selection du pivot prenant en compte les solutions ainsi que l'exploration des iterations precedantes. Ainsi, le graphe des k plus courts chemins generes par l'exploration s'etend le plus possible non pas vers les branches de couts provisoires minimaux mais vers les branches de couts definitifs minimaux, et parmis elles, celles dont les couts provisoires sont minimaux. La technique est donc, dans l'esprit, tres proche de l'algorithme A*. La complexite temporelle estimee est de O(n*m+k*n*log(n)) avec une complexite spatiale de O(k*n). De plus, toutes les techniques d'acceleration classiques n'utilisant pas d'evaluation arriere optimale (A*, landmarks) deviennent directement utilisables ce qui permet d'accroitre les performances d'execution. En conclusion, la resolution du probleme des k plus courts chemins multimodaux dependants du temps par l'extension des methodes de resolution vastement etudiees du probleme des k plus courts chemins conduisent a de tres mauvaises performances temporelles. Nous proposons des algorithmes permettant de meilleures performances experimentales.