| HAL-Inria | Les publications, logiciels... des scientifiques Inria |
Communication dans un congrès
Plus courts chemins dans un graphe planaire et création d'un réseau de routes aériennes
Résumé : Cet article présente une solution mise en oeuvre pour la création d'un réseau de routes aériennes ainsi que les améliorations qui lui ont été apportées. Afin de résoudre ce problème, les auteurs, partant d'un premier réseau simplifié, ont, dans un premier temps, utilisé un algorithme de recherche local à base de recuit simulé et d'algorithme des plus courts chemins de Floyd-Warshall afin d'optimiser celui-ci et tenter de fournir aux avions la trajectoire la plus courte possible. Puis, afin d'améliorer les performances, une nouvelle méthode permettant de " maintenir " ces plus courts chemin est détaillée, tout d'abord par l'utilisation d'invariants, puis par un algorithme ad-hoc. Si les résultats sur des exemples généraux montrent une réelle amélioration du temps de calcul, le passage à l'application considérée semble en revanche ne pas être aussi encourageant.
Littérature citée [9 références]
https://hal.inria.fr/inria-00000046
Contributeur : Christine Solnon <>
Soumis le : mardi 24 mai 2005 - 18:28:42
Dernière modification le : jeudi 23 août 2018 - 09:49:18
Document(s) archivé(s) le : jeudi 1 avril 2010 - 21:31:14
Contributeur : Christine Solnon <>
Soumis le : mardi 24 mai 2005 - 18:28:42
Dernière modification le : jeudi 23 août 2018 - 09:49:18
Document(s) archivé(s) le : jeudi 1 avril 2010 - 21:31:14