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)