Résumé:

Le problème de construction d’horaires anonymes avec équité survient dans plusieurs compagnies aériennes nord-américaines. Il consiste à déterminer des horaires mensuels anonymes qui seront, par la suite, affectés aux membres d’équipage selon leurs préférences et leur séniorité. Ces horaires doivent satisfaire des règles de sécurité et de convention collective. De plus, afin d’assurer une équité entre les employés, chaque horaire doit avoir autant que possible le même nombre de jours de congé et le même nombre d’heures créditées (payées). Dans cet article, nous proposons une formulation approximative de type partitionnement d’ensemble pour ce problème et deux heuristiques pour le résoudre. La première heuristique est une méthode heuristique de génération de colonnes standard qui fait appel à une procédure d’arrondi pour engendrer des solutions entières. La seconde est obtenue en combinant la première avec une méthode d’agrégation dynamique de contraintes qui a récemment été proposée dans la littérature. Des résultats numériques montrent que, pour les plus grandes instances testées, l’heuristique d’agrégation dynamique de contraintes peut produire des solutions de meilleure qualité en une fraction du temps de calcul requis par l’heuristique de génération de colonnes standard.

Téléchargez le PDF pour en apprendre plus. (Seulement disponible en anglais)

Résumé:

Dans cet article, on raconte l’histoire de l’équipe GENCOL et du logiciel d’optimisation du même nom. C’est avant tout le récit d’une collaboration qui se poursuit depuis trente ans entre les chercheurs François Soumis et Jacques Desrosiers, les institutions universitaires HEC Montréal et l’École Polytechnique de Montréal, les centres de recherche CRT et GERAD, ainsi que les sociétés essaimées GIRO et AD OPT.

Téléchargez le PDF pour en apprendre plus.

Résumé:

Dans cet article, nous étudions le problème de fabrication quotidienne des itinéraires et des horaires des avions d’une flotte hétérogène afin de maximiser les profits anticipés d’une compagnie aérienne. Ces itinéraires doivent couvrir un ensemble de segments de vol opérationnels dont les fenêtres de temps de départ, les durées de vol et les profits anticipés sont connus en fonction de chaque type d’avion. Nous formulons ce problème de deux façons différentes, soit comme un problème de partition d’un ensemble avec contraintes supplémentaires et comme un problème de multiflot avec contraintes de temps. Nous décrivons la structure du réseau du sous-problème lorsque la relaxation linéaire est résolue par une technique de génération de colonnes pour le premier modèle ou par une approche de décomposition de Dantzig-Wolfe pour le second modèle. Les solutions entières sont obtenues en utilisant un algorithme de séparation et d’évaluation progressive. Les bornes inférieures sont calculées en résolvant la relaxation linéaire du problème. En exploitant l’équivalence entre les deux formulations, nous proposons plusieurs stratégies de branchement optimales compatibles avec la technique de génération de colonnes. Finalement, nous présentons certains résultats numériques obtenus à partir de données fournies par deux compagnies aériennes. Ces résultats montrent que ce problème peut être résolu en un temps raisonnable par une technique de génération de colonnes apportant ainsi une augmentation substantielle des profits.

Téléchargez le PDF pour en apprendre plus. (Seulement disponible en anglais)

Résumé:

Cet article décrit le problème de construction d’horaires mensuels personnalisés avec choix de préférences pour les membres d’équipage (pilotes et officiers) en transport aérien. Ce problème consiste à affecter aux membres d’équipage des rotations, des repos, des vacances, des entraînements, etc., tout en considérant un ensemble de requêtes pondérées réflétant les préférences de chacun. L’affectation doit tenir compte de l’ancienneté de chaque employé: la construction de l’horaire à pointage maximal pour un employé ne doit jamais s’effectuer au détriment de l’horraire d’un employé ayant plus ancienneté. De ce projet de recherche et de développement est né un système informatisé de construction d’horaires personnalisés qui est en usage chez Air Canada depuis le mois de mai 1995.

La méthode de résolution employé peut se résumer comme suit. Pour chaque employé, du plus ancien au plus récent selon l’ordre d’ancienneté, un problème résiduel est résolu: étant donné un employé et un ensemble de rotations non affectées, la solution d’un problème linéaire en nombres entiers détermine l’horaire à pointage maximal de l’employé tout en considérant les employés résiduels. La résolution du problème résiduel s’effectue par une méthode d’évaluation et de séparation dans un arbre de branchement où, à chaque noeud de branchement, un problème linéaire est résolu par la technique de génération de colonnes. Les solutions entières sont obtenues en utilisant des plans coupants sans lesquels il n’aurait pas été possible de résoudre certains des problèmes résiduels.

Téléchargez le PDF pour en apprendre plus. (Seulement disponible en anglais)

Résumé:

Etant donné un ensemble de vols devant être couverts par un seul type d’avions, le problème simultané de routage d’avions et d’horaires d’équipages consiste à déterminer un ensemble d’itinéraires d’avion et de rotations d’équipage tels que chaque vol est couvert par un appareil et un équipage, tout en satisfaisant un ensemble de contraintes supplémentaires. Alors que certaines contraintes supplémentaires telles que le temps maximum de vol et les contraintes d’entretien ne concernent que les équipages ou les avions, des contraintes liantes imposent des temps minimums de connexion pour les équipages qui dépendent des connexions utilisées par les appareils. Pour traiter ces contraintes liantes, nous proposons une approche de résolution basée sur la décomposition de Benders. Le processus de résolution itère entre un problème maître qui résout le problème des itinéraires d’avions, et un sous-problème qui résout le problème des rotations d’équipages. En raison de leur structure particulière, ces problèmes sont eux-mêmes décomposés et résolus par génération de colonnes. Une méthode d’évaluation et de séparation heuristique est utilisée afin d’obtenir des solutions entières. Sur un ensemble d’instances basées sur des données réelles fournies par un transporteur, l’approche intégrée a généré des économies importantes par rapport au processus de planification séquentiel souvent utiliée en pratique. La plus grande instance résolue comporte plus de 500 vols sur une période de 3 jours.

Téléchargez le PDF pour en apprendre plus. (Seulement disponible en anglais)