Open Journal of Transportation Technologies 交通技术, 2013, 2, 147-153 http://dx.doi.org/10.12677/ojtt.2013.22027 Published Online May 2013 (http://www.hanspub.org/journal/ojtt.html) Compare of the Estimation Method of Matrix Based on Maximum Entropy Model Wenjun Hu1, Xizhao Zhou2 1Shanghai Zhongqiao College, Shanghai 2Shanghai Maritime University, Shanghai Email: huwenjun0@yahoo.com.cn Received: Mar. 6th, 2013; revised: Apr. 1st, 2013; accepted: Apr. 10th, 2013 Copyright © 2013 Wenjun Hu, Xizhao Zhou. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract: Maximum Entropy model is an efficient and simple model to estimate origin destination matrix. After introducing the formation and principle of basic maximum entropy model, this article uses Stirling ap- proximate formula and log sum approximate formula to simplify basic model and obtains six improved mod- els. Then it tests seven models in two networks under three different conditions, namely the total demand is fixed or unfixed, the prior matrix is feasible or unfeasible and the node continuity condition is satisfied or unsatisfied and compare the properties of these models. The results show that they show uniform in searching for optimum solutions. However, several formations produce large errors under some circumstances, which restrict their applications in reality. Keywords: Transportation Engineering; Maximum Entropy Model Estimation; Comparative Study; Trip Distribution Matrix 出行分布矩阵的极大熵估计法比较研究 胡文君 1,周溪召 2 1上海中侨学院,上海 2上海海事大学,上海 Email: huwenjun0@yahoo.com.cn 收稿日期:2013 年3月6日;修回日期:2013 年4月1日;录用日期:2013年4月10 日 摘 要:极大熵方法是用于估计起讫点间出行分布矩阵的一种高效简便的方法。在介绍基础极大熵公 式的形式和原理后,应用Stirling近似公式和对数近似公式简化基本极大熵公式,得出六个改进的极大 熵公式,在总出行需求固定或可变、先验 OD 矩阵可行或不可行、节点流连续 条件满足或不满足 的三种 不同的情况下在两个网络上测试七个极大熵公式,对其特征进行比较。结果表明七个目标函数在寻优 时表现出一致性,但是在一些特定的情况下,有几个公式产生较 大误差,使得其在实际使用中受 到限制。 关键词:交通工程;极大熵估计;比较研究;出行分布矩阵 1. 引言 描述车辆出行起始点和终点在空间上分布的出 行分布矩阵是交通规划、管理与控制的基础数据。 传统获取起讫点出行分布矩阵的方法是进行大规模 的抽样调查,但这项工作需消耗极大的人力、财力和 时间,其耗费的资源和组织上的难度是可以想象 Copyright © 2013 Hanspub 147 出行分布矩阵的极大熵估计法比较研究 的,而且直接调查的矩阵存在抽样率低、抽样统计精 度不高、数据更新周期长度等问题。当前,由于城市 交通监控系统的普及,路段交通流量成为较容易获取 的信息,因此通过观测到得路段交通流量来估计未知 出行分布矩阵,是一种效率高、周期短的矩阵获取方 法。然而,从路段交通流量来估计未知出行分布矩阵, 会遇到几个实际问题。其一,一般来说,OD 对的个 数远远大于路段的个数,仅仅通过路段流量来估计矩 阵,无法得到唯一解,因而还需加上先验信息(如历史 出行分布矩阵)。其二,在实际中,很少有一个 OD 需 求完全观测路段流量,一组观测数据中的路段流量不 一定是节点连续的,因为数据收集难免会有误差,而 且数据收集往往不在同一地点进行。其三,实际出行 分布矩阵未知,很难验证一次 OD 估计的优劣,只能 间接地以观测流量与分配流量比较作为衡量优劣的 指标。 为了应对以上种种问题,国内外研究者提出许多 出行分布矩阵估计模型,如基于热力学熵原理的极大 熵(Maximum Entropy)模型,以最小二乘原理为基础的 最小二乘(Least Square)模型,以信息论原理为基础的 最小信息量(Minimum Information)模型以及极大似然 (Maximum Likelihood)模型和重力(Gravity)[1-3]模型等。 在众多 OD 矩阵估计模型中,极大熵模型因其模 型结构简单、原理明确,已被大部分学者所认同,所 以本文一开始就提出并阐述极大熵OD估计模型的基 本公式和内在原理,然后提出以其为基础所作的一系 列简化假设和改进公式,接着分别以五路段网络和二 路段网络两个简单的网络为例,比较三种不同的情况 下1) 总出行需求固定或可变;2) 先验OD 矩阵可行 或不可行;3) 节点流连续条件满足或不满足,各个极 大熵 OD 估计公式所获得的最优解的特征和变化趋 势,最后给出比较的结论。 2. 极大熵模型 2.1. 没有先验矩阵的极大熵模型 极大熵模型认为车辆的出行是随机的。若将车辆 在OD 对ij间的出行看作一次随机事件,则事件的总 次数为[4]: ij ij TT (1) 根据排列组合,在所有的事件中这一事件发生的 机会为: ! ! ij ij ij T ZT T (2) 直观上 ij Z T越大, 出现的可能性越大。可以 证实,这一直观想象符合极大熵原理,一般取为 Max ij T ij Z T。 2.2. 具有先验矩阵的极大熵模型 在实际问题中,常常会得到一个旧的 OD 矩阵。 由于交通环境的变化,改变了 OD 出行分布情况,此 时可借助先验信息(如历史 OD 矩阵),加上新的路段 观测流量来获得一个新的 OD矩阵。 给定作为一个先验的 OD 矩阵,不一定要完 全对应观测路段流量,但可用来拓展极大熵函数(2), 使其成为带有先验矩阵的极大熵模型(3 )[5]: ij tij t 1 ! Max ,! Tij ij ijij ij ij ij ij ij T ZTt T t t (3) 无论是目标函数(2)还是(3),都应满足路段流量约 束关系,所以一般应加上约束条件: a aij ij ij x Tp (4) 式中, a x 为路段 a的观测流量,为从起点i到终点 j的实际出行次数,为从起点 i驶向终点 j的车辆 经过路段 a的比例。 ij T a ij p 3. 对基础极大熵公式的改进和变换 3.1. 改进极大熵公式 基础极大熵公式(2)和(3) 直接作为目标函数计算 起来非常复杂,因为阶乘运算会产生很大的数字,所 以一般采用近似方式将其简化[6] 。最常用是采用 Stirling 近似公式: ln !ln x xxx t (5) 在(3)两边取对数后进行简化,其中 , ij ij ij ij TTt : 2 Max,lnln ij ij ijij ij ij T T ZTt TT tt (6) Copyright © 2013 Hanspub 148 出行分布矩阵的极大熵估计法比较研究 如果进一步把路网中的总需求或者叫总出行次 数T看做常数,并去掉这一项,则可进一步简化为如 下的 Willumsen[7]基础公式: 3 Max,ln ij ij ijij ij ij T ZTtT t (7) 另一种修正方式是假设总出行次数T固定,T和 t两项几乎相等,将公式(7)中的某一部分减去 再加 上 进行修正: ij T ij t 4 Max,ln ij ij ijijijij ij ij T Z TtTT t t (8) 有些改进极大熵公式除使用 Stirling 近似外,更 进一步采用对数近似公式(9)将(8) 简化为 Willumsen 改进公式(10),若再假设 ij ij tT ,则成为 Ortuza & Willumsen公式(11) : 23 111 11 ln 23 xx x xxx x (9) 2 5 1 Max ,2 ij ijijij ij ij ZTtT t T (10) 2 6 1 Max ,2 ij ijijij ij ij ZTtT t t (11) 极大熵模型除了这些目标函数外还需加上路段 流量的约束条件(4),把约束(4 )加到目标函数中去的最 容易的方式是使用拉格朗日乘子,可将有约束的目标 函数转化为等价的无约束目标函数。在这一过程中, 一个常见的问题是观测数据一般不能保证节点连续 性,因为数据在不同地点、不同时间点收集,而且收 集过程中不可避免会有误差。Van Aerde et al.提出应将 流量约束最小化而不是去除,即并不是寻找完全对应 观测路段流量的最可能的 OD矩阵,而是从那些匹配 路段流量的矩阵中寻找可能的OD矩阵,使误差最小: 2 2 Min a ijaaaij ij aaij YTv vvTp (12) 同时求解(12)和基础公式(2)或(3)。但是,要融合 这两个表达式有一个难处:一个要使可能性最大,另 一个要使路段流量误差最小,而拉格朗日乘子只 能把等价约束加到有约束目标函数上去。Van Aerde et al.提出了一个方法,取(12)中每次 OD 对间出行 的 偏导数(13)并将其加入目标函数(3): ij T 2 20 a aijij aij ij aaa aijij xyxy aaxy vTp T vppT p (13) ! Max ! 2 ij ij ij ij ij ij aaa ija ijijxyxy ijaa xy t T ZTt vppT p (14) 同样,使用Stirling 近似将其简化,得Van Aerde et al.公式(15),求解后可获得最匹配观测路段流量的 OD 矩阵: 7 Max ,lnln 2( ij ij ijij ij ij aaa ijaijijxyxy ijaaxy T T ZTt TT tt vppT p (15) 3.2. 极大熵公式及其特征归纳 极大熵基本和改进公式可归纳为以下七个目标 函数: 1 ! ! Max Tij ij ij ij ij ij ij T ZT t t (16-1) 2 Maxlnln ij ij ij ij T T ZT T tt (16-2) 3 Maxln ij ij ij ij T ZT t (16-3) 4 Maxln ij ijij ij ij ij T Z TT t t (16-4) 2 5 1 Max 2ij ij ij ij ZT T t (16-5) 2 6 1 Max 2ij ij ij ij ZT t t (16-6) Copyright © 2013 Hanspub 149 出行分布矩阵的极大熵估计法比较研究 7 Max lnln 2 ij ij ij ij aaa ija ijijxyxy ijaa xy T T ZT T tt vppT p (16-7) 对各个目标函数的特征,包括是否包含简化假 设、总出行次数T是否假设为固定或其他假设情况进 行归纳,列在表 1中。另外,目标函数有时会产生负 值,使得一个OD对间的出行数为负,需要在每个公 式中对变量 加上非负约束。 ij T0 ij T 4. 极大熵公式比较研究 4.1. 网络描述 为了对几个形式不同的极大熵公式作比较,给出 两个简单测试网络,其中一个网络总需求 T固定,另 一个总需求 T可变,以研究两种情况下使用各个极大 熵公式对最优解的影响。在节点连续性没有满足和先 验OD 矩阵不可行时又做了进一步比较。 给定 OD 出行的次数为整数次,不考虑诸如 1.5 次出行等非整数情况,将解空间限定在整型值,则在 求解时无需列出每个公式,而是列出所有可能的整数 解来构造一个解空间,然后从该解空间中寻找最优 解。虽然使用的网络规模小、结构简单,但得出的结 论是一般性的,可推广到其它较大的网络。 第一个网络是一个五路段网络,如图 1,它有两 个起节点1、2,两个终节点5、6,四个 OD 对 ,五个路段。五个路段的观测路段流量 见表 2。 15 162526 ,,,TTTT Table 1. Hypothetical situations of maximum entropy formula 表1. 各个极大熵公式假设情况 目标函数 包含简 化假设 包含 Stirling 近 似公式 包含近似 公式(10) 假设总出行 次数 T固定 假设 ij ij tT (16-1) 否 否 否 否 否 (16-2) 是 是 否 否 否 (16-3) 是 是 否 否 否 (16-4) 是 是 否 是 是 (16-5) 是 是 是 是 否 (16-6) 是 是 是 是 是 (16-7) 是 是 否 否 否 Table 2. Observed link flow of five-link network 表2. 五路段网络的观测路段流量 路段 观测路段流量 1~3 30 2~3 50 3~4 80 4~5 60 4~6 20 1 3 4 5 6 2 Figure 1. A five-link network 图1. 一个五路段网络 共有 21 种可行的需求情况,通过设定一个 OD 对的需求可以计算其它三个OD对的需求,比如给定 则 15 T 16152515 261615 15 30 ,60 , 2020 3010 TTTT TT TT 这些可行需求满足总需求约束 ,节点流连续约 束 T80 13 233445 46 x xxxx 15 162526 ,,, 0TTTT 26 16 0,TT ,非负约束 。具体的需求情况如表3所示。另 外,第 1种和第 21 种需求情况使得一个 OD 对间流 量为 0,分别是 0 ij T ,这两种极端的情况会 给数学公式带来麻烦,因为 项在分母上,所以分析 时去掉这两种极端的情况,仅考虑情况 2~20。 第二个网络是一个两路段网络,如图 2,有三个 节点 1、2、3,1是起节点,3是终节点,2既是起节 点又是终节点。有三个OD 对,两个路段 1~2 和2~3,每个路段的观测路段流量见表4。 12 1323 ,,TTT 共有 11种可行的需求情况,同样,通过设定一 个OD 对的需求可以计算其它两个 OD 对的需求,见 表5。去掉第一和最后一种会在分母上产生 0的情况, 仅分析第 2~10 种情况。与五路段网络一个不同之处 是,这里的总需求 T不是固定的,而是随着可行解的 变化而变化。 Copyright © 2013 Hanspub 150 出行分布矩阵的极大熵估计法比较研究 Table 3. Solution set of five-link network 表3. 五路段网络的解集 需求情况 15 T 16 T 25 T 26 T 总需求 T 1 10 20 50 0 80 2 11 19 49 1 80 3 12 18 48 2 80 4 13 17 47 3 80 11 20 10 40 10 80 20 29 1 31 19 80 21 30 0 30 20 80 Table 4. Observed link flow of two-link network 表4. 两路段网络的观测路段流量 路段 观测路段流量 1~2 10 2~3 15 Table 5. Solution set of two-link network 表5. 两路段网络的解集 需求情况 12 T 13 T 23 T 总需求T 1 0 10 5 15 2 1 9 6 16 3 2 8 7 17 4 3 7 8 18 10 9 1 14 24 11 10 0 15 25 2 1 3 Figure 2. A two-link network 图2. 两路段网络 4.2. 极大熵公式的寻优一致性 各个极大熵公式虽然表现形式各不相同,但在最 优解的选择上却是一致的。在先验 OD矩阵可行时, 可以通过列举所有的可行解来获得最优解,一直重复 这一过程直到 涵盖整个可行解范围。在上节给出的 ij t ij t 两个网络上计算七个目标函数。为省略篇幅,仅给出 公式(16-1)和(16-3)在两个网络上的计算结果,见表 6~ 9。 Table 6. All feasible solutions of five-link network by (16-1) 表6. 公式(16-1)在五路段网络上的所有可行解 需求情况 ij ij tT ij ij tT 2 0.0051 2.2834e−074 1.0872e−050 1.8739e−037 3 0.0037 4.5638e−058 4.2716e−040 2.3939e−033 4 0.0031 1.8171e−048 9.2551e−033 1.1428e−030 5 0.0027 9.2640e−042 4.7387e−027 1.0793e−028 6 0.0025 9.7994e−037 2.0176e−022 3.4168e−027 7 0.0023 7.4874e−033 1.2941e−018 4.6028e−026 8 0.0021 8.0000e−030 1.7408e−015 2.9850e−025 9 0.0021 1.7533e−027 5.9995e−013 9.9575e−025 10 0.0020 9.9288e−026 5.9990e−011 1.7625e−024 11 0.0020 1.6639e−024 1.8734e−009 1.6639e−024 12 0.0020 8.8325e−024 1.8914e−008 8.2237e−025 13 0.0020 1.5017e−023 6.1690e−008 2.0351e−025 14 0.0020 7.8094e−024 6.2522e−008 2.3315e−026 15 0.0021 1.1055e−024 1.8043e−008 1.0878e−027 16 0.0022 3.4186e−026 1.2635e−009 1.6746e−029 17 0.0023 1.5490e−028 1.6140e−011 5.9106e−032 18 0.0026 4.7693e−032 2.1874e−014 2.3911e−035 19 0.0030 1.7888e−037 9.5101e−019 2.3091e−040 20 0.0040 3.7945e−047 3.3378e−026 3.4914e−049 Table 7. All feasible solutions of two-link network by (16-1) 表7. 公式(16-1)在两路段网络上的所有可行解 需求情况 ijij tT ij ij tT 2 0.0785 3.9374e−007 1.3842e−008 3 0.0585 4.9961e−005 2.7831e−005 4 0.0498 6.2984e−004 8.6146e−004 5 0.0454 0.0018 0.0027 6 0.0434 0.0014 0.0014 7 0.0432 2.7583e−004 1.2208e−004 8 0.0451 1.1888e−005 1.4845e−006 9 0.0501 5.8643e−008 1.0545e−009 10 0.0633 4.7096e−012 2.7344e−015 Copyright © 2013 Hanspub 151 出行分布矩阵的极大熵估计法比较研究 Table 8. All feasible solutions of five-link network by (16-3) 表8. 公式(16-3)在五路段网络上的所有可行解 需求情况 ij ij tT ij ij tT 2 0 −164.2891 −109.7691 −79.2910 3 0 −126.4426 −85.0622 −69.5232 4 0 −105.6599 −67.9812 −63.1642 5 0 −88.5706 −54.7022 −58.4842 6 0 −76.9029 −43.9445 −21.9722 7 0 −67.8866 −35.1032 −52.2551 8 0 −60.8556 −27.8419 −50.3285 9 0 −55.4234 −21.9570 −49.0814 10 0 −51.3572 −17.3223 −48.4807 11 0 −48.5203 −13.8621 −48.5203 12 0 −46.8443 −11.5440 −49.2183 13 0 −46.3183 −10.3666 −50.6195 14 0 −46.9891 −10.3702 −52.8031 15 0 −48.9752 −11.6440 −55.8990 16 0 −52.9667 −14.3508 −60.1208 17 0 −57.9667 −18.7816 −65.8379 18 0 −66.1555 −25.4884 −73.7537 19 0 −78.8071 −35.6897 −85.4595 20 0 −101.3593 −53.1333 −106.0477 Table 9. All feasible solutions of two-link network by (16-3) 表9. 公式(16-3)在两路段网络上的所有可行解 需求情况 ij ij tT ij ij tT 2 0 −12.2025 −15.5505 3 0 −7.0650 −7.6501 4 0 −4.3700 −4.0568 5 0 −3.2437 −2.8383 6 0 −3.4657 −3.4657 7 0 −5.0539 −5.8689 8 0 −8.2402 −10.3207 9 0 −13.6584 −17.6768 10 0 −23.3216 −30.7731 从各个表中可以看出无论总需求固定还是可变, 当解的情况与先验 OD矩阵情况相同即 时,目 标函数最大即可能性最大。表6、7中更详细地列出 了各个可行解,第一列是解与先验 OD 矩阵相同的情 ij ij tT 况,是最优解,分别是从 0.0051 变化到0.0040,从 0.0785变化到 0.0633,均呈现从大到小再变大的趋势, 后三列是解的情况不同于先验OD矩阵的情况,计算 出的目标函数值较小。公式(16-3)的计算结果也有类 似趋势。说明尽管公式( 16-1)~(16 -7) 产生不同的目标 函数值,但在寻找最优 OD 矩阵上它们是一致的。当 总需求固定时,所有的公式都收敛到先验 OD矩阵, 当总需求变化时,除了(16-4)、(16- 5) 、(16-6)外所有 的目标函数都产生对应OD矩阵的最优解,因为总需 求固定是这三个公式的先决假设条件。 4.3. 先验 OD 矩阵不可行对寻优的影响 有时一个先验 OD矩阵可能并不是进行本次估计 的可行矩阵,因此有必要进一步研究先验OD 矩阵不 可行的情况,不仅能明确不可行情况对不同公式表现 特征的影响,而且还能明确不同目的下选择哪一个公 式来计算最合适。通过生成满足均匀分布的随机数来 生成 1000 组先验矩阵,然后列举所有可行解来获得 所有公式在每个先验矩阵下的解。以不含任何简化假 设的公式(16-1)的解作为比较基准,其它公式获得的 解与之比较来估计误差。在五路段网络中共有 19 个 可行解,最大误差即为 19;在两路段网络中共有 9个 可行解,最大误差即为9。在总需求固定的五路段网 络下, (16-1)、(16-2) 总是产生相同的解,(16-3)、(16-4)、 (16-7)产生的解与基准很相近,以(16-3)为例,见图 3。 误差比较小,而且没有误差即误差为 0的情况很多, (16-5)、(16-6)的误差比较大,超过 20%,见图 4。在总 需求可变的两路段网络下, (16-1)、(16-2)产生相同解, -29-2 7-25-2 3-21-19-17-15-13-11-9 -7 -5 -3-1 1 3 5 7 911131517192123252729 0 10 20 30 40 50 60 70 80 90 累 计 频 率 % Figure 3. Error of optimal solution on five-link network by (16-3) 图3. 公式(16-3)在五路段网络上最优解的误差 Copyright © 2013 Hanspub 152 出行分布矩阵的极大熵估计法比较研究 Copyright © 2013 Hanspub 153 -29-2 7-25-23-21-19-17-15-13-11-9-7 -5 -3 -11 3 57911131517192123252729 0 2 4 6 8 10 12 14 16 18 20 累 计 频 率 % Figure 4. Error of optimal solution on five-link network by (16-5) 图4. 公式(16-5)在五路段网络上最优解的误差 (16-3)、(16-7) 有微小误差,(16-4)、(16-5) 、(16-6)有 明显误差,说明(16-5)、(16-6)这两个公式在实际运用 中受到限制。 4.4. 节点流连续条件不满足对寻优的影响 在实际过程中,节点的流连续性条件往往不能满 足,但是即使不满足,这七个公式仍能估计OD 出行 表,原因是路段流量已经被转化成了等价的满足节点 流连续性且使路段流误差最小的路段流量。在公式 (16-1)~(16-6)中,寻优的过程是先解决节点流连续性 问题,再根据极大熵技术求解来获取 OD出行表,而 公式(16-7) 把流量 条件加入目标函数中,同时解决流 连续性和极大熵问题,所以七个公式的计算结论几乎 相同,当然从计算效率上看(16-7)的计算效率更佳。 5. 结论 在现今的交通状况下,实测或系统性 OD交通调 查数据还不健全,有必要通过简单、经济、可行、快 速的方法解决交通规划基础数据不足的问题。极大熵 模型因其模型结构简单、原理明确,在OD 估计中已 受到广泛应用。采用各种简化假设,对基础极大熵公 式进行不同的简化和变形,得到了七个不同表现形式 的极大熵OD 估计目标函数,采用罗列可行解空间的 形式,在总需求可变、先验 OD矩阵不可行以及节点 流连续性条件不满足的情况下比较了不同公式的特 征。结果表明,尽管目标函数的表现形式各不相同, 但在寻优时却表现出一致性,无论其处于总需求固定 还是可变的网络中。当总需求可变时, (16-4)、(16-5)、 (16-6)产生较大误差,使用受限。当先验 OD 矩阵不 可行时,(16-5)、(16-6)产生的误差高达 20%,严格限 制了公式的使用。节点流连续性几乎不影响最优解的 获取,只影响计算效率,在七个公式中(16 -7) 的计算 效率最佳。在实际应用中,应该根据不同的应用要求 和条件选择合适的目标函数形式,以达到理想的及最 佳的计算结果。 参考文献 (References) [1] L. G. Willumsen. Simplified transport models based on traffic counts. Transportation Research Part B, 1981, 10(3): 257-278. [2] J. Ortuzar, L. G. Willumsen. Modelling transport. 3rd Edition, Chichester: Wiley, 2001. [3] M. Van Aered, H. Rakha and H. Paramhamsan. Estimation of OD matrices: The relationship between practical and theoretical considerations. Transportation Research Record No. 1831, 1831: 122-130. [4] 马广英, 李平, 闻育. 基于极大嫡模型的交通出行矩阵解法 研究[J]. 浙江大学学报(工学版), 2006, 40(10): 1779-1782. [5] 周晶, 陈森发, 徐南荣. 均衡交通状态下 OD 矩阵的估计方法 [J]. 信息与控制, 1993, 225(2): 71-82. [6] 邵春福. 交通规划原理[M]. 北京: 人民铁道出版社, 2006. [7] J. H. Van Zuylen, L. G. Willumsen. The most likely trip matrix esti- mated from traffic counts. Transportation Research Part B, 1980, 14B(3): 281-293. |