Groupe d’études et de recherche en analyse des décisions

G-99-49

Problème d'affectation des types d'avion aux vols

L'affectation de type d'avion aux vols consiste à déterminer, pour chaque arc de vol, le type d'avion qui lui sera affecté de façon à maximiser les profits globaux. Ce problème peut être formulé à l'aide d'un modèle linéaire de multiflots en nombres entiers, et résolu par la méthode de Branch & Bound dans laquelle chaque noeud de l'arbre de branchement est un problème de multiflots linéaire. Cependant, les problèmes de multiflots linéaires ont des nombres de variables et de contraintes de l'ordre du produit du nombre de vol et du nombre de types d'avion. Ce sont donc de très grands problèmes difficiles à résoudre par le Simplex. L'approche proposée consiste à restreindre le problème au départ à un sous-ensemble des variables originales. D'autres variables seront itérativement générées en prenant les arcs des chemins de coûts réduits négatifs obtenus à partir de la résolution des sous-problèmes de la génération de colonnes jusqu'à l'optimalité.

, 55 pages