×

zbMATH — the first resource for mathematics

A constraint programming-based approach to the crew scheduling problem of the Taipei mass rapid transit system. (English) Zbl 1306.90053
Summary: This paper addresses the crew scheduling problem for a mass rapid transit (MRT) system. The problem is to find a minimum number of duties to cover all tasks while satisfying all the hard and soft scheduling rules. Such rules are complicated in real-world operations and difficult to follow through optimization methods alone. In this paper, we propose a constraint programming (CP)-based approach to solve the problem. The approach involves a CP model for duty generation, a set covering problem model for duty optimization, and alternative ways to identify the final solution in different situations. We applied the proposed CP-based approach to solve a case problem for the Taipei MRT. Case application results using real-world data showed that our approach is capable of reducing the number of daily duties from 58 to 55 and achieving a 5.2 % savings in labor costs. We also incorporated the soft rule considerations into the CP model in order to generate alternative optimum solutions that would improve the workload balance. The coefficient of variation of the work time distribution improves significantly, falling from 21 % to approximately 5 %. Given the CP model’s comprehensive coverage of various scheduling rules, our proposed approach and models would also be applicable to other MRT systems.

MSC:
90B35 Deterministic scheduling theory in operations research
90C30 Nonlinear programming
Software:
OPL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Apt, K. R. (2003). Pricinples of constraint programming. Cambridge: Cambridge University Press. · Zbl 1187.68132
[2] Barnhart, C; Cohn, A; Johnson, E; Klabjan, D; Nemhauser, G; Vance, P; Hall, RW (ed.), Airline crew scheduling, No. 56, 517-560, (2003), New York
[3] Brailsford, SC; Potts, CN; Smith, BM, Constraint satisfaction problems: algorithms and applications, European Journal of Operational Research, 119, 557-581, (1999) · Zbl 0938.90055
[4] Caprara, A; Fischetti, M; Toth, P; Vigo, D; Guida, PL, Algorithms for railway crew management, Mathematical Programming, 79, 125-141, (1997) · Zbl 0887.90056
[5] Cavique, I; Rego, C; Themido, I, Subgraph ejection chains and tabu search for the crew scheduling problem, Journal of the Operational Research Society, 50, 608-616, (1999) · Zbl 1054.90546
[6] Chew, KL; Pang, J; Liu, QZ; Ou, JH; Teo, CP, An optimization based approach to the train operator scheduling problem at Singapore MRT, Annals of Operations Research, 108, 111-122, (2001) · Zbl 0993.90501
[7] Chu, SCK; Chan, ECH, Crew scheduling of light rail transit in Hong Kong: from modeling to implementation, Computers Operations Research, 25, 887-894, (1998) · Zbl 1042.90561
[8] Silva, A, Combining constraint programming and linear programming on an example of bus driver scheduling, Annals of Operations Research, 108, 277-291, (2001) · Zbl 1001.90029
[9] Desaulniers, G., Desrosiers, J., & Solomon, M. M. (2005). Column generation. New York: Springer. · Zbl 1084.90002
[10] Elizondo, R; Parada, V; Pradenas, L; Artigues, C, An evolutionary and constructive approach to a crew scheduling problem in underground passenger transport, Journal of Heuristics, 16, 575-591, (2010) · Zbl 1230.90122
[11] Ernst, AT; Jiang, H; Krishnamoorthy, M; Sier, D, Staff scheduling and rostering: A review of applications, methods and models, European Journal of Operational Research, 153, 3-27, (2004) · Zbl 1053.90034
[12] Fahle, T; Junker, U; Karisch, SE; Kohl, N; Sellmann, M; Vaaben, B, Constraint programming based column generation for crew assignment, Journal of Heuristics, 30, 59-81, (2002) · Zbl 1073.90542
[13] Ftulis, SG; Giordano, M; Pluss, JJ; Vota, RJ, Rule-based constraints programming: application to crew assignment, Expert Systems With Applications, 15, 77-85, (1998)
[14] Gabteni, S; Grönkvist, M, Combining column generation and constraint programming to solve the tail assignment problem, Annals of Operations Research, 171, 61-76, (2009) · Zbl 1179.90207
[15] Goumopoulos, C; Housos, E, Efficient trip generation with a rule modeling system for crew scheduling problems, Journal of Systems and Software, 69, 43-56, (2004)
[16] Grönkvist, M, Accelerating column generation for aircraft scheduling using constraint propagation, Computers and Operations Research, 33, 2918-2934, (2006) · Zbl 1086.90023
[17] Hooker, JN; Rossi, F (ed.); etal., Operations research methods in constraint programming, 527-570, (2006), Amsterdam
[18] ILOG. (2003). ILOG OPL Studio 3.7 Studio user’s manual. SA: ILOG. · Zbl 0993.90501
[19] Lustig, IJ; Puget, JF, Program does not equal program: constraint programming and its relationship to mathematical programming, Interfaces, 31, 29-53, (2001)
[20] Mackworth, AK, Consistency in networks with relations, Artificial Intelligence, 8, 99-118, (1977) · Zbl 0341.68061
[21] Park, T; Ryu, KR, Crew pairing optimization by a genetic algorithm with unexpressed genes, Journal of Intelligent Manufacturing, 17, 375-383, (2006)
[22] Puget, J. F. (1995). A comparison between constraint programming and integer programming. In Proceedings of the Conference on Applied Mathematical Programming and Modelling (APMOD95). Uxbridge: Brunel University
[23] Taipei City Government, Department of Civil Affairs. (2013). Statistics in population and each district households in Taipei city July-2013. Retrieved August 2, 2013, from http://www.ca.taipei.gov.tw/public/Attachment/3829432175.xls · Zbl 1230.90122
[24] Ticketing Center of Station Operations Division. (2013). Transport volume statistics: June-2013. Resource document. Taipei Rapid Transit Corporation. Retrieved July 5, 2013 from http://web.trtc.com.tw/RidershipCounts/E/10206e.htm · Zbl 0938.90055
[25] Van Hentenryck, P. (1999). The OPL optimization programming language. Combridge, MA: MIT Press.
[26] Hentenryck, P, Constraint and integer programming in OPL, Journal on Computing, 14, 345-372, (2002) · Zbl 1238.90102
[27] Wilson, N. H. M. (1999). Computer-aided transit scheduling (Vol. 471). Berlin: Springer. · Zbl 0920.00055
[28] Yunes, TH; Moura, AV; Souza, CC, Hybrid column generation approaches for urban transit crew management problems, Transportation Science, 39, 273-288, (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.