Journées de l'optimisation 2009 Optimizations days

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.

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.

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.