Calcul des dates d'atterrissage d'une séquence d'avions pour des fonctions de coût convexes et affines par morceaux - Archive ouverte HAL Access content directly
Conference Papers Year : 2019

Calcul des dates d'atterrissage d'une séquence d'avions pour des fonctions de coût convexes et affines par morceaux

(1) , (2) , (2)
1
2
Maurice Diamantini
Alain Faye
  • Function : Author
  • PersonId : 952532
  • IdHAL : alain-faye
Julien Khamphousone
  • Function : Author
  • PersonId : 1057819

Abstract

Ce papier étudie le problème du séquencement des avions lors de leur arrivée à l'aéroport, problème connu dans la littérature sous le nom de Aircraft Landing Problem [1]. Il s'agit de séquencer les avions arrivant sur la piste d'atterrissage tout en respectant des conditions de sécurité entre les avions. Les avions créent des turbulences et une durée minimum entre deux atterrissages successifs doit être respectée. La durée de séparation dépend du type des avions qui se suivent. Un petit avion qui atterrit derrière un gros avion doit attendre plus longtemps qu'un gros avion qui atterrit à la suite d'un petit. Chaque avion $i$ peut atterrir dans une certaine fenêtre de temps $[E_i , L_i ]$. $E_i$ est la date au plus tôt à laquelle l'avion peut atterrir, $L_i$ est la date au plus tard. Dans cette fenêtre, $T_i$ est la date préférée d'atterrissage qui correspond à la date à laquelle l'avion arriverait sur la piste s'il allait à sa vitesse de croisière. Si l'avion $i$ était seul il atterrirait à la date $T_i$ mais en présence d'autres avions un arbitrage est nécessaire. Les avions doivent soit accélérer pour atterrir plus tôt ou au contraire ralentir voire faire des boucles pour arriver plus tard afin de respecter les contraintes de sécurité. Une déviation par rapport à la date préférée d'atterrissage engendre un coût. Dans la littérature on considère généralement qu'une avance ou un retard engendre un coût linéaire en fonction de l'écartement à la date préférée d'atterrissage. L'objectif est de minimiser le coût total de déviation. Sur chaque piste, le problème se décompose en deux phases : d'abord choisir l'ordre des avions et ensuite calculer les dates d'atterrissage. Ce dernier problème peut se résoudre par un PL (Programme Linéaire) [3, 5, 6, 7]. A. Faye [4] propose un algorithme de complexité quadratique en fonction du nombre d'avions. Cependant, un coût linéaire peut s'avérer assez éloigné des coûts réels encourus. Par exemple, un retard peut avoir des conséquences sur les passagers en correspondance et sur les vols ultérieurs sur lesquels le personnel de bord devra prendre place. On conçoit facilement que plus le retard est grand, plus les complications sont nombreuses et que plus l'impact sur le coût s'accroît. Il est donc légitime de modéliser la fonction coût par une fonction convexe et affine par morceaux centrée en la date préférée d'atterrissage et avec des pentes croissantes de part et d'autre de cette date. Pour des raisons d'équité entre compagnies aériennes, une fonction de ce type a été introduite par Soomer et Franx [6]. Pour un ordre fixé des avions, le coût total était calculé par un PL. Ici, nous proposons un algorithme polynomial dont la complexité dépend à la fois du nombre d'avions et du nombre de pentes de la fonction de coût d'un avion. Ainsi, si n est le nombre d'avions et si b est le nombre maximum de pentes que peut comporter le coût d'un avion, la complexité de l'algorithme est $O(n^2 b^2)$. Cet algorithme est basé sur la programmation dynamique et est une généralisation de l'algorithme proposé dans [4].
Fichier principal
Vignette du fichier
ROADEF2019_paper_45.pdf (228.65 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02354405 , version 1 (07-11-2019)

Identifiers

  • HAL Id : hal-02354405 , version 1

Cite

Maurice Diamantini, Alain Faye, Julien Khamphousone. Calcul des dates d'atterrissage d'une séquence d'avions pour des fonctions de coût convexes et affines par morceaux. ROADEF 2019, Feb 2019, Le Havre, France. ⟨hal-02354405⟩
267 View
52 Download

Share

Gmail Facebook Twitter LinkedIn More