Hybrid Column Generation Approaches for Urban Transit Crew Management Problems

Tallys H. Yunes (), Arnaldo V. Moura () and Cid C. de Souza ()
Additional contact information
Tallys H. Yunes: Institute of Computing, University of Campinas, Caixa Postal 6176, CEP 13084-971, Campinas, SP, Brazil
Arnaldo V. Moura: Institute of Computing, University of Campinas, Caixa Postal 6176, CEP 13084-971, Campinas, SP, Brazil
Cid C. de Souza: Institute of Computing, University of Campinas, Caixa Postal 6176, CEP 13084-971, Campinas, SP, Brazil

Transportation Science, 2005, vol. 39, issue 2, 273-288

Abstract: This article considers the overall crew management problem arising from the daily operation of an urban transit bus company that serves the metropolitan area of the city of Belo Horizonte, Brazil. Due to its intrinsic complexity, the problem is divided in two distinct subproblems: crew scheduling and crew rostering . We have investigated each of these problems using mathematical programming (MP) and constraint logic programming (CLP) approaches. In addition, we 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 to be much faster for the scheduling problem. 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; this number is even larger for the rostering problem. 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 desktop PC.

Keywords: public transportation; crew scheduling; constraint programming; hybrid algorithms; column generation (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1030.0078 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:39:y:2005:i:2:p:273-288

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().