城轨交通乘务任务配对的集合分割模型及算法

Set Partition Model and Algorithm for Crew Pairing Problem in Urban Rail Transit

摘要:

基于城轨乘务值乘规则，建立了城轨乘务任务配对的集合分割模型（R CP），并结合列生成思想和跟随分支策略设计了求解算法（CGBF算法）.实例验证结果表明：该模型与算法能够满足乘务任务配对方案的要求，相对于当前手工编制，具有编制效率高、目标函数更优（即任务数量少、任务工作效率高）等特点.

关键词:城市轨道交通; 乘务任务配对; 集合分割问题; 列生成思想; 跟随分支策略

Abstract:

A set partition model (R CP) for the crew pairing problem in urban rail transit was proposed based on practical considerations in rail transit operations. A hybrid algorithm of column generation and branch on follow ons (CGBF) was designed to solve R CP. The numerical results show that the proposed model and algorithm can meet requirements of crew pairing and yield better objective values than the existing manual methods.

Key words:urban rail transit; crew pairing problem; set partition problem; column generation; branch on follow ons