TY - JOUR

T1 - Cyclic and non-cyclic crew rostering problems in public bus transit

AU - Xie, Lin

AU - Suhl, Leena

PY - 2015/1/1

Y1 - 2015/1/1

N2 - The crew rostering problem arises in public transport bus companies, and addresses the task of assigning a given set of anonymous duties and some other activities, such as standbys and days off, to drivers or groups of drivers, without violating any complex labor union rules. In addition, the preferences of drivers are considered during the assignment. The plan generated for each driver/group of drivers is called a roster. Optimal rosters are characterized by maximum satisfaction of drivers and minimal operational costs. To generate a personalized roster for each driver/group of drivers, the problem is formulated as a multi-commodity network flow problem in this paper. In each network layer, a roster is generated for each driver or driver group. The network model is very flexible and can accommodate a variety of constraints. In addition, with a minor modification, the network can formulate the cyclic and non-cyclic crew rostering problems. To the best of our knowledge, this is the first publication which solves both problems with one model. The main goal of this paper is to develop a mixed-integer mathematical optimization network model for both problems with sequential and integrated approaches and to solve this model using commercial solvers. Both problems are usually solved with the sequential approach. Therefore, another contribution of this paper is comparing the sequential approach with the integrated one. Our experiments on real-world instances show that the integrated approach outperforms the sequential one in terms of solution quality.

AB - The crew rostering problem arises in public transport bus companies, and addresses the task of assigning a given set of anonymous duties and some other activities, such as standbys and days off, to drivers or groups of drivers, without violating any complex labor union rules. In addition, the preferences of drivers are considered during the assignment. The plan generated for each driver/group of drivers is called a roster. Optimal rosters are characterized by maximum satisfaction of drivers and minimal operational costs. To generate a personalized roster for each driver/group of drivers, the problem is formulated as a multi-commodity network flow problem in this paper. In each network layer, a roster is generated for each driver or driver group. The network model is very flexible and can accommodate a variety of constraints. In addition, with a minor modification, the network can formulate the cyclic and non-cyclic crew rostering problems. To the best of our knowledge, this is the first publication which solves both problems with one model. The main goal of this paper is to develop a mixed-integer mathematical optimization network model for both problems with sequential and integrated approaches and to solve this model using commercial solvers. Both problems are usually solved with the sequential approach. Therefore, another contribution of this paper is comparing the sequential approach with the integrated one. Our experiments on real-world instances show that the integrated approach outperforms the sequential one in terms of solution quality.

KW - Business informatics

KW - Transportation

KW - Crew rostering

KW - Multi-commodity network flow

KW - Cyclic crew rostering

KW - Non-cyclic crew rostering

UR - http://www.scopus.com/inward/record.url?scp=84939550863&partnerID=8YFLogxK

U2 - 10.1007/s00291-014-0364-9

DO - 10.1007/s00291-014-0364-9

M3 - Journal articles

VL - 37

SP - 99

EP - 136

JO - OR Spectrum

JF - OR Spectrum

SN - 1436-6304

IS - 1

ER -