基于TOP的地铁乘务交路优化模型及算法研究

Study on Optimization Model and Algorithm for Metro Crew Routing Based on TOP

针对地铁乘务交路时长不均衡、停留等待时间过长和乘务交路编制效率低下的现状,结合乘务基地配置和乘务劳动作业规定,将车辆周转图分割成若干个乘务作业片段,并将其抽象为节点,建立时空网络有向图,将乘务交路优化问题转换为团队定向问题,建立了以乘务交路时长均衡和停留等待时间最小为优化目标的乘务交路优化模型;针对乘务交路数量的不确定性,结合时空网络有向图的特性,在标准蚁群算法的基础上,设计了交叉蚁群算法求解模型;以成都地铁某线路为例,对模型和算法进行验证。结果表明:交叉蚁群求解模型和算法能够有效地表征乘务交路优化问题,并获得较优的乘务交路方案,为下一步的乘务指派奠定基础。

For the current situation of the duration imbalance, long waiting time and low preparation efficiency of the metro crew routing, the spatiotemporal network directed graph is built by dividing the vehicle circling diagram into lots of crew operation segments which are abstracted as nodes according to the configuration of the crew depots and the regulations for crew labor operation.The optimization model of crew routing with the optimization objectives of balancing the crew routing duration and minimizing the waiting time is constructed by converting the crew routing optimization problem into the team orienteering problem. To address the uncertainty of the crew routing number, the cross-ant colony algorithm is designed to solve the model based on the standard ant colony algorithm by combining the properties of spatiotemporal network directed graph. Finally,the model and algorithm are validated in the context of a line of Chengdu metro, which can effectively represent the crew routing optimization problem and obtain the better crew routing solution, setting the foundation for the next step of crew assignment.