Share Cahiers du GERAD par Jean-François Cordeau, Goran Stojković, François Soumis et Jacques Desrosiers 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. Lire la suite