客运专线乘务交路计划编制的优化模型与算法

Modeling and Solving the Crew Scheduling Problem of Passenger Dedicated Line

乘务交路计划是乘务人员的日工作计划,是客运专线运营管理的核心问题之一。针对该问题约束条件复杂、表述困难的特点,建立基于可行解的集覆盖模型进行描述。集覆盖模型是一个典型的组合优化问题,针对一般的分枝定界法求解问题规模不大、效率不高的不足,本文将适合求解大规模线性规划问题的列生成法嵌入分枝定界法,设计求解乘务交路计划问题的分枝定价算法,并重点描述实现该算法的3个关键问题:(1)初始解的生成;(2)价格子问题的求解;(3)分枝策略的确定。以京津城际铁路为背景,对提出的方法进行验证,结果表明,该方法能有效地求解乘务交路计划编制问题。

The crew schedule is the daily work plan of crews, and crew scheduling is one of the key problems in operation and management of passenger dedicated lines（PDL）. Due to the complex constraints which are difficult to describe in mathematical formula, a set covering model based on feasible solutions is built to describe railway crew scheduling problems. The set covering model deals with typical combinatorial optimization. Since general branch and bound algorithms are poor to solve large size integer problems, this paper embeds the column generation algorithm, which is proper to solve large size linear programming problem, into the branch and bound tree, called the branch and price algorithm, to solve the railway crew scheduling problems. Three core techniques of this algorithm are presented in detail： （1） initial solution generation; （2） solving pricing problems; （3） branching strategy. The performance of the algorithm is tested by the data of the PDL from Beijing to Tianjin. And the computational results demonstrate that this algorithm is effective.