(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202210942738.4 (22)申请日 2022.08.08 (65)同一申请的已公布的文献号 申请公布号 CN 115017667 A (43)申请公布日 2022.09.06 (73)专利权人 西南交通大 学 地址 610031 四川省成 都市二环路北一段 111号 (72)发明人 杨渝华　倪少权　 (74)专利代理 机构 北京集智东方知识产权代理 有限公司 1 1578 专利代理师 刘林　陈攀 (51)Int.Cl. G06F 30/18(2020.01) G06F 30/20(2020.01)G06Q 10/06(2012.01) G06Q 10/10(2012.01) G06Q 50/26(2012.01) G06F 111/04(2020.01) (56)对比文件 CN 111353639 A,2020.0 6.30 CN 114662778 A,202 2.06.24 审查员 刘洛 (54)发明名称 列车运行图与车底运用计划协同优化方法 及装置 (57)摘要 本发明提供了列车运行图与车底运用计划 协同优化方法及装置， 所述方法包括： 获取城市 轨道交通线路参数、 城市轨道交通线路拓扑结构 和城市轨道交通历史客流信息； 对城市轨道交通 线路拓扑结构进行重构； 根据城市轨道交通历史 客流信息和重构后的城市轨道交通线路拓扑结 构计算客流需求信息； 根据客流需求信息， 建立 列车运行图与车底运用计划协同优化模型； 采用 混合整数规划算法和启发式算法求解列车运行 图与车底 运用计划协同优化模型， 得到协同优化 后的列车运行图与车底运用计划。 本发明提出了 与客流需求相协调的列车运行图及车底运用计 划协同编制优化方法， 通过此方法能够提高运营 企业的运输服 务质量及客 流吸引力。 权利要求书5页 说明书13页 附图3页 CN 115017667 B 2022.11.29 CN 115017667 B 1.列车运行图与车底运用计划协同优化方法， 其特 征在于， 包括： 获取城市轨道 交通线路参数、 城市轨道 交通线路拓扑结构和城市轨道 交通历史客流信 息； 根据所述城市轨道交通线路参数， 对所述城市轨道交通线路拓扑结构进行重构， 得到 重构后的城市轨道交通线路拓扑 结构； 根据所述城市轨道交通历史客流信息和所述重构后的城市轨道交通线路拓扑结构计 算客流需求信息； 根据所述 客流需求信息， 建立列车运行图与车底运用计划协同优化模型； 采用混合整数规划算法和启发式算法求解所述列车运行图与车底运用计划协同优化 模型， 得到协同优化后的列车运行图与车底运用计划； 其中， 根据所述城市轨道 交通历史客流信 息和所述重构后的城市轨道 交通线路拓扑结 构计算客流需求信息， 包括： 根据乘客进站站点信 息和出站站点信 息， 利用所述重构后的城市轨道 交通线路拓扑结 构， 计算得到城市轨道交通线路拓扑重构后的进站站点信息和出站站点信息， 所述城市轨 道交通历史客 流信息中包括乘客进站 站点信息、 进站时间信息和出站 站点信息； 根据所述乘客进站时间信 息、 城市轨道 交通线路拓扑重构后的进站站点信 息和城市轨 道交通线路拓扑重构后的出站站 点信息对乘客进 行分组聚合， 其中， 将具有相同进站站 点、 进站时间和出站站点的乘客聚合在一起， 形成不同的乘客组， 统计每个所述乘客组的乘客 总人数， 得到不同的人数统计结果， 利用全部的所述人数统计结果形成随时间变化的客流 OD矩阵； 其中， 采用混合整数规划算法和启发式算法求解所述列 车运行图与 车底运用计划 协同 优化模型， 得到协同优化后的列车运行图与车底运用计划， 包括： 获取所述启发式算法的参数， 所述参数包括总迭代优化最大次数itstop， 总迭代优化最 长时间Cstop， 单次循环最长时间cstop； 计算投入使用列车车底数量的取值可行域， 根据投入使用列车车底数量的取值可行 域， 初选应投入使用的列车 车底运用数量、 乘客的等待时间、 列车运行图和车底运用计划； 构造以减少总的乘客等待时间为导向的邻域并求解： 对第 一结果中包含的各组所述乘 客的等待时间进行排序， 并剔除无需等待的乘客组， 根据剩余的乘客组所涉及的变量Dis、 ytodi、 Wtodi构造邻域， 随后在单次循环最长 时间cstop内借助整数规划方法进行优化， 得到优 化后的列车车底运用数量、 优化后的乘客的等待时间、 优化后的列车运行图和优化后的车 底运用计划； 构造以均衡各组乘客等待时间为导向的邻域并求解： 对各组所述优化后的乘客的等待 时间进行排序， 对等待时间为最大值的乘客组所涉及的变量Dis、 ytodi、 Wtodi构造邻域， 随后 在单次循环最长时间cstop内运用整数规划方法进行优化， 得到新的列车运行图和新的车底 运用计划； 对模型进行全局优化： 将所述新的列车运行图和所述新的车底运用计划作为所述列 车 运行图与车底运用计划协同优化模型求解的初始启发信息， 在单次循环最长时间cstop内运 用整数规划方法进行优化， 根据优化原则对所述新的列车运行图和所述新的车底运用计划 进行更新；权　利　要　求　书 1/5 页 2 CN 115017667 B 2最大循环次数判断并输 出最优解： 分析是否达到总迭代优 化最大次数itstop， 若未达到， 则重复构 造以减少总的乘客等待时间为导向的邻域并求解、 构 造以均衡各组乘客等待时间 为导向的邻域并求解、 对模型进行全局优化和 最大循环次数判断并输出最优解的步骤； 若 达到， 则输出最优解， 获取最佳列车运行图和车底运用计划； 根据所述城市轨道交通线路参数， 对所述城市轨道交通线路拓扑结构进行重构， 得到 重构后的城市轨道交通线路拓扑 结构， 包括： 结合所述城市轨道交通线路参数， 对所述城市轨道交通线路拓扑结构进行调整， 调整 后的城市轨道交通线路拓扑 结构中包 含N个节点， 每 个所述节点代 表一个物理站点； 考虑到获取到的城市轨道 交通线路拓扑结构有可能不完整， 因此利用城市轨道 交通线 路参数对城市轨道交通线路拓扑结构进行调整完善， 保证城市轨道交通线路拓扑结构的完 整性； 若调整后若城市轨道交通线路上有Stot个站点， 则调整后的城市轨道交通线路拓扑结 构表示为So＝{1,2,…,Stot}， 其中， Stot相当于N； 将列车对应的车辆段作为一个虚拟站点， 根据列车运行方向的站点分布， 结合所述虚 拟站点， 重构城市轨道交通线路拓扑结构， 重构后的城市轨道交通线路拓扑结构中包含2 N+ 1个节点， 第2N+1个节点代 表所述虚拟站点， N 为正整数； 其中， 计算投入使用列车车底数量的取值可行域， 根据投入使用列车车底数量的取值 可行域， 初选应投入使用的列车车底 运用数量、 乘客的等待时间、 列车运行图和车底运用计 划， 包括： 列车运营时间范围[0,Tn]、 列车区间运行时间的合理范围 列车停站时间 的合理范围 列车安全运行间隔时间的合理范围[Hmin,Hmax]， 计算各列车在 各站点的到 达时刻可 行域[DLis,DUis]； 根据列车在各站点的到达时刻可行域[DLis,DUis]， 结合列车最小折返间隔时间 和 所述车底运用编制参数， 计算列车 车底可用数量的取值可 行域[RSL,RSU]； 根据最优导向原则， 使用列车车底可用数量的取值可行域[RSL,RSU]内的取值， 随机生 成规格化列车运行图及相应的车底运用计划， 并记录目标函数Zopt的取值， 随后以目标函数 Zopt中的Z1即乘客在站台总等待时间最小化为参考标准构建邻域 并获取邻域搜索后的目标 函数； 通过在列车车底数量可行范围[RSL,RSU]内循环取值， 遍历列车车底可用数量的取值 可行域[RSL,RSU]中列车车底运用数量取值， 获取不同列车车底数量对应的邻域搜索后的 目标函数， 将全部的所述邻域搜索后的目标函数按照优劣程度进行排序筛选， 得出第一结 果， 所述第一结果包括最佳邻域搜索后的目标函数对应的列车车底运用数量、 乘客的等待 时间、 列车运行图和车底运用计划； 将所述第一结果作为初选应投入使用的列车车底运用 数量、 乘客的等待时间、 列车运行图和车底运用计划； 其中， Dis表示一次列车 行程i在站点s的到 达时间； ytodi表示该组乘客是否通过列车 行程i完成出行； Wtodi表示该组乘客选择列车 行程i出行时的在车站等待时间。 2.根据权利要求1所述的列 车运行图与车底运用计划 协同优化方法， 其特征在于， 根据 所述客流需求信息， 建立列车运行图与车底运用计划协同优化模型， 包括：权　利　要　求　书 2/5 页 3 CN 115017667 B 3