(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210842568.2 (22)申请日 2022.07.18 (71)申请人 东南大学 地址 210096 江苏省南京市江宁区东 南大 学路2号 (72)发明人 刘志远　张凯　刘攀　陈新元　 张奇　杨俊宴　 (74)专利代理 机构 南京经纬专利商标代理有限 公司 32200 专利代理师 陈月菊 (51)Int.Cl. G06Q 10/06(2012.01) G06Q 10/04(2012.01) G06Q 30/02(2012.01) G06Q 50/26(2012.01)G08G 1/01(2006.01) G06F 9/50(2006.01) (54)发明名称 基于两阶段并行的组合模式划分与交通分 配方法 (57)摘要 本发明公开了一种基于两阶段并行的组合 模式划分与交通 分配方法， 包括如下步骤： S1、 设 置集群并行、 网络拓扑和需求基本参数； S2、 初始 化路径集； S3、 增广路径集合； S4、 模式划分与交 通流量分配； S5、 算法停止 条件的判断。 本发明在 路径流量分配技术的基础上， 提出了基于计算集 群的两阶段并行概念， 第一个并行阶段是基于多 处理器的， 第二个并行阶段是基于多计算机的， 设计了大规模城市交通组合模式划分与交通并 行分配技术， 在大规模交通网络中的试验结果表 明， 两阶段并行计算方法具有更 快的收敛速度。 权利要求书3页 说明书13页 附图3页 CN 115239116 A 2022.10.25 CN 115239116 A 1.一种基于 两阶段并行的组合模式划分与交通分配方法， 其特 征在于， 包括如下步骤： S1、 设置集群并行、 网络 拓扑和需求基本参数； S2、 初始化路径集； S3、 增广路径集 合； S4、 模式划分与交通 流量分配； S5、 算法停止条件的判断， 如果车流量收敛， 根据更新后路径上的车流量确定城市交通 网络流量， 否则返回S3， 并将更新后的路段费用从主节点广播到各个工作节点。 2.如权利要求1所述的两阶段并行的组合模式划分与交通分配方法， 其特征在于， S1的 具体步骤为： 在计算机集群设置两阶段并行， 设置T台计算机， 并且每 台计算机都有M个处理器； 设置 一台主计算机、 T ‑1台工作计算机和T* M‑1个工作处 理器； 其中主节点负责计算全网路径流 量调整， T ‑1台工作节点负责 OD对之间的最短路计算； 在输入城市道路交通网络基本参数时， 输入私家车和地铁交通出行需求分布情况； 其 中， 交通网络基本参数包括各路段自由流行驶时间、 路段上的交通流承载能力、 路段阻抗函 数和交通分配精度阈值； 交通出行需求分布情况包括 起讫点和起讫点间的交通 量。 3.如权利要求2所述的两阶段并行的组合模式划分与交通分配方法， 其特征在于， S1 中， 在计算机集群设置两阶段并行， 并给每个节 点输入城市道路交通网络基本参数， 具体过 程包括： S101、 在计算机集群设置 两阶段并行： T台计算节点， 每个节点上有M个线程； 每个起点的索引为o， 如果o％(T ×M‑1)等于一个 线程ith的索引， 那么基于该o的最短路树有 线程ith计算； S102、 输入目标函数 方程和约束条件： 约束条件： 式中， 目标函数(1)由两项组成， 分别反映了拥塞效应和OD需求对网络服务水平的弹 性； 式(2)为流量守恒条件； 方程式(3) ‑(4)为对决策变量， 即私家车路径 流和地铁线路流的 非负性约束； 其中， A表示路段的集合， a∈A； W表示OD对的集合， od∈W； Pod表示OD对od间的路 径集合， p∈Pod； 表示OD对od间路径k上的流量； v ′a和v″a分别表示非最短路k和最短路 上的路段流量； ta(v)表示路段a的阻抗函数； 表示路段 ‑路径的关系矩阵， 当路段a在OD 对od的第k 条路径上时， 取值为1， 否则， 取值为0； 表示OD对od间的出行需求 上限， qod是私 家车模式的需求， 是地铁模式的需求， 其中 是地铁模式下OD对 关联权　利　要　求　书 1/3 页 2 CN 115239116 A 2的逆需求 函数； S103、 设置私家车路段阻抗函数ta(v)和地铁线路的运行成本 其中， t0是自由 流行驶时间， Ca为路段a上的交通流承载能力， α和β 为 预设参数， va表示路段a的流量， 具体计 算公式如下： 地铁线路的运行成本可以用二进制的l ogit函数表示 为： 式中 为OD对之间的地铁模式需求； and 之差表示OD对之间的流量需求， 由OD对 的路径流之和决定； 离散参数γ为常数， 反映了需求对差旅成本的敏感性； 为 为OD对之 间的地铁模式固定出行时间， 是固定 的， 反映了地铁运行时间； 为常数， 表示地铁模式 下OD对之间的步行时间， 即乘客 从出发地到地铁站的时间和乘客从地铁站到目的地的时间 之和。 4.根据权利要求2所述的两阶段并行的组合模式划分与交通分配方法， 其特征在于， S2 的具体步骤： 在T ‑1台工作节点上， 使用两阶段并行技术并行计算每个起点的最短路树， 以 根据最短路树确 定各个OD对之间的最短路， 对每个OD对建立一个路径集合， 将OD对之间的 最短路作为初始路径加入 该OD对对应的路径集合， 将OD对之间的出行需求加载到该OD对对 应的初始路径上； 在主节点上， 在私家车模式和地铁模式之间调节车流量， 将路径上的车流 量叠加到道路网络中的路段上， 以得到路段流量， 并根据更新后的路段流量更新路段出行 时间， 之后将更新后的路段 出行时间广播到T ‑1台工作节点。 5.根据权利要求2所述的两阶段并行的组合模式划分与交通分配方法， 其特征在于， S3 的具体步骤为： 在 T‑1台工作节 点上， 并行初始化路径 集合。 对道路交通网络上的每个 OD对， 基于更新后的路段出行时间， 使用两阶段并行技术更新每个起点的最短路树； 将每个OD对 的最短路与OD对的路径集合中的所有路径进行对比， 如果现有的路径集合中没有 该条最短 路， 就将该条最短路加入路径集合中， 并将该路径上的路径 流量暂时设置为0， 然后将T ‑1台 工作节点计算的OD之间最 新的最短路结果收集到主节点上。 6.根据权利要求2所述的两阶段并行的组合模式划分与交通分配方法， 其特征在于， S4 的具体步骤为： 在主节点上应用组合块坐标下降和自适应梯度算法调整路径流量， 对交通 网络上的每个OD对， 保持路径集合不变， 利用组合块坐标下降和自适应梯度算法以迭代形 式比较私家车最短路径成本 与地铁线路成本的运行时间 在第一种情况下， 计算目标函数式的二阶， 然后更新私家车路径流和地铁线路流； 在第二种 情况下， 计算目标函数式的二阶， 然后更新私家车路径流和地铁线路流； 从 而在私家车模式和地铁模式之间调节车流量； 如果车流量收敛， 根据更新后路径上 的车流 量确定城市交通网络流量， 否则返回S 3， 并将更新后的路段费用从主节 点广播到T ‑1台工作 节点。权　利　要　求　书 2/3 页 3 CN 115239116 A 3