一种基于模拟退火算法的交通需求量估计方法
一种基于模拟退火算法的交通需求量估计方法
【技术领域】
[0001] 本属于交通诱导系统中的动态交通分配技术领域，特别涉及一种基于模拟退火算 法的交通需求量估计方法。
【背景技术】
[0002] 在交通诱导系统中，最优化路网资源的配置是系统的最终目的。而其计算基础就 是用户的需求量，也就是从某个节点出发到另一个节点的车流总量。
[0003] 对一个城市或者局部的路网而言，对每一个节点到其他所有节点的车流总需求量 排列起来，就得到需求矩阵，也称为路网的0D矩阵。0D矩阵是一个不可观测量，而可以观测 的量是实际产生在路段上的流量。同样地，将每一个节点到周围单步可达的节点上的路段 流量排列在一起，构成流量矩阵，称为路网的F矩阵。
[0004] 对于0D矩阵的估计方法，都是基于可观测的F矩阵进行估计的。从目前流行的方法 来看，大致分为以下几类：
[0005] 1.通过非线性规划的方法。其目标函数是用户通行代价向量的距离，通常选择二 范数，即：
[0006]
[0007] 其约束条件为路网的流量守恒约束、非负约束等等。求解方法为F-W方法，计算搜 索方向，优化搜索步长。其最大的弊病就在于随着路网规模的增加，其计算量急剧膨胀(对 已有的η个节点，多一个节点，就需要计算它到所有η个节点的需求，也需要计算其他节点对 新增节点的需求，总共是2*η多个迭代方向）。
[0008] 2.通过线性规划的方法。其目标函数是用户整体的代价函数之和，由于目标函数 是线性的，约束条件和上面相同也是线性的，因此成为线性规划。但是这种方法不能反映局 部路段的信息，因此存在严重的精度不足的问题。
[0009] 3.通过路网平衡的方法。以上两种方法通过用户的整体代价进行优化，其本质是 系统最优。根据Wardrop平衡原则，其第一是系统最优，第二是用户平衡。路网平衡就是基于 第二条平衡原则提出来的，它指出路径分配的结果是达成用户均衡，因此估计的0D矩阵分 配后将产生相同的路段阻抗函数，基于此进行计算。然而其限制条件较为明显，现实中用户 不会实时按照全局信息最优化自己的出行策略。
[0010] 4.通过最小熵方法。这种方法认为前面的方法没有对路网检测到的流量信息进行 充分的挖掘，因此通过定义信息熵来解决。这个方法的局限是理论依据不足，而且容易受到 噪声的干扰。
[0011]本发明旨在解决0D矩阵的逆推问题，发展一个适合于各种路网结构的方法。如前 面提到的，线性规划和非线性规划的方法目标函数过于简单，求解过程复杂度高;最小熵方 法依赖于对信息的挖掘;路网平衡的方法局限性大。本发明从前两种方法得到启发，提出自 己的目标函数，采用模拟退火的随机优化方法进行求解，精度较高。
【发明内容】
[0012]本发明的目的是提出一种基于模拟退火算法的交通需求量估计方法，其特征在 于，包括两个计算方式，第一个是目标函数，第二个是对结果进行评价，在此基础上实现具 体的交通需求量估计，具体步骤为：
[0013] 1)所述目标函数，提出目标函数为：
[0014]
[0015] 式中的每个量的物理含义为:根据【背景技术】之中对0D矩阵和F矩阵的定义，现在数 学化如下，假设路网规模为η，则：
[0016] (a)0D矩阵:表示路网的交通流量需求，每一个分量0Di,j表示从节点i出发至I」节点j 的车辆需求量；
[0017] (b)F矩阵:表示路网观测到的每个具体路段的车流量，每一个分量Fi,j表示从节点 i出发到相邻的节点j的车辆数，注意到，如果i和j之间并不直接相邻，〇Dlu有可能不为0,但 是是等于0的，因为车辆只能通过其他节点的转发从i到达j ;
[0018] (c)另外，类似的定义户:代表给定0D矩阵，按照配流原则分配的路网的车流量矩 阵。对应于观测到的实际流量分布F，用户的整体代价函数为c，对应分配的P :，用户的整体 代价记为备
[0019]下面对目标函数的两项分别考察：
[0020] (a
:作为目标函数的第一项，也是主项，采用二范数 形式，对所有不同的量的差值求平方和，下标i，j遍历了路网节点，也就是全观测矩阵F和分 配矩阵的所有元素均被计算在内。注意到其本质是对流量做一个最小二乘法的拟合；
[0021] (b) ^ ~則:称为目标函数的修正项，是因为二范数对于稀疏的矩阵计算能力有 限，由于前面所提到的：如果i和j之间并不直接相邻，则F 1U是等于0的，因此F矩阵通常是带 稀疏性质的，引入一范数的计算可以忽略为〇的部分，弥补稀疏的路网流量分布矩阵带来的 不足；
[0022] 2)所述对结果进行评价，首先定义评价准则为差距矩阵的每个元素是相对标准 差，采用其最大者为评价指标，指标越小，算法越好，评价公式为：
[0023]
[0024] 这个指标能评价优化解的可信程度；
[0025] 所述基于模拟退火算法的交通需求量估计方法，其特征在于，具体为单时间段模 拟退火算法估计0D矩阵的具体步骤：
[0026] 步骤1.初始化得到一个解^為^初始化一个常数t，在模拟退火算法之中，这个常 数的名字就叫做温度常数;具体说，温度常数一定要和路网的规模成正相关，以保证模拟退 火算法的全局搜索能力较强，建议采用初值t=10([n/1()])，其中η代表路网规模，[n/10]代表 除以10之后的四舍五入规则；
[0027] 步骤2.根据步骤1得到的解，计算目标函数，具体做法是:根据动态交通分配准则 将估计的0D需求分配得到路段流和用户代价，也就是将分配到具体路段得到的#(|.同 时统计用户群体代价&根据目标函数计算公式，就可以得到步骤1的解对应的目标函数值， 在模拟退火算法之中，每一个解对应的值称之为该解的能量；
[0028] 步骤3.为了使算法的迭代步骤开始在步骤1得到的解或者外循环得到的上一次迭 代的最优解上随机生成另外一个随机解，其生成方式为:采用变步长更新方法:在初始解 上增加或者减去一个不超过给定步长k的整数，建议k的初始值为交通流量均值^^的一 半，其中η代表路网规模；
[0029]步骤4.根据步骤3得到的解，计算其能量，计算方式同步骤2;
[0030]步骤5.如果误差减小，则接受这个解，否则按照概率接受这个解，按概率接受的方 式为：
[0031] 步骤6.内循环:重复步骤3-5达到100次，这时候可以挑选出来这100次里面具有最 低能量值的解，称之为上一代最优解；即是说，因为最低能量值对应的是目标误差函数的最 小化，而在物理世界里，最低能量值通常对应温度下降，因此这个算法的名字就叫做模拟退 火算法；
[0032] 步骤7.外循环：退火，温度下降，k也随之下降，下降常数均为0.99,也就是k = 0.99*k，t = 0.99*t，之后做四舍五入得到新的步长，然后将步骤6得到的上一代最优解进入 步骤3,重复步骤3到7;
[0033] 步骤8.终止:当温度达到下限的时候，或者连续100次得到的解的能量值差小于给 定阈值，或者步长下降为〇,则系统循环结束，此时的解即认为是最优解。否则重复步骤2到 4;马尔科夫概率模型保证了当循环次数趋于无穷的时候，这个解逼近理论最优解。
[0034] 所述步骤7中k要求是整数，而t则不必。
[0035] 所述步骤8中当温度达到下限的时候，步长下降为0时，前后两次的解不会有变化。
[0036] 本发明的有益效果是考虑到实际的路网是动态运行的，交通调度人员总可以通过 分散的车载设备或者先验知识来获取这样的初始信息，从而对连续变化的0D矩阵进行估 计。本专利采用在上一时间序列中进行优化得到的解作为初始化的解，换言之，在上述步 骤1-8之外增加最外层的循环，其循环增量是系统的运行时间。
[0037] 本发明在估计单个规模不超过20的0D矩阵的时候，精度较高，最大误差不超过 20% ;在求解连续时间段的0D矩阵的时候，求解时间在车辆上路的时间之内，说明是一个实 用的算法。并且其最大误差按照置信度的迭代收敛也在逐渐减小
【附图说明】
[0038] 图1为对规模为10的0D矩阵进行时间长度为10的连续估计示意图。
【具体实施方式】
[0039] 本发明提出一种基于模拟退火算法的交通需量估计方法，包括两个计算方式，第 一个是目标函数，第二个是对结果进行评价，在此基础上实现具体的算法流程;具体步骤 为：
[0040] 1)所述目标函数，本专利提出目标函数为：
[0041]
[0042] 式中的每个量的物理含义为:根据【背景技术】之中对0D矩阵和F矩阵的定义，现在数 学化如下，假设路网规模为η，则：
[0043] (a)0D矩阵:表示路网的交通流量需求，每一个分量0Di,j表示从节点i出发到节点j 的车辆需求量；
[0044] (b)F矩阵:表示路网观测到的每个具体路段的车流量，每一个分量Fi,j表示从节点 i出发到相邻的节点j的车辆数，注意到，如果i和j之间并不直接相邻，〇Dlu有可能不为0,但 是是等于0的，因为车辆只能通过其他节点的转发从i到达j ;
[0045] (c)另外，类似的定义代表给定0D矩阵，按照配流原则分配的路网的车流量矩 阵。对应于观测到的实际流量分布F，用户的整体代价函数为c，对应分配的f，用户的整体代 价记为热
[0046]下面对目标函数的两项分别考察：
[0047] (a
作为目标函数的第一项，也是主项，采用二范数 形式，对所有不同的量的差值求平方和，下标i，j遍历了路网节点，也就是全观测矩阵F和分 配矩阵，的所有元素均被计算在内。注意到其本质是对流量做一个最小二乘法的拟合； [0048] 称为目标函数的修正项，是因为二范数对于稀疏的矩阵计算能力有 限，由于我们之间提到的，如果i和j之间并不直接相邻，则F1U是等于0的。因此F矩阵通常是 带稀疏性质的，引入一范数的计算可以忽略为〇的部分，弥补稀疏的路网流量分布矩阵带来 的不足。
[00 49] 2)所述对结果进行评价，首先定义评价准则为差距矩阵的每个元素为相对标准 差，采用其最大者为评价指标，指标越小，算法越好，评价公式为：
[0050]
[0051 ]这个指标能最好地评价优化解的可信程度。其中
[0052] 所述单时间段模拟退火算法估计0D矩阵的具体步骤：
[0053] 步骤1.初始化得到一个解，初始化一个常数t，在模拟退火算法之中，这个常 数的名字就叫做温度常数。具体到我们这个问题，温度常数一定要和路网的规模成正相关， 以保证模拟退火算法的全局搜索能力较强，建议采用初值t = 10 ([n/1()])，其中η代表路网规 模，[η/10]代表除以10之后四舍五入。
[0054] 步骤2.根据步骤1得到的解，计算目标函数，具体做法是:根据动态交通分配准则 将估计的0D需求分配得到路段流和用户代价，也就是将分配到具体路段得到的1?，同 时统计用户群体代价仏根据目标函数计算公式，就可以得到步骤1的解对应的目标函数值， 在模拟退火算法之中，每一个解对应的值称之为该解的能量；
[0055] 步骤3.为了使算法的迭代步骤开始（算法收敛条件之一是前后两代解的差异较 小，见步骤8)，在步骤1(或者外循环得到的上一次迭代的最优解，见步骤7)得到的解上随机 生成另外一个随机解，生成方式为:采用变步长更新方法:在初始解上增加或者减去一个不 超过给定步长k的整数，建议k的初始值为交通流量均$的一半，其中η代表路网规 模；
[0056] 步骤4.根据步骤3得到的解，计算其能量，计算方式同步骤2;
[0057] 步骤5.如果误差减小，则接受这个解，否则按照概率接受这个解，按概率接受的方 式为：
[0058]步骤6.内循环:重复步骤3-5达到100次，这时候可以挑选出来这100次里面具有最 低能量值(因为最低能量值对应的是目标误差函数的最小化，而在物理世界里，最低能量值 通常对应温度下降，因此这个算法的名字就叫做模拟退火算法！）的解，称之为上一代最优 解；
[0059] 步骤7.外循环：退火，温度下降，k也随之下降，下降常数均为0.99,也就是k = 0.99*k，t = 0.99*t，之后做四舍五入得到新的步长（因为k要求是整数，t则不必），然后将步 骤6得到的上一代最优解进入步骤3，重复步骤3到7;
[0060] 步骤8.终止:当温度达到下限的时候，或者连续100次得到的解的能量值差小于给 定阈值，或者步长下降为〇(此时前后两次的解不会有变化），则系统循环结束，此时的解即 认为是最优解。否则重复步骤2到4;马尔科夫概率模型保证了当循环次数趋于无穷的时候， 这个解逼近理论最优解。
[0061] 本发明考虑到实际的路网是动态运行的，交通调度人员总可以通过分散的车载设 备或者先验知识来获取这样的初始信息，从而对连续变化的0D矩阵进行估计。本专利采用 在上一时间序列中进行优化得到的解作为初始化的解，换言之，在上述步骤1-8之外增加最 外层的循环，其循环增量是系统的运行时间。
[0062] 实施例
[0063] 在实际的过程中，从分散的车载终端获取0D信息，从而我们可以迭代计算两种信 息的置信度。
[0064] 具体操作流程为：（1)根据初始种子利用模拟退火算法获取优化解；（2)根据其他 信息来源获取部分信息；（3)根据置信度水平计算结果，根据实际结果计算两种方式的置信 度，更新置信度水平。
[0065] 1.对于单个0D矩阵的估计
[0066]假设已知路网的需求水平，也就是每个0D对平均的需求量，作为初始种子(例如在 程序中，设置0D种子是一个除了对角线元素之外其余均为40的矩阵）。仿真数据对0D对进行 随机设置，使其均值落在这附近(例如在程序中，在每对0D对上加上了随机数）。
[0067] 根据路网规模和平均服务水平选择初始温度和终止温度(例如在程序中，终止温 度一般选择为1〇〇,初始温度一般选择为然后进入循环。
[0068] 循环过程中，由上一个解随机生成下一个解，如果误差函数随之减小，那么认为这 个方向是一个可行方向，下一次依然按照这个方向进行随机搜索(体现在程序中，也就是不 改变正负号）。如果误差函数并不减小，那么认为这个方向不是可行方向，下一次的方向重 新进行随机生成。
[0069] 2.连续时间段的0D矩阵估计
[0070] 考虑到实际的过程中，我们可以从其他渠道(例如分散的车载终端)获取0D信息， 因此我们有两个信息渠道。从而我们可以迭代计算两种信息的置信度。对规模为5、10的0D 矩阵进行了估计，比较结果如表1所示。
[0071]表1为分别对规模为5、10的0D矩阵进行了估计，其中估计矩阵式本算法对原始矩 阵的一个估计结果：
[0072]
【主权项】
1. 一种基于模拟退火算法的交通需求量估计方法，其特征在于，包括两个计算方式，第 一个是目标函数，第二个是对结果进行评价，在此基础上实现具体的交通需求量估计，具体 步骤为： 1) 所述目标函数，提出目标函数为：式中的每个量的物理含义为:根据【背景技术】之中对OD矩阵和F矩阵的定义，现在数学化 如下，假设路网规模为n，则： (a) OD矩阵:表示路网的交通流量需求，每一个分量ODi, j表示从节点i出发到节点j的车 辆需求量； (b) F矩阵:表示路网观测到的每个具体路段的车流量，每一个分量Fi, j表示从节点i出 发到相邻的节点j的车辆数，注意到，如果i和j之间并不直接相邻，ODiu有可能不为0,但是 F 1, j是等于0的，因为车辆只能通过其他节点的转发从i到达j ; (c) 另外，类似的定义#:代表给定OD矩阵，按照配流原则分配的路网的车流量矩阵，对 应于观测到的实际流量分布F，用户的整体代价函数为c，对应分配的f，用户的整体代价记 为S; 下面对目标函数的两项分别考察：作为目标函数的第一项，也是主项，采用二范 数形式，对所有不同的量的差值求平方和，下标i，j遍历了路网节点，也就是全观测矩阵F和 分配矩阵#丨的所有元素均被计算在内，注意到其本质是对流量做一个最小二乘法的拟合； (b)鉍一 ai:称为目标函数的修正项，是因为二范数对于稀疏的矩阵计算能力有限，由 于前面所提到的：如果i和j之间并不直接相邻，则Fiu是等于0的，因此F矩阵通常是带稀疏 性质的，引入一范数的计算可以忽略为〇的部分，弥补稀疏的路网流量分布矩阵带来的不 足； 2) 所述对结果进行评价，首先定义评价准则为差距矩阵的每个元素是相对标准差，采 用其最大者为评价指标，指标越小，算法越好，评价公式为：这个指标能评价优化解?^的可信程度。2. 根据权利要求1所述基于模拟退火算法的交通需求量估计方法，其特征在于，具体为 单时间段模拟退火算法估计OD矩阵的具体步骤： 步骤1.初始化得到一个解，初始化一个常数t，在模拟退火算法之中，这个常数的 名字就叫做温度常数;具体说，温度常数一定要和路网的规模成正相关，以保证模拟退火算 法的全局搜索能力较强，建议采用初值t = 10([n/1()])，其中η代表路网规模，[n/10]代表除以 10之后的四舍五入规则； 步骤2.根据步骤1得到的解，计算目标函数，具体做法是:根据动态交通分配准则将估 计的OD需求分配得到路段流和用户代价，也就是将分配到具体路段得到的flj,同时统 计用户群体代价适，根据目标函数计算公式，就可以得到步骤1的解对应的目标函数值，在模 拟退火算法之中，每一个解对应的值称之为该解的能量； 步骤3.为了使算法的迭代步骤开始在步骤1得到的解或者外循环得到的上一次迭代的 最优解上随机生成另外一个随机解，其生成方式为:采用变步长更新方法:在初始解上增加 或者减去一个不超过给定步长k的整数，建议k的初始值为交通流量均;的一半，其 中η代表路网规模； 步骤4.根据步骤3得到的解，计算其能量，计算方式同步骤2; 步骤5 .如果误差减小，则接受这个解，否则按照概率接受这个解，按概率接受的方式 为： 步骤6.内循环:重复步骤3-5达到100次，这时候可以挑选出来这100次里面具有最低能 量值的解，称之为上一代最优解；即是说，因为最低能量值对应的是目标误差函数的最小 化，而在物理世界里，最低能量值通常对应温度下降，因此这个算法的名字就叫做模拟退火 算法； 步骤7.外循环:退火，温度下降，k也随之下降，下降常数均为0.99，也就是k = 0.99*k，t = 0.99*t，之后做四舍五入得到新的步长，然后将步骤6得到的上一代最优解进入步骤3,重 复步骤3到7; 步骤8.终止：当温度达到下限的时候，或者连续100次得到的解的能量值差小于给定阈 值，或者步长下降为〇,则系统循环结束，此时的解即认为是最优解，否则重复步骤2到4;马 尔科夫概率模型保证了当循环次数趋于无穷的时候，这个解逼近理论最优解。3. 根据权利要求2所述基于模拟退火算法的交通需求量估计方法，其特征在于，所述步 骤7中k要求是整数，而t则不必。4. 根据权利要求2所述基于模拟退火算法的交通需求量估计方法，其特征在于，所述步 骤8中当温度达到下限的时候，步长下降为0时，前后两次的解不会有变化。
【专利摘要】本发明公开了属于交通诱导系统中的动态交通分配技术领域的一种基于模拟退火算法的交通需求量估计方法。包括两个计算方式，第一个是目标函数，第二个是对结果进行评价，具体操作流程为：(1)根据初始种子利用模拟退火算法获取优化解；(2)根据其他信息来源获取部分信息；(3)根据置信度水平计算结果，根据实际结果计算两种方式的置信度，更新置信度水平。本发明的有益效果是考虑到实际的路网是动态运行的，交通调度人员总可以通过分散的车载设备或者先验知识来获取这样的初始信息，从而对连续变化的OD矩阵进行估计。
【IPC分类】G06Q50/30, G06Q10/04
【公开号】CN105488581
【申请号】CN201510781021
【发明人】胡坚明, 裴欣, 张似衡, 张毅, 谢旭东, 李力, 姚丹亚
【申请人】清华大学
【公开日】2016年4月13日
【申请日】2015年11月13日
【技术领域】
[0001] 本属于交通诱导系统中的动态交通分配技术领域，特别涉及一种基于模拟退火算 法的交通需求量估计方法。
【背景技术】
[0002] 在交通诱导系统中，最优化路网资源的配置是系统的最终目的。而其计算基础就 是用户的需求量，也就是从某个节点出发到另一个节点的车流总量。
[0003] 对一个城市或者局部的路网而言，对每一个节点到其他所有节点的车流总需求量 排列起来，就得到需求矩阵，也称为路网的0D矩阵。0D矩阵是一个不可观测量，而可以观测 的量是实际产生在路段上的流量。同样地，将每一个节点到周围单步可达的节点上的路段 流量排列在一起，构成流量矩阵，称为路网的F矩阵。
[0004] 对于0D矩阵的估计方法，都是基于可观测的F矩阵进行估计的。从目前流行的方法 来看，大致分为以下几类：
[0005] 1.通过非线性规划的方法。其目标函数是用户通行代价向量的距离，通常选择二 范数，即：
[0006]
[0007] 其约束条件为路网的流量守恒约束、非负约束等等。求解方法为F-W方法，计算搜 索方向，优化搜索步长。其最大的弊病就在于随着路网规模的增加，其计算量急剧膨胀(对 已有的η个节点，多一个节点，就需要计算它到所有η个节点的需求，也需要计算其他节点对 新增节点的需求，总共是2*η多个迭代方向）。
[0008] 2.通过线性规划的方法。其目标函数是用户整体的代价函数之和，由于目标函数 是线性的，约束条件和上面相同也是线性的，因此成为线性规划。但是这种方法不能反映局 部路段的信息，因此存在严重的精度不足的问题。
[0009] 3.通过路网平衡的方法。以上两种方法通过用户的整体代价进行优化，其本质是 系统最优。根据Wardrop平衡原则，其第一是系统最优，第二是用户平衡。路网平衡就是基于 第二条平衡原则提出来的，它指出路径分配的结果是达成用户均衡，因此估计的0D矩阵分 配后将产生相同的路段阻抗函数，基于此进行计算。然而其限制条件较为明显，现实中用户 不会实时按照全局信息最优化自己的出行策略。
[0010] 4.通过最小熵方法。这种方法认为前面的方法没有对路网检测到的流量信息进行 充分的挖掘，因此通过定义信息熵来解决。这个方法的局限是理论依据不足，而且容易受到 噪声的干扰。
[0011]本发明旨在解决0D矩阵的逆推问题，发展一个适合于各种路网结构的方法。如前 面提到的，线性规划和非线性规划的方法目标函数过于简单，求解过程复杂度高;最小熵方 法依赖于对信息的挖掘;路网平衡的方法局限性大。本发明从前两种方法得到启发，提出自 己的目标函数，采用模拟退火的随机优化方法进行求解，精度较高。
【发明内容】
[0012]本发明的目的是提出一种基于模拟退火算法的交通需求量估计方法，其特征在 于，包括两个计算方式，第一个是目标函数，第二个是对结果进行评价，在此基础上实现具 体的交通需求量估计，具体步骤为：
[0013] 1)所述目标函数，提出目标函数为：
[0014]
[0015] 式中的每个量的物理含义为:根据【背景技术】之中对0D矩阵和F矩阵的定义，现在数 学化如下，假设路网规模为η，则：
[0016] (a)0D矩阵:表示路网的交通流量需求，每一个分量0Di,j表示从节点i出发至I」节点j 的车辆需求量；
[0017] (b)F矩阵:表示路网观测到的每个具体路段的车流量，每一个分量Fi,j表示从节点 i出发到相邻的节点j的车辆数，注意到，如果i和j之间并不直接相邻，〇Dlu有可能不为0,但 是是等于0的，因为车辆只能通过其他节点的转发从i到达j ;
[0018] (c)另外，类似的定义户:代表给定0D矩阵，按照配流原则分配的路网的车流量矩 阵。对应于观测到的实际流量分布F，用户的整体代价函数为c，对应分配的P :，用户的整体 代价记为备
[0019]下面对目标函数的两项分别考察：
[0020] (a
:作为目标函数的第一项，也是主项，采用二范数 形式，对所有不同的量的差值求平方和，下标i，j遍历了路网节点，也就是全观测矩阵F和分 配矩阵的所有元素均被计算在内。注意到其本质是对流量做一个最小二乘法的拟合；
[0021] (b) ^ ~則:称为目标函数的修正项，是因为二范数对于稀疏的矩阵计算能力有 限，由于前面所提到的：如果i和j之间并不直接相邻，则F 1U是等于0的，因此F矩阵通常是带 稀疏性质的，引入一范数的计算可以忽略为〇的部分，弥补稀疏的路网流量分布矩阵带来的 不足；
[0022] 2)所述对结果进行评价，首先定义评价准则为差距矩阵的每个元素是相对标准 差，采用其最大者为评价指标，指标越小，算法越好，评价公式为：
[0023]
[0024] 这个指标能评价优化解的可信程度；
[0025] 所述基于模拟退火算法的交通需求量估计方法，其特征在于，具体为单时间段模 拟退火算法估计0D矩阵的具体步骤：
[0026] 步骤1.初始化得到一个解^為^初始化一个常数t，在模拟退火算法之中，这个常 数的名字就叫做温度常数;具体说，温度常数一定要和路网的规模成正相关，以保证模拟退 火算法的全局搜索能力较强，建议采用初值t=10([n/1()])，其中η代表路网规模，[n/10]代表 除以10之后的四舍五入规则；
[0027] 步骤2.根据步骤1得到的解，计算目标函数，具体做法是:根据动态交通分配准则 将估计的0D需求分配得到路段流和用户代价，也就是将分配到具体路段得到的#(|.同 时统计用户群体代价&根据目标函数计算公式，就可以得到步骤1的解对应的目标函数值， 在模拟退火算法之中，每一个解对应的值称之为该解的能量；
[0028] 步骤3.为了使算法的迭代步骤开始在步骤1得到的解或者外循环得到的上一次迭 代的最优解上随机生成另外一个随机解，其生成方式为:采用变步长更新方法:在初始解 上增加或者减去一个不超过给定步长k的整数，建议k的初始值为交通流量均值^^的一 半，其中η代表路网规模；
[0029]步骤4.根据步骤3得到的解，计算其能量，计算方式同步骤2;
[0030]步骤5.如果误差减小，则接受这个解，否则按照概率接受这个解，按概率接受的方 式为：
[0031] 步骤6.内循环:重复步骤3-5达到100次，这时候可以挑选出来这100次里面具有最 低能量值的解，称之为上一代最优解；即是说，因为最低能量值对应的是目标误差函数的最 小化，而在物理世界里，最低能量值通常对应温度下降，因此这个算法的名字就叫做模拟退 火算法；
[0032] 步骤7.外循环：退火，温度下降，k也随之下降，下降常数均为0.99,也就是k = 0.99*k，t = 0.99*t，之后做四舍五入得到新的步长，然后将步骤6得到的上一代最优解进入 步骤3,重复步骤3到7;
[0033] 步骤8.终止:当温度达到下限的时候，或者连续100次得到的解的能量值差小于给 定阈值，或者步长下降为〇,则系统循环结束，此时的解即认为是最优解。否则重复步骤2到 4;马尔科夫概率模型保证了当循环次数趋于无穷的时候，这个解逼近理论最优解。
[0034] 所述步骤7中k要求是整数，而t则不必。
[0035] 所述步骤8中当温度达到下限的时候，步长下降为0时，前后两次的解不会有变化。
[0036] 本发明的有益效果是考虑到实际的路网是动态运行的，交通调度人员总可以通过 分散的车载设备或者先验知识来获取这样的初始信息，从而对连续变化的0D矩阵进行估 计。本专利采用在上一时间序列中进行优化得到的解作为初始化的解，换言之，在上述步 骤1-8之外增加最外层的循环，其循环增量是系统的运行时间。
[0037] 本发明在估计单个规模不超过20的0D矩阵的时候，精度较高，最大误差不超过 20% ;在求解连续时间段的0D矩阵的时候，求解时间在车辆上路的时间之内，说明是一个实 用的算法。并且其最大误差按照置信度的迭代收敛也在逐渐减小
【附图说明】
[0038] 图1为对规模为10的0D矩阵进行时间长度为10的连续估计示意图。
【具体实施方式】
[0039] 本发明提出一种基于模拟退火算法的交通需量估计方法，包括两个计算方式，第 一个是目标函数，第二个是对结果进行评价，在此基础上实现具体的算法流程;具体步骤 为：
[0040] 1)所述目标函数，本专利提出目标函数为：
[0041]
[0042] 式中的每个量的物理含义为:根据【背景技术】之中对0D矩阵和F矩阵的定义，现在数 学化如下，假设路网规模为η，则：
[0043] (a)0D矩阵:表示路网的交通流量需求，每一个分量0Di,j表示从节点i出发到节点j 的车辆需求量；
[0044] (b)F矩阵:表示路网观测到的每个具体路段的车流量，每一个分量Fi,j表示从节点 i出发到相邻的节点j的车辆数，注意到，如果i和j之间并不直接相邻，〇Dlu有可能不为0,但 是是等于0的，因为车辆只能通过其他节点的转发从i到达j ;
[0045] (c)另外，类似的定义代表给定0D矩阵，按照配流原则分配的路网的车流量矩 阵。对应于观测到的实际流量分布F，用户的整体代价函数为c，对应分配的f，用户的整体代 价记为热
[0046]下面对目标函数的两项分别考察：
[0047] (a
作为目标函数的第一项，也是主项，采用二范数 形式，对所有不同的量的差值求平方和，下标i，j遍历了路网节点，也就是全观测矩阵F和分 配矩阵，的所有元素均被计算在内。注意到其本质是对流量做一个最小二乘法的拟合； [0048] 称为目标函数的修正项，是因为二范数对于稀疏的矩阵计算能力有 限，由于我们之间提到的，如果i和j之间并不直接相邻，则F1U是等于0的。因此F矩阵通常是 带稀疏性质的，引入一范数的计算可以忽略为〇的部分，弥补稀疏的路网流量分布矩阵带来 的不足。
[00 49] 2)所述对结果进行评价，首先定义评价准则为差距矩阵的每个元素为相对标准 差，采用其最大者为评价指标，指标越小，算法越好，评价公式为：
[0050]
[0051 ]这个指标能最好地评价优化解的可信程度。其中
[0052] 所述单时间段模拟退火算法估计0D矩阵的具体步骤：
[0053] 步骤1.初始化得到一个解，初始化一个常数t，在模拟退火算法之中，这个常 数的名字就叫做温度常数。具体到我们这个问题，温度常数一定要和路网的规模成正相关， 以保证模拟退火算法的全局搜索能力较强，建议采用初值t = 10 ([n/1()])，其中η代表路网规 模，[η/10]代表除以10之后四舍五入。
[0054] 步骤2.根据步骤1得到的解，计算目标函数，具体做法是:根据动态交通分配准则 将估计的0D需求分配得到路段流和用户代价，也就是将分配到具体路段得到的1?，同 时统计用户群体代价仏根据目标函数计算公式，就可以得到步骤1的解对应的目标函数值， 在模拟退火算法之中，每一个解对应的值称之为该解的能量；
[0055] 步骤3.为了使算法的迭代步骤开始（算法收敛条件之一是前后两代解的差异较 小，见步骤8)，在步骤1(或者外循环得到的上一次迭代的最优解，见步骤7)得到的解上随机 生成另外一个随机解，生成方式为:采用变步长更新方法:在初始解上增加或者减去一个不 超过给定步长k的整数，建议k的初始值为交通流量均$的一半，其中η代表路网规 模；
[0056] 步骤4.根据步骤3得到的解，计算其能量，计算方式同步骤2;
[0057] 步骤5.如果误差减小，则接受这个解，否则按照概率接受这个解，按概率接受的方 式为：
[0058]步骤6.内循环:重复步骤3-5达到100次，这时候可以挑选出来这100次里面具有最 低能量值(因为最低能量值对应的是目标误差函数的最小化，而在物理世界里，最低能量值 通常对应温度下降，因此这个算法的名字就叫做模拟退火算法！）的解，称之为上一代最优 解；
[0059] 步骤7.外循环：退火，温度下降，k也随之下降，下降常数均为0.99,也就是k = 0.99*k，t = 0.99*t，之后做四舍五入得到新的步长（因为k要求是整数，t则不必），然后将步 骤6得到的上一代最优解进入步骤3，重复步骤3到7;
[0060] 步骤8.终止:当温度达到下限的时候，或者连续100次得到的解的能量值差小于给 定阈值，或者步长下降为〇(此时前后两次的解不会有变化），则系统循环结束，此时的解即 认为是最优解。否则重复步骤2到4;马尔科夫概率模型保证了当循环次数趋于无穷的时候， 这个解逼近理论最优解。
[0061] 本发明考虑到实际的路网是动态运行的，交通调度人员总可以通过分散的车载设 备或者先验知识来获取这样的初始信息，从而对连续变化的0D矩阵进行估计。本专利采用 在上一时间序列中进行优化得到的解作为初始化的解，换言之，在上述步骤1-8之外增加最 外层的循环，其循环增量是系统的运行时间。
[0062] 实施例
[0063] 在实际的过程中，从分散的车载终端获取0D信息，从而我们可以迭代计算两种信 息的置信度。
[0064] 具体操作流程为：（1)根据初始种子利用模拟退火算法获取优化解；（2)根据其他 信息来源获取部分信息；（3)根据置信度水平计算结果，根据实际结果计算两种方式的置信 度，更新置信度水平。
[0065] 1.对于单个0D矩阵的估计
[0066]假设已知路网的需求水平，也就是每个0D对平均的需求量，作为初始种子(例如在 程序中，设置0D种子是一个除了对角线元素之外其余均为40的矩阵）。仿真数据对0D对进行 随机设置，使其均值落在这附近(例如在程序中，在每对0D对上加上了随机数）。
[0067] 根据路网规模和平均服务水平选择初始温度和终止温度(例如在程序中，终止温 度一般选择为1〇〇,初始温度一般选择为然后进入循环。
[0068] 循环过程中，由上一个解随机生成下一个解，如果误差函数随之减小，那么认为这 个方向是一个可行方向，下一次依然按照这个方向进行随机搜索(体现在程序中，也就是不 改变正负号）。如果误差函数并不减小，那么认为这个方向不是可行方向，下一次的方向重 新进行随机生成。
[0069] 2.连续时间段的0D矩阵估计
[0070] 考虑到实际的过程中，我们可以从其他渠道(例如分散的车载终端)获取0D信息， 因此我们有两个信息渠道。从而我们可以迭代计算两种信息的置信度。对规模为5、10的0D 矩阵进行了估计，比较结果如表1所示。
[0071]表1为分别对规模为5、10的0D矩阵进行了估计，其中估计矩阵式本算法对原始矩 阵的一个估计结果：
[0072]
【主权项】
1. 一种基于模拟退火算法的交通需求量估计方法，其特征在于，包括两个计算方式，第 一个是目标函数，第二个是对结果进行评价，在此基础上实现具体的交通需求量估计，具体 步骤为： 1) 所述目标函数，提出目标函数为：式中的每个量的物理含义为:根据【背景技术】之中对OD矩阵和F矩阵的定义，现在数学化 如下，假设路网规模为n，则： (a) OD矩阵:表示路网的交通流量需求，每一个分量ODi, j表示从节点i出发到节点j的车 辆需求量； (b) F矩阵:表示路网观测到的每个具体路段的车流量，每一个分量Fi, j表示从节点i出 发到相邻的节点j的车辆数，注意到，如果i和j之间并不直接相邻，ODiu有可能不为0,但是 F 1, j是等于0的，因为车辆只能通过其他节点的转发从i到达j ; (c) 另外，类似的定义#:代表给定OD矩阵，按照配流原则分配的路网的车流量矩阵，对 应于观测到的实际流量分布F，用户的整体代价函数为c，对应分配的f，用户的整体代价记 为S; 下面对目标函数的两项分别考察：作为目标函数的第一项，也是主项，采用二范 数形式，对所有不同的量的差值求平方和，下标i，j遍历了路网节点，也就是全观测矩阵F和 分配矩阵#丨的所有元素均被计算在内，注意到其本质是对流量做一个最小二乘法的拟合； (b)鉍一 ai:称为目标函数的修正项，是因为二范数对于稀疏的矩阵计算能力有限，由 于前面所提到的：如果i和j之间并不直接相邻，则Fiu是等于0的，因此F矩阵通常是带稀疏 性质的，引入一范数的计算可以忽略为〇的部分，弥补稀疏的路网流量分布矩阵带来的不 足； 2) 所述对结果进行评价，首先定义评价准则为差距矩阵的每个元素是相对标准差，采 用其最大者为评价指标，指标越小，算法越好，评价公式为：这个指标能评价优化解?^的可信程度。2. 根据权利要求1所述基于模拟退火算法的交通需求量估计方法，其特征在于，具体为 单时间段模拟退火算法估计OD矩阵的具体步骤： 步骤1.初始化得到一个解，初始化一个常数t，在模拟退火算法之中，这个常数的 名字就叫做温度常数;具体说，温度常数一定要和路网的规模成正相关，以保证模拟退火算 法的全局搜索能力较强，建议采用初值t = 10([n/1()])，其中η代表路网规模，[n/10]代表除以 10之后的四舍五入规则； 步骤2.根据步骤1得到的解，计算目标函数，具体做法是:根据动态交通分配准则将估 计的OD需求分配得到路段流和用户代价，也就是将分配到具体路段得到的flj,同时统 计用户群体代价适，根据目标函数计算公式，就可以得到步骤1的解对应的目标函数值，在模 拟退火算法之中，每一个解对应的值称之为该解的能量； 步骤3.为了使算法的迭代步骤开始在步骤1得到的解或者外循环得到的上一次迭代的 最优解上随机生成另外一个随机解，其生成方式为:采用变步长更新方法:在初始解上增加 或者减去一个不超过给定步长k的整数，建议k的初始值为交通流量均;的一半，其 中η代表路网规模； 步骤4.根据步骤3得到的解，计算其能量，计算方式同步骤2; 步骤5 .如果误差减小，则接受这个解，否则按照概率接受这个解，按概率接受的方式 为： 步骤6.内循环:重复步骤3-5达到100次，这时候可以挑选出来这100次里面具有最低能 量值的解，称之为上一代最优解；即是说，因为最低能量值对应的是目标误差函数的最小 化，而在物理世界里，最低能量值通常对应温度下降，因此这个算法的名字就叫做模拟退火 算法； 步骤7.外循环:退火，温度下降，k也随之下降，下降常数均为0.99，也就是k = 0.99*k，t = 0.99*t，之后做四舍五入得到新的步长，然后将步骤6得到的上一代最优解进入步骤3,重 复步骤3到7; 步骤8.终止：当温度达到下限的时候，或者连续100次得到的解的能量值差小于给定阈 值，或者步长下降为〇,则系统循环结束，此时的解即认为是最优解，否则重复步骤2到4;马 尔科夫概率模型保证了当循环次数趋于无穷的时候，这个解逼近理论最优解。3. 根据权利要求2所述基于模拟退火算法的交通需求量估计方法，其特征在于，所述步 骤7中k要求是整数，而t则不必。4. 根据权利要求2所述基于模拟退火算法的交通需求量估计方法，其特征在于，所述步 骤8中当温度达到下限的时候，步长下降为0时，前后两次的解不会有变化。
【专利摘要】本发明公开了属于交通诱导系统中的动态交通分配技术领域的一种基于模拟退火算法的交通需求量估计方法。包括两个计算方式，第一个是目标函数，第二个是对结果进行评价，具体操作流程为：(1)根据初始种子利用模拟退火算法获取优化解；(2)根据其他信息来源获取部分信息；(3)根据置信度水平计算结果，根据实际结果计算两种方式的置信度，更新置信度水平。本发明的有益效果是考虑到实际的路网是动态运行的，交通调度人员总可以通过分散的车载设备或者先验知识来获取这样的初始信息，从而对连续变化的OD矩阵进行估计。
【IPC分类】G06Q50/30, G06Q10/04
【公开号】CN105488581
【申请号】CN201510781021
【发明人】胡坚明, 裴欣, 张似衡, 张毅, 谢旭东, 李力, 姚丹亚
【申请人】清华大学
【公开日】2016年4月13日
【申请日】2015年11月13日
最新回复(0)