（交通运输规划与管理专业论文）城市道路交通网络空间的拥堵瓶颈识别.pdf

f 煳 i d e n t i f i c a t i o no fbo t t l e n e c k sm 啪a nr o a dn e t w o r k ad i s s e r t a t i o ns u b m i t t e dt o s o u t h e a s tu n i v e r s i t y f o rt h ea c a d e m i cd e g r e eo fm a s t e ro fe n g i n e e r i n g b y z h e n g z h o n g y u a n s u p e r v i s e db y p r o f c h e n gl i n t r a n s p o r t a t i o nc o l l e g e s o u t h e a s tu n i v e r s i t y d e c2 0 0 9 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 研究生签名：j 她日期：址柚 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名：遂孓j 尘导师签名t 坚e t期：蝴 摘要 摘要 交通瓶颈是交通系统的薄弱环节，对交通瓶颈的识别研究有助于有效地改善交通系统的整体 运行状况。本文主要研究内容包括三个方面：拥堵交通网络模型、要素瓶颈识别和结构瓶颈识别。 第部分，拥堵交通网络流模型是本文的理论基础，首先简单介绍了起点算法的基本原理、 计算流程和收敛准则，起点算法收敛迅速而且精度高，在所有尊擤 传统模型的算法中具有巨大的 优势。在此基础匕，介绍了内惩罚函数法的基本原理，将起点算法与内惩罚函数法相结合，建立 容量制约交通分配模型。本文在单向路网中详细演示了两个算法的具体寞眵过程， 第二部分，要素瓶颈识别以拥堵交通网络流模型的交通分配结果为基础。在这部分首先介 绍了交通瓶颈的些属性，包括交通瓶颈的定义、分类、拥堵属性以及拥堵产生的原因与影响因 素；在要素瓶颈识别方面，将瓶颈分为点、线、面三个层次并给出了瓶颈空间分布的判断标准。 第三部分，尝试性的提出了结构瓶颈这概念，从宏观层面匕把握城市中存在的瓶颈。城市 交通拥堵问题的本质可以归结为城市道路交通供需失衡，因此，从交通供给和交通需求的耦合关 系入手，总结了城市道路供需平衡理论以及交i 豆供给与交通需求的互动关系；尝试从“交通需求 不变，调整路网结构”这一思路出发，提出结构瓶颈识别的标准与流程，解决路网结构瓶颈识别 这一问题。 最后，结合淮南市具体路网，对前文的要素瓶颈和结构瓶颈识别进行具体应用。 关键词：拥堵交通网络流模型； 起点算法；内惩罚函数法；要素瓶颈；结构瓶颈；识别 a b s t r a c t t r a f f i cb o t t l e n e c ki sl t a ek e yp 0 硫o f t r a f f i cs y s t e m 1 h er e s e a r c ho f c o n g e s t e db o t t l e n e c ki d e n t i f i c a t i o nw i l l i m p r o v et h ei n t e g r a t eo p c l a t i o np e r f o r m a n c eo f t r a t t i en e t w o r ke f f e c t i v e l y m a i n l yt h r e ep a r t s 雹i n c l u d e di nt h e p a p e r ，, w h i c h 刮陀c o n g e s t e di r a f f i en e t w o r km o d e l , i d e n t i f y i n gt h ee s s e n t i a lb o t t l e n e c ka n dt h es l r u e t u r a lb o t t l e n e c k i d e n t i f i c a t i o n 1 h ec o n g e s t e d 锄cn e t w o r km o d e li st h et h e o r 甜c a lb a s i sf o rt h i sp 印既i nt h e 触p a r t , t h e 岫a r i di t s e f f i c i e n ti m p l e m e n t a t i o n , c o n v e r g e n c ec l i t e r i o l lo fo r i g i n - b a s e da l g o r i n a ma i n l r o d u c 缸硼a l g o r i t h mi s c o n v e r g e n tf a s ta n di th a sah i g hp r e c i s i o n c o m p a r e dw i t ho t h e ra l g o r i 伍m , w h i c hi su s e dt os o l v e 血e 位l 赶i c a s s i g n m e n tm o d e l s , i th a sa w i d em 咄o nt h i sb a s i s , t h ep a p e ri n t r o d u c e st h eb a s i cp r i n c i p l eo ft t a ei n n e r p e n a l t yf u n c t i o n a n d 蛔l ，t h ep a p e ri st of i to r i g i n - b a s e da l g o r i t l l r ni n t oi n n e rp e n a l t ya p p r o a c h , s oa st os o l v e l t a ec a p a c i l a t e d 心a 伍ca s s i g n m e n tm o d e l t w op a r t i c u l a rp r o c e s so fe t t m e n ti m p l e m e n t a t i o na ms h o w ni nt h e 球i p 既 i nt h es e c o n dp a r t , l h ee s s e n t i a lb o t t l e n e c ki d e n t i f i c a t i o ni sb a s e do i lf i l er e s u l t so fl l l ei r a t e 笛咄尹删i n t h i sp a r t , t h ep l o 删e so fc o n g e s t e db o t t l e n e c k , i n c l u d i n gt h ed e f i n i t i o n , s o r t , r e a s o na n dl t a ei n f l u e n c ef a c t o r so f c o n g e s t e db o t t l e n e c ka 圮i n l r o d u e e d t h ee s s e n t i a lc 0 理删b o t t l e n e c ki sd i v i d e di n t ot h r e ep 峨w h i c h 淝 i n t e r s e c t i o n , l i n k , a n de o n g e s t e c tr e g i o n n 圮i d e n t i f i c a t i o nc r i t e r i o ni sa l s og i v e n i nl l a et h i r dp a r t , t h ep a p e ra l t e n 啦t og i v et t 圮c o n c e p to fs m m u v a lb o t t l e n e c k , w h i c h 啪i d e n t i f y 吐硷 c o n g e s t e db o t t l e n e c ki nt h em a e r o s e o p i c a la s p e 吐m 锄cc o n g e s t i o np r o b l e mb ea t m b u t e d 幻f i l li m b a l a n c e b e t w e 岛ls u p p l ya n dd e m a n do fu r b a nl l d 伍c t h u s , t h el l a e o r yo fs u p p l y - d e m a n da n dt h e i rr e l a t i o mi l l es u m m e d u p f r o mt h ei d e ao f 恤cd e m a n dc h 粕西l 玛a d j u s t i n gt h er o a dn e t w o r ks l r u c t 哦 t h i sp a p e rf r i e st og i v et h e i m p l e m e n ta n d c r i t e r i o no f s l m e t 啪1b o t t l e n e c k f i n a l l y , l t a ee s s e n l i a lb o t t l e n e c ki d e n t i f i c a t i o na n ds l r u c t u r a lb o t t l e n e c ki d e n t i f i c a t i o na 他d o n e w i l t at h es p e c i f i c r o a dn e t w o r ki nh u a n a n k 呵w o r d s ：c o n g e s t e d 恤cn e t w o r km o d e l ；o r i g i n - b a s e da l g o r i 岫i n n e rp e n a l t yf u n e t i o r t ；e s s e n t i a l 目录 目录 摘要 a b s t r a c t 目录 第章绪论 1 1 研究背景及意义 1 1 1 研究背景 1 1 2 研究意义 1 2 交通拥挤识别研究现状 1 2 1 国外研究现状 1 2 2 国内研究现状 1 2 3 存在的问题 1 3 研究目标及主要内容 1 3 1 研究目标。 1 3 2 主要内容 2 1 a 章节安排 第二章拥挤交通网络模型。 2 1 起点算法 8 8 2 1 3 起点算法的收敛准则 2 1 a 传统均衡模型应用于拥挤交通网络的缺陷 2 1 5 起点算法计算实例 2 2 容量制约交通分配模型简介 2 2 1 容量制约交通分配模型的优点。 2 2 3 容量制约下的基本的数学规划模型 2 2 3 两种求解算法的介绍 2 3 内惩罚函数法的实现p 2 】 2 3 1 构造伪可行集 1 l 1 1 ； 。1 7 2 3 2 惩罚参数的选取与更新 2 3 a 内惩罚函数法流程 2 3 5 内惩罚函数法实例详解 1 7 。1 7 1 8 1 9 目录 第三章路网要素瓶颈识别 2 1 3 1 1 交锺磅箨灏的定义 2 1 3 1 2 交通瓶颈的拥堵属性2 l 3 1 3 交通拥堵的特性2 3 3 1 4 交通瓶颈的分类。 3 2 交通瓶颈的形成原因及影响因素2 4 3 2 1 交通桶颈成因分析。 3 2 2 交通瓶颈的影响因素 2 6 2 6 3 3 路网要素瓶颈识别。 3 3 2 要素瓶颈的判别标准 3 3 4 实例 2 7 2 8 第四章结构瓶颈识别3 0 4 1 1 道路交通供需平衡内涵 4 1 2 各供需平衡间的关系。 。3 0 。3 2 3 2 4 2 道路交通供需互动关系。 4 3 路网结构瓶颈识别 4 3 1 结构瓶颈识别思路 4 3 2 路网结构。 3 3 3 3 4 3 3 结构瓶颈识别标准 4 3 4 结构瓶颈识别流程 3 6 3 7 第五章城市道路交通网络空间的拥堵瓶颈识：男 l 一以淮南市为例3 8 5 1 淮南市交通概况3 8 5 1 2 城市交i 蓖需求概况 5 2 要素瓶颈识别。 5 3 结构瓶颈识别 5 3 1 淮南市路网拥堵原因分析 5 3 2 淮南市路网结构瓶颈识别 第六章结论与展望 6 1 主要研究成果。 i v 。4 2 4 3 4 6 4 6 目录 6 2 研究展望 参考文献 附录 v 4 7 第一章绪论 1 1 研究背景及意义 i i 1 研究背景 第一章绪论 城市交通是城市社会、经济活动的纽带和动脉，对城市发厨 口人民生g r ：k 习z 的提黼极其 重的作用。改革开放以来，我国社会经济高速增长，人民生活水平不断提高，城市化进程加快。 随着私人小汽车保有量的大幅度增加，当前城市道路交通建设未能跟得匕柳动化进程的步伐，交 通供给与需求的矛盾已初现端倪，经常出现严重的交通拥挤及堵塞现象，直接导致了交通延误增 大，行车速度降低，给人们的出行造成极大不便，带来无可挽回的时间损失；与此同时，低速度 行驶增加了排污量，加重了环境污染及能源与资源的浪费，给社会带来巨大的经济损失，因此城 市道路交通拥堵问题已经成为制约社会经济发展的瓶颈。这是我国社会关注的叫噍点，也是一 个世界性的难题。 因此，国家对大城市的交j 副翔堵问题非常重：视，投入了大量的资金组织科技人员进行科学研 究。由北京交通大学高自友教授领衔申报，并以首席专家身份主持的“大城市交通拥堵瓶颈的基 础科学问题研究”( 编号：2 0 0 6 c b 7 0 5 5 0 0 ) 作为6 5 个“9 7 3 ”计划立项项目之一，已于2 0 0 6 年通 过剩技部申请立项。目前，“大城市交通拥堵学术研究中心”已经在北方交通大学落成，该项目共 有7 个课题( 1 】，具体如下：1 ) 城市交通需求生成棚理与瓶颈识别；2 ) 道路交通流的非线性动力 学特性；3 ) 路网交通拥堵的形成机理与传播特性；4 ) 城市交通系统的时空复杂性与结构瓶颈演 化：5 ) 城市交通系统的组织优化与控制；6 ) 城市交通信息融合、集成与计算实验；7 ) 典型大城 市交通疏堵问题的综合实证研究。其中，子课题“城市交通需求生成机理与瓶颈识别”由东南大 学交通学院王炜教授负责。本文以国家自然科学基金“城市道路交通网络空间的拥堵瓶颈识别” ( 编号：5 0 6 7 8 0 3 7 ) 为依托，研究道路交通网络的瓶颈识别问题。 i i 2 研究意义 从表象e 来看，城市交通的拥堵似乎是因为交通供给跟不匕交通需求的增长。事实上，城市 交通供给与交通需求是对相互影响、又相互制约的矛盾体。虽然我国大多数城市建成了初具规 模的道路网及交通配套设施，但是由于传统的城市建设只是被动地适应交通需求总量的增长，没 有系统地考虑城市空间、土地利用等因素与交通系统之间的相互作用关系，忽视了交通需求与交 通供给之间的耦合，使得方面交通需求的增长缺乏有序性，另方面交通供给的增长映乏有效 性。我龠】迫切需要解析城市交通系统的供需耦合机理，识别不同层面上的交通拥堵瓶颈，为提出 切实可行的预防交通拥堵的措施、制定科学的城市交通系统规划奠定理论基础。 识别拥堵瓶颈的研究意义在于： 东南大学硕士学位论文 ( 1 ) 从路网要素层次确定交通拥堵的瓶颈，更加有效地进行交通组织优化和控制。 ( 2 ) 解析交通需求与道路网之间的耦合机理，从宏观匕认识交通拥堵的结构瓶颈。 ( 3 ) 使得交通供给随着需求的变化而协调发展，通过交通规划设计提高道路供给的有效性 1 2 交通拥挤识别研究现状 目前，世界各国在交通拥堵瓶颈识别方面主要集中在以下2 个方面：( 1 ) 交通瓶颈的研究； ( 2 ) 交通瓶颈识别算法。 1 交强 仔瑶页的研究 瓶颈是交通网络的薄弱环节，如交叉口、交织段、分流合流点均是交通瓶颈的常发地点。目 前对交通瓶颈的研究大多是针对单个路段或交叉口的，内容基本e 是瓶颈处的交通流拥堵特征、 拥堵的评价指标等。 1 9 9 9 年，美国公路使用者联盟( a m 盘i c a n h i g h w a y u s e r s a l l i a n c e ) 发布了题为疏通美国的 大动脉：良性公路方略的研究报告，此报告分析了美国最严重的交通瓶颈，认为这些瓶颈是导 致交通阻塞的重要原因田。报告将这些瓶颈按总延误时间进行了排序，并且分析了如果不进行交 通改善，这些瓶颈将会导致的严重后果，还预测了采用相应措施将会带来的效益，如减少事故， 保护环境，节约时间等。此报告为同类研究的首创。2 0 0 4 年，美国公路使用者联盟又发布了题为 0 ) 一m i n c ，lr 尺脚) 2 - i 本文之所以选用最大最小路径费用差作为收敛准则，主要出于以下几个方面的考虑： 1 从直觉上就应该发现占w 优于l 沿，不仅仅是因为s w 直接与传统的用户平衡的定义相关， 而且，对于现实的大型网络来说，实际上只有小部分是拥堵的，这样就可能出现实际已经很拥堵 而未达到平衡，r g 却小于0 0 1 的情况。 2 占阳是为起点算法度身定做的收敛准则。对于其他算法而言，计算g w 可能觉得比较繁琐， 因为对于每个o d 对除了计算最小路径费用之外，还需要计算最大使用路径费用，计算过程中还 需要反复的计算s 。的值，这是个不小的额外工作量。但是对于起点算法而言，这份额外的工 作量也就不存在了，因为每次更新起点的限制子网络时有项工作就是计算结点的最大贡献费用， o d 对的最大使用路径费用正好就是结点最大贡献费用，每次搜索最短路径树的时候都能计算得 到最小路径费用。 2 1 4 传统均衡模型应用于拥挤交通网络的缺陷 传统均衡模型如起点算法，潜在的假设道路匕没有发生阻塞状态，在应用于拥堵交通网络匕还 存在着若干问题。 ( 1 ) 不考虑路段容量的约束，与现实不符 任何条道路都有个实际容量，作为交通流量的上限限制交通量无限制增长。当交通量低 于路段容量时，路段匕朐车辆正常处于行使状态；当交通量高于路段容量时，路段处于阻塞状态， 如果交通流量继续增加，堵塞地点就会从路段下游不断向匕游延伸，最终导致路段交通运行瘫痪， 这就是现实中人们感受的道路拥堵。 然而，传统的交通分配均衡模型在交通分配的过程中允许交通量大于路段实际通行能力而不 加任何约束，这就导致某些路段交通量会无限增加，而根据b p r 函数算出的旅行费用却没有得到 明显的增加，比如说在- 些拥堵路段，分配模型得出的路段交i 臣量二、三倍于其路段容量，而旅 行费用却没有增加许多。这显然与日常生活中，人f f 埘于堵车晚误时间这一常识相违背。 ( 2 ) 未考扈拥挤状态的等待时间与延误 网络拥挤状态下，车辆不得不停车等待，然而传统模型只考虑了在城市路段上的行驶时间， 却并没有考虑堵车时的等待时间。 1 0 第二章拥堵交通网络模型 迄今为止，美国公路局b p r 函数是唯公认的来自于实际观测的路段费用函数。b p r 函数 中变量和参数的选定主要是根据海量的实际观测数据统计分析得出的。然而，这个公式是从市际 公路观测得到的，对城市道路只能描述车辆在路段部分的行驶时间。但城市道路网络上的车辆除 了在路段部分要花费行驶时间外，在信号灯交叉口还往往要花时间等待绿灯，存在排队延误，并 且这个延误在整个出行时间中占相当大的比例( 2 0 - - , 4 0 ) 。因此，如果只考虑路段行驶时间而忽 略节点分流向延误时间是不适合城市道路网的。基于b p r 函数进行的交通均衡分配与实际的城市 道路网上的交通分配状况无疑会存在一定的出入。这种出入不是来自于数据调查和统计，而是来 自于模型本身。也就是说不是统计和随机误差，而是理论和模型本身的缺陷【j 。 2 1 5 起点算法计算实例 实例采用的单向路网来自文献闭，并在此基础上略做修改，增加路段1 0 - 1 3 ，同时改变部分 路段的自由旅行时间。该路网有2 0 条路段、1 3 个结点和4 个o d 对，如图2 - 2 所示。图中线段 旁边的斜体数字代表路段的自由旅行时间，黑体数字代表路段通行能力，l 和4 是起点，2 和3 是终点。设路网的控制精度为0 0 1 ，路段费用函数为美国公路局的b p r 函数，两个参数的值分别 为0 1 5 和4 。 0 7 0 0 7 弋 八 77 1 5 9 0 03 0 07 0 0 1r 1? | | | | 巧 7 彘- ( 、 5 一 9 0 0 一v 3 0 0 7 一8 0 0 7 似 9f 39f o 9 0 0 6 d 0 5 d d硝d d7 c ) d j rr 1 r1 v、 1 0 彳夼 8 。彳讣 9 。 23 u 7 0 0 7 弋岁 7 0 0 7 世乡 7 0 0 一弋 l4 0 0 8 0 0 ；78 6 0 0 7 7 4 6 0 0 2 0 0 ，r1 乱 f ， 。厂，、 图2 - 2 单向路网的交通需求、路段通行能力和自由旅行时间 依照起点算法的计算流程，在经过1 5 轮迭代后，最大最小费用差的最大值为0 0 0 8 0 6 6 ，小 于控制精度0 0 1 ，满足收敛条件，退出循环。具体的交通分配结果见表2 - l 。 当交通量大于路段通行能力时，该路段即为拥堵路段。从交通分配的结果可以看出，有四条 l i 东南大学硕士学位论文 路段的交通量超过了路段通行能力，分别为：5 6 、7 1 l 、7 8 、8 2 ，呒攘中加粗部分。另外 还有两条路段接近饱和状态，分别为6 7 、9 1 3 ，见表中斜体部分。 表2 - 1 起点算法交通分配结果 路段路段通行能力交通量费用费用导数 1 - 5 9 0 08 0 07 6 5 5 5 10 0 0 3 2 7 7 5 l 1 27 0 0 4 0 08 1 2 7 9 50 0 0 1 2 7 9 5 4 99 0 0 3 6 6 5 01 4 0 5 7 7 50 0 0 0 6 3 0 3 4 57 0 04 3 3 5 09 1 9 8 5 7 0 0 0 1 8 3 2 2 5 - 96 0 03 7 1 6 69 1 9 8 7 6 0 0 0 2 1 3 9 1 5 - - 6 8 0 08 6 1 8 46 0 1 0 1 90 0 0 4 6 8 8 6 昏一1 0 5 0 001 3 0 6 - - 79 0 0 8 6 1 8 45 6 3 0 6 60 0 0 2 9 2 7 0 7 1 1 4 0 04 5 3 7 01 1 2 3 4 3 70 0 1 9 6 9 9 3 7 一83 0 0 4 0 8 1 47 2 5 4 7 40 0 2 2 8 3 1 1 3 27 0 0 8 0 8 1 41 2 6 6 4 7 10 0 1 3 1 8 9 3 9 一1 3 6 0 0 5 7 1 6 61 0 11 2 4 80 ( ) 0 7 7 8 4 1 争一l o7 0 0 1 6 6 5 01 0 0 0 4 80 0 0 0 1 1 5 3 l 伊一l l7 0 01 6 6 5 0 8 0 0 3 8 49 2 2 7 3 e - 0 5 l o 1 37 0 007 0 l l 一37 0 0 4 2 8 3 48 1 6 8 2 40 0 0 1 5 7 2 l l 一2 7 0 01 9 1 8 6 9 0 0 7 6 20 0 0 0 1 5 8 8 1 2 87 0 0 4 0 01 5 2 3 9 90 ( x ) 2 3 9 9 0 1 2 63 0 0 070 1 3 37 0 0 5 7 1 6 61 1 7 3 3 9 30 0 0 5 1 3 5 4 2 2 容量制约交通分配模型简介 在前节中，介绍了传统均衡模型应用于拥挤交通网络中的缺陷，鉴于j 描述交通网络的状态，在传统的用户均衡模型中，应添加对网络要素的流量加以 义的是容量制约下交通网络流模型能够反映交通网络的拥挤状态，在拥挤的两 旅行费用由行走时间和延误构成。 2 2 1 容量制约交通分配模型的优点 传统模型中考虑路段容量制约的条件是交通分配研究领域的个重要分j 件的交通分配模型( s m c o l 【l s tr a i ：d 弘m ) ，或者简称为容量制约模型p 。 1 2 第二章拥堵交通网络模型 相较于传统模型，容量制约交通分配模型具有如下优点1 2 0 1 ： 1 确定路段容量比确定合适的路段特征函数容易 交通工程师需要选择合适的旅行时间和交通量的函数关系，标定特征函数中的各项参数。在 交通工程时间中，通常采用美国公路局首先提出的多项式函数( b p r ) ，b p r 函数中变量和参数 的选定主要运用根据海量的实际观测数据统计分析得出。为了得到比传统模型更加精确的交通流 模式需要限制路段交通量的上限。这可以通过合理确定路段通行能力和旅行时间函数这两种方法 来实现，实际上确定路段通行能力比确定合适的路段特征函数容易得多。 2 限制了路段交通量的非现实增长。 限制路段交通流量的非现实增长，可以更加准确地反映拥堵网络的交通流状态。研究交通拥 堵的形成机理与传播特性，容量制约下的交通分配方法比传统的无容量制约下交通分配方法更加 准确。把更多的注意力集中在路网的交通瓶颈，对加深了解交通瓶颈发生拥堵的内在原因，n i 6 瓶颈路段之间的关系、瓶颈路段对出行者路径选择行为的影响都有意义。 3 台哩控制路段交通流量的需要 如果路网一点都不拥堵，并不见得是件好事，因为那意味着路段资源没有得到充分的利用： 如果路网过于拥堵，交通拥堵严重影响居民的日常正常出行，就会怨声载道。交通管理者应该很 清楚拥堵路段的通行能力，并目采取措施把路段交通量控制在这个范围之内。为了减少交通噪音 对居民生活的影响，需要确定路段交通量的环境容量。由于停车设施的不足或者为了避免下游瓶 颈路段不发生堵塞，也需要控制路段的交通量。 4 可以粗略地估计交叉口的等待时间 文献幽】虽然提出了交叉口的流向、流向阻抗和流向流量的概念和相应的交通分配模型，但 是并没有考虑到城市道路容量制约的条件。车辆在拥堵交叉1 3 的等待时间是容量制约模型的自生 变量，可以粗略估计交叉口的拥堵程度。 2 2 2 容量制约下的基本的数学规划模型 给定个交通网络n = ( g a ) ，其中n 和a 是路段和结点的集合。用r 表示起点的集合，s 表 示终点的集合。容量制约模型可以表示成为下面的非线性规划问题。 曲 z ( x ) = f 乞( w ) a w 2 - 2 s f = 垡疗 v r 天，s s 2 - 3 k f 7 0 v k k 二，r ，s s x a = 磁 v 口彳，七k ，r ，se s ，jk 1 3 2 _ 4 2 5 东南大学硕士学位论文 x 口c 口 v a a 其中，z ) 是目标函数，是路段口的完全路段流量，r 。是路段费用函数，g ，。是起点广和 终点j 之间的交通需求，是起点，和终点j 之间第后条路径的交通量，k 。是起点，和终点j 之间的路径集合，砼是开关函数，c ：是路段口的通行能力。 容量制约模型是线性约束，关于路段流量的严格凸最优化规划问题，它有唯一的最优路段解。 此外，最优化的充分必要条件可以用k a m s h - k u h n - t u k e r ( k k t ) 条件来表述。分别用“。和v 。表 示路径费用和路段通行能力的最优化乘子的值。则k k tg r f 牛- 如下： ( c ? + 万嚣v a u 措) = 0 v 后k 二，灭，s s ” ，。( c a x o ) = 0 2 - 8 簟+ 豫1 ，口一”厝0” 4 c o x 。0 0v 七磊0 ，r ，j s 1 ，口0 嚣= q 噶 七 v a 彳 v r r ，j s 其中，簟= 略r 口表示路径旅行时间下面引入广义的路黼时间簟： 筇= 豫化+ v 口) z 一 q 、q口， 口 公式2 - 7 和公式2 - 9 可以写成： 2 - 1 0 2 - 1 l 2 1 2 2 - 1 3 2 1 4 ? ( 6 7 - - u 府) = 0 v 七k 疗，广r ，s s 2 - 1 5 占? 一“疗0 2 - 1 6 很明显，公式2 - 1 5 和公式2 - 1 6 满足w a r d r o p 用户均衡原则，也就是所有使用的路径的广义 旅行时间相等，并且小于其他不使用的路径的广义旅行时间。 为了理解广义旅行时间在交通网络中的物理意义，公式2 8 、公式2 1 0 和公式2 - 1 2 可以概括 为： 0jc 口= j c a v a 彳 2 - 1 7 1 ，口= 0jx 口c a v a 彳 2 1 8 由式2 - 1 7 可以看出，当路段交通量饱和的时候，v a 0 ，把它理解成因为路段通行能力约 束而引起的等待时间也是可以的。在实际中，路段总的旅行时间由两部分组成：行驶时间和路段 达到通行能力的时候在交叉口的等待时间。因此，直观匕可以把关于路段通行能力约束的拉格朗 1 4 第二章拥堵交通网络模型 日乘子匕解释成饱和路段在交叉口处的等待时间。 2 2 3 两种求解算法的介绍 容量制约交通分配模型属于带线性约束的非线性规划问题，求解的方法主要有两类：惩罚函 数法和拉格朗日乘子法。惩罚函数法求解带线性约束的非线形规划问题的基本思想是利用问题的 目标函数和约束函数构造出带参数的增广目标函数，把线性约束非线形规划问题转化为系列无 约束非线形规划问题来求解。增广目标函数由两个部分构成，部分是原问题的目标函数，另一 部分是由约束函数构造出的惩罚项，惩罚项的作用是对超出可行域的点进行惩罚。惩罚函数法主 要有两种形式。种称为外部罚函数法( 或称外点法) ，这种方法的迭代点般在可行域的外部移 动，随着迭代次数的增加，惩罚的力度也越来越大，从而迫使迭代点向可行域靠近。而且外惩罚 函数通常和拉格朗日乘子法结合在起，构筑增强拉格朗日乘子法；另种称为内部罚函数法( 或 称内点法) ，它从满足约束条件的可行域的内点开始迭代，并对企图穿越可行域边界的点予以惩罚， 当迭代点越接近边界，惩罚就越大，从而保证迭代点的可行性。 ( 1 ) 增强拉格朗日乘子法的基本原理 下面先介绍拉格朗日乘子法的基本原理，拉格朗日乘子法以下面的非线性规划问题为研究对 象： m i i l 乙( w ) = r t a ( w ) a w + - i - t t g ( x ) + 专c ig ( x ) 1 2 2 1 9 s f ( 2 - 3 ) ( 2 - 5 ) 增强拉格朗日函数可以表示为： 1 厶( x ，) = z ( x ) + g ( 功+ 去c ig ( x ) 1 2 2 - 2 0 二 其中c 是外惩罚参数，是任意正实数；是关于约束方程g ( 功相对应的拉格朗日乘子向量， 其各个分量不小于零。给定乘子向量和惩罚参数c 七，则标准的增强拉格朗日乘子法可以描述 为以下的邂水姗： d 七= m a x ( o ，七+ c ( x 。一c o ) ) 2 - 2 1 然后在r ”蠡k _ t _ x t 以( ，) 最小化，于是获得新轮的用户均衡临时解。再根据最新得到 的临时解更新乘子向量，同时放大参数： “1 = m a x ( o ，七+ c ( 屯一c ) ) 2 - 2 2 c + 1 ：k c 七 2 - 2 3 其中，k 1 ，其中惩罚参数和乘子的初值可以任意选取。可以证明，惩罚参数c 足够大的 时候，只要乘子向量接近最优拉格朗日乘子，0 ( ，) 最小化的解便趋近最懈x ，所 有适用于无约束规划的方法都可以适用于增强拉格朗日最小化问题的求解。 经过推导，最终的增强拉格朗日乘子函数为： 1 5 东南大学硕士学位论文 工l e o 。( l ，) = z ( x ) + 去莓【m a ) 【( o ，心+ 昭口( 以) ) 2 一疋】 秘 于是，增强拉格朗日乘子只需再x 域e 对目标函数进行优化，这样可以节省计算时间并减少 对计算资源的占用。此时，拉格朗日乘子可更新如下： ：+ 1 = ：+ c 七g ：( x ：+ c g 。( x ：，心，力= m a x o ，：+ c 七g 口( ) 】 2 - 2 5 ( 2 ) 内惩罚函荔眩的基本原理 内惩罚函数法以下面的非线性规划问题为研究对象： 幽 z ( w ) = r 乞( 叻咖+ 厂p ( 以) 2 - 2 6 j t ( 2 - 3 ) ( 2 - 5 ) 其中，y 是内惩罚参数，而且： p ( x o ) 一- 。g 警- - x a 讹彳 物 对公式2 - ， 7 两边关于x 口求导得： 塑亟! ： ! v 口彳 出。c o x 。 目标函数对路径搬求骱导数，得到广义路径旅行时间： 2 猫 斋= 弘+ 7 掣既 2 彩 比较公式2 - 1 4 ，可以得到： ：d p - ( x o ) 2 - 3 0 如果厂 0 ，那么所有路段的 0 ，也就是说不饱和的路段也有1 ，口 0 。这看起来好像 与公式2 - 18 和2 - 19 不相符。侣是。我们取公式2 - 3 0 右边的极限，可以得到： 掣 o ，狮矾一- 。 i f l i m ，卅x a g ( x 口一c 。) 2 g l 2 3 8 2 惩罚项在内函数中所占的比例 在内惩罚函数法中，用内惩罚函数代替原目标函数，内惩罚函数和惩罚项的总和。随着最优 解的不断逼近，惩罚项对内惩罚函数的贡献应当不断下降。因此，利用惩罚项对内惩罚函数的比 例，可以用公式2 - 3 9 作为收敛准则： 业! 占， ( x ) + z ( 功 。 经过多次运行程序进行检验，建议取岛= 0 。 2 3 4 内惩罚函数法流程 2 - 3 9 步骤l ：用起点算法求解无约束交通分配子问题，获得路段交通量的初始可行解z o ； 步骤2 ：初始化。设初始惩罚参数y o = l ，根据公式2 - 3 7 确定d 0 ，根据公式2 - 3 3 确定f o ，根 据公式2 - 3 2 确定初始伪可行集。设迭代参数n = l ； 步骤3 ：调用起点算法主循环函数，求解内惩罚函数下的用户均衡问题。获得和特定的惩罚 参数，o 相对应的路段她的黜；转煳4 ； 步骤4 ：收敛隹啦验l 。根据公式2 - 3 8 进行【i 5 渤r 性l 检验，如果满足收敛性条件，结束循环。 如果不满足，转入步骤5 ： 步骤5 ：收敛性硷验2 根据公式2 - 3 9 进行收敛性2 检验，如果满足收敛性条件，结束循环。 如果不i i 学足，转入步骤6 ； 步骤6 ：取力= 刀+ 1 ，根据公式2 - 3 5 更新惩罚参数y 一，根据公式2 - 3 7 更新等待时间d ”的 值，根据公式2 - 3 3 更新s “的值，根据公式2 - 3 2 确定更新伪可行集，调用起点算法的主循环函数， 然后转入步骤4 。内惩罚函数法的流程图如图2 - 3 所示。 1 8 第二章拥堵交通网络模型 2 3 5 内惩罚函数法实例详解 继续采用图2 2 所示的路网，下面我们用容量制约模型进行交通分配，然后利用分配结果进 行比较。参数设置方面，取o = l ，最大最小路径费用差为0 0 1 ，占l = 0 8 ，岛= 0 ，扩张因子 0 2 5 ，在经过l 轮迭代后，可以看到由起点算法分配得到的初始可行解中的过饱和路段的流量发 生了不同程度的减少，但是仍然没有满足路段约束条件，其他刁蝴的路段的交通量得到重新分 布，需要继续进行迭代。 经过2 6 7 0 轮，收敛性检验l 的结果为0 6 4 6 0 8 4 4 ，小于岛= 0 8 ，算法收敛，退出迭代。容 量制约交i 疆盼配的结果见表2 - 3 ，此时拥堵路段5 6 的流量以远小于容量，其余3 条过饱和路段 的流量也满足容量约束条件。 1 9 东南大学硕士学位论文 表2 - 2 内惩罚函数法篇次迭代结果 暇c ，砖 础 l 巧9 0 08 0 0 8 0 00 4 0 0 3 6 6 5 0 4 3 3 5 0 3 7 1 6 6 8 6 l 鼻4 o 8 6 1 8 4 4 岛7 0 懈1 4 8 帽1 4 5 7 1 6 6 1 6 6 5 0 1 6 6 5 0 o 4 2 8 3 4 1 9 1 8 6 4 0 0 4 5 0 8 3 4 9 2 3 8 3 8 7 6 5 0 7 6 5 4 4 3 6 6 3 2 & 8 7 2 8 8 5 8 3 8 2 5 0 8 2 5 0 8 o 4 1 配 2 7 1 2 l 瑚7 0 0 4 0 0 4 0 00 1 2 岖3 0 0 0 00 1 3 日7 0 0 5 7 1 6 65 8 3 8 0 路段路段通行能力交通量 费用 费用导数等待时间 l 巧 9 0 08 0 07 6 5 5 5 10 0 0 3 2 7 7 50 8 1 2 7 9 5 1 4 2 0 5 9 0 4 5 5 4 9 欲4 巧 5 4 4 1 2 5 1 3 s 诵 1 0 3 5 8 7 4 s ：1 鹅昕 1 1 4 9 9 9 7 lo 3 4 4 1 9 lo 0 5 0 6 l 8 0 4 0 堪 7 8 1 2 明雷 9 m 5 5 5 1 5 2 3 9 9 7 1 3 日 7 0 05 9 9 1 1 8 8 6 80 0 0 5 9 1 8 3 70 7 8 9 姆 鼹妻窖鲫 o o o o 衄o o嬲沥刀o o o o o o o oo旅o o嘲膨肌o o o o o o o l l 彻姗彻鲫咖姗螂枷姗彻鲫瑚彻彻瑚 彻 似蛳似她一 m | 馨奶 o 0 o o o 0 o酾孔o o o o o o o o 2 4 8 2 2 l 一一一一一。一一一一一一一。一一一。一一一一一。一一一一一一一。一一一。 椭姗姗享彻。袱枷砉彻劝姗姗。枷姗枷。彻姗瑚鲫湖铷啪枷姗御鲫彻御瑚咖瑚瑚瑚 纠瑚她眦一蜥 第三章路网要素瓶颈识别 3 1 1 交通瓶颈的定义 第三章路网要素瓶颈识别 交通拥挤是交通需求( _ 定时间内想要通过道路的车辆数) 超过道路通行能力时，超过通行能 力的那部分车辆滞留在道路匕形成排队的交通现象 3 3 1 。当道路网某个路段或者交叉口的交通流量 超过其通行能力时，行经此处的车辆速度降低，拥挤度增加，此路段或交叉口即形成了一处交通 瓶颈。交通瓶颈还可以表述为：因为交通事件或者通行能力限制导致道路服务水平下降的位置。 根据研究对象的不同，可以对交通瓶颈的进行简单的定义： ( 1 ) 路网瓶颈：研究对象为整个路网，在进行瓶颈识别时，路网内全部可能的瓶颈均应加以 考虑。本文研究的就是均衡网络中的路网瓶颈。 ( 2 ) 路线瓶颈：研究对象为起讫点之间的出行线路，在进行瓶颈识别时，只对线路内可能的 瓶颈位置加以考虑。 ( 3 ) 设施瓶颈：由于设计的原因，同线路匕有些路段通行能力大，有些路段通行能力小。 通行能力小的路段就是设施瓶颈。研究设施瓶颈的个特点是：考虑的是路段通行能力，而不是 服务交通量。有可能在现状交通条件下，设施瓶颈处车辆行驶速度很快，服务水平很高，所以设 施瓶颈