| Summary |
Li-Yu Chiang， 2006.06
Institute of Transportation Technology and Management
National Chiao Tung University
The goal of Mass Rapid Transit (MRT) system is to provide good service quality. The roster has great influence about the service quality and morale of drivers. The crew rostering of MRT drivers is an important problem. The scheduler not only has to provide a roster to satisfy all labor and the corporation regulations (hard constraints) but also needs to consider fitting individual preferences (soft constraints) as much as possible. This research is focused on the rostering problem for the Taipei Rapid Transit Corporation (TRTC), which has not been studied before.
Traditional methods to solve crew rostering problem are usually based on mathematical programming (MP) or heuristic method that is not efficient or difficult to describe the problem with complicated constraints in detail. In this research, we formulated the equitable crew rostering problem as a three-stage model with mathematical programming and constraint programming (CP). The first phase is the off-day scheduling problem, to which we applied integer programming to solve the problem. The second phase, shift scheduling problem, was formulated as constraint satisfaction problem (CSP) and solved by a CP model. The third phase, rostering problem, was also formulated as CSP and solved by a CP model to obtain an equitable roster.
We have applied our models to a case study of rostering data provided by TRTC. Using 1.29GHz personal computer and ILOG OPL Studio 3.7, we obtained a one-month roster which has 84 drivers in 5 minutes. In addition to all hard constraints, our results satisfied all the flexible constraints regarding the equity of the allocation of off days to drivers. Our model can generate feasible and equitable rosters very efficiently and provide as a reference for the scheduler. Future research may take crew scheduling problem into account to allocate driving hours more equally among drivers. |
