A Crew Scheduling with Chinese Meal Break Rules

An efficient crew scheduling can significantly reduce the operational cost for transit enterprises. However, the crew scheduling problem, known to be NP-hard, is complicated by the fact that there are many restrictions on the shift generation. Moreover, there are some special requirements in China, for example, meal break is normally required to be taken during the conventional time ranges for lunch or dinner, which is called a Chinese meal break rule to distinguish from the western ones. It also makes the existing crew scheduling approaches encountering difficulties. On the basis of the “generate and select” approach to solve the crew scheduling problem, this paper proposes an approach to handling the Chinese meal break rule in the phase of “generate”. Taking advantages of the characteristics of Chinese meal break rule and problem domain knowledge, a heuristic-based approach is proposed to select some promising relief opportunities (ROs). A shift generation approach is then devised to generate a large set of potential shifts that satisfy the Chinese meal break rule. Experimental results from 12 groups of real-world problem instances demonstrate the success of the proposed approach, which can greatly reduce the number of potential shifts generated. Therefore, it is suggested that the proposed approach be used to solve the large scale crew scheduling problems with Chinese meal break rule.

摘要：有效的乘务调度能够为公交企业带来巨大的成本节约，但是，公交乘务调度问题因受制于一系列劳动法规的约束变得十分复杂。我国公交普遍存在的“中式用餐”约束，进一步加大了问题的复杂性，使得西方主流调度系统面临困难。本文基于“生成与选择”方法解决乘务调度问题，关键在于“生成”阶段处理“中式用餐”难题；利用“中式用餐”约束和乘务问题特点，设计一种基于启发式规则的换班机会筛选方法；在所选换班机会集合的基础上构造能满足“中式用餐”约束的潜在乘务班次集合。对实际公交乘务调度问题中的12组实例进行测试，表明本文方法不仅能处理 “中式用餐”约束，而且能极大减少所求问题的规模，因此适用于解决大规模的带有“中式用餐”约束的乘务调度问题。