Crew Scheduling Problems

MD31.1 A New Column Generation Methodology for Solving the Commercial Crew-Scheduling Problems: Application to the French Railroads Maher Koubaa, Diane Bellant, Pierre Dejax, Bernard Rannou --- Ecole Centrale Paris, Lab. Prod. Lostique, Grands Voie des, Malabry Cedex, 92295 , France (koubaa@pl.ecp.fr)

This paper deals with the modelling and solving of large scale commercial crew scheduling problems encountered in railroad companies. We present a new formulation of the problem based on a real application with the french High Speed Railroads. Application on real data shows drastic improvement from a previous method.

MD31.2 On Valid Inequalities & Facets for a Formulation of the Crew Scheduling Problem Odile Marcotte, Benoit Rochefort, Francois Soumis --- Univ. of Quebec, GERAD & DIRO, 3000 ch Cote-Ste-Catherine, Montreal, Quebec, H3T 2A7 , Canada (odile@crt.umontreal.ca)

The crew scheduling problem can be modeled as a variant of the multicommodity flow problem. We describe some fractional solutions that arise when one solves the linear relaxation of this problem, and show that they are often related to odd cycles. We also give a large class of valid inequalities and prove that some of them are facets of the convex hull of integral solutions.