@techreport{TR-IC-00-18,
  number = {IC-00-18},
  author = {Tallys H. Yunes and Arnaldo V. Moura and Cid C. {de Souza}},
  title = {Hybrid Column Generation Approaches for Solving Real World Crew Management Problems},
  month = {December},
  year = {2000}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 38 pages.
    \par\selectlanguage{english}\textbf{Abstract}
      This article considers the overall crew management problem that
      arises from the daily operation of an urban transit bus company
      that serves the metropolitan area of the city of Belo Horizonte,
      in Brazil.
        \par
      Due to its intrinsic complexity, the problem is divided in two
      distinct problems, namely: crew scheduling and crew rostering.
      We have tackled each one of these problems using Mathematical
      Programming (MP) and Constraint Logic Programming (CLP)
      approaches. Besides, we also developed hybrid column generation
      algorithms for solving these problems, combining MP and CLP. The
      hybrid algorithms always performed better, when obtaining
      optimal solutions, than the two previous isolated approaches. In
      particular, they proved much faster for the scheduling problem.
        \par
      All the proposed algorithms have been implemented and tested
      over real world data obtained from the aforementioned company.
      The coefficient matrix of the linear program associated with
      some instances of the scheduling problem contains tens of
      millions of columns, and this number is even larger for the
      rostering problem.
        \par
      The analysis of our experiments indicates that it was possible
      to find high quality, and many times optimal, solutions that
      were suitable for the company's needs. These solutions were
      obtained within reasonable computational times, on a typical
      desktop PC.
  }
}