In this problem, a minimum-cost set of aircraft routes and crew pairings must be constructed while choosing a departure time for each flight leg within a given time window. Linking constraints ensure that the same schedule is chosen for both the aircraft routes and the crew pairings, and impose minimum connection times for crews that depend on aircraft connections and departure times. We propose a compact formulation and a Benders decomposition method with a dynamic constraint generation procedure to solve it. Computational experiments show that allowing some flexibility on the schedule yields significant cost savings.

We consider a crew scheduling problem with preferential bidding in the airline industry. We present a graph coloring model and a tabu search algorithm for determining if the problem contains at least one feasible solution. We then show how to combine the proposed algorithm with a heuristic sequential scheduling method that uses column generation and branch-and-bound techniques.

Airline planning and operations problems are complex and require detailed and accurate modeling to be solved efficiently and effectively. The challenge for optimization systems is to be able to adapt timely to a changing environment and to model and solve the changed problems accurately. We describe a special purpose modeling system and its application in airline planning and operations. We give concrete examples of this successful marriage of end-user modeling and large scale optimization.

L’accroissement soutenu du transport aérien au cours des dernières décennies a induit sur les plate-formes aéroportuaires des phénomènes de saturation du trafic des avions au sol. Si pendant longtemps, la piste était considérée être le facteur limitatif de la capacité aéroportuaire, les problèmes de gestion du trafic sur les voies de circulation sont devenus de plus en plus difficiles à résoudre et viennent eux aussi limiter la capacité aéroportuaire. Dans cette communication une nouvelle approche pour la gestion des mouvements au sol des avions, aussi bien à l’arrivée qu’au départ, est proposée. L’objectif est de générer pour chaque avion un itinéraire (une route et un calendrier) sur la plate-forme aéroportuaire de façon à minimiser les retards résultant de conflits de trafic et de phénomènes de saturation. Un premier itinéraire associé à une fenêtre de temps est proposé à chaque avion et en chaque point de décision de la route correspondante celui-ci peut être modifié compte tenu de la situation réelle du trafic. Le réseau de voies de circulation des avions sur la plate-forme aéroportuaire est représenté par un graphe orienté. Pour chaque arc est évalué le temps moyen de parcours en fonction des prévisions de flux de trafic qui empruntent ce tronçon et ses tronçons adjacents. La distribution nominale des flux dans le réseau résultant d’études de capacité de la plate-forme aéroportuaire est utilisée pour formuler un premier problème d’optimisation qui permet de sélectionner, en accord avec les objectifs de capacité, un ensemble de routes performantes pour la tranche horaire considérée. La notion de fuseau de routes est alors introduite afin de structurer l’ensemble de ces routes et faciliter la sélection en ligne des itinéraires. La gestion en ligne des mouvements des avions au sol prend en compte les phénomènes de files d’attente. Une heuristique est mise en œuvre de façon à générer en ligne des corrections aux itinéraires proposés aux avions. Pour cela les différents itinéraires possibles sont évalués en tenant compte des attentes estimées au niveau des différentes files d’attente qui leur sont associées. La mise en œuvre de cette approche, de caractère adaptatif, se réalise sur un horizon fuyant subdivisé en plusieurs phases de façon à tenir compte des contraintes opérationnelles associées au mouvement des avions au sol. L’approche proposée a été testée dans le cas de l’aéroport de Toulouse-Blagnac avec des données réelles. Mots Clef : optimisation, heuristique, réseaux, transport aérien, capacité aéroportuaire.