Grant: Collaborative Research and Development Grants

Les problèmes d'horaires traités par AD OPT et Giro ont des structures semblables, il s'agit de couvrir à coût minimum un ensemble de tâches avec des horaires d'employés. Dans le domaine aérien, le problème de rotations d'équipages couvre avec des rotations chaque vol une fois et le problème des blocs mensuels couvre avec des blocs mensuels chaque rotation plusieurs fois pour avoir le personnel requis dans chaque vol. En transport en commun, le problème journalier couvre avec des journées de chauffeurs chaque parcours d'autobus une fois. Tous ces problèmes se formulent à l'aide de modèles de recouvrement d'ensemble qui comportent un très grand nombre de variables et de contraintes. Notre équipe a développé des algorithmes qui permettent de résoudre sans considérer toutes les variables en même temps et réduisent le nombre de contraintes en agrégeant au départ des tâches qui devraient probablement se suivre dans une solution. L'agrégation est modifiée au besoin durant la résolution pour atteindre l'optimalité. Ces algorithmes ont été mis en service sur les problèmes de rotations d'équipages aériens où chaque tâche doit être couverte une seule fois. Les objectifs de ce projet sont de :-Développer des méthodes d'apprentissage automatique pour obtenir à partir des solutions des mois précédents de l'information sur les tâches qui devraient probablement se suivre dans une solution.-Généraliser ces algorithmes pour élargir leurs domaines d'application : traiter les problèmes de chauffeurs d'autobus et les problèmes de blocs mensuels d'agents de bord travaillant en équipes, optimiser simultanément les rotations et les blocs mensuels. -Réaliser des implantations des algorithmes capables de traiter les problèmes commerciaux.Ce projet donnera un avantage concurrentiel à AD OPT et Giro qui disposeront de meilleurs logiciels que leurs concurrents.#(cr)#(lf)The scheduling problems addressed by AD OPT and Giro have similar structures. They consist in covering at minimal cost a set of tasks with employee schedules. In the air transportation industry, the crew pairing problem aims at covering each flight with crew rotations once, and the crew rostering problem attempts to cover each crew rotation with monthly blocks many times in order to guarantee that each flight has the required staff. In the public transportation industry, the daily problem aims at covering each bus route with drivers' workdays once.All these problems can be formulated with set covering models that contain a very large number of variables and constraints. Our team developed algorithms that solve these problems without considering all the variables at the same time and that reduce the number of constraints by initially aggregating tasks that are likely to come one after the other in a solution. In order to reach optimality, this aggregation can be modified during the resolution if needed. These algorithms were put to use on airline crew pairing problems, in which each task has to be covered once. The objectives of this project are as follows:- Develop machine learning methods in order to extract from solutions of previous months information about the tasks that are likely to come one after the other in a solution.- Generalize these algorithms so as to widen their scope of application: dealing with bus drivers problems and with monthly blocks problems of flight attendants working as a team, and simultaneously optimizing pairing and monthly rostering.- Make implementations of the algorithms that are able to deal with commercial problems.This project will give a competitive advantage to AD OPT and Giro, which will have at their disposal better software than their competitors.