Chapitre 5
Méthode de resolution
5.1 Introduction
Notre probleme s'est formulé en un programme
linéairede grande taille a variables mixtes, nous nous
intéressons a la résolution de ce type de problemes.
Nous commencons par introduire certaines méthodes exactes
quinous semble intéressantes, des que la taille du problleme devient
importante, ce qui est le cas de notre problleme, larésolution avec de
telles méthodes devient trés coüteuse en termede temps
d'exécution et d'espace mémoire.
Pour cela, nous avons proposé une méthode
approximative dite heuristique qui permet de trouver une solution
approchée réalisable, en un temps d'exécution relativement
rapide, que l on considère acceptable.
Les méthodes exactes, dontlobjectif est de
déterminer 'optimum exact sont appliquées
généralement sur les probllmes qui peuvent tre résolus de
facon optimale et rapide. Pour la minimisationdes retards qui est un probleme
formulé sous forme dun programme inéaire variables mixtes, et qui
est de plus basésur deséstimés, donc l'utilisation des
méthodes exactes ne semble pas tre la plus appropriée. Ceci ne
nous empeche pas de citer les méthodes exactes de résolution des
programmes linéaires mixtes PLM) esplus répandues [PICOO].
5.2 Méthodes exactes
5.2.1 Branch and Bound (LAND et DOIG 1960)
Les procédures de séparation et évaluation
explorent mplicitement l'ensemble des solutions du probeme en divisant
séquentiellement l'ensemble des solutions possibles en plusieurs
sous-ensembles qui contiennent toutes les solutions entiCres possiblessElles
eectuent une recherche arborescente partielle grace a l'utilisationdesbornes
aux différents noeuds de l'arborescence.
L' utilisation de cette méthode devient délicate
lorsque atailledu probeme est trés grande
5.2.2 Méthode de Decomposition par partitionnement des
variables(Benders 1962)
En notant par X : la variable continue et Y : la variable
entiére. Le principe de la méthode est de fixer les variables Y.
on resoud le programme linéaire en X et on obtient un Y meilleur, et
ainsi de suite jusqu'â l'obtention d'une solution optimalee
Pour déterminer le vecteur Y on doit résoudre a
chaqueitération un PL en nombre entiers appelé maître
restreinttCeci permetde transformer la résolution dun probléme a
variablesmixtes en a résolution d'une suite de problémes en
nombre entierssLa résolution du programme maître restreint
peutconduire en pratique des difficultés si le nombre de variables Y est
trop élevé[BER95]
5.3 Méthodes approchées
Les Méthodes approchées ou heuristiques, qui
aucontrairedes précedentes, sont bien adaptées au probleme de
minimisationdes durées de retard avec une simulation du flux detrafic
aérienet dans les cas oü le probleme est complexe. Ce sont donc ces
méthodes qui seront utilisées pour la résolution du
probléme..aétudier comme eur nom l'indique, ces méthodes
ne garantissent pas lobtentionde l'optimum global, mais uniquement de trouver
un optimum intéressant parmi d'autres
L'application de ces méthodes nous aide atrouver bonne
solution et raisonnable en terme de temps dexécution[SEVO3]
Algorithme de l'heuristique de Regulation
C'est un algorithme en temps réel, le but est dexposer es
solutionss
Notations EOBT: départ Block Estimé ;
ETOT: crénreau Estimé ;
ETO : l'heure estimée d'entrée dans une zone
régulée
CTO : l'heure calculée d'entrée d'un vol dans une
zone régulée COBT: le départ block calculé ;
CTOT : le décollage calculé ;
Troul : le temps de roulage ; on le pred égal a 10mn; T:
la durée de vol;
Waypoints : Ce sont les balises ou les points par lesquels passe
un vol;
Distance : Distance séparant deux Waypoints Vitesse : la
vitesse de l'aéronef ;
capa :la capacitéd'un secteur ; (capa = 10 nombre
d'avions/heure) ;
Demande: c'est le nombre de vol dontle plan a été
déposé pour traverser les secteurs
Algorithme Regulation VAR
Table Trafic 40'eme journée : table; TABSEC[i]
: tableau;
seci, i,b,a : entier ;
sort : boolean ;
CTO[i], RTD[i], T3[i],C2[i] : tableau
Procedure Secteur (ENTREE Table Trafic
40'emejournée (équivalent du PLN de la journée
modéle) Table SectPoint SORTIE : Table Strip); //Procédure
principale//
Begin
Récupérer_Point(Table Trafic) //Procédure
pourrécupérer e point//
Compare_Secteur(Table SectPoint) //Procédure pour
compareres secteurs//
TABLE STRIP //résultat de la procédure//
End;
Procedure Strip (ENTREE Table Strip; SORTIE : Table
StripFinal);
Begin
/ /La procédure pour récupérer le Temps d
entrée et sortie des vols dans les secteurs//
TABLE STRIPFINAL //Résultat(SecteurTentrée,
Tsortie)//
End;
STRIPFINAL -* STRIPFINAL Triée// On tri la table
STRIPFINAL//
BEGIN
Pour i = 1 a 7 faire
seci : seci + 1; //Récupererla demande (charge) des
7secteurs de la table Table Secteur//
table5.suivant
Fin pour
//On l'injecte dans l'application principale//
Pour i = 1 a 7 faire
TABSEC[i] : 0;
Fin pour
TABSEC[1] : sec1; TABSEC[2] : sec2TABSEC[3] sec3
TABSEC[4] : sec4 ; TABSEC[5] : sec5TABSEC[6] sec6
TABSEC[7] :
sec7;
i: 1;
Tantque i 7 faire
DEMANDE : TABSEC[i]; //DEMANDE est le nom dun champ dans la table
1//
i : i+1;
table1.suivant ;
Fin tantque
Pour i = 1 a 500 faire
CTO[i] : 0; RTD[i] : 0 ; T3[i] 0
Fin pour
Pour i = 1 a 7 faire
C2[i] : 0;
C2[1] : min(T2,10,1); //min(T2101) procedure minimum)//
Fin pour
Pour i = 2 a 7 faire
b : 0;
Poura:=1ai-1 faire
b : b+TABSEC[a];
Fin pour
C2[i] : min(T2,10,b+1);
Fin pour
b : 1; i : 1 ; a: 1 ; sort faux
/ / Rmq: sort indique est ce qu'un vol est parmila charge du
secteur est sorti ou paselle est initialisee a false//
Tantque (sort faux) et (i TABSEC[1]) faire
Si i 10 alors
RTD[b] : 0
sinon
RTD[b] : C2[1]-T1[i] ; b : b+1;
i : i+1;
Finsi
Fin tantque
Affiche(RTD[b]); //Affichage du tableau des retards//
End.
et on a l'organigramme delheuristique
| 
