Séminaire “Un chercheur du GERAD vous parle!”

Titre : Optimization methods for large-scale vehicle and crew scheduling problems. The contribution of Montréal.

Conférencier : François Soumis – Professeur titulaire, Département de mathématiques et de génie industriel, Polytechnique Montréal, Canada

The planning process in air transportation is divided in many steeps: fleet assignment and aircraft routing, crew pairing, crew rostering, aircraft and crew recovery. All these problems have a similar mathematic structure. It consists to cover at minimum cost, a set of tasks with feasible routes. Problems with the same structure also appear for rail and bus transportation.

The first idea popularize by our team was the column generation reaching an optimal solution by solving many problems with a reduced number of variables. I will present many ideas to speed up the resolution process and results on real live problems.

A second idea developed by our team was the reduction of the number of constraints by constraints aggregation. This method takes advantage of degeneracy by removing degenerated constraints. The aggregation is modified dynamically to reach an optimal solution. With fewer constraints the linear relaxation produces less fractional solutions and speed up the branch-and bound. Results on problems with up to 56 000 constraints will be presented.

Finally I will present a breakthrough for the set-partitioning problem: a new algorithm producing and improving sequence of integer solutions up to optimality, with simplex pivots.

---

Du café et des biscuits seront offerts au début du séminaire.
Bienvenue à tous!