基于块坐标下降的大规模城市交通网络流量监测方法转让专利
申请号 : CN202011350776.8
文献号 : CN112562325B
文献日 : 2021-11-02
发明人 : 刘志远 , 陈新元 , 张凯 , 王泽文 , 张奇
申请人 : 东南大学
摘要 :
本发明公开了一种基于块坐标下降的大规模城市交通网络流量监测方法，其可以收集城市道路交通网络上的运行参数；并行计算道路交通网络上的最短路建立初始路径集合；更新路段身的车流量和出行时间；并行计算最短路更新路径集合；利用块坐标方法更新路径流量；计算精度指标，判断收敛状态。本发明在路径流量分配技术的基础上，利用坐标下降的概念，设计了大规模城市交通网络流量并行分配技术，在大规模交通网络中的试验结果表明，块坐标并行计算方法具体更高的收敛速度。
权利要求 :
1.一种基于块坐标下降的大规模城市交通网络流量监测方法，其特征在于，包括如下步骤：
S1，获取设定城市内道路交通网络上的运行参数，设置交通流量分配精度阈值M，以及计算过程中的参数FreC；所述运行参数包括路段自由流行驶时间，路段上的交通流承载能力，路段阻抗函数，道路交通网络上的机动车出行需求分布情况；所述机动车出行需求分布情况包括机动车出行的起点、机动车出行的终点、以及OD对之间的出行需求；所述OD对包括起点和该起点对应的终点，出行需求指从出行起点O到出行终点D的机动车数量；
S2，并行计算每个起点的最短路树，根据最短路树确定各个OD对之间的最短路，对每个OD对建立一个路径集合，将OD对之间的最短路作为初始路径加入该OD对对应的路径集合，将OD对之间的出行需求加载到该OD对对应的初始路径上；将路径上的车流量叠加到道路网络中的路段上，以得到路段流量，并根据更新后的路段流量更新路段出行时间；
S3，对道路交通网络上的每个OD对，基于更新后的路段出行时间并行更新每个起点的最短路树；将每个OD对的最短路与OD对的路径集合中的所有路径进行对比，如果现有的路径集合中没有该条最短路，就将该条最短路加入路径集合中，并将该路径上的路径流量暂时设置为0；
S4，对交通网络上的每个OD对，保持路径集合不变，利用迭代算法更新路径上的车流量，如果车流量收敛，根据更新后路径上的车流量确定城市交通网络流量，否则返回S3；
对交通网络上的每个OD对，保持路径集合不变，利用迭代算法更新路径上的车流量包括：
S4.1，设置迭代次数i的上限阈值，用数值MaxI表示，一旦迭代次数i大于等于MaxI，则当前步骤停止，计算道路交通网络的精度误差；
S4.2，判断i是否是FreC的整数倍，如果i是FreC的整数倍，对道路交通网络上的OD对的路径集合W分割成若干子集合，否则，对一个缩小的OD对的路径集合 分割成若干子集合，建立一个空的受限制的OD集合 用来存放OD对；将 分割成若干子集合Wi，下标i表示第i个子集合；
S4.3，选择一个分割后的子集合Wi，并行地计算子集合中OD对的精度指标，如果这个OD对的精度不足，则需要利用下降算法调整这些OD对中的路径流量，同时将这些精度不足的OD对加入一个新的受限制的OD集合 如果这个OD对的精度足够，则在当前过程中不进行路径流量调整；其中OD对的相对误差rgod为：od
式中 表示OD对之间的最短出行时间，q 表示OD对之间的出行需求，va表示路段流量，od
ta(va)表示路段出行时间，A 表示OD对中所有路径经过的路段集合；精度不足指相应精度指标大于精度阈值M，精度足够指相应精度指标小于或等精度阈值M；
S4.4，选择下一个子集合Wi，重复步骤S4.3，直到所有子集合都被访问；
S4.5，如果受限制OD对集合 是空集，则不再进行迭代，跳出步骤S4；如果当前迭代次数超过一定的阈值MaxI，则不再进行迭代，以当前各个子集合包括的路径流量确定各个路径的车流量，跳出步骤S4；否则，令i＝i+1， 并返回S4.1。
2.根据权利要求1所述的基于块坐标下降的大规模城市交通网络流量监测方法，其特征在于，步骤S4.2中，对道路交通网络上的OD对的路径集合W分割成若干子集合包括：S4.2.1：设定并行度ParaL，并行度ParaL表示同时计算的任务数量；
S4.2.2：根据并行度ParaL，将集合W分成 个块，令 j表示W中OD对的索引，对于块n∈{1,…,G}，剩余的OD对被划入第G+1个块，将得到的各个块确定为各个子集合；其中，符号 表示向下取整，j与n具有如下关系：j＝n+k×G,k∈￥,j∈Block n。
3.根据权利要求1所述的基于块坐标下降的大规模城市交通网络流量监测方法，其特征在于，步骤S4.3中，如果这个OD对的精度不足，则需要利用下降算法调整这些OD对中的路径流量，同时将这些精度不足的OD对加入一个新的受限制的OD集合 包括：S4.3.1：计算OD对之间每条路径的路径出行时间；
S4.3.2：计算OD对之间最短路径出行时间；
S4.3.3：计算OD对的精度误差rgod；
S4.3.4：如果OD对的精度误差rgod大于精度阈值M，使用优化方法调整OD对之间的路径流量；将该OD对加入OD对集合
S4.3.4：对子集合Wi中的所有OD对完成流量调整后，将更新后的路径流量重新叠加到路段上，更新路段流量；
S4.3.5：对流量受到调整的路段更新该路段的出行时间；
S4.3.6：回到步骤S4.3.1，更新下一个子集合中的路径流量，并扩增OD对集合
4.根据权利要求1所述的基于块坐标下降的大规模城市交通网络流量监测方法，其特征在于，还包括：
S5，对交通网络上的所有OD对，计算整个交通网络的精度误差rg，如果精度误差rg大于精度阈值M，表明城市路网上的出行需求到达收敛状态，符合出行者的出行选择行为，结束计算；否则，更新M，令M＝rg/2，返回执行步骤S3；精度误差rg为：od
其中 表示OD对之间的最小出行时间，q 表示OD对之间的出行需求，va表示路段流量，ta(va)表示路段出行时间，A表示交通网络上路段的集合；rg越接近0，网络交通流量越接近收敛状态。
5.根据权利要求1所述的基于块坐标下降的大规模城市交通网络流量监测方法，其特征在于，步骤S2，S3和S5中的最短路树计算均采用并行计算的方法进行求解，在交通网络中，并行地对所有起点，采用单源最短路算法求解单个起点到网络上其他节点之间的最短路树。
说明书 :
基于块坐标下降的大规模城市交通网络流量监测方法
技术领域
[0001] 本发明涉及交通控制技术领域，尤其涉及一种基于块坐标下降的大规模城市交通网络流量监测方法。
背景技术
[0002] 城市道路交通网络的流量分配问题是交通规划，管理与控制领域的关键性问题。在交通工程领域具有基础性作用，是科学合理评估交通治理政策，规划方案，管理措施的重
要工具。交通分配问题的核心是快速求解。在过去的几十年里，开发高效的交通分配技术一
直是交通工程师和科学家关注的焦点，不断扩张的城市交通网络和对高精度解的需要激励
研究人员开发更高效快捷的交通网络流量监测技术，以用于相应交通网络流量分配。
Beckmann于1956年将提出了一个与交通网络流量分配问题等价的数学模型，为开发高效交
通网络流量分配技术提供了一个良好的基础。自此之后，基于Beckmann模型，很多交通网络
流量分配技术被开发出来。这些技术可以被分成三种类型，即(1)基于路段的交通网络流量
分配技术；(2)基于路径的交通网络流量分配技术；(3)基于起点的交通网络流量分配技术。
要工具。交通分配问题的核心是快速求解。在过去的几十年里，开发高效的交通分配技术一
直是交通工程师和科学家关注的焦点，不断扩张的城市交通网络和对高精度解的需要激励
研究人员开发更高效快捷的交通网络流量监测技术，以用于相应交通网络流量分配。
Beckmann于1956年将提出了一个与交通网络流量分配问题等价的数学模型，为开发高效交
通网络流量分配技术提供了一个良好的基础。自此之后，基于Beckmann模型，很多交通网络
流量分配技术被开发出来。这些技术可以被分成三种类型，即(1)基于路段的交通网络流量
分配技术；(2)基于路径的交通网络流量分配技术；(3)基于起点的交通网络流量分配技术。
[0003] 基于路段的交通网络流量监测或者分配等技术是通过更新路段流量估计交通网络流量的分布情况。基于路段的交通网络流量分配技术在实践和研究中得到了广泛的应
用，其具有很多优点，比如：操作方法简单，计算机存储路段流量不需要占用过多的内存空
间。但是基于路段的交通网络流量分配技术的计算精度不高，很难获得精确解。根据现有研
究，基于路段的交通网络流量分配技术的精度只能达到1E‑7左右(采用广泛使用的相对误
差作为精度指标)。为了进一步提高精度，研究者们提出了基于路径的交通网络流分配技
术，该技术将Beckmann模型分解为基于起讫点的模型，然后依次求解各个基于起讫点的模
型，调整每个起讫点之间的交通流量。基于路径的交通网络流量分配技术可以获得较高的
收敛精度(超过1E‑12)，但是存储路径变量需要占用很多的计算机内存空间，所以研究者开
发了基于出行起点的交通网络流量分配技术。这类技术将Beckmann模型分解为基于起点的
模型，并依次求解这类模型。
用，其具有很多优点，比如：操作方法简单，计算机存储路段流量不需要占用过多的内存空
间。但是基于路段的交通网络流量分配技术的计算精度不高，很难获得精确解。根据现有研
究，基于路段的交通网络流量分配技术的精度只能达到1E‑7左右(采用广泛使用的相对误
差作为精度指标)。为了进一步提高精度，研究者们提出了基于路径的交通网络流分配技
术，该技术将Beckmann模型分解为基于起讫点的模型，然后依次求解各个基于起讫点的模
型，调整每个起讫点之间的交通流量。基于路径的交通网络流量分配技术可以获得较高的
收敛精度(超过1E‑12)，但是存储路径变量需要占用很多的计算机内存空间，所以研究者开
发了基于出行起点的交通网络流量分配技术。这类技术将Beckmann模型分解为基于起点的
模型，并依次求解这类模型。
[0004] 尽管现有的交通网络流量监测或者分配等技术能够在一定程度上解决交通分配问题，但是这些技术都是串行计算的，随着计算机技术的发展和普及，计算机的多核计算算
力已经获得很大的增长。而现有的串行计算方法不能利用计算机的多核心处理能力，容易
使城市道路交通网络的流量监测或者分配等问题的效率低。
力已经获得很大的增长。而现有的串行计算方法不能利用计算机的多核心处理能力，容易
使城市道路交通网络的流量监测或者分配等问题的效率低。
发明内容
[0005] 针对以上问题，本发明提出一种基于块坐标下降的大规模城市交通网络流量监测方法，使一种基于交通网络流量分配技术可以有效的利用计算机并行计算资源，进一步提
高城市道路交通网络的流量分配问题的分配效率和精度，其可以有效利用计算机多核计算
资源的大规模城市交通网络流量分配技术，快速分配交通需求，评估交通基础设施建设工
程和交通管理方案的影响，进而帮助管理部门做出科学合理的决策。
高城市道路交通网络的流量分配问题的分配效率和精度，其可以有效利用计算机多核计算
资源的大规模城市交通网络流量分配技术，快速分配交通需求，评估交通基础设施建设工
程和交通管理方案的影响，进而帮助管理部门做出科学合理的决策。
[0006] 为实现本发明的目的，提供一种基于块坐标下降的大规模城市交通网络流量监测方法，包括如下步骤：
[0007] S1，获取设定城市内道路交通网络上的运行参数，设置交通流量分配精度阈值M，以及计算过程中的参数FreC；所述运行参数包括路段自由流行驶时间，路段上的交通流承
载能力，路段阻抗函数，道路交通网络上的机动车出行需求分布情况；所述机动车出行需求
分布情况包括机动车出行的起点、机动车出行的终点、以及OD对之间的出行需求；所述OD对
包括起点和该起点对应的终点，出行需求指从出行起点O到出行终点D的机动车数量；
载能力，路段阻抗函数，道路交通网络上的机动车出行需求分布情况；所述机动车出行需求
分布情况包括机动车出行的起点、机动车出行的终点、以及OD对之间的出行需求；所述OD对
包括起点和该起点对应的终点，出行需求指从出行起点O到出行终点D的机动车数量；
[0008] S2，并行计算每个起点的最短路树，根据最短路树确定各个OD对之间的最短路，对每个OD对建立一个路径集合，将OD对之间的最短路作为初始路径加入该OD对对应的路径集
合，将OD对之间的出行需求加载到该OD对对应的初始路径上；将路径上的车流量叠加到道
路网络中的路段上，以得到路段流量，并根据更新后的路段流量更新路段出行时间；
合，将OD对之间的出行需求加载到该OD对对应的初始路径上；将路径上的车流量叠加到道
路网络中的路段上，以得到路段流量，并根据更新后的路段流量更新路段出行时间；
[0009] S3，对道路交通网络上的每个OD对，基于更新后的路段出行时间并行更新每个起点的最短路树；将每个OD对的最短路与OD对的路径集合中的所有路径进行对比，如果现有
的路径集合中没有该条最短路，就将该条最短路加入路径集合中，并将该路径上的路径流
量暂时设置为0；
的路径集合中没有该条最短路，就将该条最短路加入路径集合中，并将该路径上的路径流
量暂时设置为0；
[0010] S4，对交通网络上的每个OD对，保持路径集合不变，利用迭代算法更新路径上的车流量，如果车流量收敛，根据更新后路径上的车流量确定城市交通网络流量，否则返回S3。
[0011] 在一个实施例中，对交通网络上的每个OD对，保持路径集合不变，利用迭代算法更新路径上的车流量包括：
[0012] S4.1，设置迭代次数i的上限阈值，用数值MaxI表示，一旦迭代次数i大于等于MaxI，则当前步骤停止，计算道路交通网络的精度误差；
[0013] S4.2，判断i是否是FreC的整数倍，如果i是FreC的整数倍，对道路交通网络上的OD对的路径集合W分割成若干子集合，否则，对一个缩小的OD对的路径集合 分割成若干子集
合，建立一个空的受限制的OD集合 用来存放OD对；将 分割成若干子集合Wi，下标i表示
第i个子集合；
合，建立一个空的受限制的OD集合 用来存放OD对；将 分割成若干子集合Wi，下标i表示
第i个子集合；
[0014] S4.3，选择一个分割后的子集合Wi，并行地计算子集合中OD对的精度指标，如果这个OD对的精度不足，则需要利用下降算法调整这些OD对中的路径流量，同时将这些精度不
足的OD对加入一个新的受限制的OD集合 如果这个OD对的精度足够，则在当前过程中不
进行路径流量调整；其中OD对的相对误差rgod为：
足的OD对加入一个新的受限制的OD集合 如果这个OD对的精度足够，则在当前过程中不
进行路径流量调整；其中OD对的相对误差rgod为：
[0015]od
[0016] 式中 表示OD对之间的最短出行时间，q 表示OD对之间的出行需求，va表示路段od
流量，ta(va)表示路段出行时间，A 表示OD对中所有路径经过的路段集合；精度不足指相应
精度指标大于精度阈值M，精度足够指相应精度指标小于或等精度阈值M；
流量，ta(va)表示路段出行时间，A 表示OD对中所有路径经过的路段集合；精度不足指相应
精度指标大于精度阈值M，精度足够指相应精度指标小于或等精度阈值M；
[0017] S4.4，选择下一个子集合Wi，重复步骤S4.3，直到所有子集合都被访问；
[0018] S4.5，如果受限制OD对集合 是空集，则不再进行迭代，跳出步骤S4；如果当前迭代次数超过一定的阈值MaxI，则不再进行迭代，以当前各个子集合包括的路径流量确定各
个路径的车流量，跳出步骤S4；否则，令i＝i+1， 并返回S4.1。
个路径的车流量，跳出步骤S4；否则，令i＝i+1， 并返回S4.1。
[0019] 具体地，步骤S4.2中，对道路交通网络上的OD对的路径集合W分割成若干子集合包括：
[0020] S4.2.1：设定并行度ParaL，并行度ParaL表示同时计算的任务数量；
[0021] S4.2.2：根据并行度ParaL，将集合W分成 个块，令 j表示W中OD对的索引，对于块n∈{1,…,G}，剩余的OD对被划入第G+1个块，将得到的各个块确定为各个子
集合；其中，符号 表示向下取整，j与n具有如下关系：j＝n+k×G,k∈￥,j∈Block n。
集合；其中，符号 表示向下取整，j与n具有如下关系：j＝n+k×G,k∈￥,j∈Block n。
[0022] 具体地，步骤S4.2中，如果这个OD对的精度不足，则需要利用下降算法调整这些OD对中的路径流量，同时将这些精度不足的OD对加入一个新的受限制的OD集合 包括：
[0023] S4.3.1：计算OD对之间每条路径的路径出行时间；
[0024] S4.3.2：计算OD对之间最短路径出行时间；
[0025] S4.3.3：计算OD对的精度误差rgod；
[0026] S4.3.4：如果OD对的精度误差rgod大于精度阈值M，使用优化方法调整OD对之间的路径流量；将该OD对加入OD对集合
[0027] S4.3.4：对子集合Wi中的所有OD对完成流量调整后，将更新后的路径流量重新叠加到路段上，更新路段流量；
[0028] S4.3.5：对流量受到调整的路段更新该路段的出行时间；
[0029] S4.3.6：回到步骤S4.3.1，更新下一个子集合中的路径流量，并扩增OD对集合
[0030] 在一个实施例中，上述基于块坐标下降的大规模城市交通网络流量监测方法，还包括：
[0031] S5，对交通网络上的所有OD对，计算整个交通网络的精度误差rg，如果精度误差rg大于精度阈值M，表明城市路网上的出行需求到达收敛状态，符合出行者的出行选择行为，
结束计算；否则，更新M，令M＝rg/2，返回执行步骤S3；精度误差rg为：
结束计算；否则，更新M，令M＝rg/2，返回执行步骤S3；精度误差rg为：
[0032]
[0033] 其中 表示OD对之间的最小出行时间，qod表示OD对之间的出行需求，va表示路段流量，ta(va)表示路段出行时间，A表示交通网络上路段的集合；rg越接近0，网络交通流量越
接近收敛状态。
接近收敛状态。
[0034] 在一个实施例中，步骤S2，S3和S5中的最短路树计算均采用并行计算的方法进行求解，即在交通网络中，并行地对所有起点，采用单源最短路算法求解单个起点到网络上其
他节点之间的最短路树。
他节点之间的最短路树。
[0035] 本发明与现有技术相比，具有以下有益效果：
[0036] (1)现有交通网络流量分配技术无法进行并行实施，也意味着无法利用计算机的多核心能力。本发明致力于并行处理交通网络流量分配问题，可以有效利用计算机的并行
计算资源。
计算资源。
[0037] (2)本发明与现有技术相比，推算速度更快，适合求解大规模交通网络流量分配问题。可以快速评估交通基础设施，交通管理方案，交通事件对城市路网造成的影响，从而科
学优化，合理指导交通设计与管理方案，对于大城市交通管理与规划项目的顺利实施具有
重要作用。
学优化，合理指导交通设计与管理方案，对于大城市交通管理与规划项目的顺利实施具有
重要作用。
附图说明
[0038] 图1是一个实施例的基于块坐标下降的大规模城市交通网络流量监测方法流程图；
[0039] 图2是另一个实施例的基于块坐标下降的大规模城市交通网络流量监测方法流程图；
[0040] 图3是一个实施例中块坐标下降技术在Philadelphia网络的测试结果示意图。
具体实施方式
[0041] 为了使本申请的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本申请进行进一步详细说明。应当理解，此处描述的具体实施例仅仅用以解释本申请，并不
用于限定本申请。
用于限定本申请。
[0042] 在本文中提及“实施例”意味着，结合实施例描述的特定特征、结构或特性可以包含在本申请的至少一个实施例中。在说明书中的各个位置出现该短语并不一定均是指相同
的实施例，也不是与其它实施例互斥的独立的或备选的实施例。本领域技术人员显式地和
隐式地理解的是，本文所描述的实施例可以与其它实施例相结合。
的实施例，也不是与其它实施例互斥的独立的或备选的实施例。本领域技术人员显式地和
隐式地理解的是，本文所描述的实施例可以与其它实施例相结合。
[0043] 参考图1所示，图1为一个实施例的基于块坐标下降的大规模城市交通网络流量监测方法流程图，包括如下步骤：
[0044] S1，获取设定城市内道路交通网络上的运行参数，设置交通流量分配精度阈值M，以及计算过程中的参数FreC；所述运行参数包括路段自由流行驶时间，路段上的交通流承
载能力，路段阻抗函数，道路交通网络上的机动车出行需求分布情况；所述机动车出行需求
分布情况包括机动车出行的起点、机动车出行的终点、以及OD对之间的出行需求；所述OD对
包括起点和该起点对应的终点，出行需求指从出行起点O到出行终点D的机动车数量；
载能力，路段阻抗函数，道路交通网络上的机动车出行需求分布情况；所述机动车出行需求
分布情况包括机动车出行的起点、机动车出行的终点、以及OD对之间的出行需求；所述OD对
包括起点和该起点对应的终点，出行需求指从出行起点O到出行终点D的机动车数量；
[0045] S2，并行计算每个起点的最短路树，根据最短路树确定各个OD对之间的最短路，对每个OD对建立一个路径集合，将OD对之间的最短路作为初始路径加入该OD对对应的路径集
合，将OD对之间的出行需求加载到该OD对对应的初始路径上；将路径上的车流量叠加到道
路网络中的路段上，以得到路段流量，并根据更新后的路段流量更新路段出行时间；
合，将OD对之间的出行需求加载到该OD对对应的初始路径上；将路径上的车流量叠加到道
路网络中的路段上，以得到路段流量，并根据更新后的路段流量更新路段出行时间；
[0046] S3，对道路交通网络上的每个OD对，基于更新后的路段出行时间并行更新每个起点的最短路树；将每个OD对的最短路与OD对的路径集合中的所有路径进行对比，如果现有
的路径集合中没有该条最短路，就将该条最短路加入路径集合中，并将该路径上的路径流
量暂时设置为0；
的路径集合中没有该条最短路，就将该条最短路加入路径集合中，并将该路径上的路径流
量暂时设置为0；
[0047] S4，对交通网络上的每个OD对，保持路径集合不变，利用迭代算法更新路径上的车流量，如果车流量收敛，根据更新后路径上的车流量确定城市交通网络流量，否则返回S3。
[0048] 具体地，本实施例使用的时间是广义的时间，包括出行者感知的行驶时间，以及行驶过程中付出的成本。
[0049] 上述基于块坐标下降的大规模城市交通网络流量监测方法，通过获取设定城市内道路交通网络上的运行参数，设置交通流量分配精度阈值M，以及计算过程中的参数FreC，
并行计算每个起点的最短路树，以根据最短路树确定各个OD对之间的最短路，对每个OD对
建立一个路径集合，将OD对之间的最短路作为初始路径加入该OD对对应的路径集合，将OD
对之间的出行需求加载到该OD对对应的初始路径上；将路径上的车流量叠加到道路网络中
的路段上，以得到路段流量，并根据更新后的路段流量更新路段出行时间，对道路交通网络
上的每个OD对，基于更新后的路段出行时间并行更新每个起点的最短路树；将每个OD对的
最短路与OD对的路径集合中的所有路径进行对比，如果现有的路径集合中没有该条最短
路，就将该条最短路加入路径集合中，并将该路径上的路径流量暂时设置为0，对交通网络
上的每个OD对，保持路径集合不变，利用迭代算法更新路径上的车流量，如果车流量收敛，
根据更新后路径上的车流量确定城市交通网络流量，以实现对城市交通网络流量的快速高
精度监测，从而实现对城市交通网络流量的快速分配。
并行计算每个起点的最短路树，以根据最短路树确定各个OD对之间的最短路，对每个OD对
建立一个路径集合，将OD对之间的最短路作为初始路径加入该OD对对应的路径集合，将OD
对之间的出行需求加载到该OD对对应的初始路径上；将路径上的车流量叠加到道路网络中
的路段上，以得到路段流量，并根据更新后的路段流量更新路段出行时间，对道路交通网络
上的每个OD对，基于更新后的路段出行时间并行更新每个起点的最短路树；将每个OD对的
最短路与OD对的路径集合中的所有路径进行对比，如果现有的路径集合中没有该条最短
路，就将该条最短路加入路径集合中，并将该路径上的路径流量暂时设置为0，对交通网络
上的每个OD对，保持路径集合不变，利用迭代算法更新路径上的车流量，如果车流量收敛，
根据更新后路径上的车流量确定城市交通网络流量，以实现对城市交通网络流量的快速高
精度监测，从而实现对城市交通网络流量的快速分配。
[0050] 在一个实施例中，对交通网络上的每个OD对，保持路径集合不变，利用迭代算法更新路径上的车流量包括：
[0051] S4.1，设置迭代次数i的上限阈值，用数值MaxI表示，一旦迭代次数i大于等于MaxI，则当前步骤停止，计算道路交通网络的精度误差；
[0052] S4.2，判断i是否是FreC的整数倍，如果i是FreC的整数倍，对道路交通网络上的OD对的路径集合W分割成若干子集合，否则，对一个缩小的OD对的路径集合 分割成若干子集
合，建立一个空的受限制的OD集合 用来存放OD对；将 分割成若干子集合Wi，下标i表示
第i个子集合，即Wi中，Wi,i＝1,2,3,…；
合，建立一个空的受限制的OD集合 用来存放OD对；将 分割成若干子集合Wi，下标i表示
第i个子集合，即Wi中，Wi,i＝1,2,3,…；
[0053] S4.3，选择一个分割后的子集合Wi，并行地计算子集合中OD对的精度指标，如果这个OD对的精度不足，则需要利用下降算法调整这些OD对中的路径流量，同时将这些精度不
足的OD对加入一个新的受限制的OD集合 如果这个OD对的精度足够，则在当前过程中不
进行路径流量调整；其中OD对的相对误差rgod为：
足的OD对加入一个新的受限制的OD集合 如果这个OD对的精度足够，则在当前过程中不
进行路径流量调整；其中OD对的相对误差rgod为：
[0054]
[0055] 式中 表示OD对之间的最短出行时间，qod表示OD对之间的出行需求，va表示路段od
流量，ta(va)表示路段出行时间，A 表示OD对中所有路径经过的路段集合；精度不足指相应
精度指标大于精度阈值M，精度足够指相应精度指标小于或等精度阈值M；
流量，ta(va)表示路段出行时间，A 表示OD对中所有路径经过的路段集合；精度不足指相应
精度指标大于精度阈值M，精度足够指相应精度指标小于或等精度阈值M；
[0056] S4.4，选择下一个子集合Wi，重复步骤S4.3，直到所有子集合都被访问；
[0057] S4.5，如果受限制OD对集合 是空集，则不再进行迭代，跳出步骤S4；如果当前迭代次数超过一定的阈值MaxI，则不再进行迭代，以当前各个子集合包括的路径流量确定各
个路径的车流量，跳出步骤S4；否则，令i＝i+1， 并返回S4.1。
个路径的车流量，跳出步骤S4；否则，令i＝i+1， 并返回S4.1。
[0058] 具体地，上述步骤S4.4提出需要串行地遍历所有子集合Wi，所有子集合的串行遍历方式都属于本实施例的描述范围。步骤S4.4对每个OD对进行路径流量调整之前，计算这
个OD的精度指标，对精度指标的定义不做具体约束，所有通过精度指标过滤OD对的方式都
属于本实施例的描述范围
个OD的精度指标，对精度指标的定义不做具体约束，所有通过精度指标过滤OD对的方式都
属于本实施例的描述范围
[0059] 本实施例设置了迭代次数i的上限阈值MaxI，一旦迭代次数i大于等于MaxI，则当前流量调整步骤停止，进入后续步骤(即步骤S5)；不同于同类技术，本实施例对相应网络中
的OD对进行了分块处理，在同一个块(Block)中并行地更新OD对之间的路径流量，在块与块
之间更新路段流量，进而修正出行时间信息；不是对所有OD对都进行流量调整，而是在步骤
S4中设置一个精度阈值(用M表示)，检查每个OD对的精度误差rgod，将不满足精度要求(即
rgod＞M)的OD对进行流量调整，从而达到减少计算量的目的；同时将这个OD对加入一个缩小
的OD对集合W％，在下次迭代中继续检查OD对的精度是否满足需求。
的OD对进行了分块处理，在同一个块(Block)中并行地更新OD对之间的路径流量，在块与块
之间更新路段流量，进而修正出行时间信息；不是对所有OD对都进行流量调整，而是在步骤
S4中设置一个精度阈值(用M表示)，检查每个OD对的精度误差rgod，将不满足精度要求(即
rgod＞M)的OD对进行流量调整，从而达到减少计算量的目的；同时将这个OD对加入一个缩小
的OD对集合W％，在下次迭代中继续检查OD对的精度是否满足需求。
[0060] 具体地，步骤S4.2中，对道路交通网络上的OD对的路径集合W分割成若干子集合包括：
[0061] S4.2.1：设定并行度ParaL，并行度ParaL表示同时计算的任务数量；
[0062] S4.2.2：根据并行度ParaL，将集合W分成 个块，令 j表示W中OD对的索引，对于块n∈{1,…,G}，剩余的OD对被划入第G+1个块，将得到的各个块确
定为各个子集合；其中，符号 表示向下取整，j与n具有如下关系：j＝n+k×G,k∈￥,j∈
Block n。
定为各个子集合；其中，符号 表示向下取整，j与n具有如下关系：j＝n+k×G,k∈￥,j∈
Block n。
[0063] 本实施例提供的块划分方式即简单方便，又可以有效避免同一个块中各个OD对之间的路径重叠度太高，从而避免路径流量无法得到有效调整。
[0064] 具体地，步骤S4.3中，如果这个OD对的精度不足，则需要利用下降算法调整这些OD对中的路径流量，同时将这些精度不足的OD对加入一个新的受限制的OD集合 包括：
[0065] S4.3.1：计算OD对之间每条路径的路径出行时间；
[0066] S4.3.2：计算OD对之间最短路径出行时间；
[0067] S4.3.3：计算OD对的精度误差rgod；
[0068] S4.3.4：如果OD对的精度误差rgod大于精度阈值M，使用优化方法调整OD对之间的路径流量；将该OD对加入OD对集合
[0069] S4.3.4：对子集合Wi中的所有OD对完成流量调整后，将更新后的路径流量重新叠加到路段上，更新路段流量；
[0070] S4.3.5：对流量受到调整的路段更新该路段的出行时间；
[0071] S4.3.6：回到步骤S4.3.1，更新下一个子集合中的路径流量，并扩增OD对集合
[0072] 在一个示例中，步骤S4.3.4中对调整路径流量的优化算法不做具体约束，所有优化算法都属于本实施例的描述范围。
[0073] 本实施例在并行处理过程中根据OD对的精度误差rgod决定是否需要进行流量调整，即如果OD对的精度误差rgod大于M则进行流量调整。
[0074] 在一个实施例中，上述基于块坐标下降的大规模城市交通网络流量监测方法，还包括：
[0075] S5，对交通网络上的所有OD对，计算整个交通网络的精度误差rg，如果精度误差rg大于精度阈值M，表明城市路网上的出行需求到达收敛状态，符合出行者的出行选择行为，
结束计算；否则，更新M，令M＝rg/2，返回执行步骤S3；精度误差rg为：
结束计算；否则，更新M，令M＝rg/2，返回执行步骤S3；精度误差rg为：
[0076]
[0077] 其中 表示OD对之间的最小出行时间，qod表示OD对之间的出行需求，va表示路段流量，ta(va)表示路段出行时间，A表示交通网络上路段的集合；rg越接近0，网络交通流量越
接近收敛状态。
接近收敛状态。
[0078] 本实施例可以实现大规模城市交通网络流量分配，相应的分配方案可以更加精细，高效，可以快速地评估交通设施在道路交通网络上的运行性能，优化交通设置的设计服
务水平，设计位置等设计指标，也可以快速评估交通管理方方案，优化交通管理措施。
务水平，设计位置等设计指标，也可以快速评估交通管理方方案，优化交通管理措施。
[0079] 在一个实施例中，步骤S2，S3和S5中的最短路树计算均采用并行计算的方法进行求解，即在交通网络中，并行地对所有起点，采用单源最短路算法求解单个起点到网络上其
他节点之间的最短路树。
他节点之间的最短路树。
[0080] 在一个实施例中，参考图2所示，上述基于块坐标下降的大规模城市交通网络流量监测方法可以包括如下步骤：
[0081] (1)读入一个典型大规模交通网络的运行参数，包括路段自由流行驶时间，路段上的交通流承载能力，路段阻抗函数，道路交通网络上的(机动车)出行需求分布情况，包括出
od
行需求的起点和终点，以及起终点(OD对)之间的需求量q ；令初始路径流量为零，路段出行
‑3
时间为自由流出行时间；设置初始精度指标(精度阈值)M＝10 ；设置检查频率FreC＝100；
od
行需求的起点和终点，以及起终点(OD对)之间的需求量q ；令初始路径流量为零，路段出行
‑3
时间为自由流出行时间；设置初始精度指标(精度阈值)M＝10 ；设置检查频率FreC＝100；
[0082] (2)并行计算每个起点的最短路树，对每个OD对建立一个路径集合Kod，将OD之间的od
最短路作为初始路径加入该集合，将OD对之间的出行需求q 都加载到初始路径上，得到初
始路径流量 基于路径流量更新路段流量va：
最短路作为初始路径加入该集合，将OD对之间的出行需求q 都加载到初始路径上，得到初
始路径流量 基于路径流量更新路段流量va：
[0083]
[0084] 其中W表示所有OD对的集合，A表示路段集合， 表示路段a与路径k的关系，如果路径k使用了路段a，则 等于1，反之为0。再根据更新后的路段流量计算路段出行时间ta
和路段出行时间的导数ta′；
和路段出行时间的导数ta′；
[0085]
[0086]
[0087] (3)对交通网络上的每个OD对，基于更新的路段出行时间并行计算每个起点的最短路树；将每个OD对的最短路与OD对的路径集合中的所有路径进行对比，如果现有的路径
集合中没有该条最短路，就将该条最短路加入路径集合中，并将该路径上的路径流量暂时
设置为0；
集合中没有该条最短路，就将该条最短路加入路径集合中，并将该路径上的路径流量暂时
设置为0；
[0088] (4)对交通网络上的每个OD对，固定路径集合不变，利用迭代算法，按照如下过程，更新路径上的流量，
[0089] 过程4.1：设置迭代次数i的上限阈值MaxI＝1000，一旦迭代次数i大于等于MaxI，则当前步骤停止，进入步骤(5)；
[0090] 过程4.2：判断i是否是FreC的整数倍，如果i是FreC的整数倍，对整个交通网络上的OD对集合W分割成128个子集合，否则，本发明对一个缩小的OD对集合W分割成128个子集
合，即Wi,i＝1,2,3,…；建立一个空集 用来存放OD对；
合，即Wi,i＝1,2,3,…；建立一个空集 用来存放OD对；
[0091] 过程4.3：选择一个分割后的子集合Wi；并行计算子集合中OD对的精度指标，比如OD对的相对误差rgod，rgod定义为：
[0092]
[0093] 其中 表示OD对之间的最小出行时间，qod表示OD对之间的出行需求，va表示路段od
流量，ta(va)表示路段出行时间，A 表示OD对中所有路径经过的路段集合。
流量，ta(va)表示路段出行时间，A 表示OD对中所有路径经过的路段集合。
[0094] 如果这个OD对的精度不足，即大于精度指标M，则需要利用梯度投影算法调整这些OD对中的路径流量，同时将这些精度不足的OD对加入一个新的受限制的OD集合 如果这
个OD对的精度足够，则在当前过程中不进行路径流量调整。
个OD对的精度足够，则在当前过程中不进行路径流量调整。
[0095] 过程4.4：选择下一个子集合Wi，重复步骤4.3，直到所有子集合都被访问；
[0096] 过程4.5：如果受限制OD对集合 是空集，则不再进行迭代，跳出步骤4；如果当前迭代次数超过MaxI，则不再进行迭代，跳出步骤4；否则，令i＝i+1， 返回过程4.1
[0097] (5)对交通网络上的所有OD对，计算整个交通网络的精度误差rg，rg定义为：
[0098]od
[0099] 其中 表示OD对之间的最小出行时间，q 表示OD对之间的出行需求，va表示路段流量，ta(va)表示路段出行时间，A表示交通网络上路段的集合；rg越接近0，网络交通流量越
接近收敛状态；
接近收敛状态；
[0100] 如果精度误差rg满足预定的精度指标，则结束计算；否则，更新M，令M＝rg/2，返回步骤(3)。
[0101] 具体地，图3记录了本实施例所述块坐标下降(PBCD)的交通网络流量分配技术的实施过程，并与串行的梯度投影(iGP)交通网络流量分配技术进行比较，可以看到PBCD技术
明显优于iGP(点虚线)。即使在串行计算模式下(实线)，PBCD也明显优于iGP，经过并行加速
后，PBCD技术的收敛时间更短(曲线)。
明显优于iGP(点虚线)。即使在串行计算模式下(实线)，PBCD也明显优于iGP，经过并行加速
后，PBCD技术的收敛时间更短(曲线)。
[0102] 本发实施例具有以下有益效果：
[0103] (1)现有交通网络流量分配技术无法进行并行实施，也意味着无法利用计算机的多核心能力。本实施例致力于并行处理交通网络流量分配问题，可以有效利用计算机的并
行计算资源。
行计算资源。
[0104] (2)本实施例与现有技术相比，推算速度更快，适合求解大规模交通网络流量分配问题。可以快速评估交通基础设施，交通管理方案，交通事件对城市路网造成的影响，从而
科学优化，合理指导交通设计与管理方案，对于大城市交通管理与规划项目的顺利实施具
有重要作用。
科学优化，合理指导交通设计与管理方案，对于大城市交通管理与规划项目的顺利实施具
有重要作用。
[0105] 以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛
盾，都应当认为是本说明书记载的范围。
盾，都应当认为是本说明书记载的范围。
[0106] 需要说明的是，本申请实施例所涉及的术语“第一\第二\第三”仅仅是区别类似的对象，不代表针对对象的特定排序，可以理解地，“第一\第二\第三”在允许的情况下可以互
换特定的顺序或先后次序。应该理解“第一\第二\第三”区分的对象在适当情况下可以互
换，以使这里描述的本申请的实施例能够以除了在这里图示或描述的那些以外的顺序实
施。
换特定的顺序或先后次序。应该理解“第一\第二\第三”区分的对象在适当情况下可以互
换，以使这里描述的本申请的实施例能够以除了在这里图示或描述的那些以外的顺序实
施。
[0107] 本申请实施例的术语“包括”和“具有”以及它们任何变形，意图在于覆盖不排他的包含。例如包含了一系列步骤或模块的过程、方法、装置、产品或设备没有限定于已列出的
步骤或模块，而是可选地还包括没有列出的步骤或模块，或可选地还包括对于这些过程、方
法、产品或设备固有的其它步骤或模块。
步骤或模块，而是可选地还包括没有列出的步骤或模块，或可选地还包括对于这些过程、方
法、产品或设备固有的其它步骤或模块。
[0108] 以上所述实施例仅表达了本申请的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来
说，在不脱离本申请构思的前提下，还可以做出若干变形和改进，这些都属于本申请的保护
范围。因此，本申请专利的保护范围应以所附权利要求为准。
说，在不脱离本申请构思的前提下，还可以做出若干变形和改进，这些都属于本申请的保护
范围。因此，本申请专利的保护范围应以所附权利要求为准。