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.