Hybrid column generation approaches for urban transit crew management problems

dc.creatorYunes, TH
dc.creatorMoura, AV
dc.creatorde Souza, CC
dc.date2005
dc.dateMAY
dc.date2014-07-30T17:59:36Z
dc.date2015-11-26T16:48:16Z
dc.date2014-07-30T17:59:36Z
dc.date2015-11-26T16:48:16Z
dc.date.accessioned2018-03-28T23:34:41Z
dc.date.available2018-03-28T23:34:41Z
dc.identifierTransportation Science. Inst Operations Research Management Sciences, v. 39, n. 2, n. 273, n. 288, 2005.
dc.identifier0041-1655
dc.identifierWOS:000229045500009
dc.identifier10.1287/trsc.1030.0078
dc.identifierhttp://www.repositorio.unicamp.br/jspui/handle/REPOSIP/68951
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/68951
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1275093
dc.descriptionT his 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.
dc.description39
dc.description2
dc.description273
dc.description288
dc.languageen
dc.publisherInst Operations Research Management Sciences
dc.publisherLinthicum Hts
dc.publisherEUA
dc.relationTransportation Science
dc.relationTransp. Sci.
dc.rightsaberto
dc.sourceWeb of Science
dc.subjectpublic transportation
dc.subjectcrew scheduling
dc.subjectconstraint programming
dc.subjecthybrid algorithms
dc.subjectcolumn generation
dc.subjectRostering Problem
dc.subjectSteiner Trees
dc.subjectPacking
dc.titleHybrid column generation approaches for urban transit crew management problems
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución