A Fix & Relax matheuristic for the Crew Scheduling Problem

This paper presents a crew scheduling model for rapid transit networks, where distances are not big but service frequency is very high. The crew scheduling problem has been traditionally modelled as a set covering/partitioning problem. Here, the presented approach faces the problem in a different way taking benefit from a linear payment policy and enabling an easier integration with other planning problems such as rolling stock circulations. For solving this new model, a Fix and Relax matheuristic is employed. Branch and Bound and commercial heuristics are also tested so as to compare the performance of the presented solution approach. In order to demonstrate the goodness of the results, experiments for real case studies drawn from the main Spanish train operator, RENFE, are presented showing a good balance between optimality and computational times. Compared to commercial software, computational times are reduced more than 94%, without sacrificing optimality GAP.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01687163
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Nov 21 2018 3:06PM