1.本发明属于智能交通技术领域，特别涉及公交车辆调度以及在路况不确定、车辆行驶时长不固定条件下的公交车辆在线调度方法。
背景技术：2.公交车作为城市中的主要交通工具，在缓解城市交通压力上发挥着极为重要的作用。因此，公交车辆调度问题是一个需要解决的关键问题。合理的公交车调度将能减少交通资源的浪费，缓解交通压力。
3.公交车辆调度问题可以描述如下：
4.每条公交线路通常包括两个控制点(cp)，分别记为cp1和cp2，公交车辆在两控制点间往返行驶。每个控制点有一个根据实际客流情况制定的发车时刻表，其包括发车时刻点。设cp1、cp2的发车时刻点集合分别为t1、t2，则一条公交线路的时刻表中的所有发车时刻点表示为t＝t1∪t2。车辆从cp1(cp2)到cp2(cp1)的行驶称为一个行程。车辆调度问题是安排所有车辆的行程来覆盖发车时刻表中所有发车时刻点且不重复覆盖任一时刻点，达到最小化车辆数等优化目标。设一辆公交车v共有n个行程，如图1所示。每个带箭头的斜线表示v的一个行程。v的每个行程必须从t中某个时刻点发车，即n个行程覆盖n个时刻点。对于v的第j个行程，其出发时刻和到达时刻分别记为lj和aj，则其行驶时长hj＝a
j-lj。第j个行程的到达时刻与第j+1个行程的出发时刻之间为休息时间rj＝l
j+1-aj，(1≤j《n)。则v的n个行程的所有行驶时长为总休息时长为总工作时长为w＝h+r。
5.在实际的公交车辆调度过程中，调度人员可能要遵守一些约束条件，下面列出一些常见的约束条件：
6.(1)车辆v必须在一个行程结束后才能开始下一个行程，且休息时间不能小于最小休息时间r
min
，即l
j+1-aj≥r
min
。
7.(2)车辆v的h和w分别不大于最大行驶时间th和最大工作时间tw以防止v长时间行驶，即h≤th，w≤tw。
8.(3)司机的居住地一般离始发控制点较近。为保证司机能在其上班所在cp处下班，v的行程数须为偶数，即n mod 2＝0。
9.公交车辆调度问题(bvsp)是在满足排班约束的条件下，安排车辆来完成发车时刻表中所有时刻点对应的行程，同时最小化公交运营成本。
10.目前，已有的公交车辆调度方法将车辆调度问题看作优化问题，普遍采用精确算法或启发式算法来预先产生一个车辆排班方案，然后在实际中按此方案调度车辆。而在实际公交运营过程中经常面临交通拥堵、恶劣天气、突发事件等不确定因素，这将导致车辆行程时间出现波动。如果在车辆排班方案中指定某台车辆在某时刻发车，但在实际中该车辆却由于交通拥堵而没有返回控制点，使得该车辆无法在该时刻点准时发车，因而预先生成的车辆排班方案不能按计划执行。
11.因此，如何在车辆行驶时间不确定的公交运营场景下，对公交车辆进行快速、高质
量的实时(在线)调度，作为智能公交领域的关键问题，仍然存在。
技术实现要素：12.针对上述现有技术中存在的问题，本发明提供一种公交车辆在线调度方法，可以在车辆行驶时间不固定场景下快速做出高质量的车辆调度决策，从而降低公交运营成本、提高服务质量。
13.本发明的公交车辆在线调度方法，包括公交车辆在线调度控制器和参数优化方法。所述控制器中设置车辆类型动态转换器和车辆选择器。
14.所述控制器将每条公交线路的两个控制点的发车时刻表合并，并按照发车时间对所有时刻点重新排序，按照时刻点的顺序进行逐点决策；在每个时刻点，所述控制器获取车辆的实时运行状态与信息输入车辆类型动态转换器和车辆选择器。
15.所述车辆类型动态转换器实时决策车辆类型和状态，并发送给车辆选择器；车辆类型动态转换器将车辆的工作状态划分为工作态、休眠态和停运态三种，车辆类型包括短班车、长班车和高峰车。
16.所述车辆选择器进行发车车辆选择，包括：确定当前发车时刻所在控制点中处于工作态的车辆，作为候选车辆；若只有一台候选车辆，选择该车发车；当至少有两台候选车辆时，计算每台候选车辆的优先值，选取优先值最大的车辆发车；所述优先值综合考虑车辆剩余行程任务、连续休息时间以及是否仅剩最后一个行程来计算。
17.所述参数优化器优化所述控制器的参数。参数优化器，采用智能优化算法离线优化控制器的参数，所述控制器的参数包括α,β,γ,δ；α,β,γ为计算候选车辆的优先值时设置的参数，δ为将短班车转化为休眠态高峰车时设置的休息时长阈值。
18.所述车辆选择器计算候选车辆vi的优先值si的方式如下：
[0019][0020]
其中α、β、γ为参数；γi表示vi的剩余行程数；gi表示vi的剩余工作时长；bi表示vi自上个行程结束后的休息时长；li表示vi是否只剩下最后一个行程：
[0021][0022]
对于短班车和高峰车，γi＝m-ei，gi＝t
w-wi；
[0023]
对于长班车，γi＝2m-ei，gi＝2t
w-wi；
[0024]
tw为最大工作时间，m为最大行程数。
[0025]
相较于现有技术，本发明的优点与积极效果在于：
[0026]
(1)本发明方法将控制器实时控制思想结合智能优化算法应用至实时(在线)公交车辆调度问题上，在实际的公交车辆调度场景下，实现根据车辆实时运行信息进行实时在线的发车调度，不受交通拥堵等随机因素的影响。同时，本发明方法也适用于离线的公交车辆调度。
[0027]
(2)本发明方法通过统计、分析车辆实时运行信息，实现了实时调度车辆的功能。方法可以在满足所有的排班约束的条件下，在线调度若干车辆以覆盖发车时刻表上的每个时刻点。本发明方法可以降低公交运营成本、提高服务质量。
附图说明
[0028]
图1是公交车辆的行程示意图；
[0029]
图2是本发明的公交车辆在线调度方法的实现示意图；
[0030]
图3是本发明的公交车辆在线调度控制器进行车辆调度的流程示意图。
具体实施方式
[0031]
下面将结合附图和实施例对本发明作进一步的详细说明。
[0032]
实际公交运营过程中，在任一时刻点，公交线路控制点cp1(cp2)的车辆信息可被实时获取，例如：停在cp处的车辆数目、每辆车的编号、休息时间、已驾驶时间、已完成的行程数等。根据这些实时车辆信息可以选取一台车从该时刻点发出，即用该车辆执行该时刻点对应的行程。若在所有发车时刻点都如此决策，则时刻表中每个时刻点都会被一个车辆行程所覆盖，从而形成车辆排班方案。因此，本发明所设计的公交车辆在线调度方法通过在每个时刻点进行决策，来生成车辆排班方案，不需提前生成整个车辆调度方案后再执行该调度方案，而是根据cp中车辆的实时信息来在线调度车辆。
[0033]
如图2所示，本发明的公交车辆在线调度方法，设计了公交车辆在线调度控制器和参数优化器。其中，公交车辆在线调度控制器进行实时决策，在每个发车时刻，控制器根据cp内的车辆信息实时选择合适的发车车辆。为了让控制器按时间顺序进行决策，将cp1与cp2的发车时刻表合并，并按照发车时间对所有时刻点重新排序。控制器按照时刻点的顺序进行逐点决策。参数优化器用于优化控制器参数。
[0034]
公交车辆在线调度控制器在每个发车时刻点，实时转换车辆类型，选择合适的车辆执行当前时刻的发车任务，并及时下达下班指令。公交车辆在线调度控制器中设置有车辆类型动态转换器(vehicle type convector,vtc)和车辆选择器(vehicle selector,vs)。控制器实时获取公交车辆运营信息。本发明实施例搭建了一个公交运营仿真环境，控制器从中获取车辆的实时运行状态与信息，如车辆所处位置、车辆编号、车辆类型、是否已投入工作、已工作时长、休息时长、已完成的行程(班次)数量等。车辆类型动态转换器根据公交车辆信息实时决策车辆类型，如短班车、长班车、高峰车。车辆选择器根据车辆实时信息以及转换后的车辆类型进行发车车辆选择。
[0035]
(一)车辆类型动态转换器的实现说明如下。
[0036]
车辆调度中需要考虑不同车辆类型，包括短班车、高峰车、长班车等，用来满足不同时段的客运需求。一般来说，长班车的最大工作时长是短班车(高峰车)的2倍。高峰车的工作时间被划分为早高峰和晚高峰两个工作时段，其间隔不算入工作时间。高峰车可在早高峰时段结束后停运一段时间，等到晚高峰时段完成剩余行程。本发明将车辆的工作状态划分为“工作态”、“休眠态”和“停运态”三种，设计了一个车辆类型动态转换器，根据车辆状态和当前车辆信息来决策车辆类型。cp中处于“工作态”的车辆可被选择发车；处于“休眠态”的车辆不会被选中发车，直到被唤醒；处于“停运态”的车辆不会被选中发车或唤醒。
[0037]
车辆类型动态转换器进行车辆类型与状态转换规则如下：
[0038]
(a)将新车初始化为“工作态”的短班车：如果当前时刻点所在的cp中没有“工作态”和“休眠态”的车辆，则需要增加一辆新车。新车的状态设为工作态，类型设为短班车。
[0039]
(b)转换为“休眠态”高峰车：如果短班车的已完成行程数e是偶数，且执行最后一
个行程后的休息时长b达到阈值δ，即e mod 2＝0and b≥δ，则将其转化为“休眠态”的高峰车。其中，阈值δ是参数。此时，时长b为高峰车中间的大间隔时段内的时间，不计入工作时间。
[0040]
(c)转换为“休眠态”短班车：如果处于“工作态”的短班车满足以下条件之一：1)w≥tw；2)h≥th；3)当前已完成行程数e等于最大行程数m，则将其“工作态”转换为“休眠态”。m的计算公式为：
[0041][0042]
其中ta表示该线路的平均单程时间。w为车辆当前总工作时长，tw为最大工作时间。h为车辆当前总行驶时长，th为最大行驶时间。
[0043]
(d)唤醒“休眠态”车辆：如果cp内没有“工作态”车辆并且有“休眠态”车辆，则唤醒一辆休眠时间最长的车辆。如果唤醒车辆是短班车，将其转换为“工作态”的长班车；如果唤醒车辆是高峰车，将其状态转换为“工作态”。
[0044]
(e)高峰车停止工作：如果处于“工作态”的高峰车满足以下条件之一：1)w≥tw；2)h≥th；3)e＝m，则高峰车停止工作,其状态变为“停运态”。
[0045]
(f)长班车停止工作：如果处于“工作态”的长班车满足以下条件之一：1)w≥2tw；2)h≥2th；3)e＝2m，则长班车停止工作,其状态变为“停运态”。
[0046]
(g)线路结束运营：完成所有时刻点的调度任务后，将仍处于“工作态”的车辆转换为“停运态”，将处于“休眠态”的长班车、高峰车转换为“停运态”的短班车。
[0047]
(二)车辆选择器的实现说明如下。
[0048]
vs根据当前发车时刻点处cp的车辆信息以及vtc输出的车辆类型、状态，实时选择车辆发出。设某发车时刻点处，cp中有c辆车v1,v2,
…
,vc，其中m辆车处于工作态。vs的选择机制设计如下：
[0049]
(1)当cp内只有一辆工作态的车vi(m＝1)时，vs直接安排vi完成当前时刻点的行程。
[0050]
(2)当cp内存在至少两辆处于工作态的车辆(m≥2)时，vs需根据车辆信息从m台候选车辆中选择一辆最合理的车覆盖该时刻点。因此，本发明按下式计算每辆车vi(1≤i≤c)的优先值si：
[0051][0052]
其中α、β、γ为参数；γi表示vi的剩余行程数；gi表示vi的剩余工作时长；bi表示vi自上个行程结束后的休息时长；li表示vi是否只剩下最后一个行程：
[0053][0054]
vs从m台候选车辆中选择优先值si最大的车辆从该时刻点发出(覆盖该时刻点)。
[0055]
(三)参数优化器的实现说明。
[0056]
参数优化器根据若干次离线的仿真车辆调度的结果逐步优化控制器参数，提升其控制效果。本发明设计参数优化器采用智能优化算法离线优化控制器的4个参数：α,β,γ,
δ。智能优化算法包括粒子群算法(pso)、遗传算法(ga)、模拟退火等。每一组参数可以组成一个控制器。然后，用该控制器在仿真环境中进行在线调度，得到一个排班方案。用该排班方案的性能评价值作为该组参数的评价值。本发明用以下指标f来评价一个车辆排班方案与对应控制器参数：
[0057]
f＝μ1×
q+μ2×
p(4)
[0058]
其中，q,p分别代表车辆排班方案中行程数为偶数的车辆数、行程数为奇数的车辆数；μ1、μ2为系数，可根据公交公司的实际需求设置。
[0059]
在使用时，本发明的公交车辆在线调度方法，首先用智能优化算法，如粒子群算法pso，离线优化控制器的参数，其次用优化后的控制器进行实时调度。如图3所示，本发明的公交车辆在线调度方法实现车辆调度的一个具体流程如下：
[0060]
步骤1，获取发车时刻表，获取当前所有公交车辆运营信息，包括车辆编号、车辆所处位置、车辆类型、是否已投入工作、休息时长、已行驶时长、已工作时长、已完成的班次数量等。设发车时刻表中共个时刻点。
[0061]
步骤2，初始智能优化算法参数，本发明实施例采用粒子群优化算法，粒子的位置向量对应一组控制器参数，每个粒子表示一个控制器，粒子的适应度函数值为对应如公式(4)的控制器生成的车辆排班方案的评分。设置迭代次数p初始值为0，迭代次数上限为
[0062]
步骤3，每个粒子对应的控制器调用车辆类型动态转换器和车辆选择器，生成一个车辆排班方案，并对该排班方案进行评分，如图3中左侧虚线框中所示。生成并评价一个车辆排班方案的流程如下：
[0063]
(1)从第一个发车时刻点开始，即当前时刻k＝1，根据当前时刻点对应的车辆信息，控制器调用车辆类型转换器更新车辆类型，之后调用车辆选择器选择发车车辆；
[0064]
(2)更新车辆信息并继续进行下一时刻的车辆选择，即此时k自增1；
[0065]
(3)按序选择发车车辆直到完成最后一个时刻点的车辆选择，即当生成了一个车辆排班方案；
[0066]
(4)通过如公式(4)的评价函数对车辆排班方案进行评分，并将排班方案与评分外部存档。
[0067]
步骤4，执行参数迭代优化过程，如图3中右侧虚线框所示。循环执行上述步骤3，直至进行次排班后停止，并输出外部存档的最优控制器参数以及对应排班方案。
[0068]
本发明实施例利用pso优化控制器的四个参数α,β,γ,δ，每个粒子被表示为一个4维向量，4个维度分别对应于参数α,β,γ,δ。4维向量即位置向量。种群的第p个粒子x
p
的位置向量表示为它的速度向量v
p
表示为x
p
的每个粒子都记录自己途经的最佳位置(p-best)和对应的评价值。全局最优粒子(g-best)是历史上评价值最优的粒子。
[0069]
粒子的速度和位置向量的更新公式如下：
[0070][0071]
[0072]
其中，d∈{1,2,3,4}；ω表示惯性权重；δ1和δ2表示加速系数；和是[0,1]范围内的随机实数；是第p个粒子的p-best的第d维度；是g-best的第d个维度。
[0073]
pso优化控制器参数的过程如下：
[0074]
第1步:初始群中有n个粒子。随机初始化每个粒子的速度和位置。
[0075]
第2步:评价种群中的所有粒子。每个粒子被解码成一组控制器参数α,β,γ,δ，然后使用这些参数赋值的控制器产生一个车辆调度方案。通过公式(4)计算粒子的评价值。
[0076]
第3步:将每个粒子的p-best初始化为其当前位置，g-best初始化为当前种群最优粒子。
[0077]
第4步:每个粒子的速度和位置分别根据公式(5)和(6)更新。
[0078]
第5步:由(4)评估种群中的所有粒子。
[0079]
第6步:对于每个粒子，如果粒子当前评价值优于p-best，它的p-best更新为粒子当前位置。如果粒子优于g-best，那么g-best被更新为此粒子。
[0080]
第7步:转到并执行第4步，直到迭代次数达到最大值。此时，g-best即是已经优化的参数，代表优化的控制器。
[0081]
除说明书所述的技术特征外，均为本专业技术人员的已知技术。本发明省略了对公知组件和公知技术的描述，以避免赘述和不必要地限制本发明。上述实施例中所描述的实施方式也并不代表与本技术相一致的所有实施方式，在本发明技术方案的基础上，本领域技术人员不需要付出创造性的劳动即可做出的各种修改或变形仍在本发明的保护范围内。
技术特征：1.一种公交车辆的在线调度方法，其特征在于，该方法将发车时刻表上的每个发车时刻点视为决策点，利用控制器从控制点中选择一辆车从该发车时刻点发出；所述控制器的输入为：当前时刻控制点内的所有车辆的实时信息，包括：车辆的工作时间、休息时间、以及已完成的行程数目；控制器的输出为：选择一辆车从该发车时刻点发出；利用所述控制器对发车时刻表中的所有时刻点进行逐点在线决策，使得时刻表中每个时刻点都被一个车辆行程所覆盖，由此形成一个公交车辆排班方案；利用一个参数优化器来优化所述控制器的参数。2.根据权利要求1所述的方法，其特征在于，所述控制器包括车辆类型转换器和车辆选择器；所述控制器将每条公交线路的两个控制点的发车时刻表合并，并对所有时刻点按时间升序排序，按照时刻点的顺序进行逐点决策；在每个时刻点，将车辆的实时运行状态与信息输入到车辆类型转换器和车辆选择器；所述车辆类型转换器实时决策车辆类型和状态，并发送给车辆选择器；车辆类型转换器将车辆的工作状态划分为工作态、休眠态、停运态三种，考虑短班车、长班车、高峰车三种车辆类型；所述车辆选择器用于选择一辆车发出，其过程为：将当前发车时刻控制点中处于工作态的车辆作为候选车辆；若只有一台候选车辆，则选择该车辆发出；若至少有两台候选车辆，则计算每台候选车辆的优先值，选取优先值最大的车辆发出；所述优先值综合考虑车辆剩余行程任务、连续休息时间以及是否仅剩最后一个行程来计算。3.根据权利要求2所述的方法，其特征在于，所述的车辆的实时运行状态与信息包括公交线路上各车辆所处位置、车辆编号、车辆类型、是否已投入工作、已工作时长、休息时长、以及已完成的行程数量。4.根据权利要求2所述的方法，其特征在于，所述车辆类型转换器实时决策车辆类型和状态，包括：(a)如果当前公交线路所在控制点上没有工作态和休眠态的车辆，则为该公交线路增加一辆新车，新车的状态设为工作态，类型设为短班车；(b)如果短班车的已完成行程数e是偶数，且执行最后一个行程后的休息时长b达到阈值δ，则将该短班车转化为休眠态的高峰车；(c)如果处于工作态的短班车满足以下三个条件之一，则转换为休眠态的短班车；1)车辆当前总工作时长w≥t
w
；t
w
为车辆的最大允许工作时间；2)车辆当前总行驶时长h≥t
h
；t
h
为车辆的最大允许行驶时间；3)当前车辆已完成行程数e等于最大行程数m；其中m的计算公式为：其中，t
a
表示该公交线路的平均单程时间；(d)如果当前公交线路所在控制点上没有工作态的车辆并且有休眠态的车辆，则唤醒一辆休眠时间最长的车辆；如果唤醒的车辆是短班车，将该车转换为工作态的长班车；如果唤醒的车辆是高峰车，将该车状态转换为工作态；
(e)如果处于工作态的高峰车满足以下三个条件之一，则高峰车停止工作，状态变为停运态；1)w≥t
w
；2)h≥t
h
；3)e＝m；(f)如果处于工作态的长班车满足以下三个条件之一，则长班车停止工作，状态变为停运态；2)w≥2t
w
；2)h≥2t
h
；3)e＝2m；(g)当完成公交线路上所有时刻点的调度任务后，将处于工作态的车辆转换为停运态，将处于休眠态的长班车和高峰车转换为停运态的短班车。5.根据权利要求2或3所述的方法，其特征在于，所述的车辆选择器，计算候选车辆v
i
的优先值s
i
的方式如下：其中α、β、γ为参数；γ
i
表示v
i
的剩余行程数；g
i
表示v
i
的剩余工作时长；b
i
表示v
i
自上个行程结束后的休息时长；l
i
表示v
i
是否只剩下最后一个行程：对于短班车和高峰车，γ
i
＝m-e
i
，g
i
＝t
w-w
i
；对于长班车，γ
i
＝2m-e
i
，g
i
＝2t
w-w
i
；t
w
为最大工作时间，m为最大行程数。6.根据权利要求1或2所述的方法，其特征在于，所述的参数优化器，采用智能优化算法离线优化控制器的参数，所述控制器的参数包括α,β,γ,δ；α,β,γ为计算候选车辆的优先值时设置的参数，δ为将短班车转化为休眠态高峰车时设置的休息时长阈值。7.根据权利要求6所述的方法，其特征在于，所述的参数优化器，采用智能优化算法离线优化控制器的参数时，利用每组参数的控制器在仿真环境中进行在线调度，得到一个排班方案，通过指标f评价车辆排班方案与对应控制器参数：f＝μ1×
q+μ2×
p其中，q、p分别代表车辆排班方案中行程数为偶数的车辆数、行程数为奇数的车辆数；μ1、μ2为预设系数；指标f值越低，表示车辆排班方案质量越高。
技术总结本发明公开了一种公交车辆在线调度方法，属于智能交通技术领域，特别适用于在路况不确定、车辆行驶时长不固定条件下的公交车辆在线调度。本发明方法包括公交车辆在线调度控制器和参数优化器，控制器中设置车辆类型动态转换器和发车车辆选择器；控制器将每条公交线路的两个控制点的发车时刻表合并，对所有发车时刻点重新排序，顺序对每时刻点决策发车；在每个时刻点，车辆类型动态转换器实时决策车辆类型和状态，发车车辆选择器进行发车车辆选择；参数优化器采用智能优化算法离线优化在线调度控制器的参数。本发明实现根据车辆实时运行信息进行实时在线的发车调度，不受交通拥堵等随机因素的影响，可降低公交运营成本。可降低公交运营成本。可降低公交运营成本。
技术研发人员：左兴权 王飞扬 黄海 吴炳林
受保护的技术使用者：北京邮电大学
技术研发日：2022.04.22
技术公布日：2022/7/5
