HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/inria-00000046
Contributor : Christine Solnon Connect in order to contact the contributor
Submitted on : Tuesday, May 24, 2005 - 6:28:42 PM
Last modification on : Tuesday, October 19, 2021 - 11:02:49 AM
Long-term archiving on: : Thursday, April 1, 2010 - 9:31:14 PM

File

Identifiers

  • HAL Id : inria-00000046, version 1

Collections

Citation

Thomas Rivière, Pascal Brisset. Plus courts chemins dans un graphe planaire et création d'un réseau de routes aériennes. Premières Journées Francophones de Programmation par Contraintes, CRIL - CNRS FRE 2499, Jun 2005, Lens, France. pp.365-372. ⟨inria-00000046⟩

Share

Metrics

Record views

165

Files downloads

424