Méthodes de résolution de problèmes de couplage et d’affectation

Télécharger le fichier pdf d’un mémoire de fin d’études

Personnel navigant

Le personnel navigant d’une compagnie aérienne est celui qui constitue les équipages des vols à effectuer : les pilotes, les copilotes, les hôtesses, …
La création de plannings pour le personnel navigant est un problème qui attire considérablement l’attention des compagnies aériennes et en même temps des communautés de la recherche opérationnelle. Comme les navigants représentent l’une des ressources les plus coûteuses d’une compagnie, une gestion efficace du personnel s’impose naturellement comme indispensable. Le problème est intéressant aussi du point de vue mathématique, car il fait l’objet de nombreuses modélisations et de nombreuses techniques de résolution, qui relèvent le plus souvent de l’optimisation combinatoire.
La plupart des compagnies aériennes ont divisé la onstruction du planning en deux sous-problèmes : la création desrotations (problème connu aussi dans la littérature sous le nom de « crew pairing ») et l’affectation de ces dernières aux navigants (« crew rostering »). Une rotation est une séquence d’activités qui commence et qui finit dans la ville de domicile d’un équipage, appeléebase. Elle peut couvrir un ou plusieurs jours.
Le but du premier sous-problème est de créer un ensemble de rotations à coût minimum qui couvre tous les vols à effectuer par la compagn ie dans un certain intervalle temporel. Une fois les rotations créées, elles sont ensuite affectées aux personnels navigants (PN).
Les travaux dans le domaine sont nombreux. En 1969, [Arabeyre et al, 69] fait déjà un tour d’horizon des travaux dédiées à la création derotations. Dans [Etschmaier et al, 85] et [Rushmeier et al, 95] on trouve des revues de littérature plus récentes.
Les dernières recherches formulent le problème de création de rotations comme un problème de partitionnement d’ensemble. Après avoir généré l’ensemble [Yan et al. 02] ou une partie [Chu et al. 97] des rotations admissibles, différentes heuristiques sont proposées pour trouver la solution de coût minimum. Une autre approche consiste à grouper les vols en périodes de service [Desaulniers et al. 97a] et, à partir de ces dernières, à créer des rotations. Les références [Crainic & Rousseau 87] et [Lavoieet al. 88] proposent des méthodes de résolution basées sur la génération de colonnes.
L’affectation des rotations peut être réalisée suivant différentes approches. L’approche utilisée par la plupart des compagnies nord-américaines (‘bidline approach’) consiste à créer des plannings anonymes sur l’horizon concerné et à les affecter ensuite aux navigants, par ordre de priorité et aussi suivant leurs préférences. L’avantage de cette approche est que chacun sait exactement si le planning qu’il accepte est en concordance avec ses préférences. Les références [Campbell et al 97] et [Christou etal. 99] proposent des méthodes de constructions des plannings utilisant cette approche. Cette approche a en particulier été appliquée dans les compagnies FedEx et Delta Air Lines. Les plannings sont construits en deux étapes. Dans une première étape, on crée, enombren maximal, des plannings individuels de très bonne qualité, c’est-à-dire qui respectent les contraintes (dures et souples) dans les moindres détails. Dans la deuxième étape on complète ces plannings à partir des rotations qui n’ont pas pu être affectées auparavant. Les plannings sont ensuite affectés aux navigants par ordre de priorité de ces derniers (qualification et ancienneté). La référence [Campbellet al. 97] utilise le recuit simulé pour la première étapeet une procédure gloutonne pour la deuxième. L’étude [Christou et al. 99] propose une procédure basée sur des algorithmes génétiques.
La plupart des compagnies européennes créent directement des plannings personnalisés pour chaque navigant. Dans ce type d’approche, le navigant exprime ses préférences avant la création du planning, sans connaître la configuration finale des rotations.
Pour la création de plannings personnalisés, plusieurs méthodes heuristiques ont été proposées, mais les méthodes basées sur le partitionnement d’ensemble («set partitioning») sont de plus en plus utilisées. [Ryan 92] propose une méthode heuristique pour la construction des plannings valides, en utilisant une matrice de contraintes qui facilite la recherche des solutions. Le problème est ensuite résolu par programmation en nombres entiers. [Gamache et al. 99] décrit une méthode de résolution basée sur générationla de colonnes. [El Moudaniet al. 00] propose une méthode d’affectation des rotations utilisant des algorithmes génétiques. Cette méthode prend aussi en compte les éventuels hangementsc de planning.
La programmation par contraintes est aussi utilisée pour résoudre le problème d’affectation de rotations. Cette technique est surtout utilisée dans les cas où le problème a beaucoup de contraintes et où on peut se contenter d’une solution faisable même si elle n’est pas optimale. Souvent, elle est combinée avec des techniques de recherche opérationnelle. Les auteurs [Guerinik et al. 95] utilisent la programmation par contraintes comme technique de prétraitement, pour réduire la dimension du problème. Ensuite, il est résolu à l’aide d’une méthode de programmation linéaire complétée par unalgorithme de Branch & Bound. Une autre alternative est d’utiliser la programmation par contraintes pour générer des colonnes dans un problème de recouvrement d’ensemble (set covering) [Caprara et al. 98a]. Cette technique facilite la représentation des contraintes les plus complexes lors de la génération de colonnes, tout en garantissant la qualité de la solution, grâce à l’utilisation de la programmation en nombres entiers. Pour résoudre le problème d’affectation de rotations, nous avons choisi l’approche « européenne » – des plannings personnalisés. Notreproblème peut être vu comme un problème d’affectation multiple généralisé. Dans lechapitre 5, nous proposons une décomposition du problème dans un ensemble de problèmes d’affectation simple et un algorithme ad-hoc pour la résolution de chaque sous-problème.

Problèmes classiques d’optimisation combinatoire

Problème d’affectation

Le problème d’affectation consiste à trouver des li ens entre les éléments de deux ensemble distincts, de manière à minimiser un coût et à respecter des contraintes d’unicité de lien. En théorie des graphes, un problème d’affectation simple peut être vu comme un problème de couplage parfait dans un graphe biparti. Un graphe G s’appelle biparti si l’on peut diviser ses sommets en deux sous-ensembles et X2 avec aucune arête de type(i,j) avec i et j dans X1 ou bien i et j dans X2. On appelle couplage d’un graphe G un sous-ensemble d’arêtes non adjacentes deux à deux. Problème d’affectation simple
Soit un ensemble de m opérations qui doivent être exécutées parnressources, n ³ m . Chaque couple (opération i, ressource j) (i = 1 à m, j = 1 à n) a un coût associé cij, qui représente la dépense associée à la réalisation del’opération i par la ressource j. En supposant que chaque opération doit être exécutée une seuleoisf et que chaque ressource est utilisée au plus par une seule opération, le problème peut êtremodélisé de la manière suivante : mn Min ∑∑cij xij (2.1) i1 j1 n i1,.., m sous : ∑ xij  1 (2.2) j1 m j1,.., n ∑ xij  1 (2.3) i1  0,1 i1,.., m,j1,.., n (2.4)
où xij est une variable binaire associée à chaque paire (opération i, ressource j) et qui vaut 1 si l’opération i est effectuée par la ressource j et 0 sinon. Si l’on considère que X1 représente l’ensemble des opérations (|X| = m) et X l’ensemble des ressources (|X | = n) du problème (2.1)-(2.4), avec m £ n alors chaque arête entre un sommeti de X1 et un sommet j de X2 signifie que l’opération i peut être effectuée par la ressourcej. On associe à chacune de ces arêtes un coût égal àcij. Comme le coût total d’un couplage est donné par la somme des coûts de chaque arête, le problème d’affectation revient à trouver un couplage de cardinal m et de coût minimal.
Ce modèle correspond à ce que l’on appelle le problème d’affectation simple.
Problème d’affectation généralisé
Dans un cadre plus général, où par exemple les ressources sont agrégées, la contrainte (2.3), appelé contrainte de capacité, n’est plus suffisante pour décrire l’utilisation des ressources. Dans ce cas, une ressource j est caractérisée par sa capacitéSj et chaque opération i nécessite la quantité de ressource ij si elle utilise la ressource j. La contrainte (2.3) devient :
m j1,.., n,k1,…, K (2.5)
∑rijk xij S kj
Dans la formulation du problème, l’indice k traduit l’existence fréquente de plusieurs contraintes de capacité généralement liées à l’utilisation de ressources annexes ou complémentaires par rapport aux ressources de base [Hennet 97]. Le problème d’affectation simple ayant des contraintes de capacité exprimées par (2.5) devient un problème d’affectation généralisé.

Problème de bin-packing

Un des problèmes les plus souvent rencontrés dans el domaine de la recherche opérationnelle est le problème de bin-packing. Celui-ci consiste à placer des objets ayant une taille donnée dans des conteneurs de capacité connue. Dans les problèmes les plus basiques, les tailles et les capacités ont une seule dimension (poids, longueur…) et tous les conteneurs ont la même capacité. Dans les problèmes plus complexes, il y a plusieurs types de conteneurs et les objets ont plusieurs dimensions. Souvent, il s’agit de dimensions géométriques ou de caractéristiques physiques (poids, volume).
Les objectifs les plus fréquents sont soit de remplir au maximum les conteneurs utilisés, sachant que les objets ne doivent pas forcément être tous sélectionnés, soit de placer tous les objets dans un nombre minimal de conteneurs, ou encore d’équilibrer les charges.
[Dyckhoff 90] propose une typologie des problèmes de bin-packing, chaque type étant caractérisé par les attributs suivants :
Dimension. Ce paramètre précise le nombre minimal des variables nécessaires à la description géométrique du modèle : une dimension 1),( deux dimensions (2), trois dimensions (3), N dimensions (N).
Type d’assignation . Deux cas sont envisagés : soit tous les objets sont affectés à une sélection de conteneurs (V), soit une sélection d’objets est affectée à tous les conteneurs (B).
Capacité des containeurs. Soit il y un seul conteneur (O) soit il y en a plusieurs avec des capacités identiques (I) ou avec des capacités différentes (D).
Taille des objets. Il peut y avoir peu d’objets de formes différentes (F), plusieurs objets de plusieurs formes différentes (M), plusieurs objets de peu de formes différentes (R), ou des objets de formes identiques (C).

Techniques de résolution retenues

Dans la paragraphe précédent, nous avons vu quelques modèles de recherche opérationnelle souvent rencontrés pour modéliser des problèmes liés à l’affectation du personnel. Ce paragraphe présente les techniques les plus performantes pour résoudre ces problèmes de recherche opérationnelle.

Méthodes de résolution de problèmes de couplage et d’affectation

Le problème d’affectation simple (2.1)-(2.4) est parmi les problèmes combinatoires les plus faciles à résoudre. En effet, sa matrice de contraintes pour les contraintes (2.2)-(2.3) a la propriété d’unimodularité. Les contraintes binaires(2.4) peuvent donc être remplacées par les contraintes de la relaxation continue suivante sans changer la solution optimale du problème qui est « naturellement » binaire. 0 xij 1 i1,.., m,j1,.., n (2.14)
Une conséquence évidente de cette propriété est quedes problèmes d’affectation simples de très grande dimension peuvent être résolus directement par des logiciels de programmation linéaire en nombres réels.
Cependant, pour des raisons de souplesse d’utilisation et d’implémentation dans des progiciels commerciaux, nous avons choisi de résoudre les problèmes d’affectation simples par des algorithmes ad-hoc, que nous allons maintenant passer en revue.

Bip Match

Le Bip Match est un algorithme rapide utilisant les chaînes alternées améliorantes pour trouver un couplage maximal dans un graphe biparti [Prins 94]. Pour un graphe G et un couplage C, une chaîne est alternéesi elle emprunte alternativement des arêtes dans Cet hors C. Pour un couplage, une chaîne alternée est améliorante (ou augmentante) si ses deux extrémités sont insaturées par le couplage.
Le fonctionnement de l’algorithme est basé sur les deux suivantes propriétés dues à Berge [Berge 83] :
Propriété .1Soit un graphe G, C un couplage de G et une chaîne alternée améliorante µ pour C. Un transfert sur µ donne un nouveau couplag e C’ avec |C’| = |C| + 1. 1
Propriété .2 Un couplage est maximal si est seulement si il n’admet aucune chaîne alternée améliorante.
Le Bip Match part d’un couplage initial non vide, obtenu en cherchant les chaînes alternées améliorantes réduites à une arête – on fecteaf chaque sommet de X à son premier successeur libre, c’est-à-dire n’étant pas déjà extrémité d’une arête du couplage.
A partir de cette affectation initiale, on cherche les chaînes améliorantes, par une exploration en largeur du graphe. Cette recherche vise à améliorer la solution trouvée par l’affectation initiale, puis la solution courante, par l’augmentation de la cardinalité du couplage. On part toujours d’un sommet insaturé de X et on s’arrête à la plus courte chaîne trouvée. On va explorer les sommets alternativement(un sommet de X, un sommet de Y…), de manière que la chaîne ait une arête hors du couplage, puis une arête dans le couplage. L’algorithme s’arrête quand il n’arrive plus à trouver des chaînes améliorantes.

L’algorithme de Busacker et Gowen

Un problème d’affectation ou de couplage maximal dans un graphe biparti peut être modélisé comme un problème de flot ; ainsi, la recherche d’une affectation optimale revient à la recherche d’un flot maximal de coût minimal. C’e st un problème classique de la théorie des graphes qui cherche à faire passer un débit maximal à travers un réseau à moindre coût.
L’algorithme de Busacker et Gowen [Busacker&Gowen 61] est une méthode simple et efficace pour trouver un tel flot. Son principe de fonctionnement est équivalent à celui du Bip Match : il part d’un flot nul et il l’augmente prog ressivement, par recherche des chaînes augmentantes.
C’est aussi une méthode primale comme le Bip Match, donc il présente les mêmes avantages que celui-ci. De plus, il prend en compte les coûts d’affectation.

L’algorithme hongrois

Un cas particulier du problème d’affectation, souvent traité dans la littérature est celui où le nombre des opérations à effectuer est égal aunombre des ressources utilisées. En effet, tout problème d’affectation simple peut être mis sous cette forme par introduction d’opérations fictives à coût nul pour toutes les ressources dans le cas m<n, ou de ressources fictives à coût nul pour toutes les opérations dans le cas m>n. Une méthode de résolution du problème d’affectation qui prend en compte cette structure est l’algorithme hongrois.
Développé en 1955 par H.W.Kuhn et nommé ainsi en honneur des mathématiciens J. Egervary et D. König, l’algorithme hongrois [Kuhn 5 5] est un algorithme dual qui utilise la modélisation sous forme de programme linéaire du problème d’affectation. Toutefois, il peut être vu comme une variante de l’algorithme de Busacker et Gowen, spécialisée pour la structure bipartie du graphe. Du fait de sa grande efficacité sur ce type de problème, c’est l’algorithme de référence en Recherche Opérationnelle pour résoudre le problème d’affectation. Son principe est basé sur le fait que les couplages de poids minimal dans le graphe du problème primal sont exactement les couplages de cardinalité maximale dans le graphe du problème dual. Une schématisation simpliste de l’algorithme hongrois pourrait être la suivante :
Etape 1. On crée la matrice des coûts (cij) (i = 1…m, j = 1…n, m = n ) initiale, qui est considérée non négative.
Etape 2. Pour chaque ligne de la matrice, on trouve l’élément minimal et on le soustrait à tous les éléments de cette ligne. S’il reste descolonnes sans coefficients nuls, pour chacune de ces colonnes, on trouve l’élément minimal et on le soustrait à tous les éléments de cette colonne.
Etape 3. On cherche une affectation admissible en vérifiant si, pour chaque ligne et chaque colonne il existe exactement une case marquée. Si oui, l’affectation trouvée est optimale. Sinon, on trace des traits (en nombre minimal) sur les lignes et les colonnes de la matrice, pour couvrir tout les 0 au moins une fois.
Etape 4. On cherche l’élément minimal non marqué. On le soustrait à tous les éléments non marqués et on l’additionne à tous les élémentsmarqués deux fois (tous les éléments qui se trouvent à l’intersection de deux raits). On retourne à Etape 3.

Méthode de relaxation Lagrangienne pour le problème d’affectation généralisé

Pour résoudre un problème d’affectation généralisé,on peut chercher à le transformer en un problème d’affectation simple et ensuite résoudre ce problème. Une méthode fréquemment utilisée pour ce genre de transformation est la relaxation Lagrangienne. En dualisant la contrainte (2.5), le critère (2.1) est remplacé parl’expression lagrangienne suivante : mn nK m L ∑∑cij xij  ∑∑ ijk (∑rijk xij Sik ) (2.15)
En relaxant les contraintes de capacité (2.5) et en pondérant leur non-respect, on a à résoudre un problème d’affectation simple, avec lesparamètres de coûts cij remplacés par les paramètres cij’ définis par :
K cij’ cij ∑ijk rijk (2.16)
Le choix des valeurs numériques, nécessairement nonnégatives, des variables dualesijk est bien sûr très important, car la solution optimale du problème d’affectation généralisé est obtenue pour les valeurs optimales de ces variables duales. Des valeurs candidates pour les paramètresijk peuvent être obtenues en résolvant le problème d’affectation généralisé dans lequel les contraintes binaires sur les variables ont été relaxées. Cela revient à résoudre le problème en remplaçant (2.4) par (2.14): 0 xij 1 i1,.., m,j1,.., n
Pour la résolution d’un problème d’affectation simple, les algorithmes décrits ci-dessus peuvent être utilisés.

Algorithmes de résolution pour le problème de bin-packing

Il est bien connu que le problème de bin-packing est un problème NP-difficile. Il y a toutefois de nombreux algorithmes de résolution quidonnent des solutions approchées en un temps de réponse polynomial. La qualité de chacun ed ces algorithmes est donnée par la garantie de performance dans le pire cas [Coffman et al. 98]. Soit A un algorithme qui donne une solution approchée etOPT un algorithme qui donne la solution optimale. A(k) représente le nombre de conteneurs utilisés par l’algorithme A pour caser k objets et OPT(k) représente le nombre optimal de conteneurs pour caser les mêmes k objets. Avec ces notations, la garantie de performance de l’algorithme A, dans le pire cas est définie par : k OPT (k ) RA  lim A(k ) (2.17)
Dans la suite, nous allons présenter quelques algorithmes et leurs performances.
Auparavant, nous donnons quelques précisions :
Tous les conteneurs sont vides au début. Chaque conteneur qui n’est pas vide est soit fermé, soit ouvert. Un conteneur est ouvert si l’on peut encore mettre des objets dedans. Un conteneur fermé n’est plus disponible pour recevoir des objets; une fois fermé, il n’est plus rouvert.
Les objets à mettre dans des conteneurs se trouvent dans une liste L = { o1, o2, o3… }. Cette liste peut être triée suivant la taille des objets, mais la règle de tri dépend de l’algorithme choisi.
Suivant la modalité d’inspection des objets à caser dans des conteneurs, les algorithmes sont divisés en deux catégories : algorithmeson-line et algorithmes off-line.

Algorithmes on-line

Un algorithme on-line traite les objets dans leur ordre, sans aucune connaissance de la taille ou du nombre des objets pas encore traités. Les conteneurs sont traités dans l’ordre C1, C2, C3… Comme règle générale, l’algorithme commence par m ettre l’objet o1 dans le conteneur C1 et ensuite il traite les autres objets dans l’ordre o2, o3, o4… Parmi les algorithmes on-line les plus connus, on trouve : Next-Fit, Worst-Fit, First-Fit, Best-Fit.
Next-Fit (NF) est peut être le plus simple des algorithmes de résolution du bin–packing. Une fois le premier objet placé, NF met chaque objet restant dans le conteneur du dernier objet placé. Si il n’y a pas de place, il ferme ce conteneur et place l’objet courant dans un conteneur vide. Cet algorithme a une complexité en O(n) et une garantie RNF 2 . Une analyse complète concernant RNF se trouve dans [Johnson 74].
Worst-Fit (WF) place l’objet courant dans le conteneur le moins rempli où l’objet peut rentrer. Si il y a plusieurs conteneurs de ce type, celui avec l’index le plus petit est choisi. S’il n’y a pas de conteneur ouvert dans lequel l’objet c ourant peut être placé, un conteneur vide est ouvert. Cet algorithme a la même garantie queNF [Johnson 74].
First-Fit (FF) place l’objet courant dans le premier conteneur ouvert ayant le plus petit index où l’objet rentre. Si il n’y a pas un tel con teneur, un autre sera ouvert. L’algorithme a une complexité en O(n log n), donc plus élevée que celle du NF, mais une meilleure garantie de performance relative au pire, car RFF 17 /10 [Johnson et al. 74].
Best-Fit (BF) place l’objet courant dans le conteneur le plus rempli où l’objet rentre. Si il y en a plusieurs équivalents, celui avec le plus petit index est choisi. Si il n’y a pas de conteneur qui puisse recevoir cet objet, un conteneur vide est ouvert. L’algorithme a une complexité O(n log n) et une garantie de performance relative au pire RBF 17 /10 [Johnson et al. 74].

Algorithmes off-line

Un algorithme off-line permet le tri des objets avant de commencer à les ranger dans les conteneurs. La règle la plus naturelle trie les objets en ordre décroissant de leur taille. En effet, un gros objet est plus facile à insérer lorsque le choix des conteneurs candidats est important. Selon la même logique, il est plus facile de compléter un conteneur déjà rempli avec un petit objet qu’avec un gros.
En combinant cette règle de tri avec les algorithmes qui viennent d’être présentés, on obtient les algorithmes suivants : Next Fit Decreasing (NFD), First Fit Decreasing (FFD),
Best Fit Decreasing (BFD). FFD et BFD ont la même garantie de performance :
RFFD  RBFD  11/ 9 , donc meilleure que dans le cas on-line.
Pendant des années, le FFD a été considérécomme le meilleur algorithme d’approximation pour la résolution du problème de bin-packing. Toutefois, des modifications ont été apportées au FFD, en essayant de trouver une meilleure garantie. Yao [Yao 80] a créé l’algorithme Refined First Fit Decreasing (RFFD) dont la garantie de performance est RRFFD 11/ 9107 , mais avec une complexité en O(n10 log n). Ensuite, [Garey & Johnson 85] ont proposé l’algorithme Modified First Fit Decreasing (MFFD) qui améliore encore plus le FFD. Sa complexité est la même que celle du FFD,O(n log n), mais la garantie de performance est meilleure : RMFFD 71/ 60.
Plus de détails concernant les différents algorithmes présentés ci-dessus figurent dans [Coffman et al. 98].

Génération de colonnes pour la résolution du problème de recouvrement d’ensemble

Une particularité du problème de recouvrement d’ensemble décrit par (2.11) – (2.13) est que, dans de nombreuses application, il a un très grand nombre de variables, ce qui est équivalent au fait que la matrice (aij) (i = 1…m, j = 1…n ) a un très grand nombre de colonnes (n>>m), de telle sorte que toutes ses colonnes ne peuvent pas être explicitées. La question qui se pose alors est de construire une technique capable de résoudre un tel problème, sans tenir compte en même temps de façon explicite de toutes les variables du problème.
Une telle technique est la génération de colonnes.Le principe consiste à ne manipuler qu’un nombre restreint de variables à la fois et à identifier (générer) les variables ou les combinaisons de variables (colonnes) entrantes dans la solution au cours de la résolution, sans les énumérer explicitement.
D’une manière plus générale, on peut réécrire (2.)14–(2.16) sous la forme suivante : Min cx (P1 ) : sous x ³ 0 Ax ³ b (2.18)
où c et x sont des vecteurs de dimension n, A est une matrice m×n, et b est un vecteur de dimension m. Même si la matrice A ne peut pas être explicitée,on suppose qu’elle est connue implicitement, c’est-à-dire que ses colonnes corres pondent aux éléments d’un ensemble que l’on sait caractériser. On suppose aussi que l’on dispose d’un algorithme « générateur» pour générer une colonne de A minimisant une fonction linéaire de la forme : z( A j ) = c j -A j (2.19) ou π = (π1, .., πm) est un vecteur ligne de paramètres.
Soit un sous-ensemble des variables du problème (P1) et A’ la sous-matrice de A correspondante (rang(A’) = m). On note (P2) la restriction de (P1) à . En utilisant par exemple l’algorithme du simplexe2, (P2) a comme solution optimale : xB = B*1b (2.20).

Table des matières

Introduction
1. Planification des ressources humaines
1.1 INTRODUCTION
1.2 QUELQUES NOTIONS SUR LA PLANIFICATION
1.3 LA PLANIFICATION DANS UN CONTEXTE AERONAUTIQUE
1.3.1 Personnel au sol
1.3.2 Personnel navigant
1.4 CONCLUSIONS
2. Modèles et techniques de résolution pour les problèmes de planification d’horaires
2.1 INTRODUCTION
2.2 PROBLEMES CLASSIQUES D’OPTIMISATION COMBINATOIRE
2.2.1 Problème d’affectation
2.2.2 Problème de bin-packing
2.2.3 Problème de recouvrement d’ensemble
2.3 TECHNIQUES DE RESOLUTION RETENUES
2.3.1 Méthodes de résolution de problèmes de couplage et d’affectation
2.3.1.1 Bip Match
2.3.1.2 L’algorithme de Busacker et Gowen
2.3.1.3 L’algorithme hongrois
2.3.1.4 Méthode de relaxation Lagrangienne pour le problème d’affectation généralisé
2.3.2 Algorithmes de résolution pour le problème de bin-packing
2.3.2.1 Algorithmes on-line
2.3.2.2 Algorithmes off-line
2.3.3 Génération de colonnes pour la résolution du problème de recouvrement d’ensemble
2.3.3.1 Convergence de la méthode
2.3.3.2 L’algorithme générateur
2.3.3.3 Recherche des solutions entières
2.4 CONCLUSION
3. Création de vacations pour le personnel au sol
3.1 INTRODUCTION
3.2 CONCEPTS DE BASE : TACHES ET VACATIONS
3.2.1 Tâches
3.2.2 Vacations
3.2.3 Personnel
3.3 PRESENTATION DU PROBLEME
3.3.1 Contraintes réglementaires
3.3.2 Méthodes de résolution dans la littérature
3.3.2.1 Modélisation par recouvrement d’ensemble
3.3.2.2 Méthodes itératives
3.4 MODELISATION PROPOSEE
3.4.1 La représentation du temps
3.4.2 Plages horaires
3.4.3 Tâches, vacations, contraintes
3.4.4 Modélisation du problème
3.5 METHODE DE RESOLUTION PROPOSEE
3.5.1 Génération de vacations
3.5.1.1 Construction des patrons de vacations
3.5.1.2 Traitement des tâches fixes
3.5.1.3 Traitement des tâches mobiles
3.5.2 Remplissage de vacations
3.6 RESULTATS OBTENUS
3.7 CONCLUSIONS
4. Création de rotations pour le personnel navigant
4.1 INTRODUCTION
4.2 CONCEPTS DE BASE
4.2.1 Rotations
4.2.2 Activités hors-vol
4.2.3 Personnel
4.3 MODELISATION ET RESOLUTION DU PROBLEME
4.3.1 Contraintes réglementaires
4.3.2 Méthodes de résolution dans la littérature
4.3.3 Modélisation proposée
4.3.3.1 Construction des PdS
4.3.3.2 Construction de rotations à partir des PdS
4.3.4 Résultats
4.3.4.1 Construction des PdS
4.3.4.2 Construction de rotations à partir des PdS
4.3.5 Post traitement des rotations
4.4 PERSPECTIVES : CONSTRUCTION D’ALGORITHMES APPROCHES
4.4.1 Construction de PdS
4.4.2 Constructions de rotations
4.5 CONCLUSIONS
5. Affectation de vacations/ rotations
5.1 INTRODUCTION
5.2 PRESENTATION DU PROBLEME
5.2.1 Contraintes réglementaires
5.3 METHODES DE RESOLUTION DANS LA LITTERATURE
5.3.1 Affectation de vacations
5.3.2 Affectation de rotations
5.4 MODELISATION DU PROBLEME
5.5 METHODE DE RESOLUTION PROPOSEE
5.5.1 Construction de la matrice de coût
5.5.2 Calcul des coûts
5.5.3 L’affectation de réserves pour le personnel navigant
5.5.4 Affectation de séquences
5.6 IMPLEMENTATION ET RESULTATS
5.6.1 Validation de la méthode
5.6.2 Implémentation
5.7 CONCLUSION
Conclusion
Bibliographie

Télécharger le rapport complet