公交车排班问题探讨
2018-08-22陈孙延沈莹莹仇佳辉
陈孙延 沈莹莹 仇佳辉
摘要：在经济高速发展的当今社会，城市交通压力陡增，公交系统对于满足人们的出行需求，緩解城市交通压力发挥着无可替代的作用。文章对于公交车排班问题进行研究，力求使用最少的公交车数量来满足不同时间段内的运营要求，提高公交车排班的合理化，合理配置有限的资源以促进经济社会的发展。文章中模型的建立以考虑公交车成本、乘客候车成本为基础：问题一，在理论研究中，公交车排班问题便可看作资源的合理分配问题。在一定的约束条件下，合理安排有限的公交车的资源即运行车辆数、运行时间的调度方法确定其先后顺序，采用优化模型，以获得时间的最优化。求得徐州市2路公交车在早高峰时段（6：00～8：00）运行所需要使用的最少公交车数量为16辆。问题二，在满足乘客需求的情况下，寻求乘客等待时间最少和运营成本最低的平衡点，以上述两个方面为目标的公交车排班方案，采用最少的公交车数量尽量减少了运营投入。此问题为多目标优化问题，采用多元线性规划进行求解。求得徐州市2路公交车完成一整天的运行所需要最少的公交车的数量为双班车21辆，单班车0辆。问题三，在问题二的基础上，要求单班车不少于3辆。在问题二已建立的模型上增加约束条件，使一整天运行所需的公交数量最少。求得徐州市2路公交车完成一整天的运行所需要最少的公交车的数量为单班车3辆，双班车18辆。问题四，相比问题一、二、三，更为贴近实际情况，其主要的数学思想在根本上是一致的，仍然为多元线性规划优化思想。采用搭建了主要的模型后，增加相应的约束条件并进行结合实际情况的调整的方法，求得徐州市2路公交车完成一整天的运行所需要最少的公交车的数量为单班车4辆，双班车19辆。
关键词：公交车排班问题；多元线性规划；优化模型
一、问题重述
（一）引言
随着经济社会不断发展，人们的出行需求迅猛增长，公交系统的作用日益凸显，同时也面临着前所未有的挑战。城市的公交系统的优化可以缓解城市交通压力，有利于节能减排低碳发展，同时也可以减轻公交车司机的工作负荷，避免疲劳驾驶，提高司机师傅的工作满意度。合理编排公交车行车计划，既符合城市公交集团人性化管理的要求，也符合提高公交车运营效率和服务质量的重要举措。
（二）问题的提出
现代社会的发展对城市公交系统的完善提出了进一步的要求。通过合理编排公交车的行车计划，可以更好地服务于城市居民，更好地服务于经济社会的发展，从而达到经济效益和社会效益的统一。如何使用最少数量的公交车来满足不同时间段内运营要求，在深入理解公交业务需求和客运行业特点的基础上，将题设问题抽象成一个明确、完整的数学模型，对模型进行求解，立足实际，设计出最优的排班方案。
在该问题中，公交车公司采用单班车和双班车进行排班，驾驶员工作时间有限，公交车的行车信息表已知，如何在满足乘车需求的基础之上，在一定时间内采用最少数量的公交车进行排班运营。
二、问题分析
本题以简单的环路公交路线为例，即公交车从A点出发，经过一系列站点后再次回到A点为1个班次。1辆公交车从起点出发到达终点停止为1个班次。公交车公司有两种类型的班车：单班车和双班车。通常情况下，均可以用于排班。
单班车：由同一个驾驶员驾驶的公交车。单班车通常要求在早高峰跑2～3个班次，晚高峰2～3个班次，一天不超过5个班次。
双班车：由两个驾驶员驾驶的公交车。双班车要求上、下午各一个司机，上午和下午司机的工作时间尽可能均匀，并且都不超过8小时。每辆双班车一天运行不超过10个班次。
（一）问题一分析
考虑到一辆公交车在早高峰时段内能够运行不止1次的班次，因此班次的数量并不能准确地对应所需公交车的数量。由于早高峰时段的时间长度有限，在合理的模型假设的前提即忽略其他因素的条件下，本文利用简单的时间轴分析出运行过程中实际需要的车辆数为6：00～7：20这一时间段内发出的公交车数。同时，由于在早高峰时段内单双班车并无区别，只是当单班车运行时需要运行2个班次。由分析可知，单班车和双班车的具体数量是有多组可行解的。
（二）问题二分析
所谓排班问题就是为了某一目的面对共同使用的资源实行时间分配，通常可表示为在一组或几组不等式的约束条件下，求解目标函数的优化。城市公交车辆运输系统相应的排班问题有如下特点：每辆公交车在一整天的运行过程中只遵循一种运行模式，不会中途变化；每辆车按时发出，根据不同的运行时段，准时完成运行任务。
问题二要求给出徐州市2路公交车完成一整天的运行所需要最少的公交车数，其数学模型采用的优化指标为：在不影响乘客出行的前提下，乘客的等待时间和公交车运行班次最少，并避免出现较大的发车时间间隔，采用多元线性规划模型解决公交车排班问题。
（三）问题三分析
问题在的模型按照题中所提要求即在问题二建立的模型的基础上增加相应的约束条件。考虑到实际问题的现实性，因此在增加约束条件得到相应的额可行解后，还应按照实际条件做出调整。
（四）问题四分析
抛开问题一、二、三的限制，建立一个更为贴近实际的数学模型，但同时又是在研究完上述问题的基础上建立模型，其主要的数学思想在根本上是一致的，仍然为多元线性规划优化思想。搭建了主要的模型后，增加相应的约束条件并进行贴近实际的调整，最终得到数学模型的现实求解。
三、模型假设
影响公交车排班的因素众多，且其中很多因素都是随机的，为研究造成了诸多不便。为了抓住重点，简化模型的建立与求解，现作出以下的假设：在同一时间段内，相邻两车的发车时间间隔在无特殊情况下相等；公交车运行的单程时间，已经包含乘客在各站（包括起点和终点）的上下车时间；每辆公交车可以运行一整天不需要加油；公交车按照行车时间表准时进站和出站，途中没有堵车和意外事故；公交车回到终点后不需要停留，可以继续进行下一班次的运行；发车间隔以分钟为最小单位；以13：30划分双班车司机的上午与下午的工作时间段；在车站等待的绝大数人不会离去。
四、符号说明（见表1）
五、模型建立
（一）模型Ⅰ（问题一的模型）
1. 确定目标函数
由于不同班次可由同一辆公交车完成，结合时间分配，通过求该时间段内最少班次，在不等式的约束条件下，继而求在早高峰时段（6：00～8：00）运行所需要使用的最少公交车数量。
S1为第一时间段即早高峰时段（6：00-8：00）内需要的班次，T1为第一时间段即早高峰时段的时间长度为120分钟，Δt1为第一时间段即早高峰时段（6：00～8：00）的发车间隔。
2. 确定约束条件
（1）最大最小发车时间间隔约束
任意相邻两车之间的发车间隔要满足最大最小发车时间间隔约束，即：
（二）模型Ⅱ（问题二的模型）
1. 确定不同时间段的最优发车间隔
（1）确定目标函数
公交车排班以服务乘客为前提，但是在排班过程中必须兼顾到经济效益。公交车排班应该是在满足乘客需求的前提下，尽可能少的使用公交车，减少不必要的投入。因此，这是一个多目标规划问题。
①考虑一天内总的班次最少
将问题二中的一整天划分为4个时间段来简化模型的建立，便于理解。
②考虑一天内乘客等待的时间最短
这两个目标是既相互联系又相互矛盾的，不可能使两者同时达到最小。这样就需要寻求一个平衡点，得到总体的最优。现在将两项加权合并为单目标函数，考虑将这两项算成一种费用。
第一项发车班次总和折算成公交公司的运输费用。由徐州市公交公司的调研数据可知，平均每车每公里的成本是320元，这个费用包括了司机的劳动工资、耗油、折旧、维修与管理等各项费用之和。因此，一天之内公交车发车的班次总和其价值可以进行如下折算：
第二项乘客总的等车时间可以折算为乘客等车损失的费用。由徐州市统计局相关资料可知，徐州市2全部职工的每月平均工资为4947.75元。假设平均每天的工作时间为8小时。
目标函数包括了公交车公司和乘客两方的利益，由于这两个目标存在着相互冲突性，两个目标函数就存在一个权值的问题，体现在目标函数中两项的加权系数的大小。在同一线路的不同时间段加权系数的最优值是不同的。例如：从公交车公司的角度考虑，早高峰时段是多数乘客的上班时间，这段时间内所需要的公交车辆数最多的。从乘客的方面考虑，早高峰对于乘客的利益影响较大，乘客希望此时的时间比较短，这个时候乘客等车时间加权系数较大。初始化时取加权系数为0.2和0.8，在计算中根据结果逐步进行比较、调整。
（2）确定约束条件
最大最小发车时间间隔约束。任意相邻两车之间的发车间隔要满足最大最小发车时间间隔约束，即：
2. 确定所需公交车的最少数量
（1）确定目标函数
问题二要求建立适当的模型求解出徐州市2路公交车运行一整天需要的最少公交车数量，总的公交车数量为单班车与双班车的数量之和。由此确定目标函数：
（2）确定约束条件
①考虑问题二是在问题一的基础上
②考虑单班车自身的约束条件
单班车通常要求在早高峰跑2～3个班次，晚高峰2～3个班次，一天不超过5个班次。
早晚高峰中单班车必须要运行2个班次，总的单班车、早高峰期单班车、晚高峰期单班车数量一致。
限制单班车运行的班次在早晚高峰期所需的总班次内。
限制每辆单班车一整天的运行班次不超过5个班次。
③考虑单班车和双班车总的约束条件
满足单班车和双板车运行的班次足够运行完一整天的4个时间段的总班次，即保证一整天的公交系统的正常运行。
④考慮不同时间段内发车间隔的约束
此模型中的不同时间段的发车时间间隔采用各个时间段的最优发车时间间隔模型中求解得知的各个时间段的发车间隔。
（三）模型Ⅲ（问题三的模型）
问题三的模型即在问题二的模型上增加约束条件
x1≥3
满足问题三中的单班车不少于三辆的要求
模型Ⅲ：
（四）模型Ⅳ（问题四的模型）
1. 确定不同时间段的最优发车间隔
（1）确定目标函数
确定不同时段的最优发车间隔模型是一致的，参数的个数以及设置不同导致最终的求解不同。目标函数为：
（2）确定约束条件
最大最小发车时间间隔约束，同时段内任意两车之间的发车间隔要满足最大最小发车时间间隔约束，即
2. 确定所需公交车的最少数量
（1）确定目标函数
求解处运行一整天所需的最少的公交车数量为目标，因此目标函数为：
minN=x1+x2（24）
（2）确定约束条件
①考虑单班车自身的约束条件
单班车在早晚高峰必须要运行2-3个班次
x1=x13=x15（25）
总的单班车、早高峰期、晚高峰期单班车数量一致。
限制单班车运行的班次在早晚高峰所需的总班次内。
限制每辆单班车一整天的运行班次不超过5个班次。
②考虑双班车自身的约束条件
③考虑单班车和双班车总的约束条件
保证一天的公交车系统的正常运行。
④考虑不同时间段内发车间隔的约束
六、模型求解
（一）模型Ⅰ的求解
将函数及数据带入MATLAB计算，得：
即最少需要24班次。
但是由于班次无法对应公交车数量，因此做出如图1（时间轴）的分析。
……
由所绘时间轴可知，运行中实际需要的公交车数量为6：00～7：20这一时间段内发出的公交车数量。修改（1）式模型有：
利用MATLAB求解有
Δt1=5S1′=16
得出最终结果：徐州市2路公交车，在早高峰时段（6：00～8：00）运行所需要使用的最少公交车数量为16辆。单班车、双班车在早高峰时段可看作同种运行模式，单双班车的具体数量如表2所列。
（二）模型Ⅱ的求解
1. 模型Ⅱ.a的求解
利用MATLAB编程求解可得出以下结论如表3所示。
考虑到MATLAB求解出的可行解不一定满足实际问题的要求，在车辆的实际排班过程中还需要对不同的实际情况做出微调。经过实验，最终将晚高峰时段的最优发车时间间隔调整为4分钟。
2. 模型Ⅱ.b的求解
利用MATLAB编程求解可得出以下结论。
最少公交车数量为20辆，其中单班车0辆，双班车20辆。
根据模型Ⅱ的求解，可得到的徐州市2路公交车排班计划表，其中总车辆数20辆，双班车总数量20辆，单班车总数量为0，所有车的总班次数208次。
（三）模型Ⅲ的求解
利用MATLAB编程求解可得出以下结论。
最少公交车数量为21辆，其中单班车3辆，双班车18辆。
根据模型Ⅲ的求解，可得到徐州市2路公交车排班计划表，其中总车辆数为21辆，总双班车数量18辆，总单班车数量3辆，所有车的总班次数199次。
（四）模型Ⅳ的求解
1. 模型Ⅳ.a的求解
利用MATLAB编程求解可得出以下结论如表4所示。
考虑到MATLAB求解出的可行解不一定满足实际问题的要求，在车辆的实际排班过程中还需要对不同的实际情况做出微调。经过实验，最终将晚高峰时段的最优发车时间间隔调整为4分钟。
2. 模型Ⅳ.b的求解
利用MATLAB编程求解可得出以下结论。
最少公交车数量为23辆，其中单班车4辆，双班车19辆。
根据模型Ⅱ的求解，可得到徐州市2路公交车排班的计划表，其中总车辆数23辆，总双班车数量19辆，总单班车数量4辆，所有车的总班次数195次。
验证模型Ⅳ求解得到的徐州市2路公交车排班表：
（1）单班车司机不安排吃饭，所有双班车司机都安排吃饭（早餐和晚餐），每餐饭需要20分钟用餐时间。早餐8：00开始供应，10：00截止；晚餐18：00开始供应，20：00截止。——即在8：00～10：00以及18：00～20：00这两个时间段内双班车的班次中至少有1次在终点站停站超过20分钟。
（2）双班车辆运行5班次以后，上午、下午班司机进行换班，换班时间最少为20分钟（含最短停站时间）。——即双班车辆运行5班次以后，双班车在终点站停站超过20分钟。
验证可知模型Ⅳ求解得到的徐州市2路公交车排班表符合问题四的约束条件。
七、模型的扩展与评价
公交车排班是影响公交运营系统运行成本、效率和服务能力、水平的重要内容，是公共交通系统着重研究核心内容之一。其中，公交行车计划编制，包括发车频率、发车时刻表、运力和司乘配置计划是公共交通系统静态调度的主要内容。
在公交静态调度优化的研究中，为了满足乘客出行需求盲目增加运营车辆将导致企业运营成本的增加，线路上投入车辆过多，引发满载率过低也是一种不必要的资源浪费。所以，在问题二、三中通过分析公交企业利益即公交企业运营成本和出行者利益即出行者候车成本，建立以企业运营成本最小和出行者候车成本最小的车辆发车间隔模型，利用多元线性规划方法，借助MATLAB进行模型求解。
本文中，采用多元线性规划模型在题设约束条件下较为完整地解决了公交车排班的问题，得出了符合要求的徐州市2路公交车排班计划表（即为表3～2、表4～1）。由此可見，采用多元线性规划模型及优化模型对公交车进行排班，制定出排班计划表，有效合理地配置了公交车辆资源，提高了公交公司的人性化管理水平。
但是，本文中的公交车排班计划仅对于原始的静态情况进行排班，未考虑道路状况和突发状况等实际情况，对实际问题进行了简化和抽象，所以，与实际问题存在一定的差异，有待于更进深入地研究，模型也有待于更进一步地优化。
参考文献：
[1]李跃鹏，等.基于遗传算法的公交车辆智能排班研究[J].交通运输系统工程与信息，2003（01）.
[2]臧辉，成俊.基于遗传算法的公交车辆智能排班研究[J].武汉职业技术学院学报，2007（03）.
[3]王庆荣，等.基于遗传算法的公交智能排班系统应用研究[J].计算机仿真，2011（03）.
（作者单位：南京邮电大学）
