(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211039159.5 (22)申请日 2022.08.29 (71)申请人 深圳市大 数据研究院 地址 518172 广东省深圳市龙岗区龙城街 道龙翔大道 2001号道远楼 225室 (72)发明人 张莲民　陈虹桥　姚子靖　王冬昊　 李润杰　张婧霞　罗敏　 (74)专利代理 机构 广州嘉权专利商标事务所有 限公司 4 4205 专利代理师 周翀 (51)Int.Cl. G06Q 10/06(2012.01) G06Q 50/26(2012.01) G06N 3/12(2006.01) (54)发明名称 公交车的运行调度方法、 调度系统及 存储介 质 (57)摘要 本发明公开了一种公交车的运行调度方法、 调度系统及存储介质， 方法包括： 获取每一原始 路线的运行数据； 根据运行数据， 确定预设的多 个标准时间段内两个终点站之间的公交标准数 量； 通过贪婪算法对各个标准时间段中对应的公 交标准数量进行调度规划， 得到多个初始运行 图， 根据初始运行图生成初始时刻表； 初始化初 始时刻表中各个初始运行图的公交配置数量， 并 以公交配置数量与公交标准数量之间的差值收 敛为条件， 通过遗传算法对初始时刻表进行遗传 迭代后得到目标时刻表。 本发明通过贪婪算法以 公交标准数量为导向生成初始时刻 表， 再通过遗 传算法得到目标时刻表， 从而有效提高公交车的 利用率。 权利要求书3页 说明书10页 附图6页 CN 115423285 A 2022.12.02 CN 115423285 A 1.公交车的运行调度方法， 其特 征在于， 包括： 获取每一原 始路线的运行 数据； 根据所述 运行数据， 确定预设的多个标准时间段内两个终点站之间的公交标准数量； 通过贪婪算法对各个所述标准 时间段中对应的所述公交标准数量进行调度规划， 得到 多个初始 运行图， 根据所述初始 运行图生成初始时刻表， 其中， 每个所述初始 运行图中的相 邻两条所述原始路线之间设有一个重合的所述终点站； 初始化所述初始时刻表中各个所述初始运行图的公交配置数量， 并以所述公交配置数 量与所述 公交标准数量之 间的差值收敛为条件， 通过遗传算法对所述初始时刻表进行遗传 迭代后得到目标时刻表。 2.根据权利要求1所述的公交车的运行调度方法， 其特征在于， 所述运行数据包括终到 时间、 始发站和终到站； 所述通过贪婪算法对各个所述标准 时间段中对应的所述公交标准数量进行调度规划， 得到多个初始运行图， 包括： 以一条未被规划的所述原始路线的始发站和终到站分别作为所述初始运行图的第一 站和第二站； 以所述第二站作为基准站， 在所述基准站对应的所述终到时间所在的所述标准时间段 中， 匹配所述公交标准数量最多且未被规划的所述原始路线的终到站作为所述初始 运行图 的第三站； 以所述第三站作为所述基准站对所述初始运行图继续进行规划， 直至所述初始运行图 的最后一站与未被规划的所述原始路线的始发站不匹配或所述初始运行图的规划时间超 过运行时间， 得到规划好的所述初始运行图； 对所有未被规划的所述原 始路线进行规划， 得到多个规划好的所述初始运行图。 3.根据权利要求2所述的公交车的运行调度方法， 其特征在于， 在所述得到规划好的所 述初始运行图之前， 还 包括： 判断所述初始运行图是否满足预设的约束条件； 当不满足约束条件则重新 规划所述初始运行图。 4.根据权利要求3所述的公交车的运行调度方法， 其特 征在于， 所述约束条件 包括： 其中， τ(i,j,t)表示公交车从终点站i出发 在标准时间段t内到达终点站j， 为1时表示公交车k以终点站j作为终到站且在标准时间权　利　要　求　书 1/3 页 2 CN 115423285 A 2段t内以终点站i为始发站， 为0时表示其他情况， 为1时表示公交车k在时间段t内停 在了终点站i， 为0时表示其他情况， sijt表示在标准时间段t内从终点站i到终点站j的公 交车的缺少数量， oijt表示在标准时间段t内从终点站i到终点站j的公交车的多余数量， fijt 表示公交标准数量， T表示标准时间段集 合， K表示公交车集 合。 5.根据权利要求1所述的公交车的运行调度方法， 其特征在于， 所述运行数据还包括不 同时间段对公交车数量的最大需求值和最小需求值， 所述公交标准数量通过取对应标准时 间段中的所述 最大需求 量和所述 最小需求 量之和的平均值得到 。 6.根据权利要求5所述的公交车的运行调度方法， 其特征在于， 所述以所述公交配置数 量与所述 公交标准数量之 间的差值收敛为条件， 通过遗传算法对所述初始时刻表进行遗传 迭代后得到目标时刻表， 包括： 以所述目标函数为收敛条件， 通过遗传算法根据 所述初始时刻表中的所述初始运行图 进行遗传迭代， 得到目标时刻表， 其中， 所述目标函数为 表示标准时间段t内从从终点站i到终点站j缺少公交车的惩罚系数， 表示标准时间 段t内从从终点站 i到终点站j多余公交车的惩罚系数， sijt表示在标准时间段t内从终点站i 到终点站j的公交车的缺少数量， oijt表示在标准时间段t 内从终点站i到终点站j的公交车 的多余数量， T表示标准时间段集 合。 7.根据权利要求6所述的公交车的运行调度方法， 其特征在于， 所述通过遗传算法根据 所述初始时刻表中的所述初始运行图进行遗传迭代， 得到目标时刻表， 包括： 以所述初始时刻表为输入时刻表； 将所述输入时刻表中的多个所述初始运行图划分为多对运行图组； 将各个所述 运行图组进行变换 得到对应的多个 变换图组； 通过所述局部搜索算法对所述运行图组和所述变换图组配置所述公交配置数量， 并根 据所述目标函数匹配得到 输出时刻表； 以所述输出时刻表遗传迭代为所述输入时刻表， 得到所述目标函数收敛为最小值 时对 应的输出时刻表为所述目标时刻表。 8.根据权利要求7所述的公交车的运行调度方法， 其特征在于， 所述将各个所述运行图 组进行变换 得到对应的多个 变换图组， 包括： 通过插入算子、 消去算子、 交换算子或移动算子对各个所述运行图组进行变换， 得到对 应的多个 变换图组。 9.公交车的运行调度系统， 其特 征在于， 包括： 数据获取模块， 获取每一原 始路线的运行 数据； 预处理模块， 根据所述运行数据， 确定预设的多个标准时间段内两个终点站之间的公 交标准数量； 初始表生成模块， 通过贪婪算法对各个所述标准 时间段中的对应所述公交标准数量进 行调度规划， 得到多个初始运行图， 根据所述初始运行图生成初始时刻表， 其中， 每个所述 初始运行图中的相邻两条 所述原始路线之间设有一个重合的所述终点站； 优化输出模块， 初始化所述初始时刻表中各个所述初始运行图的公交配置数量， 并以 所述公交配置数量与所述 公交标准数量之 间的差值收敛为条件， 通过遗传算法对所述初始权　利　要　求　书 2/3 页 3 CN 115423285 A 3