Optimisation Des Crew-Routes Multibase

République Algérienne Démocratique et Populaire
Ministère de l’Enseignement Supérieur et de la Recherche Scientifique

Université des Sciences et de la Technologie Houari Boumediene
Faculté de Mathématiques
Département de Recherche Opérationnelle
Mémoire
En vue de l’obtention du Diplôme de MASTER
Spécialité : Recherche Opérationnelle
Option : Engineering en Recherche Opérationnelle (ERO)
Thème :
Optimisation des crew-routes multibase
Présenté par :
— GUEMMAZ Dalia .
— DJOUMER Yasmine.
Soutenu le : 13/07/2023, devant le jury composé de :
Président : Mme TIACHACHAT Meriem USTHB

Rapporteur : M. BOUTICHE Mohamed Amine USTHB
Examinateur : Mme. Kahoul Nawel USTHB
Invitant : M.AMEUR ENTREPRISE
Code Mémoire : 08/ERO/23 .
1
Remerciements
Nous remercions avant tout, Dieu le tout puissant, de nous avoir donné la santé et le courage afin de mener ce
travail à terme.
Tout d’abord, ce travail n’aurait pas pu avoir le jour sans l’aide et l’encadrement de Mr BOUTICHE Mohamed
Amine , on le remercie pour sa patience sa rigueur durant notre préparation de ce mémoire.
Nos remerciements s’adressent aussi à Madame TIACHACHAT Meriem pour avoir accepté de présider le jury et
à Madame KAHOUL Nawel de bien vouloir examiner ce mémoire.
Nos remerciements de plus nos chers parents pour leur amour et leur indéfectible soutien, qui nous aide à avancer
au quotidien. Sans oubliez nos frères et sœurs pochent à nos cœurs .
Nous souhaitons également adresser nos remerciements les plus sincères aux personnes qui nous ont apporté leur
soutien et qui ont contribué à la réussite de cette agréable année universitaire.
Enfin , Nous exprimons ici notre profonde gratitude envers tous ceux qui ont contribué, de prés ou de loin à la
réalisation de ce mémoire et que nous ne pouvons malheureusement mentionner individuellement.
2
Dédicace
J e dédie ce modeste travail :
A ma famille, elle ma dote d’une éducation digne , son amour a fait de moi ce que je suis aujourd’hui :
A mon grand frère ≪ ADEM ≫ et ma petite sœur ≪ WISSEM ≫ qui m’avez toujours soutenu.
A mon cher YOUCEF , je souhaite te dédier ces mots remplis de reconnaissance et

de gratitude pour tout ton soutien inestimable durant mon parcours. Tu as été un pilier solide, un
encouragement constant et une source d’inspiration pour moi, et je tiens à te remercier du fond du cœur.Que dieu
vous protège pour nous.
A mes chères tantes ≪ HAKIMA ≫ et ≪ HACIBA ≫.
A u Département de Recherche opérationnelle.
S ans oublier ma meilleure amie pour toujours ≪ NAZIHA ≫
J e dédie le fruit de mes 22 ans d’études ,≪ DALIA ≫.
GUEMMAZ
DALIA
Dédicace
J e Dédiée ce modeste travail :
A la femme la plus douce au monde, qui n’a jamais dit non a mes exigences et qui n’a épargné aucun Effort
pour me rendre heureuse :
M ON ADORABLE MAMAN
A l’homme, mon précieux offre de dieu, qui n’a pas cessée de me soutenir tout au long de mes études, qui doit
ma vie, ma réussite et tout mon respect :
M ON Cher PAPA
Q uoi que je fasse ou je dise, je ne serai point vous remercié comme il se doit, votre affections me couvre, votre
bienveillance me guide et votre présence a mes cotés a toujours été ma source de force.
A Amon cher mari ≪ Azzedine ≫ qu’il a été toujours a mes cotés pour m’encourager me conseiller et me
soutenir dieu le protège.
A ma chère sœur ≪ IMENE ≫ et mes deux chers frères ≪ YOUNES ≫ ET ≪ YACINE ≫ a qui je souhaite la
réussite a l’examen du bac .
A mon grand père, mes grand mères que dieu leurs donne une longue et joyeuse vie.
A tous mes oncles et mes tentes, mes cousin, mes cousine ainsi que ma belle famille , les amis que j’ai connu
jusqu’à maintenant ainsi que mon binôme ≪ Dalia ≫ :merci pour leurs amours et encouragements .
A UNE Pensé a mon très cher grand père ≪ tu es toujours dans mon cœur ≪ DJEDOU ≫
DJOUMER
YASMINE
4
R ÉSUM É-ABSTRACT-
Résumé : Ce travail est consacré à la résolution du problème de planification d’équipages, au

niveau de la compagnie aérienne Air Algérie . Notre objectif à travers ce mémoire est d’établir une
solution pratique et efficace afin d’améliorer la gestion des équipages et de minimiser les erreurs lors
de l’affectation des personnels navigant aux vols tout en utilisant les outils et les techniques de la
recherche opérationnelle.
Dans l’étape de résolution on a proposé une méthode approchée , et afin d’implémenter les résultats
nous avons conçu une application sous le langage Python.
Abstract : This work is devoted to solving the problem of crew planning, at the level of the airline
Air Algérie. Our objective through this thesis is to establish a practical and effective solution to improve
crew management and minimize errors when assigning aircrew to flights while using the tools and
techniques of operational research.
In the resolution step we proposed an approximate method, and in order to implement the results
we designed an application in the Python language.
5
Table des matières
Terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Introduction générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Chapitre I Présentation De La Compagnie Aérienne 15

I.1 Présentation de la compagnie Air Algérie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
I.1.1 Création-Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
I.1.2 Statut juridique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
I.1.3 Missions et prestations de la compagnie . . . . . . . . . . . . . . . . . . . . . . . . 16
I.1.4 Réseaux, destinations et bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
I.1.5 Ressources de la compagnie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
I.1.5.1 Moyens humains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
I.1.5.2 Moyens matériels (La flotte) . . . . . . . . . . . . . . . . . . . . . . . . . . 19
I.1.6 Terminologie et abréviations : [6] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
I.1.7 Hiérarchie et structure générale de la compagnie . . . . . . . . . . . . . . . . . . . 21
I.1.8 Présentation de l’organisme d’accueil . . . . . . . . . . . . . . . . . . . . . . . . . . 22
I.1.8.1 Présentation de la direction programme . . . . . . . . . . . . . . . . . . . 22
I.1.8.2 Critères de performances : . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Chapitre II Problématique 26
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
II.1 Position du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
II.1.1 La Création de rotation : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
II.1.2 L’Affectation de rotation : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
II.2 Problème d’affectation du personnel navigant de la compagnie aérienne Air Algérie . . . 27
II.3 Aperçu du logiciel AIMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
II.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Chapitre III Modélisation du problème 29

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
III.1 Concepts de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
III.1.1 Optimisation mathématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
III.1.2 Programme linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6
III.1.3 Formule mathématique d’un programme linéaire . . . . . . . . . . . . . . . . . . . 30
III.1.4 Complexité algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
III.1.4.1 Problème facile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
III.1.4.2 Problèmes difficiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
III.1.5 La Modélisation d’un problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
III.2 La modélisation du problème d’affectation du personnel navigant [5] . . . . . . . . . . . . 31
III.2.1 Notation et définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
III.2.2 Notation des indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
III.2.3 Notation des ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
III.2.4 Notation des paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
III.2.5 Définition des variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
III.2.6 Définition des contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
III.2.6.1 Contrainte de capacité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
III.2.6.2 Contrainte limitant le temps de vol . . . . . . . . . . . . . . . . . . . . . 34
III.2.6.3 Contrainte limitant le temps de repos . . . . . . . . . . . . . . . . . . . . 34
III.2.6.4 Contrainte relative au non-chevauchement . . . . . . . . . . . . . . . . . 34
III.2.6.5 Contrainte relative aux alertes . . . . . . . . . . . . . . . . . . . . . . . . . 34
III.2.7 La fonction objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
III.2.8 le modèle mathématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
III.2.9 Taille du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
III.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Chapitre IV Méthode de résolution 39

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
IV.1 Technique de base et méthodes de résolution . . . . . . . . . . . . . . . . . . . . . . . . . . 39
IV.1.1 L’optimisation combinatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
IV.1.2 Résolution d’un problème d’optimisation combinatoire : . . . . . . . . . . . . . . . 40
IV.1.2.1 Les méthodes d’optimisation combinatoire . . . . . . . . . . . . . . . . . 40
IV.1.2.2 Les méthodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
IV.1.2.3 Les méthodes approchées (heuristiques) . . . . . . . . . . . . . . . . . . 41
IV.1.2.4 La métaheuristique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
IV.2 Approche de résolution pour le problème d’affectation du personnel navigants . . . . . . 43
IV.2.1 Méthode de résolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
IV.2.2 Adaptation de l’euristique au problème . . . . . . . . . . . . . . . . . . . . . . . . 43
IV.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Chapitre V Implémentation 46
V.1 Présentation et avantages du langage choisi [3] . . . . . . . . . . . . . . . . . . . . . . . . . 46
V.1.1 Présentation de l’environnement ≪ python ≫ . . . . . . . . . . . . . . . . . . . . . 46
7
V.1.2 Les avantages du logiciel choisi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
V.2 Implementation de l’heuristique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
V.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Conclusion générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Table des figures
I.1 Organigramme de la compagnie [6] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

I.2 Organigramme de la direction des programmes d’Air Algérie [6] . . . . . . . . . . . . . . 23
I.3 Relations avec les autres structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
II.1 Processus d’optimisation du programme de vols pour une compagnie aérienne [5] . . . . 27
III.1 Contrainte de repos PN base/ hors base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
IV.1 Classifications des méthodes d’optimisation combinatoire [4] . . . . . . . . . . . . . . . . 40

IV.2 Contrainte de repos PN base/ hors base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
V.1 Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
V.2 Extrait du planning des vols hebdomadaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
V.3 Extrait du tableau des équipages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
V.4 TSV * Temps De Service De Vol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Liste des tableaux
I.1 Tableau siège social [4] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

I.2 Le réseau national d’Air Algérie [4] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
I.3 Réseaux internationaux d’Air Algérie [4] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
I.4 La flotte de la compagnie Air Algérie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
IV.1 TSV * Temps De Service De Vol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

TERMINOLOGIE
• Personnel navigants (membres d’équipage) : Le personnel navigants d’une compagnie aérienne

est celui qui constitue les équipages des vols à effectuer, ce dernier est constitué d’un :
- Personnel navigant technique << PNT >> : le commandant de bord et l’officier pilote de
ligne
- Personnel navigant commercial << PNC >> : les hôtesses de l’air et les stewards.≫
• Vols : Les vols sont les trajets spécifiques que les avions effectuent entre différentes destinations.
Chaque vol a des caractéristiques uniques telles que l’heure de départ, l’heure d’arrivée, la durée
du vol, l’aéroport de départ et l’aéroport d’arrivée.
• Planning de vols : Un planning de vols est un calendrier organisé des vols prévus par une
compagnie aérienne sur une période donnée. Il inclut les informations telles que les numéros de
vol, les aéroports de départ et d’arrivée, les horaires de départ et d’arrivée, la durée du vol, le
type d’avion et la fréquence des vols. Il permet de planifier et de coordonner les opérations de vol
de manière efficace en attribuant les ressources disponibles aux différentes routes et destinations.
• Planning mensuel (planning) : Il s’agit d’une séquence de jumelages séparés par des périodes
de repos qui couvre une période de temps donnée (généralement un mois de planification
standardisé).
• Rotation : Ou encore crew route est l’activité aérienne qui consiste à effectuer un ou plusieurs
services de vols avec retour à la base d’affectation.Il est caractérisé par :
- Son identifiant(Le numéro du crew route ).
- La catégorie d’avion utilisée
- La longueur du crew route (donné en jour).
- Les dates /heures de départ et d’arrivée.
- La fréquence de rotation (par semaine) et la capacité en nombre de membres d’équipage
nécessaires. Ce dernier se voit attribuer une rotation spécifique qui détermine son emploi du temps
et ses affectations de vol pour la période considérée.
• Bases : sont les points de départ et de retour pour les membres de l’équipage lorsqu’ils effectuent
un crew route. En d’autres termes, et pour la compagnie Air Algérie chaque fois qu’un personnel
navigant se lance dans une rotation d’équipage, il commence et termine son vol à l’une de ces
bases spécifiques (Alger (ALG), Annaba (AAE), Constantine (CZL) et Oran (ORN)).
11
• Temps écoulé : Il s’agit de la période pendant laquelle un membre d’équipage est éloigné de sa
base, également appelée Temps Hors Base (THB).
• Repos post-courrier (Le repos de personnels naviguant après un vol) : c’est la période de
récupération accordée aux membres de l’équipage après avoir terminé un vol, ce qui fait un
temps de repos nécessaire pour assurer leur sécurité, leur bien-être et leur performance lors des
prochains vols. La durée du repos post-courrier varie en fonction des réglementations et des
politiques de la compagnie aérienne, ainsi que de la nature du vol effectué.
• Repos légal hebdomadaire (RH) : C’est une durée de repos de 24h durant laquelle le membre du
personnel navigant ne peut être programmé.
12
INTRODUCTION G ÉN ÉRALE
L’industrie du transport aérienne est vitale pour la croissance socio-économique mondiale en créant
des emplois, soutenant le tourisme, les entreprises locales et en stimulant l’investissement et le
commerce international. En Algérie , la compagnie aérien ≪ Air Algérie ≫ occupe une place de premier
plan sur le marché global algérien en tant que principale compagnie aérienne du pays, qui joue un rôle
central dans la connectivité du pays avec le reste du monde, d’une gamme diversifiée de destinations
nationales et internationales, la compagnie aérienne offre des possibilités de voyage pratiques et fiables
pour les passagers algériens et étrangers. En termes de chiffre d’affaires, Air Algérie a connu une
croissance significative ces dernières années. En 2019, la compagnie a enregistré un chiffre d’affaires de
102 milliards de dinars algériens, démontrant sa position solide sur le marché et sa contribution à
l’économie du pays. L’aviation civile en Algérie joue également un rôle clé dans le développement
économique et touristique du pays. En facilitant les déplacements, Air Algérie favorise les échanges
commerciaux, stimule l’industrie du tourisme et renforce les liens sociaux et culturels entre l’Algérie et
d’autres pays.
D’autre part , deux des problèmes clés dans la majorité des compagnies aériennes tel que Air
Algérie : la construction des vols et l’affectation du personnel navigant. Ces derniers sont étroitement
liés et font l’objet d’études approfondies en recherche opérationnelle pour trouver des solutions
efficaces à cause de leurs enjeux économiques qui jouent un rôle très important du fait de la qualité du
programme de vol de chaque pays. La construction des vols concerne la planification et l’organisation
des itinéraires aériens ainsi que la gestion des horaires de vol. Les compagnies aériennes doivent
prendre en compte de multiples facteurs, tels que la demande des passagers, les contraintes
opérationnelles, les réglementations de l’aviation et les disponibilités des avions. La recherche
opérationnelle propose des approches mathématiques et informatiques pour résoudre ce problème
complexe, en optimisant l’utilisation des ressources et en maximisant l’efficacité globale du réseau de
vols. L’affectation du personnel navigant est un autre défi majeur dans le transport aérien. Il s’agit
d’assigner les membres d’équipage aux vols spécifiques en tenant compte de leurs compétences, de
leurs qualifications, des réglementations sur les temps de vol et de repos, ainsi que de leurs préférences
individuelles. La recherche opérationnelle propose des méthodes d’optimisation avancées pour
résoudre ce problème complexe, en tenant compte des contraintes et des préférences spécifiques, tout
en garantissant la sécurité et la qualité des vols. On effet elle intervient dans ces deux problèmes en
13
offrant des outils et des techniques pour modéliser et résoudre ces derniers telles que : la
programmation linéaire, la programmation par contraintes, les algorithmes et les méthodes de
recherche heuristique. Ces approches permettent de modéliser les problèmes, d’optimiser les décisions
et de trouver des solutions efficaces, contribuant ainsi à une meilleure planification des vols et à une
utilisation plus efficace des ressources humaines. [1]
Pour résoudre cette problématique, nous proposerons une heuristique qui tient compte des objectifs
des décideurs ainsi que des contraintes entourant le problème. Par la fin nous présentons
l’implémentation de cette méthode. Ce document suivra la structure suivante :
✓ Le premier chapitre se focalise sur la présentation de l’entreprise AIR ALGERIE, Son organisation
administrative et ses activités.
✓ Dans le deuxième chapitre, on se concentre sur l’explication de la problématique.
✓ Dans le chapitre trois, on donne un aperçu sur les modélisations trouver pour ce problème.
✓ Le quatrième chapitre contient les méthodes de résolution en recherche opérationnelle, et à la fin

du chapitre on met le point sur la méthode de résolution adopté.
✓ Le cinquième chapitre porte sur l’implémentation de notre méthode.
14
CHAPITRE I
PR ÉSENTATION DE LA COMPAGNIE A ÉRIENNE
I.1 Présentation de la compagnie Air Algérie

AIR ALGERIE est une société par action- S.P.A dont le capital est de 37.000.000.000,00 DA.
I.1.1 Création-Historique
La compagnie aérienne Air Algérie a une histoire riche qui remonte à plusieurs décennies. Fondée
le 15 mars 1947, elle est devenue la compagnie nationale algérienne et a joué un rôle clé dans le
développement du transport aérien en Algérie.
Au départ, Air Algérie était connue sous le nom de Compagnie Générale de Transport (CGT) et a été
créée en tant que société mixte franco-algérienne. Son premier vol commercial a eu lieu le 30 septembre
1947, reliant Alger à Bône (aujourd’hui Annaba) en utilisant des avions DC-3.
Au fil des années, cette compagnie a connu une croissance significative, élargi son réseau de vols
nationaux et internationaux. Elle a progressivement modernisé sa flotte et introduit des avions plus
performants pour répondre à la demande croissante des passagers.
En 1963, à la suite de l’indépendance de l’Algérie, la compagnie a été nationalisée et renommée Air

Algérie. Elle est devenue une entreprise publique sous la tutelle du ministère des Transports.
Air Algérie a continué de se développer en établissant des partenariats avec d’autres compagnies
aériennes internationales et en augmentant sa présence sur les marchés mondiaux. Elle a étendu son
réseau de vols pour desservir plusieurs destinations en Europe, en Afrique, en Amérique du Nord, au
Moyen-Orient et en Asie. La compagnie aérienne a également joué un rôle vital dans le développement
économique et touristique de l’Algérie en favorisant les échanges commerciaux et en facilitant les
déplacements des passagers.
Aujourd’hui, elle continue d’opérer en tant que compagnie aérienne nationale, offrant des services de
transport aérien réguliers et charter. Elle s’efforce de maintenir des normes élevées en termes de sécurité,
de confort et de qualité de service, tout en contribuant au développement de l’industrie aéronautique
15
Chapitre I Présentation de la compagnie Air Algérie
en Algérie.
I.1.2 Statut juridique
Conformément à la législation en vigueur, en particulier l’ordonnance n° 95-25 du 25 février 1995

concernant la gestion des capitaux de l’État, Air Algérie a été transformée en une entreprise publique
économique (E.P.E. / S.P.A.). Cette transition vers l’autonomie a été accompagnée d’un ensemble de
mesures visant à consolider l’entreprise et à lui fournir des fondations solides, afin de la préparer aux
défis nouveaux du secteur du transport aérien. L’objectif de ces mesures est d’assurer la viabilité de
l’entreprise et de lui permettre de faire face aux évolutions à venir.
Dénomination AIR ALGERIE

Siège social 1, place Maurice Audin, Alger
Durée 99 ans à compter de son immatriculation au registre de commerce
Capital social Fixé à 14 milliards Dinars Algériens.
TABLE I.1 – Tableau siège social [4]
I.1.3 Missions et prestations de la compagnie
• La mission d’Air Algérie est de connecter l’Algérie au monde grâce à des services de transport
aérien sûr et de qualité, en offrant une gamme de prestations adaptées aux besoins des passagers
et des activités pour inclure des vols long
— courriers afin de suivre la croissance économique du pays.

— La mis en service de la ligne Alger-Montréal depuis le 15 juin 2007 et le prévoit du lancement
des lignes Alger-New York et Hassi Messaoud-Houston avant la fin de l’année 2007.
— Une gamme de prestation (des vols réguliers et sécurisés, le confort des passagers, un service
de qualité à bord des avions).
— Des charters pétroliers qui transportent quelques 500 000 passagers/an.
• Des charters Omra et Hadj qui transportent les pèlerins vers les lieux saints de l’Islam.
• Un centre ou commissariat hôtelier (catering) qui permet à Air Algérie de couvrir ses Besoins au
départ d’Algérie, ainsi que l’assistance des autres compagnies.
I.1.4 Réseaux, destinations et bases
Un vaste réseau de 96 400 km. Chaque année, la compagnie transporte plus de 3 millions de passagers
et près de 20 000 tonnes de fret, tant sur son réseau international que sur réseau national, tel que :
1. Réseau national : dessert vingt-neuf (24) escales dont deux (2) au centre du pays, Six (6) à l’est, deux
(2) à l’ouest et quinze (15) au sud du pays.il permet de joindre n’importe quel point sur le territoire
national grâce à la programmation de plusieurs vols par semaine
16
Réseau Villes du réseau intérieur Algérie (RIA) Code

ALGER ALGER
Centre
BEJAIA BEDJAIA
CONSTANTINE CZL
ANNABA AAE
SETIF QSF
Est
TEBESSA TEE
BATNA BLJ
JIJEL GJL
ORAN ORN
Ouest
TLEMCEN TLM
ADRAR AZR
BISKRA BSK
BECHAR CBH
DJANET DJG
EL OUED ELU
TOUGOURT TGR
GHARDAIA GHA
Sud HASSI MESSAOUD HME
IN AMENAS IAM
IN SALAH INZ
OUARGLA OGX
TINDOUF TIN
TAMANRASSET TMR
BORDJ BARDJI MOKHTAR BMW
ILIZI VVZ
TABLE I.2 – Le réseau national d’Air Algérie [4]
17
2. Réseau international : Ce réseau regroupe trente-quatre (34) escales pour vingt-trois (23) pays
divisés en Quatre (4) réseaux, dont neuf (9) escale pour le réseau France, onze (11) escales pour le
réseau Europe, huit (8) escales pour le Maghreb/Moyen-Orient et six (6) escales pour l’Afrique.
Réseau Pays Escales

Paris
Marseille
FRANCE France Lyon
Toulouse
Nice
Lille
Metz
Bordeaux
Montpellier
Italie Rome
Suisse Genève
Allemagne Frankfurt
EUROPE
Berlin
Espagne Madrid
Barcelone
Alicante
Belgique Bruxelles
Angleterre Londres
Russie Moscou
Turquie istanbul
Tunisie Tunis
Maroc Casablanca
MAGHREB/
Egypt Le Caire
MOYEN-ORIENT
Tordanie Amman
Syrie Damas
Arabie saoudite Djedda
Emirat A.U Dubaı̈
Liban Beyrouth
Niger Niamey
AFRIQUE Mali Bamako

Sénégal Dakar
Burkina Faso Ouagadougou
Cote d’Ivoire Abidjan
Mauritanie Nouakchott
TABLE I.3 – Réseaux internationaux d’Air Algérie [4]
18
En outre, Il existe un réseau de vente comprenant 150 agences en Algérie et à l’étranger relié à un
système de réservation et distribué à travers les GDS auprès desquels Air Algérie est abonnée.
Air Algérie dispose de bases opérationnelles à travers l’Algérie et à l’étranger pour soutenir ses
activités. Les principales bases incluent : l’aéroport d’Alger, Oran, Constantine et Annaba en
Algérie, ainsi que des bases internationales à Paris, Marseille et Montréal. Ces bases jouent un
rôle essentiel dans la planification des vols, la maintenance des avions et la coordination des
opérations de la compagnie.
I.1.5 Ressources de la compagnie
I.1.5.1 Moyens humains
S’élevant à 1650 employés en 1970, l’effectif a atteint aujourd’hui 9456 personnes réparties comme
suit :
-Personnel au sol : 8139 ,7.
-Personnel navigant : 1317 dont 200 commandants de bord, 256 pilotes et 120 mécaniciens
navigants, 256 hôtesses et 431 stewards.
I.1.5.2 Moyens matériels (La flotte)
Air Algérie possède une flotte diversifiée composée d’avions tels que : [4]
Pour les vols long-courriers :
✈ 5 Airbus A330-200.
✈ 2 Boeing 737-400.
✈ 5 Boeing 737-600.
✈ 10 Boeing 737-800.
✈ 3 Boeing 767-300.
Pour les vols domestiques :
✈ ATR 72-500.
Flotte Air Algérie cargo :
✈ Boeing 737-200.
✈ Lockheed L-100-300 (L-383G).
19
Types d’avions Nombres Capacités

d’avions (Sièges)
Boeing 767-300 03 253
Boeing 737-600 05 101
Boeing 737-800 10 148
ATR 72-500 06 66
Air bus A330-200 05 269
Fokker F27 02 40
Lockheed “Ilrcules” 02 Volume : 170 m3
L 100-30 (Cargo) Charge : 21 tonnes
Total 33
TABLE I.4 – La flotte de la compagnie Air Algérie
Au total, la compagnie dispose de 33 appareils, dont 31 sont utilisés pour le transport des passagers
et 2 pour le transport de marchandises. L’âge moyen de la flotte est de 5 ans.
I.1.6 Terminologie et abréviations : [6]
- DOA Direction des Opérations Aériennes.

- DOS Direction des Opération au Sol.
- DG Direction Générale.
- DC Division Commerciale.
- DP Direction des Programmes.
- DGTF Direction Gestion Technique de la Flotte.
20
I.1.7 Hiérarchie et structure générale de la compagnie
La structure organisationnelle de l’entreprise repose sur trois fonctions principales : commerciales,

techniques et exploitation. Actuellement, et Afin de garantir un bon fonctionnement compte tenu de la
diversité des tâches qui incombent à la compagnie, Air Algérie est structurée en plusieurs directions,
comme le démontre l’organigramme suivant :
F IGURE I.1 – Organigramme de la compagnie [6]
21
I.1.8 Présentation de l’organisme d’accueil
I.1.8.1 Présentation de la direction programme
La Direction des Programmes d’Air Algérie est une entité au sein de la compagnie aérienne chargée
de la gestion et de la coordination des programmes et projets de l’entreprise .Elle joue un rôle clé dans :
le développement de nouveaux itinéraires, l’expansion de la flotte, l’amélioration des services et la
modernisation des opérations. La Direction couvre quatre (04) secteurs d’activité qui garantissent une
optimisation des ressources :
• La Programmation Flotte : Rotation Avions.
• La Programmation PN (Personnel Naviguant) : Rotation équipages et affectation PN (Personnel

navigant).
• Affrètements frètements.
• Les Ressources Humaines.
22
Organigramme de la direction des programmes d’Air Algérie 21 23
F IGURE I.2 – Organigramme de la direction des programmes d’Air Algérie [6]
23
⋇ (A) Missions :
La Direction des Programmes (DP) d’Air Algérie a pour principales missions :
1. Concevoir et mettre en œuvre un programme d’exploitation optimal afin d’assurer le bon
fonctionnement de la compagnie.
2. Contribuer à l’amélioration des parts de marché d’Air Algérie en mettant en place des
stratégies visant à attirer davantage de passagers et à augmenter le volume de trafic.
3. Élaborer le programme individuel du personnel navigant, en construisant les rotations
équipages et en affectant les rotations au personnel navigant conformément aux
réglementations et aux besoins opérationnels.
4. Réaliser, suivre, réajuster et contrôler en permanence le programme de vol et les équipages,
en s’assurant de la conformité aux horaires prévus et de l’efficacité des ressources.
5. Évaluer et faire le bilan du programme d’exploitation, en analysant les résultats obtenus et en
identifiant les mesures correctives nécessaires.
6. Obtenir les créneaux horaires nécessaires dans les aéroports pour assurer les opérations de
vol d’Air Algérie.
7. Affréter des capacités supplémentaires lorsque nécessaire, en cas de besoins supplémentaires
ou de contraintes opérationnelles.
8. Gérer les accords intergouvernementaux et inter-compagnies pour faciliter les partenariats et
les collaborations avec d’autres compagnies aériennes.
9. Gérer les bases de données relatives à l’utilisation des avions et des équipages, en assurant
un suivi précis des ressources et des performances opérationnelles.
10. Assurer la gestion, le suivi et la formation du personnel de la Direction des Programmes, en
veillant à ce que les membres de l’équipe soient compétents et bien formés pour remplir leurs
responsabilités.
⋇ (B) Structure :
Pour assurer sa mission, La Direction des Programmes d’Air Algérie est structurée de manière à
inclure :
• Un directeur des programmes.
• Des responsables de programme.
• Des équipes opérationnelles.
• Des analystes et experts, ainsi que du personnel de soutien administratif.
Cette structure vise à assurer une gestion efficace des programmes et des projets au sein de la compagnie.
Les responsabilités de la direction comprennent la planification, la coordination et la mise en œuvre des
initiatives stratégiques, l’analyse des données, l’évaluation des performances opérationnelles, la gestion
des ressources et la coordination avec les autres départements de la compagnie.
24
I.1.8.2 Critères de performances :
Les critères de performances de la Direction des Programmes selon les définitions utilisées dans les
réglementations nationales et internationales sont :
• Optimisation du taux d’utilisation des aéronefs et des équipages.
• Minimisation des heures supplémentaires PN (Personnel Naviguant).
• Minimisation des vols de mise en place.
• Minimisation des hébergements et de l’indisponibilité PN (Personnel Navigant ) hors de sa base

mère.
• Taux de satisfaction de la demande.
F IGURE I.3 – Relations avec les autres structures
25
CHAPITRE II
PROBL ÉMATIQUE
Introduction :
La réalisation d’un planning de vols pose un grand problème pour une compagnie aérienne
(notamment AIR Algérie) , pour cela la majorité d’entre elles ont le divisés en deux sous problèmes .
Entre le 20 et le 25 de chaque mois et après avoir reçu la liste des rotations, Air Algérie affiche le
planning de vols qui contient tout le personnel navigant et les vols à effectuer pour le mois à venir.
Cependant, le planning généré par le logiciel utilisé (AIMS) peut contenir des erreurs : le temps
de repos des Personnel navigant n’étant pas toujours pris en considération. Pour remédier à cela, AIR
Algérie a décidé de mettre en place une équipe composée de 12 personnes qui intervient manuellement
pour y apporter des corrections.
L’objectif de ce présent mémoire est d’établir un planning prenant en considération le temps de repos
de personnel navigant et d’éviter le double travail qui génère des coûts supplémentaires.
II.1 Position du problème

La création des plannings dans le domaine de l’aviation est une problématique complexe en raison
de sa grande taille et des contraintes liées à la réglementation du travail. Afin de la simplifier la plupart
des compagnies aériennes ont divisé ce problème en deux sous-problèmes distincts :
II.1.1 La Création de rotation :
Consiste à générer des rotations à partir d’une liste de vols prévus (précédemment proposé), sur une
période donnée. Ce problème est généralement résolu en deux étapes principales :
• Regrouper les vols programmés par la compagnie aérienne en journées de travail ou périodes de
service.
• Enchaı̂ner ces journées de travail de manière à créer des rotations.
26
Chapitre II Présentation de la compagnie Air Algérie
II.1.2 L’Affectation de rotation :
Vise à assigner aux membres d’équipage toutes les rotations prévues, issues de la résolution du
problème de création de rotations, sur une période de temps T . Tout en respectant les contraintes,
réglementaires ,disponibilité , des activités pré-affectées (réunions, congés maladie, stages ou
formations, etc.)et leurs qualifications.
F IGURE II.1 – Processus d’optimisation du programme de vols pour une compagnie aérienne [5]
II.2 Problème d’affectation du personnel navigant de la compagnie

aérienne Air Algérie
Le département ”conception personnel navigant” de la compagnie Air Algérie se consacre
principalement à l’affectation mensuelle du personnel navigant. Cette activité est réalisée en utilisant le
logiciel AIMS.
II.3 Aperçu du logiciel AIMS

AIMS Software est une solution logicielle spécialement conçue pour optimiser les opérations dans
le domaine de l’aviation. Son objectif est d’améliorer l’efficacité, de réduire les coûts et de garantir la
conformité réglementaire. Sans malheureusement prise en considération des réglementations locales de
chaque pays (Algérie dans le cas présent).
La fonction principale du logiciel AIMS consiste à gérer différentes étapes d’adaptation, notamment :
27
Chapitre II Présentation de la compagnie Air Algérie
1. Accrochage entre le mois m et m+1.

2. Introduction des données telles que les visites médicales, les congés, etc.
3. Couverture des vols particuliers (par exemple ALG JAD CZL).
4. Affectation automatique des équipages aux itinéraires de vol (lancement du logiciel).
5. Correction manuelle des erreurs survenues lors du lancement, comme les arrivées tardives ou
les regroupements de repos.
6. Couverture manuelle des vols non affectés par le logiciel aux vols supplémentaires.
7. Finalisation manuelle des programmes équilibrés.
8. Remise des programmes aux chefs de secteurs.
9. Validation des programmes.
10. Affichage.
11. Traitement des réclamations des membres de l’équipage.
Cependant, le logiciel AIMS présente plusieurs inconvénients, notamment :
1 - Non-respect des contraintes : Le logiciel AIMS viole certaines contraintes, comme les night
stops successifs et les arrivées tardives.
2 - Non-équité des heures de vol : Le programme de l’équipage n’est pas équitable en termes
de répartition du temps de vol. Certains membres d’équipages peuvent avoir plus d’heures de
vol que d’autres.
3 - Surcharge de travail : Chaque étape de l’élaboration du programme de l’équipage nécessite
un certain délai. Pour respecter ces délais, il est parfois nécessaire de violer certaines
contraintes. Par exemple, au lieu d’accorder deux vendredis de repos à un membre
d’équipage, on lui accorde seulement un vendredi.
II.4 Conclusion
Ce chapitre a été consacré à la présentation général du problème de planification du personnel
navigant et comment celui-ci est géré par la compagnie air Algérie ,en utilisant le logiciel AIMS qui ne
prend malheureusement pas les contraintes liées au repos du personnel ce qui la contraint à dédier
toutes une équipe à retraiter ses affectations de façon manuel, qui fait l’objet de notre étude.
28
CHAPITRE III
MOD ÉLISATION DU PROBL ÈME
Introduction
Après avoir exposé de manière descriptive le problème d’affection du personnel navigant posé par
la compagnie aérienne Air Algérie et suite à plusieurs recherches, on n’a constaté que ce dernier est bien
connu et déjà traité d’une manière détaillée par la littérature scientifique qui définit toutes les contraintes
et objectifs que les compagnies aériennes peuvent rencontrer, c’est sur ces études qu’on a décidé de
baser notre approche en reprenant ces modèles comme point de départ . Dans ce chapitre, nous nous
concentrerons sur les concepts de base liés à l’optimisation mathématique ainsi que le traitement de
la modélisation du problème d’affectation du personnel navigant, partant du cas général de ≪ Garuda
Indonesia ≫ au cas particulier de ≪ Mle BOUILEF SALIHA ≫ et ≪ Mlle HEMICI MERIEM ≫ , université
de blida ≫.
III.1 Concepts de base
III.1.1 Optimisation mathématique
L’optimisation consiste à rechercher et trouver les solutions les plus performantes parmi un
ensemble de solutions possibles. Un problème d’optimisation mathématique est défini par un espace
de recherche, qui représente l’ensemble des solutions envisageables, un objectif à atteindre et un
ensemble de contraintes à respecter. Dans ce contexte, l’objectif est de trouver la meilleure solution qui
optimise les critères définis, tout en tenant compte des contraintes imposées
III.1.2 Programme linéaire
Un programme linéaire est un problème mathématique qui implique une fonction linéaire à
optimiser, et dont le domaine est défini par un ensemble d’équations ou d’inéquations linéaires. Les
inéquations linéaires qui définissent le domaine sont également appelées contraintes .
Plus précisément, dans un programme linéaire, l’objectif est de trouver les valeurs des variables
29
Chapitre III Modélisation du problème
qui minimisent ou maximisent une fonction linéaire donnée, sous certaines contraintes linéaires. Les
contraintes sont généralement des inéquations de la forme ≤ ou ≥, et elles limitent les valeurs que les
variables peuvent prendre dans le domaine du problème.
Le but du programme linéaire est donc de trouver les valeurs des variables qui satisfont toutes les
contraintes linéaires, tout en optimisant la fonction linéaire définie. Les méthodes de résolution des
programmes linéaires, telles que la méthode du simplexe ou les méthodes de programmation linéaire en
nombres entiers, permettent de trouver une solution optimale dans le domaine défini par les contraintes.
III.1.3 Formule mathématique d’un programme linéaire
Un programme linéaire est formulé comme suit : [5]


 Xn
max(min)Z = cj x j (Fonction Objectif)







 j=1



Sous contraintes :






 Xn
aij xj ≤ bi i ∈ {1..m1 } (Contraintes d’inégalité).





j=1
(P L) n

 X



 aij xj ≥ bi i ∈ {1..m2 } (Contraintes d’inégalité).
 j=1





 Xn
aij xj = bi i ∈ {1..m1 } (Contraintes d’inégalité).







 j=1



x ≥ 0 j = 1..n
j
- (PL) est un programme linéaire à n variables et m contraintes.

- Les éléments cj , aij et bi (i = 1..m ; j = 1..n) sont des constantes prédéfinies et connues.
Z est la fonction objective que l’on cherche à maximiser ou minimiser, et c1 , c2 , ..., cn sont les
coefficients correspondants des variables x1 , x2 , ..., xn .
Les contraintes d’inégalité spécifient que la somme pondérée des variables doit être inférieure ou
égale à une valeur donnée bi , où aij est le coefficient correspondant à la variable xj .
Les autres contraintes d’inégalité peuvent être spécifiées de manière similaire, mais avec des
inégalités inversées (≥) et des valeurs bi correspondantes. Les contraintes d’égalité spécifient que la
somme pondérée des variables doit être égale à une valeur donnée bi .
Les variables xj doivent être non négatives, c’est-à-dire xj ≥ 0, où j est l’indice de la variable.
III.1.4 Complexité algorithmique
La complexité algorithmique est une mesure de l’efficacité d’un algorithme, c’est-à-dire la quantité
de ressources (temps, espace) qu’il nécessite pour résoudre un problème donné. Cette mesure permet
30
de classer les problèmes en fonction de leur difficulté relative.
III.1.4.1 Problème facile
Un problème est considéré comme facile du point de vue de la complexité algorithmique s’il peut
être résolu en temps polynomial. Cela signifie que la quantité de temps nécessaire pour résoudre le
problème est bornée par une fonction polynomiale de la taille de l’entrée.
III.1.4.2 Problèmes difficiles
Les problèmes difficiles sont ceux pour lesquels il n’existe pas d’algorithme efficace connu pour les
résoudre en temps polynomial .Souvent regroupés sous la classe des problèmes NP-complets qui font
référence à des problèmes difficile de les trouver une solution optimale en un temps raisonnable .la
solution peut être vérifiée en temps polynomial, mais pas nécessairement trouvée efficacement.
III.1.5 La Modélisation d’un problème
La modélisation mathématique est essentielle pour résoudre un problème de manière efficace. Elle
permet de représenter le problème de manière claire et compréhensible, offrant ainsi une vision globale
de l’ensemble du problème. Pour réaliser cette modélisation, il est nécessaire de suivre certaines étapes :
1. Identifier les paramètres du problème : Il s’agit des valeurs données ou connues qui
influencent le problème. Ces paramètres peuvent inclure des quantités fixes, des limites de
temps ou d’espace, des contraintes physiques, etc.
2. Identifier les différentes variables : Les variables sont les quantités que nous cherchons à
déterminer ou à optimiser. Elles peuvent être des décisions à prendre ou des paramètres à
ajuster pour obtenir la meilleure solution possible. Il est important de définir clairement les
variables pour formuler correctement le problème.
3. Identifier les contraintes : Les contraintes sont les conditions ou les limites auxquelles la
solution doit se conformer, toute en aident à restreindre l’espace des solutions possibles.
4. Formuler la fonction objectif : La fonction objectif est la mesure quantitative utilisée pour
évaluer la qualité des solutions. Elle peut être une fonction à maximiser ou à minimiser, en
fonction des objectifs spécifiques du problème. Elle est souvent basée sur les variables du
problème et peut prendre en compte les contraintes.
III.2 La modélisation du problème d’affectation du personnel

navigant [5]
Dans le cadre de la modélisation du problème d’affectation de personnel navigant, nous avons
constaté qu’il existe déjà plusieurs études et modèles développés par d’autres chercheurs dans ce
31
domaine. Ces travaux antérieurs ont abordé les différentes contraintes et étapes spécifiques associées à
la gestion du personnel navigant.
Par conséquent, dans cette étude, nous ne procéderons pas à une nouvelle modélisation du problème
d’affection de personnel navigant. Au lieu de cela, nous nous appuierons sur les travaux existants et les
modèles développés par d’autres chercheurs pour analyser et discuter des contraintes et des étapes
spécifiques liées à ce problème.
Parmi les étapes importantes à prendre en compte dans la gestion du personnel navigant, on peut
citer celles spécifiques à ≪ Cas de Garuda Indonesia ≫ ,telles que la certification et la qualification des
pilotes conformément aux réglementations de l’autorité de l’aviation civile indonésienne , la gestion
des horaires de travail pour assurer la conformité avec les règles de durée de service ,ainsi que la
disponibilité des membres du personnel pour leurs affectations , et en tenant compte de la construction
des appariements d’équipage.
De plus, ces contraintes sont liées à la planification des examens médicaux ,du temps de vols , de la
formation (entrainement ) et des jours de congé annuels des équipages de cockpit, ainsi qu’à la
réglementation du travail des équipages de cockpit internationaux, régionaux et nationaux. Les
contraintes spécifiques sont énumérées dans les équations (19), (20), (21) et (22) du modèle
d’optimisation présenté.
D’autre part, le modèle développé par, qui prend en charge les contraintes spécifiques qui y sont
intégrées et qui peuvent inclure des aspects tels que les qualifications nécessaires pour chaque type de
vol, les restrictions de durée de service, les contraintes de disponibilité, les contraintes de rotation des
équipages, etc. L’examen et l’analyse de ces contraintes spécifiques permettront de mieux comprendre
les défis associés à l’affection du personnel navigant et les solutions proposées par le modèle de Blida.
Donc, cette étude se concentre sur l’analyse et la discussion des contraintes et des étapes spécifiques
liées à la gestion du personnel navigant. Nous nous appuierons sur les travaux existants et les modèles
développés par d’autres chercheurs pour examiner les aspects pertinents du problème d’affection du
personnel navigant, en mettant en évidence les contraintes et les solutions proposées par ces études
antérieures.
Sachant que le modèle présenté par : Mlle BOUILEF SALIHA et Mlle HEMICI MERIEM ,dans leurs
mémoire ≪ Modélisation et résolution du problème d’affectation de personnel navigant ≫ , Ait abordé
des problèmes similaires à notre étude comme suit [5] :
32
III.2.1 Notation et définition
III.2.2 Notation des indices
i : un personnel navigant.
j : un crew route (rotation).
l : un jour du mois.
III.2.3 Notation des ensembles
N : ensemble des personnels navigants N = {1, 2, ...., n}.

M : ensemble des crew route M = {1, 2, ...., m}.
L : ensemble de jours du mois L = {1, 2, ...., n}.
K : ensemble des alertes programmées dans le mois.
S : ensemble des crew route chevauchés.
III.2.4 Notation des paramètres
Cj : le nombre du personnel navigant nécessaire pour effectuer j.

dj : le temps de vol du crew route j.
dmax : le temps de vol maximum par mois pour tous navigant.
tj : la longueur du crew route j (donnée en jour).
III.2.5 Définition des variables
Soient les variables suivantes :


 1 si le personnel navigant i est effecté au crew rout j.
xij = (III.1)
 0 sinon

 1 si la rotation r chevauchée avec la rotation s.
prs = (III.2)
 0 sinon

 1 si la rotation j commence le jour l.
qjl = (III.3)
 0 sinon
On définit la variable réelle :

Ypq ∈ R+ : qui représente la différence en temps de vol mensuel entre le navigant p et q.
33
III.2.6 Définition des contraintes
III.2.6.1 Contrainte de capacité
Cette contrainte assure que chaque crew route j est couvert en l’affectant à un nombre Cj du PN.
X
xij = Cj ∀j ∈ M
i∈N
On distingue deux cas :
• Cj = 1 pour le PNT.
• Cj ≥ 1 pour le PNC.
III.2.6.2 Contrainte limitant le temps de vol
Cette contrainte assure que pour chaque PN le temps de vol mensuel ne doit pas dépasser dmax .
X
dj xij ≤ dmax ∀i ∈ N
j∈M
III.2.6.3 Contrainte limitant le temps de repos
Cette contrainte assure que chaque PN qui travaille six jours consécutifs, doit être libre le septième
jour.
X p+6
X
tj xij qjl ≤ 6 ∀p = 1.24 ∀l = 1, L ∀i = 1, n
j∈M l=p
III.2.6.4 Contrainte relative au non-chevauchement
Cette contrainte assure que deux crew route ne doivent pas être chevauchés.
X
xij pjs xis (s − j) = 0 ∀j ∈ M
s∈S
III.2.6.5 Contrainte relative aux alertes
Cette contrainte assure que le nombre total des alertes programmées mensuellement ne doit pas
dépasser quatre pour chaque personnel navigant.
X
xij ≤ 4 ∀i ∈ N
j∈k
On distingue deux cas :

- Quatre alertes relatives au structure du type ≪S≫ pour le PNT.
- Quatre alertes relatives au structure du type ≪AS≫ pour le PNC.
34
III.2.7 La fonction objectif
L’objectif est de minimiser la différence en temps de vol entre tous les couples de navigants
L’expression de la fonction objectif est la suivante :
n−1
X n
X m
X
M in(Z) = dj (xpj − xqj )
p=1 q=p+1 j=1
On introduit la variable réelle positive :
m
X
Ypq = dj (xpj − xqj ) Avecp = 1...(n − 1), q = (p + 1)...n
j=1
Ainsi la fonction objectif est formulée sous la forme suivante :

n−1
X n
X
M in(Z) = Ypq
p=1 q=p+1
III.2.8 le modèle mathématique
Le modèle peut s’écrire comme un programme linéaire à variables mixtes sous la forme suivante :

 n−1
X X n

M in(Z) = Ypq






 p=1 q=p+1



 Xm
∀j = 1..m



 xij = cj

i=1



m



 X



 dj xij ≤ dmax ∀i = 1, n
j=1



(P L) X

 xij ≤ 4 ∀i = 1, n

 j∈K


 p+6

 X m X

x t x ≤6 ∀p = 1.24 ∀l = 1, L ∀i = 1, n

ij j ij






 j=1 l=p

 X
pjs xis (s − j) = 0 ∀i = 1, n ∀j = 1, m



 xij

 s∈S




∀x ∈ {0, 1} , ∀p ∈ {0, 1} , ∀q ∈ {0, 1}

ij js jl
L’objectif est de minimiser la différence en temps de vol entre tous les couples navigants. Dans notre
cas nous avons les données suivantes : nombre de P N = 1000 Nombres de vols par mois = 6028
35
III.2.9 Taille du problème
(A) Taille de variables :

T V = m × (n + |S| + |L|)
Où :
• m représente le nombre de variables mixtes dans le modèle,

• n représente le nombre de variables discrètes dans le modèle,
• |S|) représente la taille de l’ensemble S de variables continues,
• |L|) représente la taille de l’ensemble L de variables binaires.
(B) Taille des contraintes
T C = 2 × n × m × (|S| + |5|) + n × (|K| + 3) + m
• n représente le nombre de variables du modèle,

• m représente le nombre de contraintes du modèle,
• |S|) représente la taille de l’ensemble S,
• |K|) représente la taille de l’ensemble K.
La formule indique que la taille des contraintes dépend du nombre de variables, du nombre de
contraintes, de la taille de l’ensemble S et de la taille de l’ensemble |K|).
Les valeurs |S|) et |K|) peuvent représenter la taille des ensembles de contraintes spécifiques au
problème en question.
Cette formule nous permet de calculer la taille totale des contraintes dans le modèle en fonction
des paramètres spécifiques du problème résolu.
Concernant notre cas en va citer une contrainte non traité dans les deux cas précédents relative au
repos du personnel navigant (base / horsbase).
F IGURE III.1 – Contrainte de repos PN base/ hors base
Dans ce modèle de diagramme, nous avons deux cas : le cas où l’avion est à la base et le cas où l’avion
est hors de la base ( Les bases mentionnées sont ALG, ORN, AAE et CST).
36
Nous avons constaté qu’il y a une contrainte de repos pour les pilotes en fonction de l’heure d’arrivée
et de départ de l’avion. Tels que :
Si l’avion arrive avant 21h et démarre après 5h du matin, le personnel navigant doit se reposer
pendant 12 heures s’il est à la base, et 10 heures s’il n’est pas à la base.
Si l’avion arrive après 21h et démarre après 5h du matin, le pilote doit se reposer pendant 14 heures
s’il est à la base, et 12 heures s’il n’est pas à la base.
Enfin, si l’avion arrive avant 21h et part avant 5h du matin, le pilote doit se reposer pendant 14 heures
s’il est à la base, et 12 heures s’il n’est pas à la base.
Ainsi, la fonction objective de notre modèle vise à minimiser les erreurs lors de l’affectation des
pilotes aux vols. Notre objectif est d’optimiser l’affectation des pilotes en tenant compte des contraintes
de repos et de réduire au maximum les erreurs qui pourraient survenir pendant le processus
d’affectation.
De plus, la modélisation de cette contrainte spécifique peut varier en fonction des détails spécifiques
du modèle et des contraintes supplémentaires qui pourraient être incluses dans le problème d’affection
des pilotes.
37
III.3 Conclusion
En conclusion, les deux modèles étudiés se concentrent sur la rotation des équipages, mais ils ont
des objectifs distincts qui se différents des nôtres . Par conséquent, il n’a pas été possible d’adapter
directement ces modèles pour prendre en compte les contraintes spécifiques telles que l’obligation d’une
seule rotation par équipage, la limite de temps de vol mensuel, le jour de repos après six jours de travail
consécutifs, et les temps de repos en fonction de l’heure d’arrivée et de départ de l’avion ainsi que de la
base où se trouve l’équipage.
Notre recherche se concentre sur la résolution de ces contraintes spécifiques afin de proposer des
solutions adaptées au problème d’affection de personnel navigant. Ainsi, il n’est pas nécessaire de
réinventer entièrement les modèles existants, car notre objectif principal est de développer des
approches et des méthodes de résolution qui répondent aux contraintes spécifiques (contrainte de
repos).
Ainsi, nous envisageons de proposer des solutions efficaces pour la gestion de l’affection du
personnel navigant en tenant compte des contraintes mentionnées précédemment. Cela permettra
d’optimiser la planification des équipages, de respecter les temps de repos requis, de garantir le respect
des limites de temps de vol mensuel et d’améliorer globalement l’efficacité de l’affectation des pilotes
aux vols.
Donc, notre recherche vise à résoudre les contraintes spécifiques liées à l’affection du personnel
navigant en considérant les différentes bases, les temps de vol, les temps de repos et autres contraintes
pertinentes. Notre objectif ultime est de fournir des solutions pratiques et efficaces pour améliorer la
gestion des équipages et minimiser les erreurs lors de l’affectation des pilotes aux vols.
38
CHAPITRE IV
M ÉTHODE DE R ÉSOLUTION
Introduction :
Après avoir vu le problème d’affectation du personnel navigant ainsi que sa modélisation dans les
chapitres précédent on a constaté qui se fait partie des problèmes complexe qu’y sont difficile à résoudre
par les méthodes exacte à cause de la grande taille de ces données.
Etant donné l’importance de ces problèmes, de nombreuses méthodes de résolution ont été
développées en recherche opérationnelle (RO) (spécialement en optimisation combinatoire ) et en
intelligence artificielle (IA). Ces méthodes peuvent être classées sommairement en deux grandes
catégories : les méthodes exactes (complètes) qui garantissent la complétude de la résolution et les
méthodes approchées (incomplètes) qui perdent la complétude pour gagner en efficacité.
Dans ce chapitre nous allons présenter une méthode approchée pour la résolution de notre problème,
tout en passant d’abord par les différents concepts et techniques de résolutions.
IV.1 Technique de base et méthodes de résolution
IV.1.1 L’optimisation combinatoire
L’optimisation combinatoire est un domaine essentiel qui fait appel à diverses techniques issues des
mathématiques discrètes et de l’informatique. Il consiste à trouver la meilleure solution dans un
ensemble discret de solutions réalisables. Généralement, cet ensemble est fini mais présente une
cardinalité très élevée.
Problème d’optimisation combinatoire : Un problème d’optimisation combinatoire est défini par un

ensemble d’instances .A chaque instance du problème est associé un ensemble discret de solutions S, un
sous-ensemble X de S représentant les solutions admissibles (réalisables) et une fonction de coût f (ou
fonction objectif) qui assigne à chaque solution s ∈ X le nombre réel (ou entier) f (s) [7].
39
Chapitre IV Méthode de résolution
IV.1.2 Résolution d’un problème d’optimisation combinatoire :
Pour résoudre un problème d’optimisation combinatoire, il est essentiel d’examiner trois aspects
spécifiques :
1. L’expression de l’objectif à optimiser.
2. La définition de l’ensemble des solutions réalisables.
3. Le choix de la méthode d’optimisation à utiliser.
Les deux premiers points sont liés à la modélisation du problème, tandis que le troisième concerne
la recherche d’une solution efficace. Afin de définir l’ensemble des solutions réalisables, il est nécessaire
de formuler de manière précise toutes les contraintes du problème. Cela ne peut être réalisé qu’en ayant
une connaissance approfondie du problème étudié et de son domaine d’application.
IV.1.2.1 Les méthodes d’optimisation combinatoire
Les méthodes d’optimisation combinatoire peuvent être regroupées en deux catégories principales :
- les méthodes exactes.
- les méthodes approchées.
F IGURE IV.1 – Classifications des méthodes d’optimisation combinatoire [4]
40
IV.1.2.2 Les méthodes exactes
Des approches qui garantissent de trouver la solution optimale d’un problème d’optimisation. Ces
méthodes reposent sur des algorithmes mathématiques qui explorent de manière exhaustive
l’ensemble des solutions possibles. Elles sont utilisées pour résoudre des problèmes de petite taille ou
des problèmes spécifiques pour lesquels une solution optimale est nécessaire.. Parmi ces algorithmes,
on peut citer :
- Les méthodes de recherche arborescente : telles que la méthode Branch and Bound (Procédure
par séparation et évaluation progressive) , qui consistent à énumérer les solutions en utilisant
des propriétés spécifiques du problème afin d’éliminer les solutions partielles qui ne mènent
pas à la solution souhaitée. Cette approche permet généralement d’obtenir rapidement la
solution optimale.
- La programmation dynamique, qui consiste à résoudre un problème d’optimisation en le
divisant en sous-problèmes et en le résolvant séparément. Une solution optimale est alors
obtenue en combinant les solutions optimales des sous-problèmes résolus de manière
optimale.
- La programmation linéaire, qui vise à minimiser ou maximiser une fonction objectif linéaire
soumise à des contraintes linéaires exprimées sous forme d’équations ou d’inéquations. Si des
variables discrètes doivent être utilisées dans la modélisation du problème (contraintes
d’intégrité), on parle alors de programmation linéaire en nombres entiers (PLNE).
Ainsi, ces différentes méthodes d’optimisation combinatoire offrent des approches variées pour
résoudre efficacement des problèmes d’optimisation.
IV.1.2.3 Les méthodes approchées (heuristiques)
Les méthodes approchées : également appelées méthodes heuristiques, sont des approches utilisées
en optimisation pour trouver des solutions proches de l’optimal sans garantir l’optimalité. Elles sont
souvent utilisées pour résoudre des problèmes complexes pour lesquels trouver une solution exacte
est difficile ou coûteux en termes de temps de calcul. Les méthodes approximatives sont généralement
basées sur des heuristiques, des règles empiriques ou des techniques d’optimisation locale pour trouver
rapidement des solutions acceptables. Elles sont plus rapides que les méthodes exactes, mais peuvent
ne pas atteindre la solution optimale.
Parmi les heuristiques couramment utilisées, nous avons :

1. Heuristique de construction : Les méthodes constructives sont des approches itératives qui
construisent progressivement une solution. Elles commencent avec une solution partielle vide
et, à chaque étape, tentent d’étendre la solution partielle de l’étape précédente. Ce processus
est répété jusqu’à ce que la solution complète soit obtenue.
41
2. Heuristique d’amélioration : Les méthodes d’amélioration visent à augmenter la valeur des

solutions existantes, qui sont souvent le résultat d’une méthode constructive. Elles explorent
l’espace des solutions pour trouver des améliorations locales en apportant des modifications à
la solution courante. Le choix entre les méthodes exactes et approximatives dépend des
contraintes de temps, des exigences de précision et de la taille du problème à résoudre.
IV.1.2.4 La métaheuristique
Une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes

d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l’ingénierie ou
de l’intelligence artificielle) pour lesquels on ne connaı̂t pas de méthode classique plus efficace.
Parmi ces méthodes : [7]

1. Recuit simulé : La méthode de recuit simulé [KIR 83, CER 85] s’inspire du processus de
recuit physique. Ce processus utilisé en métallurgie pour améliorer la qualité d’un solide
cherche un état d’énergie minimale qui correspond à une structure stable du solide .En
partant d’une haute température à laquelle le solide est devenu liquide, la phase de
refroidissement conduit la matière liquide à retrouver sa forme solide par une diminution
progressive de la température. Chaque température est maintenue jusqu’à ce que la matière
trouve un équilibre thermodynamique. Quand la température tend vers zéro, seules les
transitions d’un état à un état d’énergie plus faible sont possibles.
2. La recherche tabou : La méthode tabou a été développée par Glover [GLO86]et
indépendamment par Hansen [HAN 86] . Cette méthode fait appel à un ensemble de règles et
de mécanismes généraux pour guider la recherche de manière intelligente au travers de
l’espace des solutions. A l’inverse du recuit simulé qui génère de manière aléatoire une seule
solution voisine s′ ∈ N (s) à chaque itération, tabou examine un échantillonnage de solutions
de N(s) et retient la meilleure s’ même si s′ est plus mauvaise que s. La recherche tabou ne
s’arrête donc pas au premier optimum trouvé.
3. Algorithmes génétiques : Les algorithmes génétiques classiques introduits par Holland
s’appuient fortement sur un codage universel sous forme de chaı̂nes 0/1 de longueur fixe et
un ensemble d’opérateurs génétiques : la mutation, l’inversion et le croisement. Un individu
sous ce codage, appelé un chromosome, représente une configuration du problème. Les
opérateurs ≪ génétiques ≫ sont définis de manière à opérer aléatoirement sur un ou deux
individus sans aucune connaissance sur le problème.
En conséquent, Les méta heuristiques sont généralement des algorithmes stochastiques itératifs, qui
progressent vers un optimum global (c’est à dire l’extremum global d’une fonction), par échantillonnage
d’une fonction objectif. Elles se comportent comme des algorithmes de recherche, tentant d’apprendre
les caractéristiques d’un problème afin d’en trouver une approximation de la meilleure solution (d’une
manière proche des algorithmes d’approximation).
42
Il existe un grand nombre de métas heuristiques différents, allant de la simple recherche locale à des
algorithmes complexes de recherche globale. Ces méthodes utilisent cependant un haut niveau
d’abstraction, leur permettant d’être adaptées à une large gamme de problèmes différents.
IV.2 Approche de résolution pour le problème d’affectation du

personnel navigants
IV.2.1 Méthode de résolution
Afin de répondre et mettre en évidence le problème d’affectation de personnel navigant pour la

compagnie aérien Air Algérie, nous avons choisi d’adopter une heuristique d’affectation. Pour les
raisons suivantes l’heuristique :
- Les heuristiques facilitent l’adaptation de notre problème en fonction des contraintes imposé.
- Temps de calcul réduit : L’utilisation d’heuristiques permet de réduire significativement les
temps de calcul (qui est une tâche très importante pour une compagnie aérienne) , par rapport
à des méthodes exactes.
- Capacité à gérer les perturbation : les heuristiques peuvent être adaptées pour prendre en
compte les perturbation d’une compagnie aérienne (retards, annulations de vols..) , et générer
des solutions de replanification efficace dans des courts délais.
IV.2.2 Adaptation de l’euristique au problème
Pour mieux comprendre les différents structures , étapes de notre heuristique utilisé voyons le
diagramme suivant :
43
L’algorithme suivant décrit le fonctionnement de cette méthode :
• Étape 1 : définir les donnée qu’on a au début ≪ tableau 1 ≫ ( il doit contenir

tout les informations concernant les crew routes) ≪ tableau 2 ≫ ( dans le quel on
trouve toutes les informations concernant les équipages) ,une liste contenant les base
connue(ALG,ORN,AAE,CST).
• Étape 2 : vérifiée a chaque fois si l’aéroport d’arrivée (STA) correspond a une base connue
(‘liste des bases’) .
• Étape 3 : obtention du nombre maximal d’heures de travail a partir de ce tableau de

contrainte :
Durée maximale du temps de service de Vol

Heure programmée
Nombre d’étapes
du début du TSV
1 2 3 4 5*
06 h 00 - 07 h 59 12 h 00 11 h 45 11 h 30 11 h 15 *
08 h 00 - 12 h 59 12 h 00 12 h 00 11 h 45 11 h 45 *
13 h 00 - 15 h 59 11 h 45 11 h 30 11 h 15 10 h 45 *
16 h 00 - 19 h 59 10 h 45 10 h 30 10 h 00 * *
TABLE IV.1 – TSV * Temps De Service De Vol
• Étape 4 : obtention du temps de repos entre une arrivée et un départ en tenant compte de
la contrainte base et hors base suivant le diagramme suivant :
F IGURE IV.2 – Contrainte de repos PN base/ hors base
• Étape 5 : Lire les donnée des vols et des équipages a partir des fichiers Excel (crée des objets
vol et équipages)
• Étape 6 : on fait l’affectation des équipages au vol en tenant compte de tout les contraintes
vu précédemment .
• Étape 7 : on obtient un fichier finale (Data Rame) contenant les équipages attribué a chaque
vol.
44
IV.3 Conclusion
Afin de prouver l’efficacité de l’approche de résolution proposée pour la réalisation d’affectations
de personnels navigants (programme d’équipage), des tests ont été menés et présentés dans le dernier
chapitre.
45
CHAPITRE V
IMPL ÉMENTATION
Introduction
Dans ce chapitre, nous aboutissons à l’étape finale de notre travail, à savoir l’élaboration d’un
logiciel aussi convivial que possible .Nous y expliquerons par ailleurs son fonctionnement afin de
faciliter son utilisation et mettrons en application la méthode de résolution proposée à travers un
exemple. L’implémentation de l’algorithme sera effectuée sur le logiciel PYTHON
V.1 Présentation et avantages du langage choisi [3]
V.1.1 Présentation de l’environnement ≪ python ≫
Le langage Python est un langage de programmation objet interprété, il offre un environnement

complet de développement comprenant un interpréteur performant et de nombreux modules. Un atout
indéniable est sa disponibilité sur la grande majorité des plates-formes informatiques courantes : Mac
OS X, Unix, Windows ; Linux, Androı̈de, IOS
F IGURE V.1 – Python
46
Chapitre V Implémentation
V.1.2 Les avantages du logiciel choisi
Python possède plusieurs points forts qui font de lui le langage tendance et le plus utilisé en ce
moment. Rien qu’en observant la définition que nous venons d’évoquer, certains de ces avantages
ressortent déjà. Ici, nous allons les approfondir afin que l’on puisse mieux comprendre la raison pour
laquelle les développeurs apprécient autant ce langage.
1. Un langage open source multi-plateformes.
2. Facilité d’apprentissage et de lecture : Python a une syntaxe claire et concise qui le rend
facile à apprendre et à lire. Sa simplicité en fait un excellent choix pour les débutants en
programmation.
3. Large gamme de bibliothèques et de Framework : Python dispose d’une vaste collection de
bibliothèques et de Framework qui facilitent le développement de diverses applications. Par
exemple, NumPy, Pandas et Matplotlib sont largement utilisés pour le traitement des données
et la visualisation, tandis que Django et Flask sont populaires pour le développement web.
4. Compatibilité multiplateforme : Python est un langage interprété, ce qui signifie qu’il peut
être exécuté sur différentes plates-formes telles que Windows, MacOs et Linux sans avoir
besoin de modifications importantes du code.
5. Grande communauté de développeurs : il bénéficie d’une communauté de développeurs
active et dynamique. Vous pouvez trouver une multitude de ressources, de tutoriels, de
documentation et de forums en ligne pour obtenir de l’aide et partager vos connaissances.
6. Polyvalence : souvent utilisé dans de nombreux domaines, tels que le développement web,
l’apprentissage automatique, l’analyse de données, l’automatisation des tâches, la science des
données, l’Internet des objets (IoT) et bien d’autres. Sa polyvalence en fait un choix attrayant
pour de nombreux projets.
7. Intégration aisée avec d’autres langages : Python peut être facilement intégré avec d’autres
langages de programmation, ce qui permet aux développeurs d’utiliser des bibliothèques
existantes et de tirer parti des fonctionnalités spécifiques à chaque langage.
V.2 Implementation de l’heuristique

Dans cette partie sera présentée l’implémentation de notre heuristique vue en chapitre précèdent en
utilisant le logiciel ≪PYTHON≫ .
Input :
On aura comme input les données suivantes :
47
⋇ Le planning des vols mensuel sous le format Excel (.xlsx) suivant
F IGURE V.2 – Extrait du planning des vols hebdomadaires .
48
⋇ Les noms des équipages , des crew routes et le nombre des personnels navigant
(NBRE PNC) sous le format Excel (.xlsx) suivant
F IGURE V.3 – Extrait du tableau des équipages.
49
⋇ Fonctions élémentaire
L’algorithme fait appel à 3 fonctions que l’on a défini comme suit :
. Assign pilots to vols
Cette Fonction prend trois arguments :

- Vols : sous forme d’une liste d’objets, << vols >>.
- Pilotes : sous forme d’une liste d’objets, << pilots >>.
- Les contraintes du problème.
Cette fonction vise a attribué des pilotes aux vols en respectant certaines contraintes.
. Get rest hours
Si l’indicateur de base (l’aéroport d’arrivée) connue a true cette Fonction permet d’obtenir les heures
de repos a partir des contrainte (Figure :Contrainte de repos PN base/ hors base).
. Get rest hours
si l’indicateur de base connue a False cette Fonction permet d’obtenir les heures de repos (dans le cas
hors base) a partir des contrainte
1. Get max work hours : cette fonction permet d’obtenir le nombre maximal d’heures de travail
de chaque équipage a partir des contrainte (figure ?)
2. Process flight pilotes : le principe de cette fonction est le suivant :
- Lire les donnée des vols et des équipages à partir de fichiers Excel.
- Créer des objets vol pilot.
- Fait appeler la fonction ¡¡ assgn pilot to vol ¿¿.
Nous obtenons comme résultat un Data Frame qui contient tous les pilotes attribués à chaque
vols.
50
Output :
On aura comme output un Fichier qui contient l’affectation équitable (prend en considération le temps
de repos nécessaire) de chaque personnels navigant aux vols.
F IGURE V.4 – TSV * Temps De Service De Vol.
V.3 Conclusion
Dans ce chapitre, nous avons principalement présenté le logiciel Python et ses fonctionnalités pour
mettre en œuvre notre application de travail. Nous avons ensuite interprété les résultats obtenus par
rapport aux résultats du logiciel de la compagnie aérienne Air Algérie ≪ AIMS ≫.
Par la fin, nous avons pu répond aux besoins de la compagnie aérienne AIR Algérie , d’avoir un
planning de vols avec une affectation de personnels navigant qui implique les différentes contraintes de
repos des personnels navigants .
51
CONCLUSION G ÉN ÉRALE
≪ On dit souvent que le but d’une vie n’est pas de surpasser les autres, mais bien de se surpasser
soi-même ≫.
En effet ce mémoire d’étude s’est focalisé sur la problématique de la planification du personnel

navigant au sein de la compagnie aérienne Air Algérie. Nous avons identifié que le logiciel utilisé,
AIMS, ne prend malheureusement pas en compte les contraintes relatives au repos du personnel, ce
qui oblige une équipe à effectuer manuellement les affectations. L’objectif central de notre recherche
était donc de résoudre ces contraintes spécifiques en prenant en considération les différentes bases, les
temps de repos et autres contraintes pertinentes. Notre but ultime était de proposer des solutions
pratiques et efficaces afin d’améliorer la gestion des équipages et de minimiser les erreurs lors de
l’affectation des personnels navigant aux vols.
Afin de répondre à cet objectif, nous avons développé une méthode approchée en nous appuyant sur
divers concepts et techniques de résolution. Par ailleurs, nous avons mis en évidence les fonctionnalités
du logiciel Python pour mettre en œuvre notre application de travail. Les résultats obtenus ont été
analysés et comparés par rapport aux résultats du logiciel AIMS utilisé par Air Algérie.
Grâce à cette approche, nous avons pu répondre aux besoins spécifiques de la compagnie aérienne
Air Algérie en proposant un planning de vols qui prend en compte les contraintes de repos du personnel
navigant. En optimisant la gestion des équipages, nous avons pu réduire la dépendance à l’intervention
manuelle .
52
BIBLIOGRAPHIE
[1] MANEX (Manuel d’exploitation d’air Algérie )
[2] M. Sakarovich, ≪ Optimisation Combinatoire. Méthodes mathématiques et Algorithmiques. Tome 2 : Graphe

et programmation linéaire ≫ , Paris, Hermann 1984.
[3] ≪ISN – Informatique et Sciences du Numérique.≫ ,Lycée Gustave Eiffel ,2017.
[4] Baifouh Belkacem & Tabharit Said, ≪Optimisation du programme de vols d’avions, et l’affectation du
personnel navigants pour TASSILI Airlines ≫ , Mémoire de fin de master,Université des Sciences et de
la Technologie Houari Boumediene, Oran, 2022.
[5] Boulief Saliha & Hemici Meriem, ≪Modélisation Et Résolution Du Problème D’affectation Du Personnel
Navigant.≫ , Mémoire de fin de master, Université de Saad Dahleb Blida ,2017.
[6] Slimani Zina & Cheballah Kahina, ≪ Optimisation et restructuration d’un programme d’exploitation
d’une base de la compagnie Air Algérie ≫ , Mémoire de fin de master,Université Mouloud Mammeri,
Tizi-Ouzou ,2016.
[7] Philippe Galinier& Michel Habib & Jin-Kao Hao≪Méthaheuristiques pour l’optimisation combinatoire
et l’affectation sous contraintes ≫, article, Vol : No. 1999
53

Optimisation Des Crew-Routes Multibase

Transféré par

Droits d'auteur :

Formats disponibles

Optimisation Des Crew-Routes Multibase

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Optimisation Des Crew-Routes Multibase

Transféré par

Droits d'auteur :

Formats disponibles

République Algérienne Démocratique et Populaire

Ministère de l’Enseignement Supérieur et de la Recherche Scientifique

Département de Recherche Opérationnelle

Spécialité : Recherche Opérationnelle

Option : Engineering en Recherche Opérationnelle (ERO)

Optimisation des crew-routes multibase

Soutenu le : 13/07/2023, devant le jury composé de :

Président : Mme TIACHACHAT Meriem USTHB

Code Mémoire : 08/ERO/23 .

J e dédie ce modeste travail :

A mon cher YOUCEF , je souhaite te dédier ces mots remplis de reconnaissance et

A mes chères tantes ≪ HAKIMA ≫ et ≪ HACIBA ≫.

A u Département de Recherche opérationnelle.

S ans oublier ma meilleure amie pour toujours ≪ NAZIHA ≫

J e dédie le fruit de mes 22 ans d’études ,≪ DALIA ≫.

J e Dédiée ce modeste travail :

Résumé : Ce travail est consacré à la résolution du problème de planification d’équipages, au

Chapitre I Présentation De La Compagnie Aérienne 15

Chapitre III Modélisation du problème 29

Chapitre IV Méthode de résolution 39

I.1 Organigramme de la compagnie [6] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

III.1 Contrainte de repos PN base/ hors base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

IV.1 Classifications des méthodes d’optimisation combinatoire [4] . . . . . . . . . . . . . . . . 40

I.1 Tableau siège social [4] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

IV.1 TSV * Temps De Service De Vol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

• Personnel navigants (membres d’équipage) : Le personnel navigants d’une compagnie aérienne

✓ Dans le deuxième chapitre, on se concentre sur l’explication de la problématique.

✓ Le quatrième chapitre contient les méthodes de résolution en recherche opérationnelle, et à la fin

✓ Le cinquième chapitre porte sur l’implémentation de notre méthode.

PR ÉSENTATION DE LA COMPAGNIE A ÉRIENNE

I.1 Présentation de la compagnie Air Algérie

En 1963, à la suite de l’indépendance de l’Algérie, la compagnie a été nationalisée et renommée Air

I.1.2 Statut juridique

Conformément à la législation en vigueur, en particulier l’ordonnance n° 95-25 du 25 février 1995

Dénomination AIR ALGERIE

TABLE I.1 – Tableau siège social [4]

I.1.3 Missions et prestations de la compagnie

— courriers afin de suivre la croissance économique du pays.

I.1.4 Réseaux, destinations et bases

Réseau Villes du réseau intérieur Algérie (RIA) Code

TABLE I.2 – Le réseau national d’Air Algérie [4]

Réseau Pays Escales

AFRIQUE Mali Bamako

TABLE I.3 – Réseaux internationaux d’Air Algérie [4]

I.1.5 Ressources de la compagnie

I.1.5.1 Moyens humains

I.1.5.2 Moyens matériels (La flotte)

Types d’avions Nombres Capacités

TABLE I.4 – La flotte de la compagnie Air Algérie

I.1.6 Terminologie et abréviations : [6]

- DOA Direction des Opérations Aériennes.

I.1.7 Hiérarchie et structure générale de la compagnie

La structure organisationnelle de l’entreprise repose sur trois fonctions principales : commerciales,

F IGURE I.1 – Organigramme de la compagnie [6]

I.1.8 Présentation de l’organisme d’accueil

I.1.8.1 Présentation de la direction programme

• La Programmation Flotte : Rotation Avions.

• La Programmation PN (Personnel Naviguant) : Rotation équipages et affectation PN (Personnel

• Les Ressources Humaines.