地铁车辆预防性检修计划优化模型与算法

Optimization Model and Algorithm of Preventive Maintenance Schedule for Metro Rolling Stock

地铁车辆检修作业的效率直接影响地铁正线运营的安全和能力,针对地铁车辆预防性检修计划优化问题,综合考虑车辆检修制度、正线列车运营需求、班组检修能力等因素,以计划时间段内安排的检修作业最多和车辆平均利用率最高为目标,建立车辆检修计划多目标混合整数非线性规划模型。为快速求得最优解,在基本回溯算法中引入检修变量,按照开始时刻的可能最小取值静态排序启发式、变量取最小值的动态排序启发式和基于检修周期的约束传播技术,并依据多个目标函数之间的优先级,分层迭代求得整个模型的最优解。最后通过算例验证模型和算法的有效性。

The efficiency of metro rolling stock maintenance directly affects the safety and capability of train operation in the main line.Aiming at the optimization of the preventive maintenance schedule for metro rolling stock,a multi-objective mixed integer nonlinear programming model was presented in this paper to improve the efficiency of maintenance as well as the availability of the rolling stock in the planning horizon.In the model,the vehicle maintenance systems,train operation timetable of the main line and maintenance capacity of the crews were taken into comprehensive consideration.To obtain the optimal solutions quickly,after imbedding into the basic backtracking algorithm with static variable ordering heuristics according to a possible minimum value of the start time of the maintenance,dynamic value ordering heuristics according to the minimum value and constraint propagation based on the maintenance cycle,the final solution of the whole model was optimized by the improved backtracking algorithm iteratively,according to the priority of the multiple objective functions.Finally,the effectiveness of the model and the algorithm was verified by the instances from Chengdu Metro Line 2in China.