Philippe Baptiste (INRA Toulouse)

Nous présentons un travail effectué en collaboration avec deux industriels du contrôle aérien. Il s’agit de séquencer un ensemble d’avions en attente au dessus d’un aéroport et de déterminer avec précision les dates d’atterrissage. En attente, un avion est placé dans une “pile” dont il ne peut sortir qu’après un temps de parcours fixé; il ne peut donc atterrir que dans quelques intervalles de temps disjoints. De plus, les atterrissages doivent être suffisamment espacés pour éviter des phénomènes dangereux de turbulence.

La complexité de différentes variantes de ce problème est étudiée. Sous certaines hypothèses simplificatrices il peut être résolu en temps polynomial. Dans sa plus grande généralité, le problème est résolu par deux techniques dont nous comparons l’efficacité : Un “Branch and Cut” (programmation linéaire) et un “Branch and Bound” avec propagation de contraintes.