標題: A constraint programming-based approach to the crew scheduling problem of the Taipei mass rapid transit system
作者: Han, Anthony F.
Li, Elvis C.
運輸與物流管理系 註:原交通所+運管所
Department of Transportation and Logistics Management
關鍵字: Crew scheduling problem;Mass rapid transit;Constraint programming;Set covering problem
公開日期: 1-十二月-2014
摘要: 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.
URI: http://dx.doi.org/10.1007/s10479-014-1619-1
http://hdl.handle.net/11536/123877
ISSN: 0254-5330
DOI: 10.1007/s10479-014-1619-1
期刊: ANNALS OF OPERATIONS RESEARCH
Volume: 223
起始頁: 173
結束頁: 193
顯示於類別:期刊論文


文件中的檔案:

  1. 000345073400009.pdf