Optimisation du réseau des routes aériennes
FONDACCI ; GOLDSCHMIDT ; LETROUIT
Type de document
CHAPITRE D'OUVRAGE (CO)
Langue
francais
Auteur
FONDACCI ; GOLDSCHMIDT ; LETROUIT
Résumé / Abstract
Le réseau aérien actuel est composé d'un ensemble de segments qui s?intersectent en des points particuliers définis par des balises émettant des signaux à partir du sol. Ce réseau conduit à un excès des distances parcourues par les avions estimé à 8 % en Europe. Or dans un proche avenir, le système GPS (Global Positioning System), qui peut déterminer précisément la position d'un avion, permettra de concevoir un nouveau réseau indépendant de moyens au sol. Il est alors possible d'envisager un réseau aérien avec d'une part des lignes aériennes en ligne droite entre les aéroports et d'autre part la possibilité donnée aux avions de changer de niveaux une ou plusieurs fois entre l'origine et la destination afin d?éviter les points de conflit potentiel. Dans cet article, nous présentons des problèmes combinatoires sur les ensembles de segments, liés à la conception d'un réseau de ce type. En particulier, nous proposons des heuristiques et des algorithmes pour les problèmes de la clique maximum, de la coloration, de la n-coloration et d'autres problèmes plus généraux sur la coloration d'un ensemble de segments. Finalement, nous présentons des résultats obtenus par l'application de nos méthodes sur des données réelles du trafic européen.