Séance TC6 - Génération de colonnes / Column Generation
Jour mardi, le 05 mai 2009 Salle Mary Husny Président Hatem Ben Amor
Présentations
|
15h30- 15h55 |
Aircrew Pairings with Possible Repetitions of the Same Flight Number |
|
Mohammed Saddoune, GERAD, École Polytechinque de Montréal, Mathématiques et génie industriel , C.P. 6079, Succ. Centre-ville, Montréal, QC, Canada, H3C-3A7 Guy Desaulniers, GERAD, École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7 François Soumis, GERAD, École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7 The crew pairing problem is usually solved by the traditional three-phase approach: daily, weekly, and monthly problems. First, we show that this approach is less efficient compared to a rolling horizon approach when the schedule is irregular. Second, if it is completely regular then a direct optimization on the weekly problem without exploiting the daily solution produces better solutions. |
|
15h55- 16h20 |
A Hierarchical Optimization Approach to Optical Network Design where Traffic Grooming and Routing is Solved by Column Generation |
|
Benoît Vignac, Université de Montréal, Informatique et recherche opérationnelle, C.P. 6128, succursale Centre-ville, Montréal, Québec, Canada, H3C 3J7 Brigitte Jaumard, GERAD et Concordia University, CIISE, 1455, boul. de Maisonneuve Ouest, CB-410-12, Montréal, Québec, Canada, H3G 1M8 François Vanderbeck, Université de Bordeaux I, Mathématiques appliquées, 351, Cours de la Liberation, F-33405 Talence Cedex, Bordeaux, France This presentation deals with a two layer optical network design problem that direct approaches have difficulties to handle efficiently. We propose a hierarchical optimization procedure where we first take care of the grooming and routing decisions and then we perform wavelength assignment. The fist stage is solved by column generation and a rounding heuristic provides integer solutions. |
|
16h20- 16h45 |
A Multi-Phase Column Genertion Algorithm for Routing Problems |
|
Hatem Ben Amor, AD OPT, Canada We propose a multi-phase column generation algorithm that solves a finite sequence of problem restrictions w.r.t. the set of routes considered in each phase. Results are presented for randomly generated vehicle scheduling problems and real-world air transportation problems. |