Grant: Collaborative Research and Development Grants

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.