单线公交司机排班计划网络流模型与求解算法

钱 程，徐小明，彭飞

(1.合肥工业大学 汽车与交通工程学院，合肥 230009；2.北京电子科技职业学院 汽车工程学院，北京 100176)

在公交运营管理中，运营组织与调度是公交企业工作的核心。公交运营组织和调度的首要任务，是有效管理和合理分配有限的车辆和人力资源，调整供需平衡，争取以最小的人力、物力及财力投入来保障日益增加的客流需求[1]。司机排班问题是公交运营规划的重要组成部分，用于司机的费用大约占整个公交公司运营成本的60%[2]，一个高质量的司机排班计划可以为公交公司节省很多成本。乘务调度问题(CSP)的目标是在满足一系列复杂劳动法规的条件下，合理安排一组乘务人员完成一天内的全部车辆运行任务，公交系统中的乘务调度问题又可称为司机排班问题(DSP)。

司机排班问题自20世纪60年代以来一直受到广泛的关注和研究，班制和用餐约束在司机排班问题中被广泛考虑。在实际的公交系统中，常规班制和早晚班制是两种常见的司机工作班制[3]。在公交司机排班问题中，设置司机用餐休息也有两种常见的方式：一种是在司机达到最大连续工作时间后设置一段长休息作为司机的用餐时间；另一种是更符合人们饮食习惯的“中式用餐”[4]，即设置司机的用餐时间窗，规定司机在用餐时间窗内用餐。

司机排班问题为NP-hard问题，这一点已被许多研究所证实[5]，对于此类问题，通常结合集合覆盖或集合划分模型进行建模[6]。乘务排班问题的主要求解方法包括列生成和启发式两种，Desrochers等[7]较早开始研究列生成算法求解公交司机排班问题，为加快列生成算法的收敛速度，一些学者开始在使用列生成算法时引入一些启发式策略和方法：Mauri等[8]提出了种群训练启发式算法，并结合列生成求解司机排班问题；Li等[9]设计了一种基于超启发式的列生成算法来加快列生成的速度；Gamache等[10]采用集合划分模型设计了在列生成中加入启发式算法应用于航空乘务调度。随着算例规模的增大，商业求解器和精确算法在求解大规模司机排班问题时可能出现难以接受的计算时间，一些学者提出了启发式算法来求解司机排班问题，其中主要有遗传算法、禁忌搜索算法和变邻域搜索算法(VNS)。针对司机常规班制和无固定司机用餐时间窗的司机排班问题，Shen等[11]对混合遗传算法进行改进，采用一种自适应进化的混合遗传算法求解该问题。针对常规班制和不带用餐时间窗的公交司机排班问题：Ma等[12]将变邻域搜索算法应用在北京公交排班问题中；彭琨琨等[13]在变邻域搜索算法中设计了一种班次评价方法对解进行评价；Shen等[14]将禁忌搜索算法应用于司机排班问题；Ma等[15]考虑了排班的公平性；De Leone等[16]设计一种贪婪随机自适应搜索启发式算法求解该问题。

综上，当前研究主要侧重于常规班制研究，极少有人在考虑早晚班制的同时结合固定用餐时间约束。针对当前研究中的不足,文中考虑早晚班制和固定司机用餐时间窗的公交司机排班问题，结合劳动法规等相关约束，构建整数规划模型，并设计基于离散事件的变邻域搜索算法求解，为司机调度计划的编制与优化提供依据。

1 司机排班问题

公交司机排班问题的目的是降低运营成本，安排公交司机执行车次任务，同时确定公交司机的班次。为了更加准确的描述问题，介绍以下术语。

1)班型是指由早晚班制确定的一段工作时间，司机在一天中可以选择在早班时间工作或在晚班时间工作。

2)班次是司机从场站签到开始直到场站签退结束，一整天完成的所有工作集合，包括签到、签退、执行车次任务、间休、等待和用餐。

一个完整的司机排班计划是司机排班问题的一个解决方案，它包括一组共同覆盖所有车次任务的可行班次。表1列出了问题涉及的各种参数，其中与时间相关的参数都是整数。文中研究的司机排班问题有以下特点。

1)文中考虑的场景是包括s1和s2两个场站的单条双向公交线路。场站作为公交车的起终点，司机可以在场站进行签到、签退、用餐、休息和等待。

2)车次时刻表为确定的输入数据。

3)所有的车次任务都要被执行，并且每个车次任务只能由一名司机执行一次，一个司机在同一时间只能执行一个车次任务。

4)司机在一天内的总工作时间不应该超过法定最大工作时长。司机总工作时间是指司机一天中从签到时间到签退时间之间的总时间，包括执行车次任务时间、间休时间、用餐时间和等待时间。

5)司机的连续工作时间不应该超过法定最大连续工作时长。连续工作时间是指司机连续执行车次任务的时间，包括间休时间和两个连续车次间的等待时间。

6)若司机的工作时间内包含用餐时间窗，司机应在用餐时间窗内进行用餐。用餐时间也被当作休息时间。

7)将计划周期[0,T]进行离散化，每个时间单元都表示为整数，比如，若计划周期为24 h，每个时间单元为1 min，T=1 440 min。

文中设置早晚两种班型，班型设置时考虑司机最大工作时长，如工作时间为06:00—22:00, 共16 h，而司机最大工作时长为8 h，则早班和晚班的工作时长都为8 h。由于存在跨班型的车次任务，在早班添加一段冗余时间t，t最大为一个车次任务时长，即早班时间为(06:00—14：00)+t，晚班时间为14:00—22:00。而司机班次的开始时间和结束时间由所在班型决定，如早班工作的司机从06：00开始工作，若司机执行的最后一个车次任务的结束时间在14:00前，则司机在14:00签退并结束工作，否则该司机在14：00+t时刻结束车次任务并签退；晚班工作的司机从14:00开始工作，在22:00签退并结束工作。

表1 数学符号及定义

2 问题模型

文中所考虑的问题表述为带有约束的最小成本多商品网络流问题，其中每个商品代表一个司机，建立一个有向无环的时空网络G=(V,A)。接下来首先介绍时空网络的构建，然后针对问题建立网络流模型。

2.1 时空网络

图1 司机r在时空网络上的一条路径

2.2 整数规划模型

(1)

(2)

(3)

(4)

(5)

∀u′→v′∈Asignj,r∈R,j∈J

(6)

(7)

∀u′→v′∈Asignj,r∈R,j∈J,m∈Mj

(8)

(9)

(10)

3 求解算法

文中提出了一种基于离散事件模型和变邻域搜索的快速求解算法，可以在可接受的计算时间内得到高质量的公交司机调度计划。为了模拟司机的工作过程，首先分析公交司机的时空状态，每个状态转换定义为一个离散事件。一串连续的离散事件能够描述一个司机一天的工作过程，也是一个司机班次。该算法第一阶段设计基于离散事件的启发式算法求得初始解，第二阶段对初始解进行变领域搜索，对解进行优化。

3.1 司机状态转换定义

图2 司机状态转移

在给定当前系统时间t下，给出文中所提出的司机调度系统状态转换的3个定义：

定义1(事件)：在司机状态改变时产生事件。

在生成调度计划的过程中，需要更新每个执行的离散事件对应的司机位置、状态和系统时间，直到最后一个离散事件被执行，即计划周期结束。司机调度仿真启发式算法由3部分组成，即初始化系统、确定系统更新步骤和更新系统信息。由于启发式算法是基于司机状态转移设计，状态转移在本质上是离散事件的产生。

3.2 初始解生成

本节将介绍初始解生成的算法，该算法通过离散事件模型模拟司机调度问题中司机的工作过程来获得初始解，初始解生成算法如下所述。

Step 1：初始化离散事件集合，集合中只包含各车次任务的开始事件和结束事件；初始化司机集合。

Step 2：遍历离散事件集合，挑选司机来执行各离散事件。

Step 3：若当前事件为车次开始事件，依次对司机的时间、位置、状态进行判断，若满足上述条件，则该司机执行该车次开始事件，该车次的到达事件也由同一司机执行，更新司机状态；否则，重新挑选司机。

Step 4：若当前事件为车次结束事件，则生成一个司机间休事件；若当前系统时间在用餐时间窗内，则生成一个司机开始用餐事件；更新司机状态，离散事件集合。

Step 5：若当前事件为司机开始用餐事件，则生成司机结束用餐事件；更新司机状态，离散事件集合。

Step 6：若当前事件为司机间休事件或司机用餐结束事件，更新系统信息。

Step 7：当最后一个离散事件被执行时，终止程序，得到一组司机执行的离散事件集合，即司机调度问题的可行解。

3.3 变邻域搜索

变邻域搜索算法是一种求解最优化问题的启发式算法，其主体为设计多个邻域，在搜索解时规律地改变当前的邻域，不断迭代地寻找更优解。文中采用的算法框架如下：

Step 1：通过3.2节所述的仿真启发式算法得到初始解s，令sbest=s，scurr=s；

Step 2：设i=0，k=1,其中i表示解连续i次迭代没有改进，k表示第k个邻域操作；

Step 3：对scurr在邻域NSk中进行局部搜索，得到s，s←NSk(scurr)；若s

Step 4：令k=k+1，重复step 3，若k>2，进行step 5；

Step 5：若scurr

Step 6：达到终止条件，即i=MaxIter，结束循环，输出最优解sbest，否则转到step 3。

设计两种不同的邻域NS1,NS2。

1)第一种邻域操作是为了避免解陷入局部最优。选择两个班次相同且执行车次任务的司机，各自挑选一个司机执行的车次任务，将两个车次任务互换司机执行。

2)第二种邻域操作是为了减少所用的司机数量。选择一个执行车次任务的司机删除，将该司机执行的任务插入其他至少执行一个车次任务的司机班次中。

需要注意的是，在进行邻域操作过程中，要保证解的可行性。

4 算例分析

表2 算例参数设置 min

表3展示了在小规模算例中VNS的解，初始解和求解器CPLEX 12.5所得的精确解结果。其中：列“H”表示发车间隔；列“|K|”表示车次任务数量；列“Cost”表示目标函数值；列“r”表示解的司机数量；列“t”表示算法运行时间；列“Gap1”表示初始解与CPLEX所得精确解之间总成本的相对差值，列“Gap2”表示VNS解与CPLEX所得精确解之间总成本的相对差值，列“Gap3”表示初始解与VNS解之间的相对差值(Gap1、Gap2、Gap3的计算方式见式(11)～(13))；“-”表示CPLEX在2 h内得不到可行解。由表3可看出，当车次任务数量增大到一定程度时，CPLEX的求解时间过长，甚至在2 h内无法求得可行解(如Inst5)，而VNS几乎都能在70 s内得到最优解，所以从整体看来，VNS的求解效率相比CPLEX的求解效率有显著提高。在算例Inst 1、Inst 4中采用VNS可得到与CPLEX相同的解，在算例Inst 2和Inst 3中结果会有少许误差(算例Inst 2中VNS的Gap为1.02%，算例Inst 3中VNS的Gap为0.73%)，以上说明VNS相比于CPLEX可以在显著提高求解效率的同时获得近似解。

表3 小规模算例计算结果

从表3还可以看出，基于离散事件的仿真算法可在0.01 s内求得可行解。与CPLEX所得精确解相比，仿真算法在Inst 1中可以得到与CPLEX相同的解，在其余3组CPLEX能够在2 h内求得解的算例中，初始解的最大Gap为10.19%，最小Gap为2.82%，说明基于离散事件的仿真算法可以在极快的时间内求得较高质量的解，甚至直接得到最优解，如Inst 1。

表4展示了大规模算例所得VNS的初始解。由于计划周期和算例规模较大，算例Inst 6-Inst 11 用CPLEX均无法在2 h内得到可行解；对于CPLEX难以求解的大规模算例，VNS能在70 s内得到解，所以VNS对于求解大规模网络的司机排班问题也有着极高的求解效率。同时，针对大规模网络的初始解求解，所提出的基于离散事件的仿真算法都能在极短时间内求得较好的初始解。根据表3、表4中的Gap3可得，VNS求得的最优解和初始解之间相差均不足10%。在Inst 1、Inst 7和Inst 11 中，初始解即最优解，所以基于离散事件的仿真算法可以求得高质量的初始解。Inst 11结果表明，该算法对于真实的数据同样有效。以上分析说明文中提出的基于离散事件的变邻域搜索算法是一种求解司机排班问题的最有效算法。

表4 大规模算例计算结果

5 结 论

文中探讨了考虑早晚班制和固定司机用餐时间的单线路公交司机排班问题，以公交司机三餐的用餐时间窗和相关司机休息法规及覆盖车次时刻表为约束，以最小化系统总成本为目标，将公交司机排班问题构建为0～1整数规划模型，设计基于离散事件的变邻域搜索启发式算法。通过案例研究，在小规模算例中该算法能够快速得到与CPLEX近似的解,在大规模算例中，该算法能够快速得到可行的司机调度方案。还有许多问题有待进一步解决，主要有以下几方面：

1)文中研究成果适用于单线公交司机排班问题，未来研究还应进一步将问题扩展为多线路公交司机排班。

2)在实际公交公司运营时，也存在多种班制混合存在的情形，多种班制混合司机排班问题也将是一个值得研究的方向。

3)文中仅考虑常规公交的司机排班问题，实际中的电动公交车司机排班问题将存在不同于常规公交的问题特点，这也是今后需要进一步探讨的课题。