A New Approach to Crew Scheduling in Rapid Transit Networks

We propose a new approach for the crew scheduling problem in rapid transit networks. With this approach we try to open a new branch for future research, providing a different way of facing the crew scheduling problem which makes integration with other planning problems easier than the traditional approach based on column generation for solving a set covering/partitioning problem. For solving this new model we develop a Lagrangian relaxation and we take advantage of an ad hoc decomposition based on time- personnel clustering. We present some preliminary computational experiments for real case studies drawn from the main Spanish train operator, RENFE.