A constraint programming-based approach to the crew scheduling problem of the Taipei mass rapid transit system

檔案

日期

2014-12-01

類型

期刊名稱

ANNALS OF OPERATIONS RESEARCH

卷期與頁次

第 223 卷,頁 173–193

ISSN

0254-5330

語言

英文

摘要

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.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Han, A. F., & Li, E. C. (2014). A constraint programming-based approach to the crew scheduling problem of the Taipei mass rapid transit system. ANNALS OF OPERATIONS RESEARCH, 223, 173–193. https://doi.org/10.1007/s10479-014-1619-1

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/123877