基于列生成算法的动车组检修计划优化  

Column Generation Algorithms Based Optimization Method for Maintenance Scheduling of Multiple Units

作　　者：王莹[1] 刘军[1] 苗建瑞[1] 

机构地区：[1]北京交通大学交通运输学院,北京100044

出　　处：《中国铁道科学》2010年第2期115-120,共6页China Railway Science

基　　金：国家自然科学基金资助项目(60674006)

摘　　要：基于动车组运用维修规程的特点,研究动车组检修计划的优化问题。构建动车组交路段和动车组检修基地相互关系的接续网络,刻画动车组担当交路段、进行检修、等待检修3种状态。进一步考虑交路段覆盖约束、检修弧能力约束和路径数量约束,以动车组可行运用计划为决策变量,以待检动车组检修前的累计运行里程最大化为目标函数,建立动车组检修计划优化模型。针对优化模型的决策变量数远远大于约束条件数量的特点,设计将列生成算法嵌入分枝定界算法的分枝定价求解算法。以广深线14列动车组的交路计划为例,采用给出的模型和算法进行动车组检修计划优化。结果表明:优化的动车组检修计划提高了动车组运用效率;只有当检修能力和备用车数量匹配时,才会使动车组得到充分的利用。Based on the characteristics of the code for operation, inspection and repair of multiple units （MU）, the optimization problem for the maintenance scheduling of MU was studied. The continuation network representing the correlation between the MU routing section and maintenance stations was built. Three MU states were described on this network, they are, cover routing section, being maintained and waiting for maintenance. Then, considering the covering, maintenance capability and routing number constraints, this paper builds an integer linear programming model with maximum traveling mileage of train units before maintenance as objective. Due to the characteristic that the number of decision variables are more than the number of constraints, this paper solves the model by applying branch-and-price algorithm. The effectiveness of the algorithm is tested by the rolling stock routing data of railway from Guangzhou to Shenzhen. The result shows that good maintenance routing can enhance the productivity of rolling stock and the productivity is maximal only when the maintenance capability and the number of spare train units are suited.

关 键 词：动车组 检修计划 接续网络 列生成算法 分枝定价算法 

分 类 号：U269[机械工程—车辆工程]