Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 10 Janvier 2006

Séquencement des vols à l'arrivée : Modélisation, Complexité et Méthodes de résolution

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr