Back

Session TC6 - Génération de colonnes / Column Generation

Day Tuesday, May 05, 2009
Room Mary Husny
President Hatem Ben Amor

Presentations

03h30 PM-
03h55 PM
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.


03h55 PM-
04h20 PM
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.


04h20 PM-
04h45 PM
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.


Back