[PDF] MODELISATION ET RESOLUTION DUN PROBLEME D

View - Download MODELISATION ET RESOLUTION DUN PROBLEME D

Previous PDF

Next PDF

3 e

Conférence Francophone de MOdélisation et SIMulation "Conception, Analyse et Gestion des Systèmes Industriels»

MOSIM'01 - du 25 au 27 avril 2001 - Troyes (France) - 215 -

MODELISATION ET RESOLUTION D'UN PROBLEME

D'AFFECTATION D'EQUIPAGES

EN TRANSPORT AERIEN

Farah ZEGHAL Michel MINOUX

Université Paris-6 Université Paris-6

4 Pl. Jussieu, 75005 4 Pl. Jussieu, 75005

Paris, France Paris, France

e-mail: Michel.Minoux@lip6.fr

RÉSUMÉ. Un des problèmes de base dans la gestion du personnel navigant (technique ou commercial) dans les

compagnies aériennes est de déterminer quels personnels affecter à chacun des vols d'un programme de vols connu sur

une période donnée (une semaine, un mois,...). Nous nous intéressons dans ce travail au cas du personnel navigant

technique (pilotes, copilotes et instructeurs). On montre comment le problème peut se modéliser comme un programme

linéaire en nombres entiers de grandes dimensions où les variables représentent l'affectation des différentes catégories

du personnel à des périodes de service. La fonction objectif consiste à minimiser le coût total des heures

supplémentaires nécessaires pour réaliser le programme de vols. Une application concrète au cas de la gestion du

personnel navigant technique (PNT) de la compagnie aérienne tunisienne TUNISAIR est présentée. L'utilisation d'un

logiciel commercial de résolution de programmes linéaires (CPLEX) permet d'obtenir des solutions optimales exactes

pour des problèmes de taille réelle.

MOTS-CLES : programmation linéaire en nombres entiers, affectation de personnels, optimisation, transport aérien.

1. INTRODUCTION

La gestion du personnel navigant (technique PNT ou commercial PNC) dans une compagnie aérienne représente un enjeu économique très important : la qualité des programmes de vols de chaque PN influe sur la rentabilité de l'activité de la compagnie. Plus le nombre d'heures supplémentaires est élevé, plus le coût total du PN est important. La construction des programmes de vols du personnel navigant est un problème rencontré par toutes les compagnies aériennes qui, pour réaliser leurs vols, doivent déterminer quels personnels navigants affecter à chacun des vols programmés. De par sa taille, le problème d'affectation est rendu difficile par les diverses contraintes réglementaires et sociales relatives, d'une part à l'enchaînement des vols (durée maximale de vol, durée maximale de service, durée maximale de vol de nuit, durée minimale de repos pré-courrier et/ou post- courrier,...) et , d'autre part à l'affectation du PN (qualifications exigées, ancienneté, composition de l'équipage,...). Ce type de problème est généralement décomposé en deux sous-problèmes formulés et résolus de façon indépendante :a) Construire une liste de séquences de vols appelées périodes de service, couvrant l'ensemble des vols de

la période de planification considérée. Chaquepériode de service est suivie d'une période de repos

post-courrier et peut être, dans certains cas, précédée d'une période de repos pré-courrier. Les vols d'une période de service s'enchaînent (la ville d'arrivée d'un vol est la ville de départ du vol qui le suit) et sont séparés par des temps d'escales. Chaque période de service construite doit impérativement satisfaire les diverses contraintes réglementaires et sociales. Notons qu'un même vol peut être couvert par plusieurs périodes de service.b) Attribuer nominativement les personnels requis à des périodes de service construites en (a) en tenant compte, là aussi, de diverses contraintes (qualifications du personnel, composition de l'équipage, congés, périodes de formation, ...), et ce, de façon à ce que chacun des vols donnés soit couvert. Les approches proposées jusqu'ici dans la littérature partent d'une formulation du problème en termes de partitionnement ou de recouvrement de grandes dimensions, à laquelle est ensuite appliqué le principe de génération de colonnes (cf. Lavoie, Minoux & Odier

1988, Hoffman & Padberg 1993, Desaulniers et co-

auteurs 1997, Stojkovic, Soumis & Desrosiers 1998, Barnhart & Shenoi 1998). Dans le présent article, nous explorons une autre approche utilisant une formulation directe du problème en tant que programme linéaire en nombres entiers de structure générale, c'est-à-dire MOSIM'01 - du 25 au 27 avril 2001 - Troyes (France) - 216 - combinant différents types de contraintes (et pas exclusivement des contraintes de partitionnement ou de recouvrement). Le cadre applicatif retenu ici est celui de l'affectation du personnel navigant technique (PNT) au sein de la compagnie aérienne tunisienne TUNISAIR. Nous commencerons, dans une première partie, par présenter la problématique générale de l'affectation de personnels navigants techniques, puis, dans une seconde partie, nous exposerons la formulation mathématique du modèle. Les résultats expérimentaux obtenus sur divers exemples réels seront discutés dans une troisième partie.

2. PRÉSENTATION DU PROBLÈME

Le problème d'affectation d'équipages peut être défini comme suit : Sur une période donnée (une semaine, un mois,...), une compagnie aérienne doit assurer un certain nombre de vols, et ce en affectant le personnel approprié (en nombre, et en qualification) à des périodes de service tout en respectant une série de contraintes. Une première étape consiste donc à construire les différentes périodes de service auxquelles les personnels navigants techniques pourront être affectés. La seconde étape est celle de la recherche d'une affectation des personnels aux périodes de service.

2.1. Étape 1: construction des périodes de service

Compte tenu des diverses contraintes réglementaires (durée maximale de vol, durée maximale de service, durée maximale de vol de nuit, durée minimale de repos pré-courrier et/ou post-courrier,...) et sociales (départ à une heure tardive pour des destinations éloignées,...) relatives à la construction des périodes de service à partir d'un ensemble de vols sur une période donnée, ce problème se trouve fortement contraint. De plus, le nombre de vols par période de service dépasse rarement les 3 ou 4 vols. Par conséquent, même pour les problèmes réels de grande taille, on a généralement recours à l'énumération exhaustive de toutes les périodes de service couvrant tous les vols programmés et satisfaisant l'ensemble des contraintes. Ainsi, les périodes de service construites se composent d'au plus 4 vols consécutifs séparés par des temps d'escale. La ville d'arrivée de chaque vol doit être la ville de départ du vol suivant et ainsi de suite. Cependant, il n'y aucune contrainte sur les villes de départ et d'arrivée des périodes de service. Pour éviter les périodes de service qui partent d'une ville à l'étranger et/ou qui reviennent à une ville à l'étranger, des coûts de mise en place sont attribués à ces périodes de service, traduisant le coût supplémentaire de transfert

du personnel navigant technique de sa base d'affectationvers la ville de départ et/ou de la ville d'arrivée vers sa

base d'affectation. A titre d'exemple, pour les 94 vols que comporte le programme de vol de l'Airbus 300 de TUNISAIR sur un mois, le nombre de périodes de service est de 118.

2.2. Etape 2 : affectation du personnel navigant

technique aux périodes de service

A ce stade, le problème consiste à affecter

nominativement le personnel navigant technique à des périodes de service de façon à réaliser le programme de vols avec un coût minimal, tout en respectant les diverses contraintes (qualifications du personnel, composition de l'équipage, congés, périodes de formation, ...). Le personnel navigant technique est scindé en trois collèges : Pilote (ou Commandant de Bord), Copilote et Instructeur. Un instructeur peut être défini comme un Pilote pouvant, en cas de besoin, remplacer un Copilote.

Un équipage se compose d'un Pilote (ou d'un

Instructeur) et d'un Copilote (ou d'un Instructeur). D'autre part, chaque personnel navigant technique est caractérisé par ses qualifications avion. En effet, la flotte est à son tour composée de différents secteurs d'avion nécessitant les mêmes qualifications avion et au sein desquels le personnel navigant technique du même collège est complètement polyvalent. Un PNT qualifié pour opérer sur un appareil d'un secteur donné, est qualifié pour opérer sur tous les autres appareils de ce secteur. En outre, par mesure de sécurité, chaque personnel navigant technique n'a le droit d'opérer que sur un seul secteur d'avion. Par conséquent, le problème d'affectation d'équipage peut être traité séparément pour chaque secteur d'avion, sans pour autant altérer la qualité de la solution attendue. Pour résoudre le problème d'affectation des personnels aux périodes de service nous allons le modéliser comme un programme linéaire en nombres entiers dont la description fait l'objet de la section suivante.

3. FORMULATION MATHEMATIQUE DU

PROBLEME

3.1. Notations

La description qui suit fera appel aux notations

suivantes : V : ensemble de tous les vols v de la période considérée .

V(s) : ensemble des vols de la semaine s.

V(m) : ensemble des vols du mois m.

PS : ensemble des périodes de service ps préalablement construites. PS(v) : ensemble des périodes de service comprenant le vol v. PS(s) : ensemble des périodes de service de la semaine s. PS(m) : ensemble des périodes de service du mois m. MOSIM'01 - du 25 au 27 avril 2001 - Troyes (France) - 217 -

I : ensemble des instructeurs.

P : ensemble des pilotes (ou Commandant De Bord).

C : ensemble des copilotes.

L PS : liste des couples de périodes de service qui ne peuvent pas être effectuées par un même PNT. I ip . liste des couples (instructeur, pilote) présentant des incompatibilités. I ic . liste des couples (instructeur, copilote) présentant des incompatibilités. I pc . liste des couples (pilote, copilote) présentant des incompatibilités. d v : durée du vol v. TV ps : nombre d'heures de vol block de la période de service ps. TC ps : nombre d'heures de vol crédit de la période de service ps. TRV ps : nombre d'heures de repos nécessaires avant la période de service ps. TRP ps : nombre d'heures de repos nécessaires après la période de service ps. T max,s , T max,m : nombre maximal d'heures de vol respectivement par semaine et par mois. T fixe : nombre d'heures de vol crédit correspondant au salaire minimal garanti. C HS : coût de l'heure de vol crédit supplémentaire d'un PNT. C MEP : coût de mise en place d'un PNT. C MEP > 0 si la période de service nécessite une mise en place, C MEP = 0 sinon. La solution cherchée sera par ailleurs décrite au moyen : - des variables entières (0-1) suivantes : X p,ps = 1 si le pilote p effectue la période de service ps, = 0 sinon. Y c,ps = 1 si le copilote c effectue la période de service ps, = 0 sinon. Z i,ps = 1 si l'instructeur i effectue la période de service ps, = 0 sinon. u v,ps = 1 le vol v appartient à la période de service ps, = 0 sinon. x pv = 1 si le pilote p effectue le vol v, = 0 sinon. y cv = 1 si le copilote c effectue le vol v, = 0 sinon. z iv = 1 si l'instructeur i effectue le vol v, = 0 sinon. - et des variables entières HS k où : HS k est le nombre d'heures de vol crédit supplémentaires effectuées par le PNT k. En utilisant ces notations, nous allons maintenant modéliser le problème d'affectation considéré.

3.2. Formulation mathématique du modèle

Le problème d'affectation d'équipages rencontré par les compagnies aériennes peut se modéliser comme un programme linéaire en nombres entiers. En utilisant les Heures de vol block = heures de vol effectuées sur l'appareil. Heures de vol crédit = les heures de vol block plus les immobilisations (les réserves, les congés annuels, la formation, les réunions, les visites médicales, ...). notations décrites ci-dessus, voici la formulation mathématique proposée :

Minimiser C

HS p?P HSquotesdbs_dbs35.pdfusesText_40

[PDF] exos corrigés problème d'affectation recherche opérationnelle

[PDF] développement limité fonction plusieurs variables

[PDF] recherche opérationnelle exercices corrigés gratuit

[PDF] programmation linéaire exercices corrigés simplex

[PDF] examen recherche opérationnelle corrigé

[PDF] exercice corrigé methode simplexe pdf

[PDF] multiples et sous multiples physique

[PDF] multiples et sous multiples physique exercices

[PDF] multiples et sous multiples du gramme

[PDF] multiple et sous multiple exercice

[PDF] multiples et sous multiples du litre

[PDF] multiplicateur fiscal formule

[PDF] multiplicateur fiscal macroéconomie

[PDF] cobb douglas explication

[PDF] revenu d'équilibre formule