（交通运输规划与管理专业论文）OD矩阵估计及检测点设置实用方法研究.pdf

摘要 摘要 o d 资料是城市交通规划与管理等工作的基础。在传统的交通规划中，一般都是通过大 规模的抽样调查( 如居民出行调查) 来获得o d 矩阵，但是由于交通数据量很大，所以调查 工作量和成本十分庞大。而通过路段实测交通量来推算o d 矩阵相比之下却更方便和低廉。 传统的o d 估计模型没有考虑拥挤效应的影响，即将估计得到的o d 矩阵分配到路网上 会出现和实际观测流量不一致的现象。在后来出现的一些双层规划的o d 估计算法中，得到 的解只是相容解，并不是双层规划解，而且收敛性不能保证。本文提出的多步双层规划模型， 不直接求解双层规划模型。而是将o d 估计过程分为固定的步数，这样可以减小每次双层规 划求解的难度，且不用考虑收敛性。对于检测点设置问题，传统的模型和算法计算量很大， 而本文提出了一个基于最大可能绝对误差的检测点设置模型，其算法效率较高，计算量不大。 本文的主要内容包括以下几个部分： o d 矩阵估计及检测点设置实用方法研究。对国内外已有o d 矩阵估计理论深入研究， 建立了一个实用化估计模型：o d 估计的多步双层规划模型及算法。将o d 估计分为固定的 步数，每一步都是一个双层规划，上层为广义最小二乘模型，下层为随机用户均衡分配模型， 即以广义最小二乘模型和随机用户均衡分配模型为基础，通过更新估计模型中目标矩阵和实 测路段上的流量来估计o d 矩阵。分别用遗传算法和相继平均法求解广义最d x - - 乘模型和随 机用户均衡分配模型。探索了o d 矩阵估计中检测点设置问题，包括检测点设置的四大原则， o d 矩阵推算精度，并对其进行了分析。研究了检测点设置的一般模型，构建了基于最大可 能绝对误差的检测点设置模型，并给出相应的启发式算法。 广义最小二乘模型及随机型用户均衡网络的算法。介绍了遗传算法，包括遗传算法的 一般算法和特点，接着设计遗传算法求解广义最小二乘模型。然后介绍了随机型用户均衡网 络模型，并用相继平均法求解随机型用户均衡网络模型。 o d 矩阵估计模块设计。介绍了组件式g i s 的特点，及其相对于传统g i s 工具的优点， 接着介绍了a r c g l se n g i n e ，包括其开发工具和运行环境，并完成了对o d 矩阵估计模块的 实现。 o d 矩阵估计模块在常德市区路网上的应用及分析。从结果来看，本文提出的o d 估计 方法避免了直接求解双层规划解，不用考虑收敛性，估计出的o d 矩阵经过分配后与实测路 段流量能较好的逼近，检测点设置方法效率较高，且都能适用于较大规模的实际交通网络。 关键词：o d 估计，广义最小二乘估计，随机用户均衡，检测点设置，g i s a b g r a c t a b s t r a c t o di st h eb a s i so fu r b a nt r a n s p o r t a t i o np l a n n i n ga n dm a n a g e m e n t i nt h et r a d i t i o n a l t r a n s p o r t a t i o np l a n n i n g ，u s u a l l yt h r o u g hal a r g e - s c a l es a m p l es u r v e y , s u c ha sh o u s e h o l ds u r v e y s ， t og e to dm a t r i x ，b u tb e c a u s eo fal a r g ev o l u m eo ft r a f f i cd a t a ，t h ei n v e s t i g a t i o ni sh u g e h o w e v e r o dm a t r i xe s t i m a t i o nb yt h em e a s u r e dv o l u m eo ft r a f f i ci sv e r yc o n v e n i e n ta n dl o w a s s i g ne s t i m a t e do dm a t r i xt on e t w o r kw o u l db ei n c o n s i s t e n tt oa c t u a lf l o w , f o rt r a d i t i o n a l m o d e lo fo dm a t r i xe s t i m a t i o nd i dn o tc o n s i d e rt h ee f f e c to fc r o w i n g l a t e ri nt h ee m e r g e n c eo f s o m eo ft h eb i l e v e lp r o g r a m m i n go de s t i m a t i o na l g o r i t h m ，t ob et h eo n l yt h em u t u a l l yc o n s i s t e n t s o l u t i o n , n o tt h eb i l e v e lp r o g r a m m i n gs o l u t i o n ，a n dc a l ln o tg u a r a n t e ec o n v e r g e n c e i nt h i sp a p e r t h em u l t i - s t e pb i - l e v e lp r o g r a m m i n gm o d e l ，d o e sn o td i r e c t l ys o l v et h eb i l e v e lp r o g r a m m i n g m o d e l ，b u td i v i d eo dm a t r i xe s t i m a t i o ni n t oaf i x e dn u m b e ro fs t e p s ，s ot h a te a c hc a nr e d u c et h e d i f f i c u l t yo fs o l v i n gt h eb i - l e v e lp r o g r a m m i n g ，a n dd on o th a v et oc o n s i d e rc o n v e r g e n c e t h e t r a d i t i o n a lt r a f f i cc o u n tl o c a t i o n sm o d e la n da l g o r i t h mn e e dam o u n to fc a l c u l a t i o n ，a n dt h i sp a p e r ， b a s e do nt h el a r g e s tp o s s i b l ea b s o l u t ee r r o ro ft h em o d e l ，t h em o r ee f f i c i e n tm e t h o dt oc a l c u l a t e t h em a i nc o n t e n t si n c l u d et h ef o l l o w i n g ： f i r s t l y , s t u d yt h em e t h o do fo dm a t r i xe s t i m a t i o na n dt h et r a f f i cc o u n tl o c a t i o n s d i v i d eo d m a t r i xe s t i m a t i o nt of i x e ds t e p s ，ab i l e v e lp r o g r a m m i n gi sc o n t a i n e dw i t he v e r ys t e p ，u p p e r - l e v e l p r o b l e m i sag e n e r a l i z e dl e a s ts q u a r e se s t i m a t o r , l o w e r - l e v e lp r o b l e mi sas t o c h a s t i cu s e r e q u i l i b r i u mm o d e l ，n a m e l y , b a s e do fg e n e r a l i z e dl e a s ts q u a r e s e s t i m a t o ra n ds t o c h a s t i cu s e r e q u i l i b r i u m ，an e we s t i m a t o ro ft h eo dm a t r i xi sp r o p o s e db yt a r g e tm a t r i xa n dt r a f f i cc o u n t s u p d a t i n g i nt h i sp a p e r , r e v i e wag e n e r a lm o d e la b o u tt r a f f i cc o u n tl o c a t i o n s ，s e tu pam o d e lb a s e d o nt h el a r g e s tp o s s i b l ea b s o l u t ee r r o ro fo dm a t r i c e s ，a n dg i v e st h ec o r r e s p o n d i n gh e u r i s t i c a l g o r i t h m s e c o n d l y , t h i sp a p e ri n t r o d u c e dg e n e t i ca l g o r i t h m ，i n c l u d i n gt h eg e n e r a lc h a r a c t e r i s t i c so f t h e a l g o r i t h ma n dt h e nt h ed e s i g no fg e n e t i ca l g o r i t h mm o d e lo fg e n e r a l i z e dl e a s ts q u a r e se s t i m a t o r t h e ni n t r o d u c e ds t o c h a s t i cu s e re q u i l i b r i u mm o d e l ，a n da p p l i e dm e t h o do fs u c c e s s i v ea v e r a g e st o s o l v et h em o d e l t h i r d l y , d e s i g no dm a t r i xe s t i m a t i o nm o d u l eb a s e do ng i s t h i sa r t i c l ed e s c r i b e st h e c h a r a c t e r i s t i c so ft h eg i sc o m p o n e n t a sw e l l 豁i t sa d v a n t a g e so p p o s e dt ot r a d i t i o n a lg i st o o l s ， a n dt h e ni n t r o d u c e da r c g i se n g i n e ，i n c l u d i n gi t sd e v e l o p m e n tt o o l sa n dr u n n i n gt i m e ，a n d c o m p l e t e dt h em o d u l eo fo dm a t r i xe s t i m a t i o n f i n a l l y , t h i sa r t i c l ef i n a l l ya p p l i e dt h eo dm a t r i xe s t i m a t i o nm o d u l eo nt h en e t w o r ko f c h a n g d e ，a n dt h e na n a l y z e dt h er e s u l t so f0 dm a t r i xe s t i m a t i o n t h er e s u l t sf r o mt h ep o i n to f v i e w , t h i sp a p e re s t i m a t e st h eo dt oa v o i dad i r e c tm e t h o df o rs o l v i n gb i l e v e lp r o g r a m m i n g s o l u t i o n s ，d on o th a v et oc o n s i d e rc o n v e r g e n c e ，t h eo dm a t r i xe s t i m a t e dt h r o u g hw i t ht h e d i s t r i b u t i o no fr o a dt r a f f i cc a nb em e a s u r e db e t t e ra p p r o a c ha c t u a lf l o w , t h ea l g o r i t h mo ft r a f f i c c o u n tl o c a t i o n si sm o r ee f f i c i e n t , a n dc a nb ea p p l i e dt ol a r g e - s c a l er e a lt r a f f i cn e t w o r k k e yw o r d s ：o dm a t r i xe s t i m a t i o n ；g e n e r a l i z e d l e a s ts q u a r e se s t i m a t o r ；s t o c h a s t i cu s e r e q u i l i b r i u m ；t r a f f i cc o u n tl o c a t i o n s ；g e o g r a p h i ci n f o r m a t i o ns y s t e m ( g i s ) i i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 己在论文中作了明确的说明并表示了谢意。 研究生签名： 日 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：边：导师签名：丝圣步 y 日 期：塑! ：! ：! 圣 第1 章绪论 1 1 研究背景及意义 1 1 1 研究背景 第1 章绪论 o d 资料是城市交通规划与管理等工作的基础，它可以反应城市交通拥堵等问题的原因 所在，以及交通需求与土地利用、经济活动等相互关系的规律。车辆o d 矩阵在交通分配和 模拟中也是很重要的数据。 传统的获取o d 矩阵的方法是通过大规模的抽样调查，如家庭调查和路边调查等，由于 交通数据量十分庞大，这项工作将耗费大量的人力、财力和物力，而且花费巨大代价得来的 数据生命周期却很短，而利用路段实测交通量来推算o d 矩阵，以其方便、快捷、低廉和时 效性高等优点，越来越引起重视l l j 。 与四阶段o d 矩阵预测方法相比，由路段流量估计o d 矩阵的方法方便、快捷、低廉、时 效性高，能为交通规划、控制及管理工作提供有效的数据。在进行两次大规模o d 矩阵调查 之间，利用路段观测交通流量来估计o d 矩阵，以便得到尽可能实时的o d 矩阵，这种方法在 发达国家已经运用得比较成熟了，而我国基础设施比较薄弱，因而更具有特殊的意义。由于 一些客观条件的限制，o d 矩阵估计理论的研究和应用在我国尚处于初级阶段，仍缺乏完整 的理论说明【z 1 。 地理信息系统( g i s ：g e o g r a p h i ci n f o r m a t i o ns y s t e m ) 作为一种综合处理和分析空间数据 的技术系统，能够有效地对地球空间数据进行采集、存储、检索、建模、分析和输出。它的 独特之处就在于能够把地理位置和相关属性信息有机地结合起来。 近年来，随着地理信息系统的飞速发展，越来越多的应用领域同g i s 技术建立了紧密的 联系。由于交通信息系统具有精度要求高、规则复杂、动态化、离散化等特点，原有的信息 技术已经不能完全满足交通应用的需求，而借助于g i s 的强大功能，可以实现交通信息化的 时代要求。交通领域q b g i s 的应用也越来越受到研究者和开发者的重视。交通地理信息系统 ( g e o g r a p h i ci n f o r m a t i o ns y s t e mf o rt r a n s p o r t a t i o n ，简称g i s - t ) 是收集、整理、存储、管 理、综合分析和处理空间信息和交通信息的计算机软硬件系统，是g i s 技术在交通领域的延 伸，是g i s 与多种交通信息分析和处理技术的集成。g i s - t 有强大的交通信息服务和管理功 能，它可以应用在交通管理的各个环节。在交通工程领域采用g i s 技术和方法研究交通规划、 交通建设和交通管理及其相关的问题，具有其他传统方法无可比拟的优点1 3 】。 1 1 2 研究意义 东南大学硕士学位论文 基于g i s 的o d 矩阵估计不仅在理论研究上有着重要的价值，而且能够应用于实际的交 通问题，具有非常重要的现实意义。改进了以往的o d 矩阵估计方法和路段交通量检测点的 布设方法，并将其设计成基于g i s 的o d 估计模块，可以对实际的路网进行估算。得到的 o d 资料是交通管理、规划等工作的基础，也是交通诱导信息的重要组成部分。 1 2 国内外研究概况 1 2 1 国外研究状况 国外的交通规划和数学规划界学者自上世纪7 0 年代起就开始了对o d 矩阵估计问题的 研究，并提出了一些估计模型和算法。这些模型包括：极大熵模型【4 1 ，最大似然模型【5 1 ，广 义最小二乘模型【6 】和贝叶斯模型1 7 1 。 上述模型均没有考虑拥挤效应的影响，路径选择概率是已知的或预先利用与流量无关的比 例交通分配法确定的，这样做的好处是计算简便，并具有一定的统计特性，但是其内在的缺 点也是显而易见的：因为o d 矩阵是用路段流量和固定的路径选择概率估计的，而估计得到 的o d 矩阵般的又用用户均衡模型u e ( u s e re q u i l i b r i u m ) 分配到路网上，由分配获得的路径 选择概率与先前估计o d 矩阵用的路径选择概率存在着不一致现象。这种现象在现实比较拥挤 的路网中尤其突出，研究者们因此寻求可以同时估计o d 矩阵和路径选择概率的方法。n g u y e n 首 先提出了基于u e 的o d 矩阵估计模型，最终得到的o d 矩阵及由它确定的出行时间符合用户均衡条 件。f i s k 提出了u e 约束下的最大熵模型。f i s k j ； 1 b o y c e 提出了将四阶段预测中的交通分布与交通分 配相结合，根据交通调查数据估计o d 矩阵的模型。y a n g 将拥挤状态下的o d 矩阵估计问题描述为 双层规划问题，并研究了多种启发式算法。f l o r i a n 和c h e n 提出了种求解双层o d 矩阵估计问题的 最速下降法【2 l 【引。 这些模型在估计过程中成功的考虑了拥挤效应，它们都是基于l i e 的组合模型。在这些模型中， 不同的出行者对出行费用的感知是相同的的。而随机用户均衡模型( s u e ) 与u e 相比更加接近现 实，它允许不同的出行者对出行费用的感知不同。基于随机用户均衡模型的o d 矩阵估计理论可以 采用i o g i t 模型或p r o b i t t 漠型来计算路径的选择概率。y a n g 等对路网拥挤状态下，同时估计o d 矩阵 及随机用户均衡交通分配模型中臼值的问题进行了研究，提出了一种最优解搜索最优步长的计算 方法【2 】。h i l a g - a ol o 等提出的模型可以同时估计随机用户均衡交通分配模型中值t 9 1 9 1 。r i c a r d o g a r c i a - r 6 d e n a s 等通过列生成算法在拥挤网络上估计0 d 矩阵1 1 0 l 。 在这些双层规划的o d 估计算法中，得到的解只是相容解，并不是双层规划解，而且收 敛性不能保证l 。 1 2 2 国内研究状况 2 第l 章绪论 我国的o d 矩阵估计理论及算法研究起步较晚，但近几年来已受到一些学者的关注，如 王炜、孙俊的大型交通网络o d 矩阵推算方法研究【1 2 】；蒲云、张苏的( o d 矩阵估计的双 水平优化模型【1 3 l ；周溪召的( o d 分布与随机均衡分配的组合模型及算法【1 4 】；杨琪、王 炜的( o d 出行矩阵的容量限制推算方法【”l 等。由于这些研究才刚刚起步，所以还未形成 较完善的理论体系。对于o d 矩阵估计技术的应用，已逐渐受到交通规划、管理部门的重视。 公安部交通管理科学研究所在宁波市交通管理发展规划编制过程中，根据1 9 9 9 年 1 2 月调查所得的宁波市中心城区2 5 个交叉口的分流向流量数据，利用t r a n s c a d 交通规划 软件提供的o d 矩阵估计模块对宁波市中心城区o d 矩阵进行了推算，并将所得的o d 矩阵在 规划的道路交通网络上进行分配。以检验交通组织管理措施( 单行线网络) 的预期实施效果。 公安部交通管理科学研究所和东南大学在国家九五科技攻关项目城市交通诱导技术的研 究过程中，对o d 矩阵推算方法进行了进一步的研究，并在示范城市江苏省常熟市进行 了试验运用1 2 】。 1 3 研究目标及主要内容 1 3 1 研究目标 论文通过研究国内外已有o d 矩阵估计理论，路段交通量检测点布设理论，建立o d 矩 阵估计模型和路段交通量检测点布设模型，并设计求解算法。通过研究a r c g i se n g i n e 开发 包相应的接口，在此基础上设计基于g i s 的o d 矩阵估计模块，模块可以进行检测点设置和 o d 矩阵估计，最后对城市路网进行实例研究。 1 3 2 研究内容 本次研究的主要内容包括以下几个方面： l 、基于多步双层规划的o d 矩阵估计实用方法 对国内外已有o d 矩阵估计理论深入研究，对o d 矩阵概念、分类、估计原理、估计模 型、估计算法进行概括阐述。研究分析双层o d 估计模型的一般形式、特点以及较之于其它 o d 矩阵估计模型的优越性能，并提出本文的估计模型：o d 估计的多步双层规划模型，将 o d 估计分为固定的步数，每一步都是一个双层规划，上层为广义最小二乘模型，下层为随 机用户均衡分配模型，即以广义最小二乘模型和随机用户均衡分配模型为基础，通过更新估 计模型中目标矩阵和实测路段上的流量来估计o d 矩阵。 2 、基于最大可能绝对误差的检测点设置模型 本文将研究o d 矩阵估计中检测点设置问题，包括检测点设置的四大原则，o d 矩阵推 3 东南大学硕士学位论文 算精度，并对检测点设置原则进行分析。研究检测点设置的一般模型，提出基于最大可能绝 对误差的检测点设置模型，并给出相应的启发式算法。 3 、基于g i s 的o o 矩阵估计模块设计 本文将介绍组件式g i s 的特点，及其相对于传统g i si 具的优点，介绍a r c g i se n g i n e ， 包括其开发工具和运行环境，并完成对o d 矩阵估计模块的实现，模块可以进行检测点设置 和o d 矩阵估计。最后将o d 矩阵估计模块在具体城市路网上进行应用，并对o d 矩阵估计 的结果进行分析。 1 3 3 论文章节安排 论文各章节关系如图1 1 ： 第1 章绪论 上 第2 章基于多步双层规划的o d 矩阵估计实用方法 _ 基 i 第3 章基于最大可能绝对误差的 础 检测点设置模型部 第4 章广义最小二乘模型及随机型分 用户均衡网络的算法 j 、 应 用 第5 章基于g i s 的o d 矩阵估计模块设计及应用 t 部 l 分 第6 章结论与展望 图1 1 论文各章节关系图 4 第2 章基于多步双层规划的o d 矩阵估计实用方法 第2 章基于多步双层规划的o d 矩阵估计实用方法 2 1o d 矩阵估计问题 在城市交通规划中。需进行大量的交通调查，比如城市居民及流动入口出行调查、城市 汽车及外地汽车出行调查、货物运输出行调查和道路交通量调查等。在这些交通调查的各类 统计资料中。对城市交通规划起关键作用的是各种类型的出行o d 矩阵，包括各种人的出行 o d 矩阵、各类车的出行o d 矩阵及各类货物的出行o d 矩阵。这些o d 矩阵是进行交通需求预 测的直接依据。各类o d 矩阵一般是通过各类出行调查来获得的，但进行出行调查需花费大 量的人力、物力及大量的时间，相比之下，进行道路流量观测，花费的人力、物力及时间较 少【1 6 】 2 1 1o d 矩阵估计概述 o d 矩阵估计与交通分配有着密切的联系，城市交通网络交通分配是城市交通规划的一 个重要组成部分，就是把各种出行方式的空间o d 量分配到具体的交通网络上，通过交通分 配所获得的路段、交叉口交通量资料是检验道路规划网络是否合理的主要依据之一。而o d 矩阵估计是根据路段交通量推算机动车o d 分布量，是交通分配的逆过程。 o d f l j 行矩阵推算根据采集到的道路网络、网络交通量、小规模或部分o d 出行调查等信 息推算出路网的o d 出行矩阵，为路网的规划、建设及交通管理提供依据，从而减少( 或不 进行) 大规模的o d 出行调查。一般说来，o d 出行矩阵推算过程包括基础数据的收集整理， 出行路径选择，o d 出行矩阵的推算以及o d 出行推算矩阵的评价四个阶段1 1 7 1 , 其过程如图 2 1 所示。 图2 1o d 出行矩阵推算过程 5 东南大学硕士学位论文 根据处理对象问题的不同，可以对o d 矩阵估计从多种角度进行分类。 l 、按路网形状分：区域o d 矩阵估计、线路o d 矩阵估计和结点o d 矩阵估计。区域o d 矩阵即人们常用的o d 矩阵，指交通区与交通区之间的出行分布矩阵，它反映了出行量在区 域空间的分布特征。线路o d 矩阵是指某一城市主干道从某一交叉口驶上干线而在另一交叉 口驶离干线的出行分布矩阵，或公共交通线路( 火车、地铁、公交线路) 上从某一站点上车 而在另一站点下车的出行分布矩阵，或水路运输线上码头间的出行分布矩阵。结点o d 矩阵 指某一道路交叉口( 或交通枢纽) 上从某一进口进入而从另一出口驶出的o d 分布矩阵，亦 即交叉i = 1 流向：或某一城镇各进出口之间的o d 分布等【l 们。 2 、按网络拥挤状况分：非拥挤网络o d 估计和拥挤网络o d 估计。前者认为交通分配 矩阵与路段流量无关，可以由路网的几何特性事先独立地确定，采用非平衡网络分配的交通 分配算法，即不考虑拥挤对行驶时间的影响。后者则考虑拥挤的影响，把o d 矩阵估计和交 通分配看成一个整体过程，采用u e ( 用户均衡分配) 或s u e ( 随机用户均衡分配) 来确定交 通分配矩阵，虽然此时的推算更加复杂，但更接近实际。 3 、按模型采用数据的类型及推算目的，可将o d 矩阵估计模型分为静态的模型和动态的 模型。“动态”是指路段流量及估计的o d 矩阵是实时的数据信息。“静态”认为估计的o d 量是 静态的，它在几天或者几个月或者几年内是不变的，同时认为观测的路段交通量是静态的， 即它在几天或者几个月或者几年内是不变的。“静态”o d 矩阵主要用于近远期的交通规划与 设计【1 8 】。本文所研究的多步双层规划模型属于静态o d 矩阵估计的范畴。 2 1 2 常见的o d 矩阵估计模型 o d 估计是交通分配的逆过程，交通分配就是在己知各种出行方式的o d 矩阵的情况下， 把空间o d 量分配到具体的交通网络上，从而得到各路段上的交通流量。通常交通分配过程 都要依照一定的原则，比如最短路原则、用户均衡原则或随机用户均衡原则。由路段交通量 推算o d 矩阵是交通分配逆过程，其数学描述为：设巧表示f 区到j 区的o d 出行量， 表示路段口的交通量，p 夕表示乃经过路段口的比例，即路段选择比，则： 乃西= 圪 口= l ，m i ，j = l ，n ( 2 - 0 j 式中，m 为调查交通量的路段数目：n 为o d 量的交通分区数目。 路径选择信息孝一般采用交通分配模型获取，对于相同的交通网络及o d 点对，不同 的交通分配模型产生不同的路径选择信息p 尹。例如，采用最短路分配，疗：0 或1 ，采 用多路径分配，o s 孝s l 。因此，采用的交通分配模型对o d 矩阵推算有很大影响。式中待 求的未知量是巧，其总数为m r - 1 ) ，一般情况下，路网中的路段数远远小于o d 矩阵的对数， 即水 0 )( 3 - 1 4 ) 表示估计o d 出行量与实际o d 出行量之间的相对误差，因为f ：芝o ，忙o ，所以丸一1 。 从而我们进一步得到 p ：f ，九= o z )( 3 1 5 ) w e w 定义 g ( a ) = ( 3 - 1 6 ) 作为o d 出行矩阵估计误差的度量。显然，g ( 五) 越小，估计精度越高，估计误差越小。 所以，定义最大可能相对误差( m p r e ，m a x i m u np o s s i b l e r e l a t i v ee r r o r ) 为限制条件t g ( 2 , ) 的最大值，其表达式如下： m p r e ( 2 ) - - - r n a x g ( 2 ) )( 3 1 7 ) 第3 章基于最大可能绝对误差的检测点设置模型 3 。1 4 1 2 相对误差 3 1 ，4 3 均方平均误差 “y , p ：t ，九- - - o ( a ) 瓯2 孚川似 s e m = 3 1 4 4 范数平均相对误差 泊颈 t - 翊相珂误左琢卜瓦f l - 舁： s e r = z e i , ：一，。l ( ，；) 3 1 4 5 相关系数 ( - i ) ( f j f ，- i ) j p ：j ! ! 一 军手。；) 2 军莩( 。) 2 式中： f = 专莩莩 f = 专军手气 3 1 5 检测点设置原则分析 ( 3 - 1 8 ) ( 3 - 1 9 ) ( 3 2 0 ) ( 3 2 1 ) ( 3 2 2 ) ( 3 - 2 3 ) 在上述原则中，o d 覆盖原则和路段独立原则是进行o d 估计的必要条件，必须要满足。 其中路段独立原则是进行o d 估计的经济性条件，也是减少检测误差影响的直接方式。最大 流截断原则和最大流量比原则都是从o d 估计精度考虑，前者针对所有o d 对而言，后者是 针对单个o d 对来说，两者一般不能同时被满足。 到目前为止，对于o d 估计中检测点设置问题已经有了很多研究。l a m 和l o 提出了遗 传算法鉴别检测路段选择的先后顺序。y a n g 等检查了o d 矩阵估计关于检测器数量和设置 东南大学硕士学位论文 位置的可靠性，提出了检测点选择的“o d 覆盖原则”，即如果o d 估计误差作为约束条件， 检测器必须设置在一定的位置使得任意一个o d 对的部分出行可以被观测到。y a n g 和z h o u 对o d 估计的检测点设置问题做了综合的调查研究。基于o d 估计的最大可能相对误差理论， 他们派生出三个有用的检测点设置原则：o d 覆盖原则、最大流截断原则和路段独立原则。 检测器设置问题也被用公式表示为一个数学规划，o d 覆盖原则和路段独立原则作为约束条 件，而观测到的总的净交通流量最大化作为目标函数。需要考虑两种不同的情况：一种是路 径流量信息己知，另一种是仅仅初始流量分布和结点转向概率是必须的。他们也提出了一个 整数线性规划( i l p ) 来决定观测规定比例总交通流量的检测器设置的最小数量。在随后的 研究中b i a n c o 等发展了迭代的两阶段程序，在已知结点转向概率的情况下推导出交通流向 量随后推出可靠的o d 矩阵估计。检测器位置解的结果只取决于网络结构。他们提出的这个 程序满足o d 覆盖原则，因此最大可能相对误差对于特定的o d 矩阵有着有限的值。 在大多数城市交通调查中，经常用境界线和查核线调查来搜集数据。通过查核线交通调 查，所有的起点和终点分别在查核线两边的交通都可以被完全截断。这点和早期的基于o d 覆盖原则的检测点设置问题形成对比。传统的境界线和查核线的选择是基于主观的选择，取 决于管辖权、区域边界线和天然的或人工障碍，例如河流和铁轨；查核线的优化设置问题在 上面提到的有限的研究中已经被忽略了。仅仅在最近的研究中，g a n 和y a n g 做了些尝试，讨 论基于检测点设置的查核线设置问题。他们提出了整数非线性规划模型( m ) 并应用遗传 算法来解决两个相关联的检测点设置问题：一种是怎样布置已知数量的检测点使得尽可能多 的o d 对被截断，另一种是分离所有的o d 对所需要检测器的数量及位置。一个显著的属性是 提出的检测点设置策略仅仅将网络的拓扑结构和先验o d 结构作为模型的输入，因而检测点 设置结果很少受道路使用者行为假设和网络交通拥挤水平影响f 2 】j f 2 2 j 。 3 2 检测点设置模型及求解 3 2 1 检测点设置的一般模型 y 抽g 提出一个模型1 2 1 , 先定义一个整型向量：z = ( z l ，z 29 9 z ，) 。驴( o ，1 ) 。 f l 若交通量检测点设在路段七上 钆一10若没有交通量检测点设在路段j 上 ( 3 2 4 ) g a n 和y a n g 提出了一个i n p ( 整数非线性规划) 模型，基于查核线的检测点设置问题， 用最短路算法来解。为了帮助说明，用么表示第七个路段幽上的虚拟行驶时间，假设是 z 七的函数，定义( 气) = z 七，k = - 1 ，2 ，。由于每个路段的行驶时间都是非负的，可以 用合适的最短路径算法( 如d i j k s t r a 方法) 在有限的迭代步数来搜索最短路径及相应的从起 第3 章基于最大可能绝对误差的检测点设置模型 点”，至终点以。的最短行驶时间，w = l ，2 ，m 。用表示o d 对w 的最短虚拟行驶时 间，w = l ，2 ，m 。明显的1 1 。是整型向量z = ( 而，z 2 ，z ，) 的函数，我们可以很容易这样 理解，如果( z ) o ，则o - d 对w 之问的最短路径上至少包含一个检测点，鉴于路段行驶时 间函数的定义，即如果( z ) o ，则起点疗，至终点聆，的o d 对w ( w = l ，2 ，m ) 至少 被一条查核线分离开。否则如果( 垆0 ，则起点，l ，至终点珂。的o d 对w 之间至少存在一 条零虚拟行驶时间的路径，即这条路径不经过任何检测点或穿过任何查核线。 对于给定数量的交通检测器， o 。如果u - - - o 的话万( 甜) = o 。很明显目标函数的值就是被分 离的o d 对的总数目。这个整数最大化问题将最短路计算视为内部过程。在模型中，所有的 o d 对被看成同等重要的，同样可以用一个带权重的目标函数，根据各个o d 对的相对重要 性。 一 另外，确定检测器最小数量和位置以分离所有o d 对的问题，可以建立如下的i n p 模 型。 册 f 哑n 【所一善万( ( 砌】+ 荟乙 ( 3 - 2 6 ) j j 气 0 ，1 ，k = 1 ，2 ， 杪是一个足够大的正常数。下面内容解释了只要y ，则此模型的最优解给出了分离 所有o d 对的检测器最小数量。用2 。作为模型的最优解，假设仍然存在一或多对o d 对没有被 分离。我们可以在所有路段安上检测器，这样所有o d 对都会被分离。在这种情况下( 3 2 6 ) 第二项毛增长至多为，而第一项y 【研一万 ，( z ) ) 】下降至少为y 。因此，当在所有 k = 1 w f f i l 路段上设置检测器时，目标函数值至少减少了( j ；f ，- - 1 ) 0 。这就和我们假设的z 是最优解 矛盾。另一方面，如果z + 是最优解，且所有的o d 对都被分离，但不是需要检测点路段的最 小数量，我们可以在现有的可行解中去除多余的检测路段或是找另一个包含更少检测路段的 可行解来减小目标函数值，因为第一项少【脚一万 。( z ) ) 】值为0 ，而且在这个过程中一直 东南大学硕士学位论文 为0 。这就又和我们的假彘是最优解矛盾。因此，可以推出当沙 ，时，模型的解给出了分 离所有o d 对所需的最小检测点数量和位置。 g a n 和y a n g 应用了遗传算法来解决i n p 问题并且演示了模型的实际应用。然而这两个 i n p 问题的计算量很大，因为模型中包含的搜索最短路这个子程序。因此，要寻找一个计算 效率更高的计算程序。 为此，本文提出了基于最大可能绝对误差的检测点设置模型，并给出了相应的启发式算 法，算法过程简单，效率较高。在文章最后的例子中可以知道基于本检测点设置模型估计出 的矩阵效果较好。 3 2 2 基于最大可能绝对误差的检测点设置模型 在3 1 4 1 节定义的网络中，实际o d 出行量和估计o d 出行量满足如下关系： e p ：t 。= v 。( 口三) w e w 苁，：= v a ( 口z ) w 6 w 用式( 3 2 7 ) 减去( 3 - 2 8 ) ，得 p ：( f 。一f ：) = o ( a 三) w 令，7 。= ，：一t 。，表示估计o d 出行量与实际o d 出行量之间的绝对误差。 定义 p ：，7 。= o ( a z ) w e 缈 g o d = ( 3 2 7 ) ( 3 - 2 8 ) ( 3 - 2 9 ) ( 3 3 0 ) ( 3 3 1 ) 作为o d 出行矩阵估计误差的度量。显然，g ( r ) 越小。估计精度越高，估计误差越小。 所以，定义最大可能绝对误差为限制条件下g ( 刁) 的最大值，其表达式如下： m p r e ( r 1 ) = m a x g ( r ) j ，z p ：刁。：o ( 口z ) 3 - 3 2 如果o d 出行矩阵估算的精度足够高，使得o d 对间出行量的估计值，：与真实值f 。相 2 6 第3 章基于最大可能绝对误差的检测点设置模型 等，那么有 r 。= ，：一f 。= o o ：o ，o ，w )( 3 3 3 ) 借鉴统计学中统计量的概念，可以认为绝对误差刁的均值为占( 刁) = o 。方差为 7 7 ： s 2 ( 刁) = 兰型，- ，标准差s ( 刁) = w h 则g 0 7 ) = s ( 露) ，这也就是说g ( 召) 表明了绝 对误差r 与均值的离散程度。由于刁的均值为零，所以g ( r ) 表明了模型对所有o d 点对间 出行量估算误差的大小，它是对所有o d 点对估算误差整体上的度量。 因为( 3 - 2 7 ) 式，且p ： o ，f ，0 ，所以0 t w ( v 口p ：) ，同理0 c ( 屹p ：) ， 所以l i = | t w ci ( 屹p ：) ，对特定的o d 对w ，要想减小其o d 估计绝对误差，可以 通过选择估计绝对误差上限即v d 成值较小的路段，由于v 口需要观测才能得到，而本章的 问题就是选择检测点观测交通量，所以各路段的交通量的真实值在检测点选择之前不能得 到。可以利用先验矩阵分配到路网上的流量吒代替路段流量的真实值v 口。 在减小o d 估计绝对误差上限的基础上建立如下非线形规划模型： 血川z ) - 荟y w ( if f 了i ) 2 ( 3 - 3 4 ) 吲= 例m i n ， m 呲i n ( 5 ：乙净 z 。= f 口e z 口) ，。( w 肜) ，i e 凡a e r , , 万? z 。1 ( w 形) d e 工 y ，= o , 1z 。= 0 , 1 髭= 0 , 1 ( a l ；w ) ( 3 3 5 ) ( 3 3 6 ) ( 3 3 7 ) ( 3 3 8 ) ( 3 - 3 9 ) 其中，f 花i 表示o d 点对w 的绝对误差上限值，p ：表示o d 点对w 在路段口( a e l ) 上的选择率，当其值为0 时，赋值为s ( 值很小的正数) 。 儿= 1 ，若o d 点对问全部路径0 上至少有一个检测点，否则为0 乙= 1 ，若交通量检测点设在路段a 上，否则为0 ( 3 4 0 ) ( 3 - 4 d 东南大学硕士学位论文 髭= 1 若o d 点对w 形问出行路径0 经过路段a ( a ) ，否则为0( 3 4 2 ) 式( 3 - 3 8 ) 确保满足o d 覆盖原则。式( 3 - 3 6 ) 是确定检测点的个数，设满足o d 出行覆盖规 则的检测点的最少个数为南，则必须满足