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

马 亮， 郭 进， 张晓霞

(1. 电子科技大学 光电信息学院，四川 成都 610054；2.西南交通大学 信息科学与技术学院，四川 成都 610031)

地铁车辆运行一段时间或者一定距离后需要进行检修，车辆检修是车辆基地(包括车辆段和停车场)的工作重点。据统计，车辆检修成本约占地铁总维修成本的40%，检修效率将直接影响列车正线运营能力，有必要通过编制车辆检修计划，统筹安排各类修程的检修作业，降低检修成本和延长车辆使用寿命。

目前，主要采用人工方式安排检修作业，效率较低且易出现问题。因此，需要研究地铁车辆检修计划的优化理论及方法，以智能形式编制检修计划。文献[1]系统地提出改进地铁检修制度的措施，压缩检修停时和提高车辆周转效率；在检修制度确定的前提下，文献[2-4]通过计算机技术建立车辆检修信息系统，辅助检调指挥日常检修作业。但文献[2-3]中信息系统的功能仅限于检修计划的增、删、改以及派工等；文献[4]建立检修工单调度0-1规划模型，通过改良的遗传算法生成检修工单，实现检修作业和人员间的最大匹配，但模型存在技能指标无法确定和不断变化的情况；文献[5]建立考虑检修车辆路由问题的混合整数规划模型，使用分支定界和列生成策略确定每一路径的列车开行方案；文献[6]针对线路维护班组调度问题，建立时空网络模型，并使用多邻域搜索算法求解。但是文献[5-6]没有考虑检修与列车运行之间的协调问题，且没有为每辆车安排检修计划。

地铁车辆的检修包括预防性检修和事后维修。相对于预防性维修，事后维修的随机性比较大，无法在检修计划中考虑；在预防性维修中，日检是每个次日上线运行车辆必须进行的。预防性检修计划是根据车辆的运行状态、运行周期、正线列车运行需求和班组检修能力，确定每日车辆的预防性检修内容、时间、班组等。因此，本文讨论的检修是指不包含日检的预防性检修，主要研究内容为当地铁车辆检修制度、正线列车运行需求、班组检修能力等因素确定时，以检修修程、检修周期、班组检修能力、上线运行车数为限制条件，以安排的检修作业总数最多为主要目标，以车辆的平均利用率最高为次要目标，建立地铁车辆预防性检修计划的多目标混合整数非线性规划模型，并设计改进的回溯算法快速迭代求解，从整体上提高车辆基地检修作业的效率和车辆的利用率。

1 多目标混合整数非线性规划模型

1.1 假设

为建立地铁车辆预防性检修计划优化模型，作如下假设：

(1) 检修制度、日运行图、日班组检修能力和每辆投入运行车辆的时间等数据确定且不变；

(2) 每项检修只要开始即不可被中断，直到结束；

(3) 每项检修从开始至结束仅由1个检修班组承担，1个班组同一时间仅承担1项检修；

(4) 仅有1个检修基地，即1个车辆段，没有附属停车场，表示车辆检修没有分场要求。

1.2 变量

( 1 )

( 2 )

( 3 )

规定只要检修在计划时间范围T内开始，即可认为此项检修属于本计划，则本计划时间范围T内安排检修rj的最少、最多次数分别为

( 4 )

式中：tNT为计划阶段T的结束时刻。

车辆ci在时间T范围内所有检修总的最少、最多次数分别为

( 5 )

令第l次检修rj的持续时间范围为

( 6 )

在时间范围T内安排检修rj的最大的时间范围和安排所有检修的最大时间范围分别为

( 7 )

1.3 目标函数

编制车辆检修计划时受限于检修周期、检修班组能力、向正线交车数量等，不能保证每项检修均可以成功进行。因此，车辆检修计划的主要目的是在满足各种限制的前提下尽量多地安排检修作业，即

( 8 )

为合理减少车辆的检修次数和过多检修带来的额外损耗，提高车辆的周转率，保证检修基地向正线交车能力，检修计划优化的次要目标为车辆的平均停修时间最短，等价于车辆的平均利用率最高，即

( 9 )

1.4 约束

编制检修计划需要满足检修制度要求，即包括修程自身的周期和停修时间要求、不同修程之间的周期限制、正线交车数量限制、日检修量不得超过班组检修能力等。

(1) 任意车辆在同一时间只能进行一项检修，即检修唯一性约束表达式b1为

(10)

(2) 相邻的同类检修之间需要满足检修周期限制，则检修周期约束表达式b2为

(11)

(3) 大修程后跟随小修程时，需要满足小修程的检修周期限制的约束表达式b3为

i=1,2,…,NCj1,j2=1,2,…,NR

(12)

式中：pj1

(4) 某检修一旦开始即不能被中断直至结束，则检修作业不可中断约束表达式b4为

vi,j1,k1×yj1=vi,j2,k2×yj2

i=1,2,…,NCj1,j2=1,2,…,NR

(13)

式中：yj1、yj2分别为检修rj1、rj2的种类名称。

(5) 大修程检修覆盖小修程检修约束

如果计划时间段内某时刻某车辆既可安排小修程，又可安排大修程，则安排大修程，如：每4次定修后需进行1次架修等。大修程覆盖小修程的约束表达式b5为

oi,j1,l1>oi,j2,l2

i=1,2,…,NCj1,j2=1,2,…,NR

(14)

(6) 检修能力限制

每天班组的车辆检修总能力是有限的，即每天同时检修的总车辆数是有限的。因此，班组检修能力的约束表达式b6为

(15)

式中：ak为tk时扣除日检班组后剩余班组检修能力。

(7) 向正线交车数量限制

为满足运行图要求，每天从车辆检修基地送往正线运行的车辆数是确定的，即向正线交车数量限制的约束表达式b7为

(16)

式中：gk为tk时向正线的最大交车数量；ej为检修rj是否影响车辆的正线运行，ej=1表示影响，否则，表示不影响。

1.5 分层迭代算法

本模型中两个目标函数的优化是冲突的，只有在目标函数式( 8 )基础上再优化目标函数式( 9 )才有意义。因此，依据两个目标函数之间的优先级，设计分层迭代算法[7-8]求解整个模型。

S(xi,j,l)={xi,j,l|bm(xi,j,l)=1

(17)

则上层优化的最优解集记为

(18)

(19)

则ψ2(xi,j,l)为整个规划模型的最优解集。

分层迭代算法将多目标优化分解为两个组合优化过程，每层优化的方法主要有确定型和启发式算法，但由于本模型规模较大，为加快求解速度，需要改进基本回溯算法。

2 改进回溯算法

2.1 变量静态排序启发式

2.2 变量取值动态排序启发式

2.3 约束传播技术

为动态约减临时解空间，在基本回溯算法中引入约束传播技术。约束传播包括减域和传播两部分，主要思想：当某1个变量论域被修改，则所有与之相关的变量都要调用减域算法修改论域，如此反复，直到所有变量的论域都约减到最小。依据检修周期约束式(11)和约束式(12)，以及相邻检修开始时刻与结束时刻关系，见式( 2 )。假设第l-1次检修rj的开始时刻和结束时刻确定，那么第l次检修rj的开始时刻和结束时刻的范围将缩小为

(20)

则再依据传播式

(21)

对第l次之后的检修rj的开始时刻与结束时刻的取值范围进行约减。

2.4 算法步骤

假设模型的最优解集记为ψ1，所有约束bm(m=1,…,7)组成的约束集记为B，调用约束传播算法记为Cpr(B)，则改进回溯算法(Improved-BT)求解以式( 8 )为目标函数的上层模型的步骤为:

Step3从第1个车辆的第1个检修构成的搜索树第1层开始深度搜索i←1，ni←1；

Step4如果i≥1且ni≥1，转step5，否则，转step10；

Step5当oi,ni≥0，则oi,ni←oi,ni-1，如果oi,ni=1，则转step6，如果oi,ni=0，转step7；

Step7对变量取值进行合法性检查。如果∀m=1,…,8, (bm(xi,ni)=1)，则转step8，否则，如果oi,ni=1转step6；

Step9如果i=NC，则返回最优解ψ1←ψ1∪{}，否则，尝试为下一个车辆安排检修作业，令i←i+1，并转step4；

3 算例分析

3.1 算例求解

表1 成都地铁2号线预防性检修

本算例的检修总数为1 575次，变量有4 725个，约束的数量级大约为百万，总迭代次数的数量级为亿。在Inter Core i3-2310M 2.1GHz & DRAM 2G & Windows XP & NET Framework 4.5环境下的PC机上运行本模型及算法。图1为改进回溯算法求解以式( 8 )为目标函数的上层模型，并得到最优解集ψ1。

由图1可得，在11.8 s的时候迭代收敛到第1个最优解，总的回溯次数为1 271 次，此时车辆最多需要进行1 225次检修，平均停修时间为1 d。由目标函数式( 8 )优化得到最优解之后，再求解以ψ1为可行解集和以式( 9 )为目标函数的下层模型，图2为求解过程。

本算例目标函数式( 8 )最大值1 225的最优解只有1个，在此基础上再求目标函数式( 9 )的最优解，直到求解时间上限的60 s的最小取值为1 d，最后得到整个规划模型的最优解，见表2。

表2 检修计划安排情况 d

续表2 检修计划安排情况 d

3.2 结果分析

在最优检修计划中，每辆车的登顶次数为59次，第1～10辆车的双周检次数为22次，第11～15辆车的双周检次数为23次。

第1辆车的第1次三月检开始和结束日期的取值范围分别为[83,99]和[85,101]，在[83,101]之间没有连续3 d的总检修次数满足检修能力约束式(15)和向正线交车约束式(16)。因此，第1辆车没有安排第1次三月检，也不会安排之后的三月检。同理，其他车辆也没有三月检计划。由于定修、大修和架修的检修周期均超过1年，因而检修计划中不包含定修、大修和架修。

(1) 安排第1辆车的第1次双周检之后，依据2.3节约束传播算法，第1辆车的第2次双周检开始日期的取值范围由[26,38]变为[29,32]；

(2) 依据变量取值动态排序启发式优先赋值为29 d，但是第6～10辆车的第1次双周检起止日期均为29 次。因此，依据检修能力约束式(15)和向正线交车约束式(16)排除第29 d；

(3) 再依据变量取值动态排序启发式尝试赋值为30 d，但是第11～15辆车的第1次双周检起止日期都为30 d。因此，依据检修能力约束式(15)和向正线交车约束式(16)排除第30 d；

(4) 再尝试赋值为31 d，满足所有约束。

同理，尝试安排其他检修，最终得到最优的预防性检修计划。

3.3 算法分析

在BT1、BT2和BT3算法中尝试引入不同于本算法的变量静态排序启发式和变量取值动态排序启发式，生成不同结构的搜索树，使得前3个算法在前期收敛到较差解的概率较大，通过图3验证可得本算法求得的最优解和求解效率比前3个算法明显好。引入约束传播技术，在搜索过程中约减变量的临时论域，使得总迭代次数比算法BT4减少数10倍，经统计两种算法总迭代次数分别为3 992 次和44 529 次。即使约束传播技术消耗一定时间，但是总求解效率比BT4高。

4 结论

本文综合考虑地铁车辆检修制度、正线运行需求、班组检修能力等因素，建立车辆预防性检修计划多目标混合整数非线性规划模型，并设计改进回溯算法快速求解，提高车辆的检修效率，保障车辆正线运行的安全性。在预防性检修计划优化基础上再考虑每日事后性维修的不确定性和每日不同时刻向正线的交车数量限制，动态优化日检修计划。今后，进一步研究地铁车辆运行计划与车辆检修计划的综合优化问题，使之全面提高地铁车辆基地服务正线运行的水平。

参考文献：

[1] 吴强.地铁车辆检修修制改进的探讨[J].现代城市轨道交通,2007(2):53-54.

WU Qiang. Discussion for Improvement of Inspection and Maintenance System for Metro Vehicles[J]. Modern Urban Transit, 2007(2):53-54.

[2] 吴胡俊实. 地铁车辆检修管理信息系统的设计与开发[D].成都:西南交通大学,2012:13-56.

[3] 曾星瑜. 地铁车辆检修信息系统的开发[D].成都:西南交通大学,2012:22-45.

[4] 唐登仕. 地铁车辆检修调度管理系统的设计与实现[D].广州:华南理工大学,2013:6-19.

[5] ANDRES J, CADARSO L, MARIN A. Maintenance Scheduling in Rolling Stock Circulations in Rapid Transit Networks[J]. Transportation Research Procedia, 2015, 10:524-533.

[6] PENG F, OUYANG Y. Track Maintenance Production Team Scheduling in Railroad Networks[J]. Transportation Research Part B:Methodological, 2012, 46(10):1 474-1 488.

[7] 刘三明. 多目标规划的理论方法及其应用研究[M]. 上海：上海交通大学出版社,2014:23-29.

[8] 胡长英. 双层规划理论及其在管理中的应用[M]. 北京：知识产权出版社,2012:12-38.

[9] GOLOMB S W, BAUMERT L D. Backtrack Programming[J]. Journal of the ACM, 1965, 12(4):516-524.

[10] BACCHUS F, RUN P V. Dynamic Variable Ordering in CSPs [C]//ACM Sigart Sigplan. 1st International Conference on Principles and Practice of Constraint Programming. Berlin Heidelberg, German:Springer Berlin Heidelberg, 1995:258-275.

[11] HUANG J, DARWICHE A. A Structure-based Variable Ordering Heuristic for SAT[C]//The International Joint Conferences on Artificial Intelligence (IJCAI). Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. United States: International Joint Conferences on Artificial Intelligence, 2003:1 167-1 172.

[12] HOOKER J. Logic, Optimization and Constraint Programming[J]. Informs Journal on Computing, 2002, 14(4): 295-321.

[13] ROSSI F, VAN BEEK P, WALSH T. Handbook of Constraint Programming[M]. Pisa: Elsevier, 2006:103-109.