基于贝叶斯层次最优化的OD矩阵估计方法

摘要

本发明公开了一种基于贝叶斯层次最优化的OD矩阵估计方法，该方法针对OD矩阵估计问题，假定OD矩阵服从伽马分布，根据历史OD矩阵和路段流量的样本信息对分布的参数进行贝叶斯估计，将传统OD矩阵估计问题转化为贝叶斯框架下的层次最优化问题，创建一套包含用户均衡‑最小方差分配模型(下层)、最小二乘法(中层)、贝叶斯后验众数估计(上层)的具有明确层次关系的三层数学规划模型方法，并设计相应的多层迭代算法进行模型求解计算，用数学方法反演估计出OD矩阵。本发明可充分利用观测路段信息和历史信息，获取精度较高的OD矩阵估计结果，为城市交通建模、规划与管理提供可靠的基础数据和依据。

说明书

技术领域

本发明属于交通运输规划与管理中的交通网络流建模与估计领域，具体涉及一种基于贝叶斯层次最优化的OD矩阵估计方法。

背景技术

交通起讫点需求矩阵(Origin-Destination Matrix，即OD矩阵)是对交通出行空间分布特征的描述，反映了交通小区之间机动车移动的基本信息。只有准确估计OD矩阵需求，才能把握现状路网的交通特性，在交通规划以及城市总体规划过程中更加有针对性地缓解拥堵等交通问题。

获取OD矩阵的传统方法为开展大规模的人工走访和问卷调查，这些方法往往代价高昂、统计精度低。随着检测技术的发展，基于观测的交通网络流量信息，成为一种可行的方法。在拥堵的交通网络中，OD矩阵估计和交通分配这两个问题常耦合在一起讨论，用双层规划模型解释。其上层是广义最小二乘法或最大熵法的OD估计问题，基于观测得到的路段流量等交通网络要素信息反演出OD矩阵；下层是用户均衡分配，形成双层最优化问题并设计启发式算法。

然而，双层规划问题的求解都十分复杂：这个双层规划最优化的问题及其局部最优解都是NP-hard问题，也是非凸的，因此算法求得的解可能落入局部最优而非全局最优。而实际上交通网络连通性很强，OD对数远大于路段数量；为了得到唯一解，需要给出更多的信息来对可行域进行进一步约束。通常会使用一个参考的历史OD矩阵，这个矩阵可以通过构建数学规划模型，在约束条件下最优化一定目标函数实现，如：最小二乘法、广义最小二乘法，最大熵法、最小信息法，基于马尔科夫链的方法。通常这些基于最优化模型的方法只输出单点信息即OD矩阵、路段流量等，但却无法获知估计变量的随机信息。统计学方法一个突出的优势是提供了流量估计的变化信息，如：经典统计方法，贝叶斯法、贝叶斯网络法。除了利用总体信息和样本信息假定变量概率分布形式，贝叶斯方法还重视先验信息，认为待估参数自身也为随机变量。其原理是先给出所有待估变量的先验分布，然后根据采集到的样本信息推导出所有待估变量的后验分布，从而给出待估变量的估计值和相应的置信区间。

虽然很多学者提出了诸多OD矩阵估计的方法，但仍然存在一些不足：(1)最小二乘法、最大熵法等往往只给出OD矩阵和路段流的单点信息，而不能给出方差、置信区间等体现其变化性质的信息；(2)常见的双层规划模型为获取OD-路段关联系数需在交通分配步骤枚举路径，在中大型网络中效率低精度差，亟需一种简便的效率型设计；(3)贝叶斯法估计OD矩阵，后验分布形式求解困难，常使用的蒙特卡洛模拟算法在实际应用时需大量抽样，且精度得不到保障。

发明内容

发明目的：针对以上问题，本发明提出一种基于贝叶斯层次最优化的OD矩阵估计方法。

技术方案：为实现本发明的目的，本发明所采用的技术方案是：一种基于贝叶斯层次最优化的OD矩阵估计方法，具体包括如下步骤：

步骤1，获取目标区域的交通网络拓扑结构、源点-终点先验OD矩阵数据、源点-终点历史OD矩阵数据以及目标区域各路段流量观测数据，并进行数据处理，包括数据清洗、剔除噪音数据；

步骤2，建立无需路径列举的用户均衡-最小方差模型，作为层次优化的下层模型；

步骤3，建立最小二乘法估计模型，作为层次优化的中层模型；

步骤4，建立伽马分布的贝叶斯参数估计，作为本发明所建层次优化的上层模型；

步骤5，通过步骤2-步骤4，得到基于贝叶斯层次优化的OD矩阵估计模型；

步骤6，利用处理后的目标区域的交通网络拓扑结构、源点-终点先验OD矩阵数据、源点-终点历史OD矩阵数据以及目标区域各路段流量观测数据，通过迭代算法对步骤5所述OD矩阵估计模型进行求解，得到目标区域的OD矩阵估计结果。

进一步地，步骤2所述建立无需路径列举的用户均衡-最小方差模型，方法如下：

步骤2.1，利用OD-路段关联系数β

v

式中，v

步骤2.2，改进原有的基于路段层流的用户均衡模型，构建具有路段层流唯一解的用户均衡-最小方差模型，具体如下：

在原有的基于路段层流的用户均衡模型的目标函数中加入以最小方差为原则的第二个目标，重新分布目标区域不同路径之间的OD需求，使路径流和路段层流具有唯一最优解，得到用户均衡-最小方差模型；

所述用户均衡-最小方差模型的目标函数为：

式中，Z(v)为用户均衡-最小方差模型的目标函数；

所述用户均衡-最小方差模型的约束条件为：

式中，δ

进一步地，步骤3所述建立最小二乘法估计模型，方法如下：

使用最小二乘法，得到最小二乘法估计模型的目标函数；所述最小二乘法估计模型的目标函数为：

式中，Z(d，w)表示最小二乘法估计模型的目标函数；d表示存储OD流量d

所述估计路段流量w

式中，β

进一步地，步骤4所述建立伽马分布的贝叶斯参数估计，方法如下：

步骤4.1，基于伽马分布的性质，计算关于路段流量的概率密度函数，如下：

式中，x为路段流量；θ为伽马分布的形状参数；λ

步骤4.2，计算以路段流量样本集合构成的向量的似然函数，如下：

式中，X表示路段流量样本集合构成的向量，x

步骤4.3，仿写步骤4.2所述似然函数，得到伽马分布的共轭先验分布，如下：

f(θ，λ

式中，η

所述三个超参数分别为：

其中，

步骤4.4，利用伽马分布对超参数更新，具体方法如下：

根据贝叶斯定理计算参数θ和λ的后验分布概率密度函数，如下：

式中，

式中，d

步骤4.5，根据概率密度最大原则，求解参数θ和λ

所述OD矩阵估计的计算公式如下：

E(q

所述OD矩阵的方差的计算公式如下：

式中，q

进一步地，所述步骤6的方法具体如下：

模型输入数据包括：交通网络拓扑结构、源点-终点先验OD矩阵数据、源点-终点历史OD矩阵数据以及目标区域各路段流量观测数据；

模型输出数据包括：估计OD矩阵、估计路段流量；

步骤6.1，设置初始迭代次数i＝0，收敛精度ε，通过先验OD量

步骤6.2，通过分配先验OD量

步骤6.3，对最小二乘法估计模型中代入OD-路段关联系数β

步骤6.4，使用辅助OD量d

步骤6.5，求解参数θ和λ

步骤6.6，计算OD矩阵估计结果：根据伽马分布统计特征，利用参数θ、λ

步骤6.7，进行收敛检验：

若满足收敛条件：

否则，将得到的q

有益效果：与现有技术相比，本发明所述技术方案具有以下有益技术效果：

本发明通过研究静态OD矩阵估计问题，创建多个数学规划问题组成层次最优化模型，并设计发明相应的多层迭代算法进行模型求解计算，提供了一种基于贝叶斯层次最优化的OD矩阵估计方法。本发明针对OD矩阵估计问题，使用部分路段观测流量及历史OD信息，将OD需求估计转化为贝叶斯参数估计问题。通过将贝叶斯法则与共轭先验概念融入模型中，将基于单一路段流量数据估计OD矩阵模型推广为贝叶斯法层次最优化的OD估计建模方法。本发明可靠性和灵活性较高，提出简单易于应用的OD矩阵估计的均衡网络分配方法，为OD需求估计提供基础数据，以达到城市交通运输规划与管理的高效性、精准性目标。

附图说明

图1是一种实施例下本发明所述基于贝叶斯层次最优化的OD矩阵估计方法的流程图。

具体实施方式

下面结合附图和实施例对本发明的技术方案作进一步的说明。

本发明所述的基于贝叶斯层次最优化的OD矩阵估计方法，参考图1，包括如下步骤：

步骤1：获取数据与模型假设；

步骤2：建立无需路径列举的用户均衡-最小方差模型，作为本发明所建层次最优化的下层模型；

步骤3：建立最小二乘法估计，作为本发明所建层次最优化的中层模型；

步骤4：伽马分布的贝叶斯参数估计，作为本发明所建层次最优化的上层模型；

步骤5：构建基于贝叶斯层次最优化的OD矩阵估计模型；

步骤6：求解层次最优化模型。

进一步地，所述步骤1中获取数据与模型假设的具体方式包括：

获取交通网络拓扑结构、先验/历史OD矩阵、路段流量观测集这三种数据类型。其中，OD矩阵即为交通起讫点需求矩阵(Origin-Destination Matrix)。先验OD矩阵为是指获得历史OD矩阵样本的之前，获得的关于OD矩阵的经验和历史资料。历史OD矩阵为收集的过去待研究时间段的道路交通观测OD样本信息。

因为获取的先验/历史OD矩阵、路段流量观测集数据不一定恰好是所研究交通网络范围内的数据，数据常常覆盖更多的交通网络区域。所以需要对先验/历史OD矩阵、路段流量观测集进行筛选。根据交通网络拓扑结构，分别筛选所研究交通网络范围内的先验/历史OD矩阵、路段流量观测集数据，得到网络上相对独立的交通网络拓扑底图和相应的交通数据，并对数据进行清洗和剔除噪音数据。

对于模型假设，本发明假定OD量q

其中，路段l

进一步地，所述步骤2中建立无需路径列举的用户均衡-最小方差模型的具体步骤为：

步骤2-1：加入中间变量OD-路段关联系数β

v

其中，β

步骤2-2：构建基于路段层流的用户均衡模型，方法如下：

步骤2-2-1：构建以路段层流v

其中，Z

步骤2-2-2：建立交通网络中所有结点的流量守恒条件：

其中，δ

步骤2-3：构建具有路段层流唯一解的用户均衡-最小方差模型。在保证用户均衡的条件下，在目标函数中加入以最小方差为原则的第二个目标，重新分布不同路径之间的OD需求，使路径流和路段层流有唯一最优解：

其中，Z为用户均衡-最小方差模型的目标函数；m是路段层流v

进一步地，所述步骤3中建立最小二乘法估计的具体步骤为：

步骤3-1：使用最小二乘法，利用贝叶法计算后验分布。其包含两项目标函数：估计的辅助OD量与先验OD量之间误差的平方和、估计路段流量与观测路段流量之间误差的平方和。具体如下：

其中，Z(d，w)为最小二乘法估计的最小化目标函数，d为存储多个辅助OD流量d

步骤3-2：进一步的，建立估计路段流量w

其中，OD-路段关联系数β

进一步地，所述步骤4中伽马分布的贝叶斯参数估计的具体流程为：假定OD量q

步骤4-1：根据伽马分布性质，计算伽马分布概率密度函数：

其中，x为待估变量，这里指路段流量；θ为伽马分布的形状参数；λ

步骤4-2：计算在样本量为n的样本{X＝x

其中，X为表示路段流量样本合集的向量，x

步骤4-3：通过仿写似然函数，得到伽马分布的共轭先验分布，共轭先验分布反映了在OD矩阵估计前，对OD需求及其分布参数θ和λ

f(θ，λ

其中，根据贝叶斯统计推断原理，参数θ和λ

η

其中

步骤4-4：伽马分布的超参数更新。

根据贝叶斯定理，计算参数θ和λ

其中：

步骤4-5：后验分布参数估计，方法如下：

步骤4-5-1：考虑指数函数在定义域内是单调的，将贝叶斯推断中常见的后验众数作为点估计，即概率密度最大原则，给出参数θ和λ

步骤4-5-2：得到参数θ和λ

E(q

其中，q

进一步地，所述步骤5中构建基于贝叶斯层次最优化的OD矩阵估计模型的具体流程为：根据步骤2至步骤4中所述，通过层次嵌套，构建基于贝叶斯层次最优化的OD矩阵估计模型，模型具体内容如下：

η

其中，式(1)-式(4)为层次最优化模型中的用户均衡-最小方差分配模型，是下层最优化问题，避免了复杂的路径列举即得路段层流v

进一步地，所述步骤6中求解层次最优化模型的具体步骤为：

设计迭代算法框架，求解基于贝叶斯层次最优化的OD矩阵估计模型。模型输入数据为：交通网络拓扑结构、先验/历史OD矩阵、路段流量观测集，输出数据为：估计OD矩阵、估计路段流。基于贝叶斯层次最优化的OD矩阵估计方法的流程图见图1，迭代算法具体步骤如下7步：

(1)初始化：设置初始迭代数i＝0，收敛精度ε，由先验OD需求

(2)求解下层模型：求解UE-最小方差模型，即分配先验OD需求

(3)求解中层模型：最小二乘模型中带入OD-路段关联系数β

(4)更新后验超参数：使用辅助OD需求d

(5)求解上层模型：计算参数后验分布的众数作为参数点估计值θ和λ

(6)计算OD矩阵估计结果：根据伽马分布统计特征，使用参数θ、λ

(7)收敛检验：如果已满足收敛条件即