考虑客流量差异的区域公交车辆调度*

郝小妮 靳文舟 査靓

(1.华南理工大学 土木与交通学院，广东 广州 510640;2.三峡大学 机械与动力学院，湖北 宜昌 443002)

公交区域调度相比单线调度，能节省车辆、司机资源，提高车辆的运营效率［1］.国外研究并实施公交区域调度已40 余年，而国内公交区域调度尚处于研究探索阶段，仍以单线调度为主［2］.公交区域调度问题包括:线网规划→时刻表生成→公交车辆调度→驾驶员排班4 个连续的步骤［3］;公交车辆调度是区域调度过程中涉及车辆、司机调配和费用节约的关键步骤，同时又受到时刻表的制约.区域公交车辆调度(RVSP)是在给定区域时刻表前提下，以所需车辆数最少或费用最小为目标，满足相关运营约束，构建完成所有车次任务的公交车辆的车次执行序列(即车辆调度方案).区域公交车辆调度属于多车场车辆调度问题(MDVSP)，此类组合优化问题已被证明为NP-hard 问题［4］，是公交领域的热点研究问题之一.

国外不少学者用网络中的不同多商品模型来描述MDVSP 问题［4-6］.Mesquita 等［7］应用分枝定界法求解MDVSP 的各种多商品模型.Lobel［8］提出用一种称为拉格朗日定价法的特殊列生成法来求解大规模MDVSP，是成功的求解方法之一.Haghani 等［9］提出了有线路时间约束的MDVSP 新0－1 规划模型和算法，依据发车时间将车次分为上午、中午、下午车次，通过空驶与连续运行的经济性比较定义了站场相容车次、线路相容车次，将总成本细化为时刻表车次成本、空驶车次成本、线路终点停留成本、车场停车成本四者之和，但却没有分析停车时间长短对成本的影响，仅统一假设车场停车成本为零.Kliewer等［10］用时空网络流模型描述MDVSP 问题，可大大缩减变量规模，有助于求解大规模车辆调度问题.总体上，国外研究文献侧重于用图论和网络流模型来描述区域公交车辆调度问题，并对求解算法做了大量探索，尤其针对大规模RVSP.

国内方面，刘志刚等［11-14］基于车场容量、续驶时间等，最小化所需车辆数与无效驾驶时间之和，分别建模研究区域公交车辆调度［11，13-14］、区域电车车辆调度［12］，并采用禁忌搜索算法［11］、蚁群算法［12-14］进行求解.不同之处，魏明等［13］引入车次任务可靠度约束，探讨不确定环境下的RVSP.上述文献逐步考虑多种现实约束，大多基于最小费用流网络模型研究RVSP.

但是，现有文献假设公交客流量一天内是均匀的，时刻表均衡分布.实际上，一天内不同时刻的公交客流量差异显著，高峰值一般出现在上午7:00～9:00 和下午17:00～19:00，7:00 前和20:00 后属于低峰期，其余为平峰时段;并且通过调研发现，我国大城市的公交线路客流高峰时间、空间分布非常集中，从而参与公交区域调度的多条线路客流高峰将在时间、空间上相互叠加，导致总体客流的高低峰客流量差异会进一步加大;很显然，客流高峰、低平峰期对车辆的需求量存在较大差异;如果忽视这种差异，全天按高峰流量配车，将导致低平峰时段车辆和司机出现较多空闲等待时间，造成资源浪费，因此需要研究实际公交客流量非均匀分布且多条线路客流高峰时间、空间分布集中情况下的区域公交车辆调度问题.针对客流量的不均衡特征，文中提出了抽停策略，即在低平峰期停运部分公交车辆，减少车辆和司机的等待时间，减少所需司机数和企业运营成本，缓解目前公交企业中存在的驾驶员不足矛盾.

1 问题描述及建模

根据一天之中公交客流量具有时间分布不均衡的特点，将所需公交车分为两类:单班车ksv和双班车kdv，单班车在早高峰及其前后1～2 h 内出车执行车次任务，之后该车抽停(车辆停运期可用于旅游包车等业务)，驾驶员休息，下午再出场参与晚高峰及其前后1～2 h 的公交运营，单班车全天只需一个驾驶员.相应地，双班车在公交运营时间范围内需要两个驾驶员换班驾驶完成全天的运营任务.文中拟在考虑公交客流时间分布不均衡及参与区域调度的多条线路客流高峰时空分布集中的情况下，基于低平峰期停运部分车辆的抽停策略，从“部分班次被某辆车完成”的集合划分问题角度研究RVSP，第一目标最小化所需车辆数、车辆等待时间和空驶时间三者之和，第二目标最大化车辆利用率，提出一个新的区域公交车辆调度模型.

1.1 假设条件

(1)道路交通状态稳定，运营时间范围内各条公交线路的车次运行时间为某一恒定值.

(2)要求所有公交车辆准时从相应车场出发执行每一个车次任务.

(3)公交车辆完成一个车次后，可不做任何停留立即开始执行下一车次.

(4)公交车加满气后，其所能运行的总时间或总里程为一确定值，与司机驾驶习惯、交通状况无关.

(5)单班车可在抽停期间加气，因此车辆调度方案中不考虑单班车的加气，仅考虑双班车的加气要求.

1.2 参数定义

T={T1，T2，…，TN}为所有区域调度范围内不同公交线路的固定时刻表对应的N 个车次任务构成的集合;对∀TiT，要求车辆在开始时刻ts，Ti从某个车场po，Ti出发，并在结束时刻ta，Ti到达车场pe，Ti;D 为车场集合，M 为车场数量;Vd为从车场dD 出发的相应车辆集合，为从车场d 出发的车辆数，Cd则为车场容量.=dtx1为车辆k 离开车场d 开始执行车次链的时刻;而到达∀xi起始点po，xi的时刻为=+time(po，x1，pe，x1)+…+time(pe，xi－1，po，xi)，如该车辆在xi的出发点po，xi加油加气，令，则为车辆在车场加油或加气所需时间;对∀xi－1，xiTkd，若time(pe，xi－1，po，xi)≠0，即从车次xi－1的终点到车次xi的起点时间不为零的空车行驶称为空驶车次(Deadhead Trip)，而time(po，xi，pe，xi)则为从车次xi起点至终点的运行时间，time(g，h)(∀g，hD)为车辆在两车场间的空驶运行时间.ci(i=0，1，2)为权重系数;tmax为每辆车受燃料限制的最大续驶时间;车辆每天的工作时间记为集合tI={tzgf，twgf，tpf}，其中表示一天之中的早高峰时段和晚高峰时段，tpf表示一天之中的平峰时段，即除去早晚高峰时段的其它运营时段.tksv表示单班每天的运营时间，tkdv表示双班车每天的运营时间.

1.3 决策变量

1.4 建立模型

目标函数为

约束条件为

目标函数式(1)表示完成给定时刻表所需的公交车辆数、车辆在执行车次过程中的等待时间及空驶车次时间三者费用之和最小.目标函数式(2)表示最大化车辆的使用效率，即车辆等待时间占总工作时间的比例最小.允许单班车在平峰期抽停有助于实现此目标.约束条件式(3)表示一辆公交车仅属于一个车场;式(4)表示给定时刻表中所有车次都应被执行;式(5)表示一个车次只能被一辆公交车执行，一辆公交车同时只能执行一个车次;式(6)表示一辆车从某车场出发，完成一天中的一系列车次任务后，收车回到原车场;式(7)保证任意时刻进入车场的车辆数不超过该车场容量;式(8)表示公交车到达某一车次起点的时刻应小于等于该车次的发车时刻，是某车次被一辆车完成必须满足的约束条件;式(9)表示车辆在执行某公交车次前是否加气;式(10)表示单班车每天的工作时间范围;式(11)表示双班车每天的工作时间范围.

2 最大最小蚁群算法求解区域公交车辆调度问题

根据蚂蚁“寻找食物”的群体行为，意大利学者首先提出了蚁群算法.蚁群算法具有正反馈、分布式计算以及启发式搜索等特点，该算法迅速成为众多学者的研究焦点，它是求解调度问题、图着色、图像处理及资源分配等组合优化问题的最有效算法之一［15-18］.蚁群算法已经在解决旅行商问题(TSP)、车辆路径问题(VRP)等获得了比较理想的结果.本质上，TSP 是VRP 的基本问题，而VSP 与VRP 又具有较强相似性，即如果将RVSP 问题中的每个具有固定行驶时间的车次任务简化为一个节点，则RVSP问题就可作为一个VRP 来求解，因此文中拟用蚁群算法求解RVSP.另外，由于蚁群算法是基于构建性的优化算法，不是基于邻域搜索的;而RVSP 问题的车次集合划分特性，使得构建性算法较邻域搜索算法更适用于求解RVSP.

由于基本蚁群算法存在收敛速度慢、易陷入局部最优等缺陷，Thomas 等［16-17］提出了最大最小蚁群算法(MMAS)，较好地克服了蚁群算法的缺陷，成为求解离散组合优化问题最好的蚁群算法之一.所以，文中采用最大最小蚁群算法求解离散组合优化问题RVSP.

2.1 MMAS 简介

MMAS 对蚂蚁算法的改进主要体现在以下3点:①只对最优解所属路径上的信息素进行更新，以提高优化效率;②为避免搜索停滞，信息素水平被限制于［min，max］区间内;③初始时刻信息素水平设为max，有利于算法初期蚂蚁大范围的“探索”.

2.2 构建问题的解

不同于TSP 问题，RVSP 的解由蚂蚁种群协作产生，且为群体共同表达，因此有必要介绍其构建机制.首先定义解的形式和解空间集.区域公交车辆调度的MMAS 解是由车次节点、加气标识和空驶标识按一定次序组合构成，每只蚂蚁模拟一辆公交车，蚁群共同协作完成完整的车次任务.在解的构建过程中，加入时间轴变量tr.在蚁群协作机制中涉及到的集合及算法原理.

1)设xk(k=1，2，…，N)为车次节点，S 为总车次集合.S 按尚无车执行车次与已有车执行车次划分为两个集合Sa和Sn，满足以下关系式:Sa+Sn=S且SaSn=，其中Sn={xi|xiexecutedj，j=1，2，…，ants，i≠j}，ants 为蚂蚁总数.

2)蚂蚁的禁忌表由两个集合构成:可执行车次集allowed 和已执行车次集executed.allowed 和executed 满足:

由于每个车次只允许由一辆车执行，蚂蚁的allowed 集合构成如下:式中，pcur为蚂蚁当前所在的站场;当allowed=∅时，蚂蚁完成其当天的车次任务.

3)每个站场正在等待执行任务的蚂蚁集合为NCi(i=1，2，3).

定义第i 条线路初始阶段所需的最小蚂蚁数为ai(i=1，2，…，n).在初始阶段，按每条线路最小蚂蚁数的要求，将蚂蚁置于线路的起始车次上.蚁群的协作机制涉及到个体蚂蚁的行为动作及群体的协调，分为正常选择车次、加气、空车调度3 种，以蚁群中的第i 只蚂蚁为例说明.

(1)正常选择车次.蚂蚁i 在正常情况下按概率在其allowedi集合中选择下一车次xj(j≥2)，须满足

式中，ts(xj)为车次xj的起始时刻，te(xj－1)为车次xj－1的运行时间.选择方法在后续第5 节中详细描述.其后更新executedi及allowedi;并更新其连续运行时间tcR，i和车次集合Sa和Sn.

(2)加气.蚂蚁存在最大连续行驶时间限制.在其完成当前车次后按下式对其状态进行检查

式中，tlj为起始站场为pcur的线路j 运行时间;若蚂蚁i 满足式(14)，则对其进行加气，加气完成后更新其allowedi，按正常选择车次的方法在allowedi中选择下一车次xj(j≥3)，则此车次满足

式中，tF为加气时间，xj－1='fuel'.

(3)空车调度.为满足车次执行完备性要求，随着tr的递增，需要不断检测执行时刻处于［tr+tdh，tr+tH］的车次状态.即

式中，tdh为站场间的空驶时间，tH定义为状态检测的时间窗口上限.若xiSa则按下列规则进行空车调度或者增加蚂蚁数.

(a1)当antk处于车次xi所属站场时，antk原先正等待执行的车次xl的起始时刻应大于xi的起始时刻，即ts(xl)≥ts(xi);

(a2)当antk处于与班次xi所属站场不同时，antk原先正等待执行的车次xl的起始时刻应大于xi起始时刻与调度时间之和，即ts(xl)≥ts(xi)+tdh.

antj在完成空车调度并更新其allowedj集合之后，选择下一车次并等待执行车次xi.同时定义antj在车次任务xi的前一个任务节点为'DH'.

(b)当antk不满足上述条件或者∀NCj=(j=1，2，3)时，新增一个蚂蚁用于执行车次xi.

同时，存在单班车与双班车的区别.在增加蚂蚁以执行车次xi时，若xi满足:ts(xi)tksv，tksv为单班车激活时间窗，则增加的蚂蚁(公交车)属性为单班车，且处于激活状态;当单班车执行完其当前车次任务xi后，若满足ts(xi)+te(xi)∉tksv，则将该蚂蚁(即单班车)的激活标识复位，即不再处于激活状态，无需选择下一车次任务，此为单班车的退出机制.

2.3 信息素和启发式信息

在进行局部搜索时，蚂蚁在考虑车次节点间的信息素浓度的同时，也会考虑车次间的等待时间，因此引入启发式信息ηij，定义为车次xi，xj之间等待时间的倒数

2.4 信息素更新规则

最大最小蚁群算法中，每条轨迹上的信息量都限制在［min(t)，max(t)］之间，较好地避免了搜索面的局部停滞.在完成所有车次选择后，对信息素进行全局更新，信息素更新采用如下规则［14］

式中，ρ(0 ＜ρ ＜1)表示信息素挥发系数，1－ρ 表示信息素的残留度;ij(t)为t 次迭代路径(xi，xj)上的信息素浓度;δij(t)是路径(xi，xj)上信息素的增量，即σ(σ≥0)个精英种群本次迭代在路径(xi，xj)留下的信息素之和，其计算式为

第k 个精英种群留下的信息素增量为

式中，Q 为种群迭代留下的总信息素，fso-far-best(k，t)为迭代的当前最优解对应的目标函数值.每次迭代完成后，更新max(t)、min(t)的值，其计算公式为

然后再比较确定最大最小信息素的当前值:当信息素ij(t)＞max(t)时，设置ij(t)=max(t);同理，当ij(t)＜min(t)时，设置ij(t)=min(t).

2.5 选择机制

蚂蚁k 按概率在其allowed 空间中选择下一节点车次xj.其选择公式为

2.6 目标函数值

以种群协作产生的解计算目标函数值(以种群中第i 只蚂蚁为例).

式中，antN为种群最终的蚂蚁数，Timew为车辆总的等待时间，Timedh为总的空驶时间，且满足

2.7 算法步骤

步骤1 各项参数初始化，迭代次数gen=1，最大迭代次数mGen=200，蚁群数grp=10，蚁群规模ants=24;

步骤2 蚁群序数i=1;

步骤3 路径信息素设置为 (gen)，当gen=1时，其为初始信息素;将蚁群i 置于各线路最早的车次节点T(0);同时蚁群根据路径信息素选择其车次链的下一班次节点T(1);

步骤4 根据算法原理描述的方法执行蚁群i的完整车次链(即解Slni(gen))的搜索;

步骤5 对解Slni(gen)进行评价，计算其目标函数值，更新最优解，同时计算路径信息素增量Δi(gen);

步骤6 i=i+1;

步骤7 若i＞grp，则将整个路径的信息素更新为(gen+1)，转步骤7;否则，转步骤3;

步骤8 gen=gen+1，若gen＞mGen，输出最优解，算法结束;否则，转步骤2.

3 算例分析

某公交公司拟采取区域调度模式经营6 条公交线路以降低营运成本，所有的公交线路相关信息及固定时刻表信息如表1 和表2 所示，各个车场之间的车辆空驶时间信息如表3 所示.已知的相关线路、车辆参数:早晚高峰时段分别为［7:00，9:00］、［17:00，19:00］，tmax=480 min，tF=20 min，Cd=25.

表1 公交线路信息Table 1 Bus routes information

表2 线路时刻表Table 2 Timetable of routes

表3 空驶车次时间信息Table 3 Time information of deadhead trip

采用C 语言编写求解RVSP 问题的MMAS 程序，默认设置如下相关参数:mGen=2000，ants=24，grp=10，(0)=max(0)=1.0，α=1，β=2，ρ=0.8，Q=1000，b=20，ai=4 (i=1，2，…，6)，c0=500，c1=1.0，c2=2.5，tH=25 min，=1.经过计算，得到问题的最优解目标函数值为29 409，对应的最优车辆调度方案如表4 所示.从表4 中结果可知:完成370 个车次任务总共需派遣42 辆车(从车场A、B、C 初始调度的车辆数分别为9、19、14)，其中包含13 辆单班车，经加油25 次和空驶63 次，所有车辆的总工作时间为29149 min、等待时间为5 459 min、空驶时间为1180 min.便于对比分析，文中也编程对370 个车次任务进行了车辆全部为双班车的常规调度，调度结果如表5 所示.表6 为文中调度方案与常规调度方案的对比，从表6 数据可知:文中调度方案的车辆等待时间占总工作时间比例为18%，而常规调度方案为28%，改进率达34%;与常规调度方案相比，文中调度方案可节省4034 min 的等待时间(按照一个司机每天工作480 min，等于一天可节省8 个司机);更重要的是，采取手工驾驶员排班方式(即单班车配1 个驾驶员;双班车车次链总工作时间大于8h 需配置2 个驾驶员，否则仅需1 个驾驶员)，文中模型所得车辆调度方案需配置67 个驾驶员，常规调度方案则需81 个驾驶员，节省14 个驾驶员，改进率达17%.由此可见，文中考虑客流时间分布不均衡特征，采取低平峰期的抽停策略而建立的改进区域公交车辆调度模型，明显减少了公交车辆的等待时间及所需驾驶员人数，节省了公交公司运营开支.

表4 包含单班车的车辆调度方案1)Table 4 Vehicle scheduling scheme including single duty bus

续表4

表5 常规车辆调度方案Table 5 Conventional vehicle scheduling scheme

续表5

表6 两种车辆调度方案的对比分析Table 6 Comparison and analysis of two vehicle scheduling schemes

4 结语

文中考虑实际公交客流的时间分布不均衡，相应时刻表也非均衡的特征，以及参与公交区域调度的多条线路客流高峰时间、空间分布集中使得总体客流的高低峰客流量差异进一步加大的情况，提出低平峰时段停运部分公交车辆的抽停策略，从“部分班次被某辆车完成”的集合划分问题角度研究RVSP，建立一个新的区域公交车辆调度模型，以所需车辆数、车辆等待时间与空驶时间三者费用之和最小为第一目标，第二目标是要求车辆等待时间占总工作时间比例最小，采用MMAS 算法求解该模型.算例结果显示，新模型所得含单班车的车辆调度结果与全部为双班车的常规调度结果相比，各个调度指标均有所改进，其中，车辆等待时间及其所占比重改进率分别达到42%、34%，车辆等待时间可减少4 034 min(相当于一天可节省8 个司机(按8 h制))，更重要的是，文中模型所得车辆调度方案比常规车辆调度方案可少配置14 个驾驶员，改进率达17%.由此可见，文中考虑客流量差异特征，在低平峰期采取抽停策略建立的改进区域公交车辆调度模型，明显减少了公交车辆的等待时间及驾驶员人数，节省了公交公司运营开支，从而证明文中模型合理、有效.

提高车辆的使用效率是区域公交车辆调度的根本目标.区域公交车辆和驾驶员的一体化调度可以进一步提高车辆利用率，减少所需驾驶员数，是下一步的研究方向之一.

［1］邹迎，李建国.公共交通区域运营组织与调度系统研究［J］.运输系统工程与信息，2003，3(2):38-42.Zou Ying，Li Jian-guo.Research in the regional operation organization and dispatching of public transportation［J］.Journal of Transportation Systems Engineering and Information Technology，2003，3(2):38-42.

［2］王大勇，臧学运，王海星.公交区域车辆调度优化研究现状与发展［J］.北京交通大学学报，2008，32(3):42-45.Wang Da-yong，Zang Xue-yun，Wang Hai-xing.Research on situation and development trend for optimization theory and method of public transit vehicle scheduling problem［J］.Journal of Beijing Jiaotong University，2008，32(3):42-45.

［3］Haghani A，Banihashemi M.A comparative analysis of bus transit vehicle scheduling models［J］.Transportation Research Part B:Methodological，2003，37(4):301-322.

［4］Bertossi A，Carraresi P，Gallo G.On some matching problems arising in vehicle scheduling models［J］.Networks，1987，17:271-281.

［5］Lamatsch A.An approach to vehicle scheduling with depot capacity constraints［C］∥Proceedings of the Fifth international Workshop on Computer-aided Scheduling of Public Transport.Berlin Heidelberg:Springer-Verlag，1992:181-195.

［6］Mesquita M，Paixao J.Multiple depot vehicle scheduling problem:a new heuristic based on quasi-assignment algorithm［C］∥Proceedings of the 5th International Workshop on Computer-aided Scheduling of Public Transport.Berlin Heidelberg:Springer-Verlag，1992:167-180.

［7］Mesquita M，Paixao J.Exact algorithms for the multipledepot vehicle scheduling problem based on multi-commodity network flow type formulations［C］∥Proceedings of the 7th International Conference on Computer-aided Scheduling of Public Transport.Berlin Heidelberg:Springer-Verlag，1999:174-187.

［8］Lobel A.Solving large-scale multiple-depot scheduling problems［C］∥Proceedings of the 7th International Conference on Computer-aided Scheduling of Public Transport.Berlin Heidelberg:Springer-Verlag，1999:193-220.

［9］Haghani A，Banihashemi M.Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints［J］.Transportation Research Part A:Policy and Practice，2002，36(4):309-333.

［10］Kliewer N，Mellouli T，Suhl L.A time-space network based exact optimization model for multi-depot bus scheduling［J］.European Journal of Operational Research，2006，175(3):1616-1627.

［11］刘志刚，申金升.区域公交时刻表及车辆调度双层规划模型［J］.系统工程理论与方法，2007，27(11):

135-141.Liu Zhi-gang，Shen Jin-sheng.Regional bus operation bilevel programming model integrating timetabling and vehicle scheduling ［J］.Systems Engineering-Theory ＆Practice，2007，27(11):135-141.

［12］Wang H，Shen J.Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints［J］.Applied Mathematics and Computation，2007，190(2):1237-1249.

［13］魏明，靳文舟，孙博，求解区域公交车辆调度问题的蚁群算法研究［J］.公路交通科技，2011，28(6):141-152.Wei Ming，Jin Wen-zhou，Sun Bo.Ant colony Algorithm for regional bus scheduling problem ［J］.Journal of Highway and Transportation Research and Development，2011，28(6):141-152.

［14］Hao X，Jin W，Wei M.Max-min ant system for bus transit multi-depot vehicle scheduling problem with route time constraints［C］∥Proceedings of the World Congress on Intelligent Control and Automation (WCICA).Beijing:Institute of Electrical and Electronics Engineers Inc，2012:555-560.

［15］Dorigo M，Gambardella L M.Ant colonies for the traveling salesman problem ［J］.Biosystems，1997，43(2):73-81.

［16］Thomas Stuztle，Holger Hoos.Max-Min ant system and local search for the traveling salesman problem［C］∥Proceedings of the IEEE Conference on Evolutionary Computation.Indianapolis:IEEE，1997:309-314.

［17］Thomas Stutzle，Holger Hoos.Improvements on the ant system:introducing max-min ant system［C］∥Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms.Wien:Springer-Verlag，1998:245-249.

［18］段海滨.蚁群算法原理及其应用［M］.北京:科学出版社，2005:244-247.