CN102542791B - 一种公交车辆调度方法 - Google Patents

Abstract

本发明公开了一种公交车辆调度方法，包括：根据发车时刻表、司机休息时间、最大等待时间和最长工作时间，为每个初始发车时刻点生成其对应车辆的发车时刻点序列block的集合；生成N条有限长度的染色体，染色体的每一位对应一初始发车时刻点；对这N条染色体进行初始化，得到N条初始化后的染色体；所述染色体中一初始发车时刻点对应一block；对当前N条染色体先交叉、后变异，对变异后的N条染色体和交叉前的N条染色体进行选择，得到选择后的N条染色体；执行交叉、变异、选择，达到预定次数，得到最优染色体；对最优染色体进行调整，根据调整后每个发车时刻点及其对应的覆盖次数和block对车辆进行调度。本发明可提高车辆调度方案的实用性和生成效率。

Description

一种公交车辆调度方法

技术领域

本发明涉及交通领域的车辆调度技术，尤其涉及一种公交车辆调度方法。

背景技术

车辆调度问题(vehicle scheduling problem，VSP)是运输调度(transportscheduling)中的一个重要领域。根据涉及的约束限制，VSP归纳起来大致可以分为里程约束、车型约束、满载约束、非满载约束和时间窗约束五类。车辆调度问题具有非常广泛的实际应用场景，但由于实际场景的复杂性，车辆调度问题根据不同的应用场景分为很多种具体的问题。

针对时间窗约束的VSP，即发车时刻点确定情况下的车辆调度问题，目前在进行车辆调度处理时主要有两种方式，一种是手工调度，一种是用车辆调度系统调度。

手工调度需要消耗很多的人力，从而导致极大的运营成本、且效率低下。

而现存的车辆调度系统所采用的车辆调度方案主要分为两种，第一种是顺序方式，即先解决车辆调度问题再解决人员调度问题，也就是说，在解决车辆调度问题时没有考虑人员调度的因素，第二种是整合方式，即同时进行车辆和人员调度。

顺序方式在解决车辆调度问题时没有考虑人的因素，比如司机的休息时间、用餐时间等，从而使得车辆调度最优化可能会限制之后的人员调度，甚至都无法产生有效的人员调度解决方案，实用性比较低。

整合方式在解决车辆调度问题的同时也试图解决人员调度问题，这样在建立解决方案模型时，变量数目会增大很多，因而解决起来难度很大，生成车辆调度方案的效率太低，比如，Freling等人提出的算法解决一条线路的车辆调度问题需要86分钟，最快的也需要40分钟左右，在实际应用中，常常会遇到由于各种临时出现的问题而需重新生成车辆调度方案的情况，比如，部分车辆出现故障，此时，需要马上重新生成新的车辆调度方案，若生成车辆调度方案的时间太长，无疑会影响所有车辆的正常运行，从而使得这种方式的实用性受到限制。

综上所述，现有技术的公交车辆调度方案在解决车辆调度问题时，普遍存在实用性较低、且生成效率低下的问题。

发明内容

有鉴于此，本发明提出一种公交车辆调度方法，可提高车辆调度方案的实用性和生成效率。

为达到上述目的，本发明实施例的技术方案是这样实现的：

一种公交车辆调度方法，其特征在于，包括以下步骤：

S1、根据一初始发车时刻点、需要的发车时刻表、司机休息时间、最大等待时间和最长工作时间，为一车辆确定包含至少一个发车时刻点的可用发车时间范围；

S2、在所述可用发车时间范围内分别任意选择一属于发车时刻表的发车时刻点，将选择的发车时刻点作为元素，生成所述初始发车时刻点对应车辆的一发车时刻点序列block；

返回执行步骤S2，直至选择完所有可用发车时间范围内、且属于发车时刻表的发车时刻点，生成由发车时刻点序列block构成的集合；

S3、返回执行步骤S1，为每个初始发车时刻点生成其对应车辆的发车时刻点序列block的集合；

S4、生成N条有限的以位为长度的染色体，所述染色体的每一位对应于一初始发车时刻点；

对所述N条染色体进行初始化，得到N条初始化后的染色体；所述初始化后的每条染色体中一初始发车时刻点唯一地对应一发车时刻点序列block；

S5、将当前的N条染色体作为第一N条染色体进行交叉处理，对交叉后的N条染色体进行变异处理，对变异后的N条染色体和所述第一N条染色体进行选择处理，得到选择处理后的N条新染色体，作为步骤S5的当前N条染色体；

S6、重复执行步骤S5直至达到预定的次数，得到最优染色体；

S7、对所述最优染色体按覆盖次数进行调整，使得未覆盖以及重复覆盖的发车时刻点减少；根据调整后每个初始发车时刻点及其对应的发车时刻点序列block对车辆进行调度。

本发明的有益效果为，通过采用遗传算法，得到较佳公交车辆调度方案，再对所述公交车辆调度方案进行调整，得到满足实际需要的公交车辆调度方案，同时，在遗传算法的设计中考虑了司机休息时间、最大等待时间等，使得本发明方案在实施时更加具备可行性，提高了公交车辆调度方案的实用性。而且，采用本发明方案，可极大地提高公交车辆调度方案的生成效率。

附图说明

图1为本发明实施例的方法流程图；

图2为本发明实施例的初始发车时刻点发出的block遍历过程示意图；

图3为本发明实施例的初始发车时刻点发出的block集合示意图；

图4为本发明实施例的染色体与block的对应关系示意图；

图5为本发明实施例的交叉处理示意图；

图6为本发明实施例的变异处理流程示意图；

图7为本发明实施例的轮盘赌操作示意图；

图8为本发明实施例的调整发车时刻点覆盖次数的整体流程图；

图9为本发明实施例的按发车时刻表上发车时刻点递减顺序调整发车时刻点覆盖次数的流程图；

图10为本发明实施例的按发车时刻表上发车时刻点递增顺序调整发车时刻点覆盖次数的流程图；

图11为本发明实施例的公交车辆调度方案调整示例图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下通过具体实施例并参见附图，对本发明进行详细说明。

本发明在解决公交车辆调度问题时，通过采用遗传算法，得到较优的公交车辆调度方案，再对其进行调整，以得到满足实际需要的公交车辆调度方案。在采用遗传算法时，考虑了司机休息时间、最大等待时间等，即考虑了人的因素，使得本发明方案在实施时更加具备可行性，提高了公交车辆调度方案的实用性。

本发明方案相对现在现存的公交车辆调度系统，不仅提高了实用性，而且提高了生成公交车辆调度方案的效率，仅需两分钟左右即可生成一条公交线路的车辆调度方案，而且很接近手工调度的结果，现有公交车辆调度系统生成一条公交线路的车辆调度方案，最快的也需要40分钟左右。

本发明实施例的方法流程如图1所示，一种公交车辆调度方法，包括以下步骤：

步骤101：根据一初始发车时刻点、需要的发车时刻表、司机休息时间、最大等待时间和最长工作时间，为一辆车确定包含至少一个发车时刻点的可用发车时间范围。

发车时刻表是已知的，比如，由公交公司预先给定，初始发车时刻点被包含于发车时刻表中，也是预先确定的。

本发明中考虑了司机休息时间，因此，使得本发明方案具备可实施性，现有许多车辆调度的解决方案都没有考虑司机休息时间，在执行时往往会遇到问题，不具备实用性。

司机休息时间可预先设定，比如完成从主站到副站、或副站到主站的一趟后，休息10分钟，再进行下一趟行程，当时间点位于用餐时间范围内比如11:30～12:30时，这时的司机休息时间还要加上司机用餐的时间，比如吃饭需用30分钟，此时，司机休息时间为10分钟+30分钟＝40分钟。

设计最大等待时间是为了避免同一发车方案中相邻两个行程的间隔时间太长，以提高效率，这个值的设定可以根据实际情况而定。

最长工作时间可以是司机一天的工作时间，也可以是司机一天工作时间的两倍(可以分给两个司机使用)，设计最长工作时间是为了将一辆车一天的驾驶时间与司机的工作时间匹配起来。

对于每一个初始发车时刻点，预先获取所述初始发车时刻点对应车辆从一个站点到另一个站点(从主站到副站一趟的行驶时间、或从副站到主站)一趟的行驶时间；

当所述车辆从一站驶往另一站时，将当前发车时刻点加上所述车辆从一站到另一站一趟的行驶时间记为所述车辆从一站到达另一站时的到达时刻点，将所述到达时刻点加上司机休息时间记为发车时刻点初始时间，将所述发车时刻点初始时间加上最大等待时间记为发车时刻点结束时间，将时间区间[发车时刻点初始时间，发车时刻点结束时间]作为所述初始发车时刻点对应车辆的可用发车时间范围。

如图2所示，假设初始发车时刻点8:00对应车辆M从主站到副站一趟的行驶时间为50分钟，则M在8:50到达副站，司机休息时间设为10分钟，则发车时刻点初始时间为9:00，假设最大等待时间为10分钟，则发车时刻点结束时间为9:10，时间区间[9:00，9:10]即为从8:00发出的车M的可用发车时间范围。

步骤102：在所述可用发车时间范围内分别任意选择一属于发车时刻表的发车时刻点，将选择的发车时刻点作为元素，生成所述初始发车时刻点对应车辆的一发车时刻点序列block；

返回执行步骤102，直至选择完所有可用发车时间范围内、且属于发车时刻表的发车时刻点，生成由发车时刻点序列block构成的集合。

所述生成由发车时刻点序列block构成的集合，包括：

将一车辆从主站到副站的一趟、或从副站到主站的一趟作为一个短程trip，当初始发车时刻点的发车时间为t_i、运行当前trip的时间为t_r、司机休息时间为R、以及最大等待时间为K时，

A、将初始发车时刻点t_i作为的第一trip发车时间，令t_c＝t_i作为block序列中的第一元素，

B、将位于区间[t_c+t_r+R，t_c+t_r+R+K]内、且属于发车时刻表上的任一发车时刻点t′作为下一个trip所选择的发车时刻点，并将该t′作为所述block序列中的下一个元素；

C、当t′-t_i≤最长工作时间时，更新t_c＝t′，返回执行步骤B，否则，将当前block序列作为初始发车时刻点t_i对应车辆的一发车时刻点序列block；

D、返回执行步骤A，直至选择完所有位于区间[t_c+t_r+R，t_c+t_r+R+K]内、且属于发车时刻表上的任一发车时刻点t′，得到发车时刻点序列block的集合。

如图2所示，在9:00～9:10之间有两个属于发车时刻表的发车时刻点，分别为9:03和9:06，即为可用发车时刻点。可以先选择其中的9:03作为8:00发出的车辆M的一个发车时刻点序列block中的元素，如图3所示，当车辆进行下一个行程时，可选10:03作为所述block的下一个元素，继续迭代下去，直至block的长度等于或大于最长工作时间，停止迭代，这时可以得到一个block，如图3，得到b_i(即为block_i)＝8:00、9:03、10:03...21:10，然后，需要选择完可用时间范围内的所有发车时刻点，对于同一初始发车时刻点，还可以得到其它block，如图3，b_j(即为block_j)＝8:00、9:06、10:10...21:40，等等，如此，可以得到多个block，组成从8:00发车的block集合。车辆调度方案中，最终会从所述block集合中选择一个block作为8:00发车的车辆一天的发车时刻点序列。

步骤103：返回执行步骤101，为每个初始发车时刻点生成其对应车辆的发车时刻点序列block的集合。

初始发车时刻点一般都是早上的发车时刻点，因为从早上开始工作比较符合司机的正常工作时间安排，每个初始发车时刻点都对应一辆车，为每个初始发车时刻点都按照步骤101和步骤102生成其对应车辆的block集合，用于后续的遗传算法中。

可以对产生的所有的block进行编号，并按照初始发车时刻点分类，每个初始发车时刻点的所有的block形成一个集合。假设初始发车时刻点集合P中的元素个数为T_p，即|P|＝T_p，假设block集合为B，而block总数为T_b，即|B|＝T_b。那么将生成T_p个集合Q₁，Q₂，…， 假设从1开始编号，每找到一个block就对它进行编号，然后让编号值递增。这里由于采用如步骤101和步骤102的深度优先搜索的方式生成所有block，所以从同一个初始发车时刻点出发的block编号都是连续的。假设第一个初始发车时刻点最后生成了200个可选的block，那么该点的block集合，Q₁，为{1，2，...，200}，而第二个初始发车时刻点的block的编号会从201开始，也就是{201，...}。这有助于之后判断某个block属于哪个初始发车时刻点的block集合。

步骤104：生成N条有限的以位为长度的染色体，所述染色体的每一位对应于一初始发车时刻点；

对所述N条染色体进行初始化，得到N条初始化后的染色体；所述初始化后的每条染色体中一初始发车时刻点唯一地对应一发车时刻点序列block。

本发明采用遗传算法，一条染色体就代表一种车辆调度方案，染色体的每一位对应一个初始发车时刻点，由于初始发车时刻点有限，因而染色体的长度不会太长。假设有p个初始发车时刻点，那么染色体的长度为p，一条染色体可以表示为：

x₁x₂…x_p

如果对于染色体的某一位，x_i，i∈[1，p]，如果有x_i＝0，表示该染色体所代表的车辆调度方案在这个初始发车时刻点没有发车；如果不为0，假设x_i＝v，表示该染色体所代表的车辆调度方案在这个初始发车时刻点发车，该点的值为block的编号，即v∈Q_i。

染色体与block的对应关系示例如图4所示，染色体的一位x₁对应的block为b₁₀₀(即block₁₀₀)＝5:35、6:15、...、20:38，其中，block₁₀₀属于x₁的初始发车时刻点5:35发出的block集合Q₁中。

作为较佳实施例，对所述染色体进行初始化的方法为：

L1、按时间顺序，选择所述染色体中属于主站的所有初始发车时刻点，对于选定的每一个初始发车时刻点，

若该初始发车时刻点还没有被发车时刻点序列block覆盖，则从该初始发车时刻点的block集合中随机选择一block作为该初始发车时刻点对应的block，记为该初始发车时刻点的覆盖block，并将所述覆盖block中包含的其它初始发车时刻点标记为已覆盖；

若该初始发车时刻点已覆盖，就选择下一个初始发车时刻点；

L2、选择所述染色体中属于副站的所有初始发车时刻点，执行步骤L1；

L3、当所述覆盖block的数量等于预先设定的覆盖block数量阈值R，或者，选择完染色体中的所有初始发车时刻点时，停止选择初始发车时刻点。

步骤L1中所述按时间顺序，包括：按时间递增的顺序，或者按时间递减的顺序。

所述覆盖block数量阈值R等于发生时刻表中发车时刻点个数除以一个block所包含的发车时刻点个数Y，Y等于最长工作时间除以车辆从主站驶往副站一趟的时间长度，或者Y等于最长工作时间除以车辆从副站驶往主站一趟的时间长度。

例如，总共有500个trip，一个发车时刻点相当于一个trip，即发车时刻点为500个，一个block有16个trip，那么可以估算一下大致需要500/16≈32个block。

其中，一个block的长度表示一个司机一天的工作时间，比如为8小时，而司机驾驶车辆从主站到副站、或从副站到主站一趟的时间，即一个trip为30分钟，则可以估算一个block所包含的发车时刻点个数，即一个block所包含的trip个数为8/0.5＝16。

作为另一较佳实施例，对所述染色体进行初始化的方法为：

从所述染色体中所有的初始发车时刻点中随机选择R个初始发车时刻点，对于其中的任一初始发车时刻点，从该初始发车时刻点的block集合中随机选择一block作为该初始发车时刻点对应的block，记为该初始发车时刻点的覆盖block，R为覆盖block数量阈值。

这里随机选择表示，从染色体x₁x₂…x_p的p个x_i中，选择R个x_i，然后从每个x_i对应的block集合中随机选择一个block来覆盖x_i。

对染色体初始化时，需要预先确定染色体初始化的次数，初始化一次就得到一条染色体。

一条染色体中包含的block数的阈值R的设定可能会影响遗传算法的收敛速度，但只要遗传算法的代数足够，就不会影响最后的结果，如可以取R＝30。

对于染色体的初始化，例如，设N₁＝{1，2，...，n₁}为主站初始发车时刻点集合，N₂＝{1，2，...，n₂}为副站初始发车时刻点集合，对某个发车时刻点i∈(N₁∪N₂)，覆盖该发车时刻点的block集合H_i，对某个block，j∈B，该block覆盖的发车时刻点集合K_j，染色体初始化时，会对每个发车时刻点进行标记，初始化每个发车时刻点为未覆盖，然后在初始化的过程中依次覆盖并改变标记。

上述染色体初始化的方法实际可分为三种，分别是：

(1)从头至尾依次覆盖：对于发车时刻点i∈(N₁∪N₂)，先访问N₁再访问N₂，而对N₁或者N₂内部，按序号从第一个发车时刻点往后开始依次覆盖，如果该发车时刻点没有覆盖，就从覆盖该发车时刻点的block集合，H_i，中随机选择一个block，bt∈Q_i，来覆盖该发车时刻点，此时将这个初始发车时刻点在染色体中对应的位的值设为bt，即使得x_i＝bt，同时将bt覆盖的其它发车时刻点标记为已覆盖；如果已经覆盖就跳过。当染色体所包含的block数为R时、或者初始发车时刻点依次访问完时停止；

(2)从尾至头依次覆盖：与从头至尾依次覆盖类似，只不过发车时刻点的访问顺序变为时间递减顺序，仍是先访问N₁再访问N₂；

(3)随机产生：从所有的初始发车时刻点中随机选择R个，对这R个初始发车时刻点依次初始化，选择该点发出的某个block。

例如：若要初始化200条染色体，可以按上述方式(1)初始化80条，按方式(2)初始化70条，按方式(3)初始化50条，得到多种初始化方式的染色体。

步骤105：将当前的N条染色体作为第一N条染色体进行交叉处理，对交叉后的N条染色体进行变异处理，对变异后的N条染色体和所述第一N条染色体进行选择处理，得到选择处理后的N条新染色体，作为步骤105的当前N条染色体。

所述对当前的N条染色体进行交叉处理，包括：

对当前的N条染色体随机配对，对于配对后得到的对染色体中的每一对染色体，互换这对染色体中部分相同位的初始发车时刻点所对应的发车时刻点序列block。

举例说明，如图5所示，从所述N条染色体中每次随机选择两条染色体，并随机选择一个初始发车时刻点以后的位置(包含所选择的初始发车时刻点)进行交叉，例如，选择x_k和y_k以后的位置(包括：x_k、...、x_p；y_k、...、y_p)进行交叉，x_k与y_k、...、x_p与y_p对应的是染色体中的同一初始发车时刻点位置，得到交叉后的染色体如图5所示。

所述对交叉后的N条染色体进行变异处理，包括：

对所述N条染色体中的任一染色体，生成该染色体的随机数z，当z小于预设的变异阀值时，按该染色体中初始发车时刻点时间递增的顺序，选择每一个初始发车时刻点，

对于当前选择的初始发车时刻点，生成所述初始发车时刻点的第一随机数p，当p小于或等于第一阈值时，生成所述初始发车时刻点的第二随机数q，

当q大于第二阈值时，设定所述初始发车时刻点没有block覆盖，否则，将所述初始发车时刻点的block变异为该初始发车时刻点对应车辆的block集合中的另一block，判断染色体中是否还有下一个初始发车时刻点，是，选择下一个初始发车时刻点，否，变异结束。

举例说明，对于任一染色体，首先生成该染色体的随机数z，若z小于预设的变异阈值，例如，0.05≤变异阈值＜0.1，变异阈值可取上述范围内的任一固定值，比如变异阈值取0.07，则当z≥0.07时，不发生变异，当z＜0.07时，该染色体的变异处理过程如图6所示：

对于当前选定的初始发车时刻点，如使用c语言的random()函数为其生成随机数p，0＜p＜1，第一阈值表示有多大的概率发生变异，预先设定第一阈值为0.05，当p大于0.05时，不发生变异，选择下一个初始发车时刻点，否则，发生变异，此时生成随机数q，0＜q＜1，第二阈值表示发生变异的方式，预先设定第二阈值为0.2，当q小于0.2时，所述初始发车时刻点变异为在该初始发车时刻点没有block覆盖，选择下一个初始发车时刻点，否则，将覆盖所述初始发车时刻点的block变异为另一个覆盖该初始发车时刻点的block，选择下一个初始发车时刻点，若没有下一个初始发车时刻点就结束。

所述对变异后的N条染色体和所述第一N条染色体进行选择处理，得到选择处理后的N条新染色体，作为步骤S5的当前N条染色体，包括：

计算每条染色体的惩罚函数值，获取2N条染色体的惩罚函数值之和F，得到每一染色体的选择概率等于其惩罚函数值除以F，设定每一染色体的累计概率为该染色体的选择概率与前一染色体的累计概率之和，使得每个染色体对应一个随机数区间为：[前一染色体的累计概率，当前染色体的累计概率]；

生成N个随机数，若其中任一随机数被包含在任一随机数区间中，则选取所述随机数区间对应的染色体，得到选择处理后的N条新染色体，作为步骤S5的当前N条染色体。

所述惩罚函数值为主站和副站的惩罚函数值之和，其中，主站或副站的惩罚函数值X为

$X=I-P\underset{s=1}{\overset{T}{\mathrm{\Σ}}}|\underset{i=1}{\overset{t_s}{\mathrm{\Σ}}}{v}_{\mathrm{si}}-1|-Q\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{z}_i$

其中，I、P、Q分别是预先设定的正整数，T表示与主站或副站发车时刻表对应的时间区间的总数，v_si表示时间区间S的第i个发车时刻点被覆盖的次数，n表示发车时刻点总数，z_i表示发车时刻点是否被覆盖，z_i＝1表示未被覆盖，z_i＝0表示已被覆盖。

P、Q均为权重，设置P惩罚的是重复覆盖的情况，即P越大，车会比越少而导致有的发车时刻点没有被覆盖，Q惩罚的是在初始发车时刻点不发车的情况，即Q越大，所有点都会覆盖掉，重复覆盖的情况也越多，可能会出现空跑的情况。

I根据P、Q来设定，赋予一个正的初始值I是为了保证最后结果为正数，I、P、Q均是经验值，从不断的试验中得到。

上述选择处理实际是用轮盘赌的方法进行选择操作，实现如下：

1)计算群体中所有染色体适应值之和，惩罚函数值就是适应值：

2N为染色体个数

2)计算每个染色体的选择概率：

$p_k=\frac{X_k}{F}$

3)计算每个染色体的累计概率：

$q_k=\underset{j=1}{\overset{k}{\mathrm{\Σ}}}{p}_j$

4)转动轮盘N次，从2N个染色体中选择N个染色体：

为了选择种群中的个体，设想有一个指针指向轮盘，转动轮盘，当轮盘停止后，指针所指向的染色体被选择。如图7所示，为6个染色体的轮盘，染色体的适应值越大表示该染色体的扇形面积就越大，被选择的可能性越大。

步骤106：重复执行步骤105达到预定的次数，得到最优染色体。

所述重复执行步骤105达到预定的次数，得到最优染色体，包括：

重复执行步骤105达到预定的次数后，得到N条染色体，将所述N条染色体中惩罚函数值最大的染色体选定为最优染色体。

步骤107：对所述最优染色体按覆盖次数进行调整，使得未覆盖以及重复覆盖的发车时刻点减少；根据调整后每个初始发车时刻点及其对应的发车时刻点序列block对车辆进行调度。

对所述最优染色体按覆盖次数进行调整，使得未覆盖以及重复覆盖的发车时刻点减少，包括，

以主站和副站为类别，将所述染色体中各个初始发车时刻点对应的发车时刻点序列block整理为按时刻点递增顺序排列的站点发车时刻表，所述站点发车时刻表中包括各个发车时刻点、及其对应的覆盖次数和覆盖block，

对于站点发车时刻表，分别执行

步骤G1：按排列顺序遍历发车时刻点，当遍历到覆盖次数为0的发车时刻点j`时，则

从发车时刻点j`开始，按照发车时刻点递减的顺序在发车时刻表中选择发车时刻点k，

若发车时刻点k的覆盖次数等于1、且发车时刻点k与发车时刻点k+1之间的时间差小于发车时刻点k对应的trip的完成时间和同一个block中下一个发车时刻点的时间的差值，则继续选择下一个发车时刻点；

若发车时刻点k的覆盖次数大于1、发车时刻点k与发车时刻点k+1之间的时间差小于发车时刻点k对应的trip的完成时间和同一个block中下一个发车时刻点的时间的差值，则进行如下调整：

GE1、将发车时刻表中的发车时刻点序列(k、k+1、...、j`-1、j`)作为待调整发车时刻点序列；选择覆盖发车时刻点k的所有block中、发车时刻点k对应的trip的完成时间和同一个block中下一个发车时刻点的时间的差值最大的block作为待调整block；

GE2、将所述待调整block中的发车时刻点k调整为发车时刻表中的发车时刻点k+1；

GE3、将覆盖发车时刻点k+1的、且未曾调整的block中的发车时刻点k+1调整为发车时刻点k+2；对于待调整发车时刻点序列(k、k+1、...、j`-1、j`)中除j`外的每一个发车时刻点，均如此调整，直至将覆盖发车时刻点j`-1的、且未曾调整的block中的发车时刻点j`-1调整为发车时刻点j`为止；

更新发车时刻表中发车时刻点j`的覆盖次数为1，发车时刻点k的覆盖次数减少1次；

如果从发车时刻点j`开始，按照发车时刻点递减的顺序在发车时刻表中未能选择出发车时刻点，则

从发车时刻点j`开始，按照发车时刻点递增的顺序在发车时刻表中选择发车时刻点k，

若发车时刻点k的覆盖次数等于1、且发车时刻点k与发车时刻点k-1之间的时间差小于发车时刻点k和同一个block中上一个发车时刻点对应的trip的完成时间的差值，继续选择下一个发车时刻点；

若发车时刻点k的覆盖次数大于1、且发车时刻点k与发车时刻点k-1之间的时间差小于发车时刻点k和同一个block中上一个发车时刻点对应的trip的完成时间的差值，进行如下调整：

GF1、将发车时刻表中的发车时刻点序列(j`、j`+1、...、k-1、k)作为待调整发车时刻点序列；选择覆盖发车时刻点k的所有block中、发车时刻点k和同一个block中上一个发车时刻点对应的trip的完成时间的差值最大的block作为待调整block；

GF2、将所述待调整block中的发车时刻点k调整为发车时刻表中的发车时刻点k-1；

GF3、将覆盖发车时刻点k-1的、且未曾调整的block中的发车时刻点k-1调整为发车时刻点k-2；对于待调整发车时刻点序列(j`、j`+1、...、k-1、k)中除j`外的每一个发车时刻点，均如此调整，直至将覆盖发车时刻点j`+1的、且未曾调整的block中的发车时刻点j`+1调整为发车时刻点j`为止；

更新发车时刻表中发车时刻点j`的覆盖次数为1，发车时刻点k的覆盖次数减少1次；

步骤G2：重复执行步骤G1，直至达到预定的次数，得到调整后的包含有各个发车时刻点、及其对应的覆盖次数和覆盖block的站点发车时刻表。

在遗传算法结束后，对最后得出的结果进行调整，来减少未覆盖以及重复覆盖的发车时刻点。通过设置相关变量，对上述调整的实现过程详细描述如下：

对于步骤106得到的最优染色体中每个初始发车时刻点所对应block中的发车时刻点，记录每个发车时刻点的覆盖次数，主站的为副站的为假设主站的发车时刻点数量为n₁，副站的发车时刻点数量为n₂，depart_time[k]为第k个发车时刻点的发车时间，relax_time[k]代表司机在跑完第k个trip后的休息时间，所述休息时间为这个发车时刻点对应的trip的完成时间和同一个block中下一个发车时刻点的发车时间的差值，

对于最优染色体中每个初始发车时刻点所对应的block，即b_i，记录b_i所覆盖的发车时刻点序列为(t_i1，t_i2，…，t_ip)，p表示这个block覆盖的发车时刻点总数，记录b_i覆盖的每个发车时刻点对应的休息时间为(r_i1，r_i2，…，r_ip)，

假设t_i1对应在发车时刻表中的发车时刻点为k，设定relax_time[k]＝r_i1，对于发车时刻表中那些未覆盖的发车时刻点，relax_time[k]＝0，对于那些覆盖次数大于1次的发车时刻点，也就是有多个block覆盖它，relax_time[k]表示所述多个block中司机在跑完第k个trip后的休息时间中的最大值，即若发车时刻点k被多个block覆盖，所述多个block中的每个block都有司机在跑完第k个trip后的休息时间，这里设定relax_time[k]为所述多个休息时间中的最大值。如此设置是为了保证后续调整的空间更大。

先调整主站的发车时刻点，之后再调整副站的发车时刻点。

调整的步骤如图8所示，具体为：

M1、初始化迭代次数i＝0，发车时刻点j＝1；

M2、从第j个发车时刻点按时间顺序递增遍历发车时刻点，直到找到未覆盖的发车时刻点j`，或者发车时刻点被访问完。若找到了覆盖次数为0的发车时刻点j`，转M4，若发车时刻点被访问完，则转M3；

M3、若i＝I，I为预设的迭代次数，算法终止；否则i＝i+1，j＝1，转M2；

M4、令k＝j`-1，转M5；

M5、若k被访问的次数为1并且depart_time[k+1]-depart_time[k]＜relax_time[k]，则令k＝k-1，继续进行同样的判断；若k被访问的次数大于1并且depart_time[k+1]-depart_time[k]＜relax_time[k]，则进行调整，调整后k和j`的覆盖次数都变为1，令j＝j`+1，转M2；否则，转M6；

M6、令k＝j`+1，转M7；

M7、若k被访问的次数为1并且depart_time[k]-depart_time[k-1]＜发车时刻点k和同一个block中上一个发车时刻点对应的trip的完成时间的差值，则令k＝k+1，继续进行同样的判断；若k被访问的次数大于1并且depart_time[k]-depart_time[k-1]＜发车时刻点k和同一个block中上一个发车时刻点对应的trip的完成时间的差值，则进行调整，调整后k和j`的覆盖次数都变为1，令j＝j`+1，转M2；否则，令j＝j`+1，转M2。

具体调整过程如下：

在步骤M5中，调整流程如图9所示，假设找到了满足调整条件的j`和k，调整的发车时刻点序列为(k，k+1，…，j′)，调整从i＝k开始，找到k对应的block，由于k被覆盖了多次，这里要找的需要进行调整的那个block，即k被覆盖多次时发车时刻点k对应的trip的完成时间和同一个block中下一个发车时刻点的时间的差值最大的block作为待调整block，设为b_tmp，b_tmp覆盖的发车时刻点序列为(t_tmp，1，…，t_tmp，k′，t_tmp，p)，

步骤U1、假设b_tmp覆盖的第k`个发车时刻点对应发车时刻表中的发车时刻点k，相应的休息时间序列为(r_tmp，1，…，r_tmp，k′，r_tmp，p)，将t_tmp，k′调整为对应时刻点k+1，这样block b_tmp将会从发车时刻点k+1发车。这样会影响到休息时间r_tmp，k′和r_tmp，k′-1；

修改r_tmp，k′＝r_tmp，k′-(depart_time[k+1]-depart_time[k])，r_tmp，k′-1＝rtmp，k′-1+(depart_time[k+1]-depart_time[k])。这样对b_tmp的调整完毕，它会覆盖时刻点k+1而不是k；

步骤U2、更新i＝i+1，执行步骤U1，直至i取完(k，k+1，…，j′)中k之后的所有发车时刻点，修改覆盖次数c_k＝ck-1，c_j′＝1。

所述步骤U2，就是再对原本覆盖时刻点i＝k+1的block进行类似步骤U1的调整，它会覆盖k+2而不是k+1，i要取完调整的发车时刻点序列(k，k+1，…，j′)中除j′外的每一个元素，都进行如步骤U1的调整，最后，原本覆盖时刻点j`-1的block经过调整后会覆盖时刻点j`，再修改覆盖次数c_k＝c_k-1，c_j′＝1，调整结束。

步骤M7与步骤M5中的调整过程类似，如图10所示，只是调整的发车时刻点序列变为了(j′，j′+1，…，k)。

在步骤M7中，假设找到了满足调整条件的j`和k，那么调整的发车时刻点序列为(j′，j′+1，…，k)，调整从i＝k开始，找到k对应的block，由于k被覆盖了多次，这里要找的需要进行调整的那个block，即k被覆盖多次时，发车时刻点k和同一个block中上一个发车时刻点对应的trip的完成时间的差值最大的block作为待调整block，设为b_tnp，b_tnp覆盖的发车时刻点序列为(t_tnp，1，…，t_tnp，k′，t_tnp，p)，

步骤V1、假设b_tmp覆盖的第k′个发车时刻点对应发车时刻表中的发车时刻点k，相应的休息时间序列为(r_tnp，1，…，r_tnp，k′，r_tnp，p)，将t_tnp，k′调整为发车时刻表中发车时刻点k-1，这样block b_tnp将会从发车时刻点k-1发车。这样会影响到休息时间r_tnp，k′和r_tnp，k′+1。

修改r_tnp，k′＝r_tnp，k′-(depart_time[k]-depart_time[k-1])，r_tnp，k′+1＝r_tnp，k′+1+(depart_time[k]-depart_time[k-1])。这样对b_tnp的调整完毕，它会覆盖时刻点k-1而不是k；

步骤V2、更新i＝k-1，执行步骤V1，直至i取完(j′，j′+1，…，k)中除j′外的所有发车时刻点，修改覆盖次数c_k＝c_k-1，c_j′＝1。

调整过程举例说明如下：

如图11所示，假设步骤106后得到的结果，即最优的染色体，将所述染色体中每个初始发车时刻点对应的block整理成主站的所有发车时刻点及其覆盖次数、和副站的所有发车时刻点及其覆盖次数，整理后的主站或副站的发车时刻表中，发车时刻点的覆盖情况如图6所示，有一部分为(7:06 0)(7:09 1)(7:12 1)(7:15 1)(7:18 1)(7:20 1)(7:23 2)(7:261)，这里牵涉到的覆盖block有如下：26号(7:098:089:17...)、27号(7:128:119:14...)、28号(7:158:149:17...)、29号(7:188:179:20...)、1号(7:208:209:20...)、2号(7:238:239:32)、3号(7:238:239:32)。按时间顺序递增遍历发车时刻点，从第一个发车时刻点开始遍历，直到找到7:06的发车时刻点未被覆盖，首先对7:06之前的发车时刻点进行遍历，若在7:06之前没有找到覆盖超过一次的发车时刻点，则从7:06之后查找，发现7:23的时刻点覆盖了两次，分别被2号block与3号block覆盖，对于2号block，发车时刻点7:23与发车时刻表中上一个发车时刻点7:20之间的时间差3分钟小于发车时刻点7:23和2号block中上一个发车时刻点对应的trip的完成时间的差值；对于3号block，发车时刻点7:23与发车时刻表中上一个发车时刻点7:20之间的时间差3分钟也小于发车时刻点7:23和3号block中上一个发车时刻点对应的trip的完成时间的差值，此时，满足条件的、可调整的block有两个，如何选择呢？选择发车时刻点7:23和同一个block中上一个发车时刻点对应的trip的完成时间的差值最大的block作为待调整block，即2号block。

因此，将2号block由覆盖7:23变为覆盖7:20，相应覆盖7:20的1号block变为覆盖7:18，按时间顺序依次往前推，这样最后26号block由覆盖7:09变为了覆盖7:06，这样7:06和7:23两个发车时刻点的覆盖次数都变为了1。

有时需要对上述最优染色体进行多次如上调整，才能得到更好的结果，这时，可进行如上调整达到预先设定的调整次数即可。

由于采用依次调整策略，也就是说改变的每个发车时刻点与原来发车时刻点的差值就是相邻两个行程的发车时刻点之间的差值，由于这个差值不是太大，因此使得调整一般都是可行的。

另外，由于在遗传算法中将未覆盖和重复覆盖的次数作为设计惩罚函数主要考虑的因素，使得在最后的调整环节之后剩余的未覆盖和重复覆盖的时刻点会大量减少，从而使得调整后的公交车辆调度方案更具实用性。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明保护的范围之内。

Claims (10)

1.一种公交车辆调度方法，其特征在于，包括以下步骤：

S1、根据一预先确定的初始发车时刻点、已知的发车时刻表、司机休息时间、最大等待时间和最长工作时间，为一车辆确定包含至少一个发车时刻点的可用发车时间范围；

S2、在所述可用发车时间范围内分别任意选择一属于发车时刻表的发车时刻点，将选择的发车时刻点作为元素，生成所述初始发车时刻点对应车辆的一发车时刻点序列block；

返回执行步骤S2，直至选择完所有可用发车时间范围内、且属于发车时刻表的发车时刻点，生成由发车时刻点序列block构成的集合；

S3、返回执行步骤S1，为每个初始发车时刻点生成其对应车辆的发车时刻点序列block的集合；

S4、生成N条有限的以位为长度的染色体，所述染色体的每一位对应于一初始发车时刻点；

对所述N条染色体进行初始化，得到N条初始化后的染色体；所述初始化后的每条染色体中一初始发车时刻点唯一地对应一发车时刻点序列block；

S5、将当前的N条染色体作为第一N条染色体进行交叉处理，对交叉后的N条染色体进行变异处理，对变异后的N条染色体和所述第一N条染色体进行选择处理，得到选择处理后的N条新染色体，作为步骤S5的当前N条染色体；

S6、重复执行步骤S5直至达到预定的次数，得到最优染色体；

S7、对所述最优染色体按覆盖次数进行调整，使得未覆盖以及重复覆盖的发车时刻点减少；根据调整后每个初始发车时刻点及其对应的发车时刻点序列block对车辆进行调度。

2.根据权利要求1所述的方法，其特征在于，所述生成由发车时刻点序列block构成的集合，包括：

将一车辆从主站到副站的一趟、或从副站到主站的一趟作为一个短程trip，当初始发车时刻点的发车时间为t_i、运行当前trip的时间为t_r、司机休息时间为R、以及最大等待时间为K时，

A、将初始发车时刻点t_i作为的第一trip发车时间，令t_c＝t_i作为block序列中的第一元素，

B、将位于区间[t_c+t_r+R,t_c+t_r+R+K]内、且属于发车时刻表上的任一发车时刻点t′作为下一个trip所选择的发车时刻点，并将该t′作为所述block序列中的下一个元素；

C、当t′-t_i≤最长工作时间时，更新t_c＝t′，返回执行步骤B，否则，将当前block序列作为初始发车时刻点t_i对应车辆的一发车时刻点序列block；

D、返回执行步骤A，直至选择完所有位于区间[t_c+t_r+R,t_c+t_r+R+K]内、且属于发车时刻表上的任一发车时刻点t′，得到发车时刻点序列block的集合。

3.根据权利要求2所述的方法，其特征在于，步骤S4中，对所述染色体进行初始化的方法为：

L1、按时间顺序，选择所述染色体中属于主站的所有初始发车时刻点，对于选定的每一个初始发车时刻点，

若该初始发车时刻点还没有被发车时刻点序列block覆盖，则从该初始发车时刻点的block集合中随机选择一block作为该初始发车时刻点对应的block，记为该初始发车时刻点的覆盖block，并将所述覆盖block中包含的其它初始发车时刻点标记为已覆盖；

若该初始发车时刻点已覆盖，就选择下一个初始发车时刻点；

L2、选择所述染色体中属于副站的所有初始发车时刻点，执行步骤L1；

L3、当所述覆盖block的数量等于预先设定的覆盖block数量阈值R，或者，选择完染色体中的所有初始发车时刻点时，停止选择初始发车时刻点。

4.根据权利要求2所述的方法，其特征在于，步骤S4中，所述对所述染色体进行初始化的方法为：

从所述染色体中所有的初始发车时刻点中随机选择R个初始发车时刻点，对于其中的任一初始发车时刻点，从包含有该初始发车时刻点的block集合中随机选择一block作为该初始发车时刻点对应的block，记为该初始发车时刻点的覆盖block，R为覆盖block数量阈值。

5.根据权利要求3或4所述的方法，其特征在于，所述覆盖block数量阈值R等于发生时刻表中发车时刻点个数除以一个block所包含的发车时刻点个数Y，Y等于最长工作时间除以车辆从主站驶往副站一趟的时间长度，或者Y等于最长工作时间除以车辆从副站驶往主站一趟的时间长度。

6.根据权利要求5所述的方法，其特征在于，步骤S5中，所述对当前的N条染色体进行交叉处理，包括：

对当前的N条染色体随机配对，对于配对后得到的对染色体中的每一对染色体，互换这对染色体中部分相同位的初始发车时刻点所对应的发车时刻点序列block。

7.根据权利要求6所述的方法，其特征在于，步骤S5中，所述对交叉后的N条染色体进行变异处理，包括：

对所述N条染色体中的任一染色体，生成该染色体的随机数z，当z小于预设的变异阈值时，按该染色体中初始发车时刻点时间递增的顺序，选择每一个初始发车时刻点，

对于当前选择的初始发车时刻点，生成所述初始发车时刻点的第一随机数p，当p小于或等于第一阈值时，生成所述初始发车时刻点的第二随机数q，

当q小于第二阈值时，设定所述初始发车时刻点没有block覆盖，否则，将所述初始发车时刻点的block变异为该初始发车时刻点对应车辆的block集合中的另一block，判断染色体中是否还有下一个初始发车时刻点，是，选择下一个初始发车时刻点，否，变异结束。

8.根据权利要求7所述的方法，其特征在于，步骤S5中，所述对变异后的N条染色体和所述第一N条染色体进行选择处理，得到选择处理后的N条新染色体，作为步骤S5的当前N条染色体，包括：

计算每条染色体的惩罚函数值，获取2N条染色体的惩罚函数值之和F，得到每一染色体的选择概率等于其惩罚函数值除以F，设定每一染色体的累计概率为该染色体的选择概率与前一染色体的累计概率之和，使得每个染色体对应一个随机数区间为：[前一染色体的累计概率，当前染色体的累计概率]；

生成N个随机数，若其中任一随机数被包含在任一随机数区间中，则选取所述随机数区间对应的染色体，得到选择处理后的N条新染色体，作为步骤S5的当前N条染色体；

步骤S6中，所述重复执行步骤S5达到预定的次数，得到最优染色体，包括：

重复执行步骤S5达到预定的次数后，得到N条染色体，将所述N条染色体中惩罚函数值最大的染色体选定为最优染色体。

9.根据权利要求8所述的方法，其特征在于，所述惩罚函数值为主站和副站的惩罚函数值之和，其中，主站或副站的惩罚函数值X为

$X=I-P\underset{s=1}{\overset{T}{\mathrm{\Σ}}}|\underset{i=1}{\overset{t_s}{\mathrm{\Σ}}}{v}_{\mathrm{si}}-1|-Q\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{z}_i$

其中，I、P、Q分别是预先设定的正整数，T表示与主站或副站发车时刻表对应的时间区间的总数，v_si表示时间区间S的第i个发车时刻点被覆盖的次数，n表示发车时刻点总数，z_i表示发车时刻点是否被覆盖，z_i=1表示未被覆盖，z_i=0表示已被覆盖。

10.根据权利要求8所述的方法，其特征在于，步骤S7中，对所述最优染色体按覆盖次数进行调整，使得未覆盖以及重复覆盖的发车时刻点减少，包括，

以主站和副站为类别，将所述染色体中各个初始发车时刻点对应的发车时刻点序列block整理为按时刻点递增顺序排列的站点发车时刻表，所述站点发车时刻表中包括各个发车时刻点、及其对应的覆盖次数和覆盖block，

对于站点发车时刻表，分别执行

步骤G1：按排列顺序遍历发车时刻点，当遍历到覆盖次数为0的发车时刻点j`时，则

从发车时刻点j`开始，按照发车时刻点递减的顺序在发车时刻表中选择发车时刻点k，

若发车时刻点k的覆盖次数等于1、且发车时刻点k与发车时刻点k+1之间的时间差小于发车时刻点k对应的trip的完成时间和同一个block中下一个发车时刻点的时间的差值，则继续选择下一个发车时刻点；

若发车时刻点k的覆盖次数大于1、发车时刻点k与发车时刻点k+1之间的时间差小于发车时刻点k对应的trip的完成时间和同一个block中下一个发车时刻点的时间的差值，则进行如下调整：

GE1、将发车时刻表中的发车时刻点序列（k、k+1、…、j`-1、j`）作为待调整发车时刻点序列；选择覆盖发车时刻点k的所有block中、发车时刻点k对应的trip的完成时间和同一个block中下一个发车时刻点的时间的差值最大的block作为待调整block；

GE2、将所述待调整block中的发车时刻点k调整为发车时刻表中的发车时刻点k+1；

GE3、将覆盖发车时刻点k+1的、且未曾调整的block中的发车时刻点k+1调整为发车时刻点k+2；对于待调整发车时刻点序列（k、k+1、…、j`-1、j`）中除j`外的每一个发车时刻点，均如此调整，直至将覆盖发车时刻点j`-1的、且未曾调整的block中的发车时刻点j`-1调整为发车时刻点j`为止；

更新发车时刻表中发车时刻点j`的覆盖次数为1，发车时刻点k的覆盖次数减少1次；

如果从发车时刻点j`开始，按照发车时刻点递减的顺序在发车时刻表中未能选择出发车时刻点，则

从发车时刻点j`开始，按照发车时刻点递增的顺序在发车时刻表中选择发车时刻点k，

若发车时刻点k的覆盖次数等于1、且发车时刻点k与发车时刻点k-1之间的时间差小于发车时刻点k和同一个block中上一个发车时刻点对应的trip的完成时间的差值，继续选择下一个发车时刻点；

若发车时刻点k的覆盖次数大于1、且发车时刻点k与发车时刻点k-1之间的时间差小于发车时刻点k和同一个block中上一个发车时刻点对应的trip的完成时间的差值，进行如下调整：

GF1、将发车时刻表中的发车时刻点序列（j`、j`+1、…、k-1、k）作为待调整发车时刻点序列；选择覆盖发车时刻点k的所有block中、发车时刻点k和同一个block中上一个发车时刻点对应的trip的完成时间的差值最大的block作为待调整block；

GF2、将所述待调整block中的发车时刻点k调整为发车时刻表中的发车时刻点k-1；

GF3、将覆盖发车时刻点k-1的、且未曾调整的block中的发车时刻点k-1调整为发车时刻点k-2；对于待调整发车时刻点序列（j`、j`+1、…、k-1、k）中除j`外的每一个发车时刻点，均如此调整，直至将覆盖发车时刻点j`+1的、且未曾调整的block中的发车时刻点j`+1调整为发车时刻点j`为止；

更新发车时刻表中发车时刻点j`的覆盖次数为1，发车时刻点k的覆盖次数减少1次；

步骤G2：重复执行步骤G1，直至达到预定的次数，得到调整后的包含有各个发车时刻点、及其对应的覆盖次数和覆盖block的站点发车时刻表。