考虑任务数的乘务计划优化模型及算法研究

张雨潇，陈霁岩

（上海工程技术大学 城市轨道交通学院，上海 201620）

0 引言

在城市轨道交通运营管理中，乘务计划是地铁系统运营计划的重要组成部分，通过城市轨道交通乘务计划编制，运营机构能够确定乘务人力资源的合理化调配，为了保证服务质量、降低乘务成本，需要对乘务计划的编制优化进行深入的研究。

国内外学者针对城市轨道交通乘务排班问题已有一定的研究，Yunes等人将乘务排班计划问题分为2个子规划问题，结合数学规划和约束逻辑规划方法开发了混合列生成算法。Yu等人针对排班工作约束，建立了以时间均衡度为目标的集合划分模型并应用列生成算法进行求解。袁仁杰针对交通运营特点，将乘务任务配对和乘务任务指派问题分别转化为集合划分覆盖和运输指派问题，分别采用列生成结合遗传算法和基于规则启发式算法求解。许仲豪等人基于列生成算法思想，以集合分割模型为主规划，将子规划问题简化为网络图上的最短路径问题，并设计了一种基于影子价格的标号法求解子规划问题。

现有研究主要针对乘务排班计划的均衡度进行探讨，而未考虑乘务排班计划的乘务任务数量优化问题。因此有必要根据城市轨道交通乘务计划实际运营现状，设计针对大规模乘务数据的优化模型和求解算法。为了在目标函数、约束条件及求解算法的研究上有所突破，本文提出以乘务任务数最小为目标函数建立模型，以此来衡量所编制的乘务排班计划质量；同时从城市轨道交通运营管理实践和乘务管理中提取出乘务特色约束条件作为模型考虑因素；此外针对本文提出的模型，为了保证解的质量的同时，对求解速度提出较好的要求，本文基于列生成算法的思想，引入遗传算法先对初始解的单位矩阵进行迭代优化，再使用列生成算法对优化后的解进行进一步求解，提高算法求解效率。

1 模型构建

1.1 主规划

对包含个最小乘务片段和个乘务任务的乘务计划问题，运用集合分割模型理论建立主规划模型如下：

其中，表示最后生成并选入乘务排班日计划的所有乘务任务成本之和；c表示第个乘务任务的成本；1，…，，为最小乘务片段个数；1，…，，为可行的乘务任务个数；x、a是0-1参数；为乘务片段集合；为乘务任务集合。

1.2 迭代过程与成本函数

对主规划进行线性松弛，得到一个标准线性规划问题，利用单纯性法进行求解。第个乘务任务，即第列的判别数计算公式具体如下：

其中，σ为每一列的判别数，反映非基列入基后对目标函数值的优化程度；表示行向量（，，…，π），这里π表示主规划中第个约束条件的影子价格；A表示第个乘务任务，是由a组成的第列的列向量。

在子规划中检索是否存在乘务任务A使得判别数σ小于0，若存在，则将此任务加入主规划使得主规划进一步优化。当迭代至某次子规划生成的所有乘务任务的检验数均大于等于0时，说明此时无法再通过添加列对主规划进行优化，从而结束迭代。

1.3 子规划

在子规划问题中，以生成的新乘务任务的判别数最小为目标构建出子规划目标函数如下：

其中，表示所需生成的新乘务任务的判别数；表示运营单位期望工作时长；表示生成的乘务任务中乘务片段的个数；te表示第个乘务片段的到达时间；tb表示第个乘务片段的发出时间；表示超时未休惩罚权重系数；表示连续值乘时间超1.2 h未休息次数；表示乘务任务的工时有效率权重系数；表示乘务任务的出勤点与退勤点不同时的惩罚权重系数；表示0-1惩罚参数，表示乘务任务的出勤点与退勤点是否不同，1为相同，0为不同；表示求解主规划所得的对偶变量，为一个行向量；A表示主规划所生成乘务任务的列向量；、、、的参数的取值具有一定的灵活性，可根据运营单位实际运营需求赋值，以取得较为理想的乘务排班方案。

在子规划中对运营过程中的特色约束进行如下表示：

（1）单次值乘时间约束，即规定一名乘务员一次连续值乘的时间不能大于规定的最长连续值乘时间，约束条件表达式为：

其中，te表示该乘务任务中第个乘务区段的结束时刻；tb表示该乘务任务中第个乘务区段的开始时刻；，分别表示乘务员单次连续值乘最小、最大时长。

（2）总值乘时间约束，即规定一名乘务员所有值乘时间的时长和不能大于规定的当日最长值乘时间，考虑到工时有效率通常在75%～85%左右，将T设为6 h，T设为2 h，约束条件表达式为：

（3）出、退勤地点约束，为了方便乘务员上下班及交接班，应尽可能使生成的每个乘务任务中第一个乘务片段的发出车站和最后一个乘务片段的到达车站相同，约束表达式如下：

其中，作为0-1惩罚参数，表示乘务任务的出、退勤点相同时为1，不同时为0；Sb，Se分别表示第个乘务片段的发出、到达车站。

（4）就餐约束，即乘务员值乘期间必须在规定时间内就餐。约束表达式为：

其中，Y是0-1参数，当该时间区段处于进餐时间区间内取1，否则取0；为0-1参数，当该乘务工作时间为高峰时段则为1，为平峰时段则为0；表示是否是平峰时段的0-1参数，若为平峰时段则为1，若为高峰时段则为0；T，T分别表示高峰、平峰时段该轮乘站列车运行间隔；t表示乘务员规定用餐时间长度；为轮乘站轮乘间隔数，通常根据线路情况轮乘站有2或3个轮乘间隔。

（5）乘务片段的接续关系，乘务片段序列中2个相邻的乘务片段必须满足一定的时间间隔，接续关系表述为：

其中，te表示第1个乘务片段的开始时刻；tb表示第个乘务片段的结束时刻；t表示乘务片段间的最小间隔时间。

2 算法设计

2.1 遗传算法优化初始解

接着通过适应值函数对编码后的染色体进行评价，其值可由如下公式计算求出：

此处，γ表示各约束条件所对应惩罚函数的权重系数，通过调整该系数保证各约束条件地位相同。

在对个体进行适应值评价后，进行若干次交叉算子操作繁衍种群。为避免种群在若干次的交叉操作后出现早熟收敛现象，采用黄金分割方法变异算子，计算第代种群中个体的第维个体4个黄金分割点的适应值，选择值最大的点对应的个体，执行变异算子操作，并推导得到如下的数学公式：

研究中采用了双重收敛判断准则，即当出现进化次数达到设定的总迭代次数，或遗传进行若干次后目标函数值不变的情况，都视为满足收敛条件结束计算。

2.2 列生成算法求解规划问题

（1）初始化，求解主规划，获得当前主规划的对偶变量，选取值最大的对偶变量对应的乘务片段，作为本次迭代生成的乘务任务起点，令1，记录该乘务片段为。

（2）令2，开始第二次迭代，若存在乘务片段能够满足式（7）～（11）约束与乘务片段接续，则将其与点连接，将连接后生成的路径纳入路径集合P中。

（3）令1，开始第次迭代，对于路径集合P中的每一条路径的终点进行步骤（2）的操作，生成路径集合P。

（4）若的值达到了预设的每个乘务任务能够包含的乘务片段个数要求，则退出迭代。若还未达到，则返回步骤（3）。

（5）根据目标函数公式（6）选出数条目标函数最小的乘务任务，作为新列添加入主规划中。

迭代结束将得出的可行乘务任务集合放入主规划，对优化后的主规划采用分支定价法进行剪枝，从而得到新的0-1整数解，此时该最优解即为最终结果。整个算法流程如图1所示。

图1 算法流程图Fig.1 Flow chart of the algorithm

3 实例分析

3.1 结果对比分析

以上海地铁某条线路的行车数据进行实例分析，根据现场工作实际情况，在不考虑权重系数的赋值对乘务计划的影响情况下，令02，1，1，取3、4、5、6、7、8，将传统列生成算法与本文所提出的改进列生成算法求解结果进行对比，见表1。

表1 EXPT不同取值时2种算法比较Tab.1 The two algorithms are compared when EXPT values are different

根据表1结果，无论期望工作时长取值如何，提出的改进列生成算法在生成的乘务任务数量上和乘务计划成本上，均比传统列生成算法更优。

本次计算结果的迭代次数与乘务排班计划成本函数值关系，如图2所示。

图2 迭代次数与成本函数值关系图Fig.2 Diagram of relationship between number of iterations and cost function value

观察图2发现，构造初始解进行第一次求解主规划时乘务计划成本最高，随着迭代次数的增加与子规划乘务任务的生成，主规划的成本函数值迅速下降，在迭代130次左右达到最优的状态，验证了本文所设计的求解算法与迭代方式的有效性和高效性。

3.2 不同权重参数对比分析

为了深入分析乘务任务数量和工时有效率之间的影响关系，研究在工时有效率权重参数不变的情况下，其他参数变化对于所生成的乘务计划工时有效率及乘务计划成本的影响。对此拟展开研究阐释如下。

（1）02，1，1时，分析的不同取值对工时有效率及乘务计划成本的影响，如图3所示。

根据图3在保持02，1，1不变的情况下，工时有效率和乘务计划成本随取值的增大呈整体下降趋势。其原因是当其他权重参数不变时，期望工作时长越低，所编制出的乘务计划更容易覆盖所有的乘务片段，反之当期望工作时长越高，乘务计划倾向于用更低的成本完成乘务片段的覆盖。

图3 EXPT不同取值时乘务计划成本与工时有效率Fig.3 Crew plan cost and man-hour efficiency with different values of EXPT

（2）6，1，1时，分析的不同取值对于工时有效率及乘务计划成本的影响，如图4所示。

图4 α不同取值时乘务计划成本与工时有效率Fig.4 Crew plan cost and man-hour efficiency with different values of α

根据图4在保持6，1，1不变的情况下，当取值由0.1至0.4时，工时有效率会随的增加而增大；当04时，工时有效率会随的增加而减小。究其原因是当其他权重参数不变时，对超时未休的状况进行一定范围内的惩罚，会有助于乘务任务的生成，但当惩罚超过该范围时，反而会限制乘务片段的组合。

在实际生产作业中，6，04，1，1可作为乘务工作编制计划中合适的一组参数。此外，运营单位需要结合实际情况与运营需求，在工时有效率、乘务任务数及乘务计划成本三者之间进行权衡，以得到满足实际需求的乘务计划。

4 结束语

（1）本文提出一种以生成乘务任务数量最小为目标的乘务排班计划问题编制方法，构造了集合分割主规划模型和乘务特色约束子规划模型，并设计了基于影子价格选择的标号法对子规划进行求解。

（2）为了克服列生成算法中因初始解质量太差导致求解速度缓慢且求解质量不够高的问题，本文引入遗传算法对列生成算法的初始解进行优化，使得改进后的列生成算法求解速度与求解质量有显著提高。

（3）以上海地铁某条线路的实际运行图数据为例进行分析，结果显示本文提出的模型与改进后的列生成算法在工时有效率和乘务员运用数方面表现良好，验证了模型与算法的适用性和有效性，同时对模型中各权重参数进行不同取值的求解对比分析，为实际生产作业中运营单位编制乘务计划提供参数依据。

（4）为了提高该模型和算法与实际生产流程的匹配度，后续研究可在模型中加入更多的现实约束条件，比如将乘务排班计划与乘务轮班计划的编制流程结合，进而使模型与算法更高效地解决现场的乘务计划编制问题。