基于任务均衡的城市轨道交通乘务任务轮转模型及算法

Crew Rostering Model and Algorithm Based on Balanced Workload in Urban Rail Transit

乘务计划是城市轨道交通运输组织的核心计划之一,优化乘务计划编制是保证日常行车安全和乘务员良好作息的重要手段。本文以乘务计划编制工作中的乘务任务轮转问题为研究对象,考虑各项任务轮转约束,以优化乘务员之间的任务均衡性为目标,建立城市轨道交通乘务任务轮转的0-1整数规划模型。由于模型变量规模较大,传统分支定界算法难以在较短时间内求得较优解,本文引入列生成思想和跟随分支策略设计该模型的快速求解算法。以实际某城市轨道交通线路乘务数据为例,通过实验发现,相对于传统人工轮转方法,本文模型求解的方案在任务均衡性和轮休安排方面具有明显优势,而在乘务员轮转规律性方面有所降低。

As crew schedule is one of the most important plans for urban rail transit,optimizing crew schedu-ling can improve the train operation safety and promote better work habits of the crews.This paper studies crew rostering problem,which is a part of crew scheduling problem.Rigorously considering the crew rostering constraints,a 0-1 integer model was proposed to balance the crew workloads.Given the large amount of 0-1 variables in the model,the use of the traditional branch and bound algorithm cannot deliver a better solution within a reasonable computing time.A fast algorithm based on column generation and branch on follow-ons was designed to solve the model.A real-world instance with crew operation data of a certain urban rail line was used to test the model and algorithm.The results show that the plan solved by the proposed model performs better in balancing workloads and arranging day offs for the crews than the traditional manual rostering plan,while the plan may deliver relatively poor work rostering regularity for the crews.