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 <>
Submitted on : Tuesday, May 24, 2005 - 6:28:42 PM
Last modification on : Tuesday, October 27, 2020 - 1:14:01 PM
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

297

Files downloads

701