27 avr 2001 · MOTS-CLES : programmation linéaire en nombres entiers, affectation de personnels, optimisation, transport aérien 1 INTRODUCTION La
Previous PDF | Next PDF |
[PDF] Transports industriels routiers, un problème daffectation - Numdam
moyens de transport aux demandes s'avèrent un délicat problème Inspiré de la méthode « Hongroise », un algorithme £ affectation autorisant le réemploi de
[PDF] Problèmes de transport - formulation des problèmes daffectation - FR
31 mar 2009 · ce cas Page 13 Problèmes de Transport Solution des problèmes de transport Problèmes d'affectation Problème de transbordement Conclusion
[PDF] Chapitre 6 Problèmes de transport
Le problème général de transport sous l'hypothèse que l'offre totale égale la Il s'agit de la classe de problèmes qui traite des questions d'affectation de tâches
[PDF] Problème de flot, daffectation et de transport - cloudfrontnet
Problème de flot, d'affectation et de transport Réalisé par : OMARI Redouane DACHRY Abdelfattah Encadré par : Mr LOUMANI Année universitaire 2008 /
[PDF] Problèmes de transport - Thèses
auteurs ont résolu le problème d'affectation associé au TOPTW, en se basant sur la solution obtenue, l'algorithme décide quels arcs, il doit insérer dans ce
[PDF] MODELISATION ET RESOLUTION DUN PROBLEME D
27 avr 2001 · MOTS-CLES : programmation linéaire en nombres entiers, affectation de personnels, optimisation, transport aérien 1 INTRODUCTION La
[PDF] Chapitre 5 – Solutions des exercices de révision - HEC Montréal
La figure ci-dessous illustre un réseau associé à ce problème destinations et les coûts de traitement aux coûts de transport, le problème des hauts fourneaux problème d'affectation, la différence venant du fait que les camions
[PDF] Problème dynamique de transport à la demande - Université de Tours
Problème dynamique de transport à la La règle d'affectation Attention, on ne peut changer l'affectation d'une requête que si aucun des deux sommets n'a
[PDF] développement limité fonction plusieurs variables
[PDF] telecharger exercices de recherche operationnelle
[PDF] recherche opérationnelle exercices corrigés gratuit
[PDF] cours de recherche operationnelle gratuit pdf
[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
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.frRÉ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 dela 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 & Odier1988, 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 transfertdu 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.