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

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

冯厚志

500227198711144613

摘要：根据旅客列车运行时间不均衡、停留等待时间长、乘务交路编制效率不高的情况，根据车站布局和乘务工作规范，将列车运行图分解为多个机组工作单元，并抽象为一个节点，构建了一个空间-空间网络有向图，把乘务交路的优化问题转化为群体导向问题，并提出了以乘客交路时间均衡和停留等待时间最少为优化目标的乘务交路优化模型；由于乘务交路数目的不确定性，并根据有向图的特点，提出了基于标准蚂蚁算法的交叉蚂蚁算法。通过成都一条轨道交通的实例，对该模型及算法进行了验证。研究结果显示，该方法可以有效地描述乘务交路的优化问题，得到乘务交路的最优解，从而为下一步的分配打下了良好的基础。

关键词：地铁；交通线路；队伍方向问题；车辆循环曲线；时间-空间网络；交叉蚂蚁算法

前言

列车运行规划是轨道交通运行规划中的一个重要组成部分，它直接影响着列车运行的时间、效率、人力成本、运输任务的顺利完成。为了提高乘务使用的效率，减少人员的费用，许多学者都从乘务的交路、乘务轮班等角度来探讨乘务的最佳化。

为了减少编组工作的复杂性，一般将乘务作业编制分为两个阶段：①将运输作业转化为乘务值乘作业，也就是编制乘务路线；②将乘务员的值乘工作指派到乘务员，也就是乘务员的排班表或乘务员的换班。本论文主要研究乘务交路编制的最佳化问题，将乘务交路规划优化问题转化为团队定路问题，以最短时长、最短停留时为目标的乘务交路，从而为下一阶段的乘务交路设计提供依据。

1条轨道交通线路优化问题的探讨

1.1小组方向

假定有n个结点和m辆汽车，m辆汽车从同一个起点开始，对n个结点进行访问，每个汽车在进入节点时都会得到一定的好处（当这个好处被汽车收集后，其他车辆将不能再进入这个节点），最后m辆汽车返回同一个目的地。从n个结点中选择每个车辆的存取路径，这样m车辆的整体效益就会达到最大。这种问题叫做TOP问题。

1.2轨道交通线路的优化设计

车辆周转计划是指在运载计划下，由运载计划决定的乘务值乘任务。乘务交路的起始点为乘务交路，即为乘务交路的出勤点和起始点；结束和结束时间是空姐休息或离开的地方和时间；乘务交路长度是指乘务人员连续值班的时间。乘务交路可以按照下面的程序来进行。

1)按照机组驻地的实际情况，对列车运行路线进行分割，得出机组运行的片断。

从图1可以看出，3个机组将运输路线图分成14个工作段。在分区时，如果没有转机条件，可以将两个从车站返回的空勤工作段合并成1个空勤任务，如图1所示，将A和B合并成一个完整的空勤工作段7。

图1乘务作业片段示意

2）根据约束条件对作业片段进行组合

如果将每个乘务作业片段看作一个乘务交路，则意味着每个乘务人员在每个乘务基地均需要休息、就餐或退勤，导致乘务人员数增加，效率不高，并且不利于后期的乘务排班[1]。为提高乘务员的工作效率，必须按照一定的约束条件将乘务作业片段进行组合，形成乘务交路。例如，将图1中编码为1、3、7、10、13的乘务作业片段进行组合，形成乘务交路1-3-7-10-13。该交路表示乘务人员既在乘务基地2出勤，也在乘务基地2退勤。不同的乘务作业片段组合形成不同的交路方案。

图2时空网络有向图G

2乘务交路优化模型

2.1符号定义

令G=(V，E)为时空网络图，其中：V={vi|i=0，1，⋯，n，n+1}为乘务作业片段集合（v0和vn+1为虚拟乘务作业片段）；E={eij|vj接续vi，i≠j}为乘务作业片段之间的有向弧集，e

ij为乘务作业片段vi和vj之间的接续弧。

2.2优化目标

1）目标1：乘务交路时长均衡。

乘务交路时长f1表示值乘任务的用时。为保证后期进行乘务排班时乘务人员的任务均衡，将乘务交路时长均衡作为优化目标，用乘务交路时长的标准差表示

2）目标2：乘务停留等待时间最小。

弧长tij表示乘务员在连续承担vi和vj任务期间需要停留等待的时间。为提高乘务员的工作效率，将乘务停留等待时间f2最小作为另一个优化目标。

3交叉蚁群算法

蚁群算法的求解是由多个蚂蚁在一张图中寻找最优的路线，而乘务交路则是在一张图中找到多条最佳路线，并且不能预先决定乘务交路数目。此外，由于蚁群算法采用了信息素的正反馈，因此很容易陷入局部最优解的求解中[2]。为了克服蚂蚁算法存在的问题，提出了一种基于交叉蚂蚁的算法。

3.1图形G的特征分析

引理1：有一组结点，其中的单元仅可以与虚拟结点v0相连接。

假定没有集合Γ，那么，对于（i≠0,n+1)，使eji为E。然而，最早的列车对应的节点是不存在使ejiE的节点vj（j≠0）。很明显，这个假定是无效的。

引理2：如果集合Γ中的单元数目是m，那么在任何一个交通线路中，其交叉点的数目都不会少于m。

假定交路中的交路数目少于m，那么集合中至少有两个结点位于同一交路上，这与1的引理冲突，假定不成立。

3.2列车运行路线的选择

通过一种动态的方式确定了空乘线路的数目，也就是在已寻优的情况下。

Step1在引理1的基础上，按照G的方向，决定集合的数目m。

步骤2按照引理2，把m个蚂蚁放在m组中。

Step3m蚂蚁是根据蚁群算法的搜索规律以及模式的限制条件来完成的。

Step4:m蚂蚁在没有找到下一个节点的情况下，如果m的蚂蚁都在vn+1的虚拟节点上，那么就转Step6，否则就是Step5。

Step5：在图G中删除m只蚂蚁所访问的节点及关联的弧，形成图G″。根据引理3，G″和G具有相同的属性，可根据图G″确定集合Γ″（只能接续v0的节点集合）。记集合Γ″中元素个数为m″，令Γ=Γ∪Γ″，m=m+m″，转Step2。

Step6m蚂蚁的搜索路线构成了一个解决方案，完成了搜索。

4实例仿真

在成都市的轨道交通规划中，有403条线路，其中19条线路的运行图中，有19条线路的运行图被用来进行运输。该线设有高大路停车场、太平园站、板桥车场3个乘务基地。双流西站、新平站是离板桥汽车段和高大路停车场最近的站点。另外，花桥车站是不具备乘务休息条件的回程站点，因此，在划分车辆周转图时，花桥车站不能被视为区段。

针对太平园站、双流西站、新平站等车站的实际情况，划分了列车运行路线，并在此基础上建立了符合列车运行时间和到达地点的有向图G，该图共有716个结点和7782个圆弧。

5结论

为解决乘务交路的优化问题，本文从乘务交路优化问题出发，从列车运行路线划分出发，把列车运行路线的优化问题转化成了团队方向问题。通过对时间、空间、最长连续值乘时间和用餐时间窗的限制，提出了以乘务交路时间平衡和最短停留时间为优化目标的乘务交路优化模型。针对传统蚁群算法的特点，利用交叉算子对蚁群算法进行了改进，并给出了基于交叉蚁群算法的交叉蚁群算法。最后，结合成都铁路客运专线的实际运行情况，对该模型及算法进行了验证。

为了检验该方法的正确性和有效性，模拟中仅考虑了u=0,0.5,1。而在实践中，则应多取一些数值，从多种方案中选择最佳方案。此外，本论文仅对乘务交路优化问题进行了探讨，并没有对空管排班问题进行深入探讨，将乘务交路分配到特定的空乘人员中，使空乘人数最少的问题成为优化的目标。

参考文献

［1］符卓,袁雪莹,车瑶.高速动车组司机乘务交路优化编制方法[J].铁道学报,2020,42(7):24-33.

［2］王东先,孟学雷,乔俊,等.基于改进蚁群算法的铁路乘务交路计划的编制[J].计算机应用,2019,39(9):2749-2756.