Le problème de routing des avions au sol consiste à planifier le mouvement des avions dans un aéroport, entre les points de stationnement et les pistes, sur un horizon de temps pouvant aller jusqu'à 40 minutes. Pour chaque avion, les points d'origine et de destination sont connus. Pour un avion au décollage, l'origine correspond au point de stationnement tandis que la destination correspond à la piste qui lui est affectée (et vice-versa pour un avion à l'atterrissage). Les heures d'origine et de destination sont basées sur des estimations fournies par différents acteurs de l'aéroport. Le problème consiste à définir et planifier les trajectoires des avions, tout en respectant des contraintes de séparation minimale pour des raisons de sécurité. L'objectif est de minimiser les retards aux points de destination ainsi que la consommation de carburant.
Trois approches de routing sont considérés dans la littérature : le routing selon un chemin fixé et prédéfini, le routing selon des chemins alternatifs, où il faut choisir un chemin parmi un ensemble de chemins prédéfinis, et le routing libre, où les trajectoires ne sont pas contraintes. Notre principale contribution est de comparer le routing selon un chemin fixé et le routing selon des chemins alternatifs, afin de déterminer l'approche la plus pertinente. Le routing libre est exclu de notre étude car difficile à mettre en oeuvre. Pour chaque approche, nous avons proposons une modélisation en PLNE et des heuristiques. Nous comparons la qualité des solutions ainsi que le temps de calcul sur des instances réalistes provenant d'un aéroport européen. Nous étudions aussi l'impact du contrôle de repoussage sur la durée de trajet et donc sur la consommation de carburant.