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

International audienceL'objectif est d'établir une méthode de calcul de k plus courts chemins contraints par un langage régulier partant à un horaire donné dans de grands multigraphes multimodaux dépendant du temps et respectant la condition FIFO. Soient n et m le nombre de noeuds et d'arcs du graphe; un chemin est une séquence d'arcs adjacents deux à deux.Bien que pour le cas classique du calcul de k plus courts chemins non contraints sur des graphes monomodaux statiques, des méthodes de résolution (Eppstein 94 et améliorations) très efficaces (O(m + n*log(n) + k) en temps) existent, ces approches sont difficilement utilisables dans notre cas car elles se basent sur un précalcul en parcours arrière.Nous proposons un algorithme à fixation d'étiquettes pour le calcul des k plus courts chemins multimodaux dépendant du temps. La difficulté de la résolution vient de ce qu'aucune règle de dominance ne peut s'appliquer, rendant tout parcours en largeur naïf prohibitif. Nous introduisons donc une régle de sélection du pivot prenant en compte les solutions ainsi que l'exploration des itérations précédantes. Ainsi, le graphe des k plus courts chemins générés par l'exploration s'étend le plus possible non pas vers les branches de coûts provisoires minimaux mais vers les branches de coûts définitifs minimaux, et parmis elles, celles dont les coûts provisoires sont minimaux. La technique est donc, dans l'esprit, très proche de l'algorithme A*. La complexité temporelle estimée est de O(n*m+k*n*log(n)) avec une complexité spatiale de O(k*n).De plus, toutes les techniques d'accélération classiques n'utilisant pas d'évaluation arrière optimale (A*, landmarks) deviennent directement utilisables ce qui permet d'accroître les performances d'éxécution.En conclusion, la résolution du problème des k plus courts chemins multimodaux dépendants du temps par l'extension des méthodes de résolution vastement étudiées du problème des k plus courts chemins conduisent à de très mauvaises performances temporelles.Nous proposons des algorithmes permettant de meilleures performances expérimentales.