Group for Research in Decision Analysis

Column generation for passenger transportation

Guy Desaulniers Professor, Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Canada

Column generation is one of the most popular optimization methods for solving various vehicle and crew scheduling problems in passenger transportation (transit, air, and rail). In this seminar, we will present an overview of the main problems in this domain (namely, the problems of constructing vehicle schedules, crew pairings, and crew members' schedules, as well as combined problems) and expose how column generation can be applied to solve them. We will highlight the difficulties that can be met and discuss the most recent methodological advances, such as dynamic constraint aggregation and dual variable stabilization, to overcome them.