论文部分内容阅读
乘务交路计划是乘务人员的日工作计划,是客运专线运营管理的核心问题之一。针对该问题约束条件复杂、表述困难的特点,建立基于可行解的集覆盖模型进行描述。集覆盖模型是一个典型的组合优化问题,针对一般的分枝定界法求解问题规模不大、效率不高的不足,本文将适合求解大规模线性规划问题的列生成法嵌入分枝定界法,设计求解乘务交路计划问题的分枝定价算法,并重点描述实现该算法的3个关键问题:(1)初始解的生成;(2)价格子问题的求解;(3)分枝策略的确定。以京津城际铁路为背景,对提出的方法进行验证,结果表明,该方法能有效地求解乘务交路计划编制问题。
Passenger service plan is the daily work plan for crew members and is one of the core issues in the operation and management of passenger dedicated lines. In view of the complex constraints and the difficult expression of the problem, this paper establishes a set covering model based on feasible solutions. Set cover model is a typical combinatorial optimization problem. For general branch-and-bound method to solve the problem of small scale and low efficiency, this paper will fit the column generation method for large-scale linear programming problems embedded branch and bound method , A branch pricing algorithm is proposed to solve the scheduling problem in passenger service planning. Three key problems of this algorithm are described: (1) generation of initial solution; (2) solution of price sub-problem; (3) branch strategy determine. Taking the Beijing-Tianjin inter-city railway as the background, the proposed method is validated. The results show that this method can effectively solve the problem of crew planning.