随着城市交通拥堵问题的日益严重，城市公共交通的主体地位也逐渐凸显。目前，为了进一步提升公交服务水平，政府投入了大量资金建设智能公共交通系统。其中，行车计划编制和公交线路驾驶员排班优化是公交系统实现智能调度的重要组成部分，直接影响到公交运营效率。

国外有关公交驾驶员排班问题的理论研究与实践探索已有50多年的历史^{[1, 2, 3]}；而国内的相关研究工作最近几年才逐渐开展，已取得一定研究成果^{[4, 5]}。总体来看，国内外的研究主要可以分为两大主流：(1)驾驶员与公交车的集中调度^{[6, 7, 8]}；(2)将驾驶员调度当成一个孤立的问题看待。前者有利于降低公交运营的总成本，后者方便公交企业的灵活运营。独立的公交线路驾驶员排班模型算法主要集中于遗传算法^{[9, 10]}、蚂蚁算法^[11]、禁忌算法^[12]和分支定界法^[13]等。但这些算法都比较繁杂，不利于实现。

从公交公司运营管理角度出发，在公交运营车辆最少的前提下，公交驾驶员的成本最小即可满足公交公司利益最大化。因此本文以公交驾驶员成本最小为目标，将公交驾驶员排班问题抽象为一个集合覆盖问题，并设计启发式方法与0-1整数规划相结合的算法，最后采用MATLAB实现问题的求解。

公交线路驾驶员排班是根据编制的行车作业计划安排驾驶员的工作。在安排驾驶员工作时应该同时满足以下条件：(1)驾驶员每天的工作一般是由一辆车或两辆车的几段工作组成的；(2)运营的公交车辆所有的工作必须包含到驾驶员的工作中，所有驾驶员的工作集合必须覆盖运营车辆的任务。由此可以看出，公交线路驾驶员排班是一个极其复杂的组合优化问题。

在公交实际运营中，驾驶员排班首先将车辆的运营工作按照换班时间点划分成一个小驾驶段集合，然后在满足一系列目标和约束的基础上将这个小驾驶段集合重新整合、连接形成一个连续驾驶段集合，最后将几个连续驾驶段连接并将其分配给一个公交驾驶员完成，即形成一个班次。可以看出,公交驾驶员排班本质上是一个组合优化问题，而这个组合优化问题是很复杂的，其复杂性主要表现在目标多、规模大、约束条件复杂多样。

为消除公交驾驶员排班问题的复杂性，文献^[13]中提出了一种列生成算法来解决集合覆盖问题，其难点在于求解初始可行解。在构建初始可行解时利用的贪婪算法和驾驶段配对方法较为复杂，初始排班方案会直接影响受限主问题的求解规模以及整个算法的循环迭代次数。本文在其基础上，设计了一种较为简单便捷的启发式算法得到可行班次集合，增加了算法的适用性。

公交线路驾驶员排班是一个将连续驾驶段予以集合，并在满足一系列目标和约束条件的基础上重新整合、连接的过程。首先将车辆调度所得的车次链按换班点分割成若干小驾驶段，考虑劳动法规约束，把小驾驶段合并成一些可行的连续驾驶段，然后对连续驾驶段进行任意组合筛选得出可行的班次集合，最后基于公交驾驶员成本最小化对可行的班次集合进行选择和再优化，即得到最终的劳动班次。

本文结合启发式方法和0-1整数规划，设计了解决公交线路驾驶员排班问题相应的算法。该算法可分为4个模块：连续驾驶段确定模块、可行班次集合产生模块、班次选择模块和班次优化模块。

(1)连续驾驶段确定模块

确定每个连续驾驶段即确定驾驶员每个工作时间段的长短。该模块为了保证驾驶员劳动法则的约束，采用有效工时不超过8 h来实现。为了保证驾驶员在连续驾驶段内较高的工作效率，采用小驾驶段之间的最小时间间隔来约束。具体的模块算法如下。

该模块已知每条车次链中每个小驾驶段的起始时间和起始地点。其中定义第p个车次链(班次)中第k个小驾驶段的起始时间为t_pks和结束时间为t_pke，第p个车次链中第k个小驾驶段的起始地点为z_pks和结束地点为z_pke。

求解每条车次链分割成的连续驾驶段的起始时间、起始地点以及所在车次链编号。

该模块的约束条件有两个。

① 每条车次链中任意相邻的两个小驾驶段之间的空闲时间不得大于0.5 h，即:

点击浏览公式

② 由每条车次链中a个连续小驾驶段合并得到的连续驾驶段有效工时不得大于8 h，即:

点击浏览公式

(2)可行班次集合产生模块

在实际运营中，一个公交线路驾驶员排班问题的规模是由连续驾驶段个数或者换班点个数所决定的。为了解决驾驶员实际换班时换车困难的问题，该模块对上一个模块所获得的连续驾驶段任意组合后，利用启发式方法筛选掉部分换班点来缩小问题规模，通过限制最小换车次数、确保组合中任意两个相邻连续驾驶段之间换班时间协调且换班地点一致，从而产生可行班次集合S。具体的模块算法如下。

已知连续驾驶段集合中元素对应的起始时间T_pks、结束时间T_pke、起始地点Z_pks、结束地点 T_pke以及所属的车次链编号。

利用以上数据求出可行的班次集合S，即连续驾驶段的可行组合。同时求出班次选择模块中目标函数需用的数据α_ij与T_zb^j(α_ij与T_zb^j具体释义见式(7)后)。

其中约束条件如下。

①每个班次j覆盖的连续驾驶段个数最多为4，即1≤N≤4。

②每个班次j覆盖的连续驾驶段最多跨越两个车次链，且必须满足每个班次只能从一个车次链到另一个车次链跨越1次。

③连续驾驶段换班时间的限制，即每个班次j中相邻的两个连续驾驶段必须满足：前一个连续驾驶段i的结束时间必须早于下一个连续驾驶段i+1的起始时间，满足：

点击浏览公式

④ 连续驾驶段换班地点的限制，即在一个班次j中，相连接的两个连续驾驶的结束与起始时间间隔小于T_single时，前一个连续驾驶段i的结束地点是后一个连续驾驶段i+1的起始地点，即满足：

点击浏览公式

(3)班次选择模块

为了保证人员排班的合理性和公平性，单个班次的运营成本计算应该是有效工时成本与超过劳动法则规定工作时间T的加班工资成本之和。在此基础上，基于集合覆盖思想进行建模。通过求解该模块中0-1整数规划问题，从可行班次集合S中选出基于人员成本最小化的可行班次集合Q，使集合Q中的全部元素结合起来能够覆盖全部的车辆运营工作。

此0-1整数规划问题具体为：

①所求的变量

x_j=1，若班次j被选中0，否则,(5)

式中x_j表示班次j是否被选中，j=1,2,…,n。

② 目标函数

点击浏览公式

式中c_j为班次j的人员成本。

点击浏览公式

式中，；t_i为连续驾驶段i的有效工时；λ为班次j的人员成本系数，班次分别覆盖1，2，3，4个连续驾驶段时，λ分别为1，0.9,0.8,0.7(班次覆盖连续驾驶段个数较多的，人员成本系数低，利于优先选择)；τ为加班权重系数，；T_zb^j为班次j的工作时间；T为劳动法则规定的工作时间，一般取8 h。

③ 约束条件

每个连续驾驶段都会被唯一的班次覆盖，即保证：

点击浏览公式

(4)班次优化模块

该模块利用启发式方法进一步筛选掉已生成的但不太“好”的班次，即对以上所得的基于人员成本最小化的可行班次集合Q，进行班次的最后优化，得到最终的班次集合O。

其中进行优化的约束条件为：

可行班次集合Q中在班时间小于5 h的班次为需要优化的班次，而需要优化的班次中任意两个班次c与d之间的空闲时间大于等于5 h可合并优化为一个新的班次，即满足：

点击浏览公式

点击浏览公式

该模型具体的优化流程如图 1所示。

图 1 基于集合覆盖理论的公交线路驾驶员排班优化流程图 Fig. 1 Flowchart of optimizing work schedule of bus drivers based on set covering theory

图选项

根据济南市某公交线路的行车作业计划表，以公交线路的换班点为分界，将该公交线路的3条车次链划分成若干小驾驶段，得到小驾驶段的到发时刻表，如表 1所示。

利用上述算法步骤，编制相应的MATLAB程序实现该问题的求解。其过程中可得到连续驾驶段的到发时刻表，如表 2所示。

将以上所得的连续驾驶段代入模型求解，并进行再次优化，得最终班次表，如表 3所示。

从计算结果可以看出，该方法体现了两个方面的优点：(1)能够有效提高驾驶员的工作效率，减少候车时间消耗，例如班次1、班次3、班次4；(2)如果驾驶员在一天内需要分时段行驶，则需要为其在换班点留够足够的休息时间，例如班次2、班次5。

为了验证本文算法的性能，选取实际人工编制和遗传算法^[9]得出其他两种不同的排班方案，以此进行对比分析。各个调度方案的相关性能数据分析如表 4所示。可以看出，本文算法的班次个数最少，且相应的班次总工作时间和人员成本也都最小，同时能够保证较快的优化速度，即MATLAB优化实现时间。因此可验证本文算法得出的排班方案最优，既能有效减少人员成本支出，又能提高排班速度。

在分析公交驾驶员排班问题复杂性的基础上，以人员总成本最小化为目标，考虑公交驾驶员排班问题的车辆运营任务、换班时间、劳动规则要求等约束，借助集合覆盖问题进行数学建模，并融合启发式方法和0-1整数规划设计算法进行了模型的求解。最后，结合济南市公交公司的实际数据，以MATLAB为平台，实现了以上算法，求出了公交驾驶员排班方案。该方案很好地解决了提高驾驶员工作连续性的问题。

本文研究的重点是单条公交线路的排班问题，只能满足对单条线路的求解要求，但相对于大规模的多场站跨线路的驾驶员排班问题，这种模型和算法仍有待改进。