（交通运输规划与管理专业论文）交通分配起点算法的原理与实现.pdf

摘要 摘要 本文研究的起点算法是国际上新提出来的一种基于路径的交通流量分配算法。由于其对目标函 数的二阶导数信息地充分利用，所以它比只利用目标函数一阶导数信息的f r a n k - w o l f e 算法收敛速度 更快、精度更高；又因为它利用限制子网络保证了网络的无环性，使路径穷举成为可能，所以它比 投影梯度算法耗费更小的存储空问起点算法的巨大优势使对其的研究成为一件迫切的工作本文 的目标就是系统研究起点算法的原理，尤其是一些细节的问题，并且在充分研究的基础上实现算法， 然后对该算法进行实例检验，评价算法的效率。 本文主要分为三个部分； 第一部分，文章系统研究了算法的原理，尤其是一些细小的、容易被人忽视的问题本文更是不 惜笔墨详加说明，一些抽象的概念都有形象的实例印证对起点算法和b u s h 算法的异同点，本文 也做了深入的探讨相信通过本文的研究，任何交通工作者都可以将起点算法用于交通规划实践 第二部分，文章采用c 程序语言在计算机上实现了起点算法，通过实践检验了算法易于程序 实现在算法实现过程中，本文设计了输入输出数据格式，网络数据、o d 数据在计算机内存上的 存储结构。文章最后还设计了起点算法一些难点的计算策略 第三部分，文章用一些标准网络检验了算法的计算效率，通过实验，起点算法对不同规模类型 网络的适应性有了清晰的表述。在检验过程中，文章还设计了一种专门适用于起点算法的收敛判断 标准，它对起点算法的计算效率有显著改善，文章同时探讨了实践中收敛精度取值应该注意的一些 原则并给出了一些建议值 最后，文章评价了起点算法的优缺点，指出了其改进方向。 关键字：交通分配；起点算法；用户均衡；收敛标准：实证 东南大学硕士学位论文 a b s t r a c t o r i g i n - b a s c aa l g o r i t h ma s an c w 锄ca s s i g n m e l a ta l g o r i t h mi sp r o p o s e dr e c e n t l y , w h i c hi sa r o u t e - b a s e da p p r o a c h b c , c a l l o f0 l i g i n - b a s c da l g o r i t l a m sm a k i n gg o o dl 埒eo ft h ei n f o r m a t i o no ft l a c s e c o n d - o r d e rd e r i v a t i v e so fo b j e x t i v cf u n c t i o n ，i th a si i i o i ce x c e l l e n tc o i l v c r g c n ( xp e r f o r m a n c ea n db e t t e r p r e c i s i o nt h a nf r a n k - w o l f ea l g o r i t h m b e c a u s eo fo r i g i n - b a s e da l g o r i t h m sm a k i n g $ u l r l ，n oc y c l e si nt l a c 蛐cn e tw i t ha 删c t i n gs u b n e t w o t k , i tw o u l dc o s tk 辩rm e m o r yt h a ng r a d i e n tp r o j c , t i o na l g o r i t h m , f o ra l g o r i t h m sn o v e l t y , o n l ys e v e r a lp e l s o l h a v ek n o w l e d g ea b o u to r i g i n - b a s e aa l g o r i t l l m t i l ep u i p o s i o ft h i sp a p e ri st h e o r yo fo r i g i n - b a s e da l g o r i t h m , e s p e c i a l l yt oi n t r o d u c e8 蛐cd e t a i l so ft h ea o l 口o r i t l a m t h e a r t i c l ev e r i f i e dt h i sj a g o r l t h mw i t hs o m es t a n d a r dl a e t sa n df o u n do u tt h ea l g o r i t l l m sp e r f o r m a n c e i nt h ef i r s tp a r t , t h ep a p e rp r e s e n t e dt h ep i o c h l r eo fo f i g 醯b a s c da l g o r i t h m e s p e , e i a l l y , s o i i i ct h i n s a n ds o m eq u e s t i o n s , w h i c h1 1 1 1 ：e a s i l y 玳笛l a 曲e d ，a 地d i s c u s s e di nd e t a i l t h i sp a p e rm a d eac o m p a r i s o n b c l w p i 。nt l a eo r i g i n - b a s e aa l g o r i t h ma n dt h eb u s ha l g o r i t h n li t i sb e l i e v e dt h a te v e r yt r a f f i ce n g i n e e r c o u l d 嘴o r i g i n - b u e aa l g o r i t l a mi ni i 斌i cp l a n n i n ga f a rr e a d i n gt h i sp a p 甑o i nt h es e e o i l dp a r t , t h en s e a r e l am a d eap i o c c d u b a s i n gm i g i n 由鹞c da l g o r i t h mi nc + + l a n g u a g e i n t h i sp r o c e d u r e ，t h ea u t h o rd 鹤i g n e dt h ef o r m a to ft h ed a 忸a n dt h es t o r a g em a n l m c ro fn 毗d a t aa n do dd a t a 缸c o m p u t e r ht h ee n d , t h ea u t h o rd e s i g n e df i l ew a ya b o u th o wt oa c t u a l i z et h en o d mo ft h eo r i g i n - b a s e x l a l g o r i t h m ht h et h i r dp a r t , t h ep a p e rv c r i f i e x lt h e 讲蛳a s c da l g o r i t h m se f f i c i e n c yw i t h m es t a n d a r dt r a f f i c n e t s b e f o r et h i s t l a cp a l e rd e s i g n e da8 p e c i a lo o n v c r g e n e ec r i t e r i o nw l a i e hi sf i tf o rt h eo r i g i n j o a s e a a l g o r i t l n n f i n a l l y , t h ea r t i c l ed i s c u s s e ds o m ep r l n d p l cf o r t h ev a l u eo f c o n v e r g e n c ec r i t e r i o ni np r a c l j c l ! l u t e d l y , t h ea r t i c l ep o i n t e do u tt h ea d v a n t a g ea n dt l a cs h o r t c o m i n go fo r i g i n - b a s e da l g o r i t h m , a n d g a w8 0 雠a d v i s e sf o ri m p r o v i n gt h ea l g o r i l l a m k e yw o r d s ：t l a f f l ea s s i g n m e n t , o r i g i n - b a s e aa i g o r i t l 锄, u s e fe q u i l i b r i u m , c o n v e r g e n c ec r i t e r i o n , e x p e r i m e n t a lw r i f i c a f i o n n 符号往释 文中符号注释表 符号定义备注 g有向网络g1 ( ，彳) g 。 起点d 的限制子网络g o1 ( ，4 ) g n节点集- p i 为节点数 a弧集彳1 1 i ，力 n x n wo d 对子集合 一 i ，。 o d 对w e w 之间的所有路 “ 径集合 k “从0 到f 所有路径的集合 d出行起点集r d出行终点集s i ，j邙蘸i ，j e n 弧41 【f ，j e a 0 d 对w e 矽之间相应 的分布交通量 路径k k ”上相应的路径交 路段a 爿上的交通量 起点0 出发经过路段4 彳的 交通量 路段a 彳的旅行费用 陋i 为弧段数 ，表示矽的元素 七表示k 的元素 k 表示k “的元素 d 表示d 的元素 d 表示d 的元素 善；6 z 硝，6 z 1 翰七；d r 6 三l o 。荟；昭，虼o d - 1 ，伽七；o r 6 # _ o f - t a o ) c fo d 对w 之问路径七e k - 的。f t 。阮弘三，呓- 1 , i r a e k ；o r 呓- 0 石翥舢酬之间最大路径弘m a x c f 石”翥舢郇之间剧、路径 m i m s 路径区间s k v 4 矿 东南大学硕士学位论文 路段4 的头结点 口一f ，】，n - j 路段4 的尾结点 起点0 出发流经结点j 的流 量 从起点0 经过路段4 的通路 比例 从起点0 到结点f 的平均费用 从起点0 到路段4 的平均费 用 结点，的基本通路 结点，的非基本通路集 结点j 的最后共同结点 a 一【f ，力，4 i 疗- - + q 。 i i - ii t - j ，t 吒o - l s v j 副v - ， 群。盔：驴 以一+ 吒 具体见2 1 3 定义5 肿j - 伽g 口。a k - j , a b j 从起点d 出发的路径都经过z 铆， 嵋 计算近似h e s s i a n 矩阵的参数具体求值见公式2 7 p 计算近似i k s s i 柚矩阵的参数 具体求值见公式2 7 。从d 出发到达，的流量中经屁，一 “叫过i 的比例 。 ，四口：) 。 耋之间最大。最小路径费用 ”懈k k “，肛0 一曲i 七k 耐 v i q 疗 吖 心q 舫 妇， 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：辛盘兰l 日期：删 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 期： 第一章概述 1 1 研究背景及意义 第一章概述 交通量分配是城市交通网络规划与交通需求预涮的关键技术，它在交通量预测、管理效果评价 中都被反复的进行【l j 交通规划当中的很大一部分工作就是反复地进行交通量分配。可以说，分配 的工作效率和精度直接决定了规划工作的效率和规划实施的效果。因此众多的交通工程学专家都把 毕生的精力用于交通量分配算法的研究，以期找到一种快速、准确的方法迅速实现交通璧在道路网 络上均衡分配。 交通分配就是在给定旅行时间函数和起讫点交通量分布已知的情况下，用适当的数理方法获得 交通量在路网上的分布模式。它可以是遵循w a r d r o p 原理的用户均衡分配【2 】，也可以是使总旅行时 间最小化的系统最优均衡分配，这两种方法都可以构造成一个带有非线性目标函数和线性约束的数 学规划问题。f r a n k - w o l f e 方法通常用于交通分配，并且被植入成熟的交通规划软件包【”这个方法 简单明快，不要求太大的储存容量，容易棱交通工程师理解和接受；更重要的是，虽然它遵循被使 用的路径的旅行时间不高于未被使用的路径的旅行时间这个原则，但是它不必记忆“被使用的路径”， 所以适用于大型的交通网络 随着城市规模的急剧扩张，城市道路交通流量不断趋近于饱和，f r a n k - w o l f e 方法的缺陷就显露 出来了由于它在流量转移时只用到了目标函数的一阶导数，因而它的收敛性就不是那么完美了， 特别是在网络饱和度超过一定的界限以后，f r a n k - w o l f e 算法就可能出现最终解在某一范围内上下波 动的现象，就是所谓的z i g z a g 现象，更严重的还会得到错误的解。同时，f r a n k - w o l f e 方法的广泛 应用使人们忽略了对路径解的认识，路径解的不唯一性1 1 】也妨碍了对路径解的深入研究而路径解 求得对于交通网络敏感度分析是有重要意义的。 近些年，基于路径的交通分配算法引起了学术界的广泛关注。这些算法把所有使用路径及其流 量看成当前解。利用这些信息。流量从高费用路径转移到低费用路径，获得平衡事实上，最初提 出的解决交通分配的方法就是一种路径算法。在该法中，按照循环顺序逐步考虑每个o d 对子，流 量从高费用的路径转移到最低费用路径上，直到两个路径的费用相同为止。一般来说，路径算法还 原了w a r d r o p 原理的最初思想，易于理解，它的精度可以达到很高的水平。但是，该算法有一个缺 点，那就是存在一个路径穷举的问题，由于环路的存在使得穷举几乎成为不可能实现的事，即使穷 举能够实现，算法的存储空间也不允许 2 0 0 2 年，以色列学者h i i l e lb a r - g e r a 首次提出了起点算法f 3 l 。该算法实质上就是一种路径算法， 他通过建立子网络的方法避免了环路，从而使得路径可以穷举该算法从提出起到现在已经有4 年 的时间了，但是并没有多少人对它进行过研究，尤其是国内的学者就更少了根据作者介绍，该算 法效率很高，不管是时问效率还是空间效率。作为一种新出现的优秀算法，我们有必要对其进行检 l 东南大学硕士学位论文 验，以期能够尽早将其用于交通规划、管理的工程实践。 1 2 国内外研究概况 1 2 1 国外研究状况 w a r d r o p ( 1 9 5 2 ) - 首次提出用户平衡条件嘲，随后b e c k m a n n 用数学方法表示了该平衡条件上世 纪六十年代后期出现了求解该问题的有效算法，使得运用u e ( u 鞴re q u 砌) f i 吣条件求解交通分配问 题成为可能 求解u e 问题的比较经典的算法是1 9 5 6 年提出的f r a n k - w o f f e 算法该算法简单、实用，并且 意义明确。对计算机的要求也不是很高可以适用于任何交通网络，当前绝大多数交通规划软件都采 用该算法进行交通分配，唯缺点就是收敛速度比较慢 一 近几年，路径的算法( r o u t e - b a s e dm e t h o d s ) 不断引起关注d a f c r m o s ( 1 9 6 8 ) 、d a f c n n o s 和 s p a i i o w ( 1 9 6 9 ) 首先提出了路径算法的思想h ，g 掀( 1 9 6 8 ) 独立实现了这种方法御b o t h e r 秆 l a t t e r ( 1 9 8 2 ) 实现了一种相似的路径算法其思想就是利用路段的费用导数计算转移流量，然后集计 所有o - d 对子中的转移量得到搜索方向，沿着该方向目标函数的最小点就是下一个解。l a r s s o n 和 p a t r i k s s o n ( 1 9 9 嘴其称为发散单纯分解法徊i s a 韶弭g a m c ds i m p u c 妇dd e c o m p o s i f i o n ) 【6 1 。j a y a k r i s h n a n 等人( 1 9 9 2 堤出了另外一种路径算法，它根据梯度投影( g r a d i e n tp r o j e c t i o n 朋印m h m ) 确定转移流量 研 以色列b e n 矗u i o n 大学的h i l l e lb a r - c m a 在他的博士论文里提出了一种基于起点的算法 ( o r i g i n - b a s c d a l g o r i t h m ) ，该算法采用新建一个子网络的方法避免了环路，使得路径穷举成为可能； 同时该算法充分利用了目标函数的二阶导数信息使得解迅速收敛，从而使该算法成为一种资源耗 费小，分配精度高的优秀算法。 1 2 2 国内研究状况 国内在交通分配方法研究方面起步较晚，同时由于国外同类研究在理论上已经比较成熟，因此 国内学者基本上是在借鉴、沿用国外研究成果基础上，根据中国的具体交通现状对模型和算法进行 拓展和完善直至创新。王炜( 1 9 8 9 ) 对非平衡多路径交通分配模型进行了改进，提出了快速的结点 分配算法嗍，同时开发了相应的应用程序。陈森发等( 1 9 9 3 ) 讨论了多种交通方式的混合平衡分配 问题，并给出了改进的f r a n k - w o l f e 算法哪 陆锋( 1 9 9 4 ) 对最短路径算法进行了系统分类和综合评价，并对算法在实时化和并行化方面的 发展趋势进行了讨论。 东南大学任刚的博士论文对管制条件下的交通分配做了系统的研究，建立的d m a m u t ( d e t e r m i n i s t i cm o d e lo fa s y m m e t r i cm u l t i m o d a lu s e r - e q u i h b d u mw i t ht u r n - d e l a y s ) 模型对于解决实际 2 第一章概述 分配问题作用颇大1 1 1 1 东南大学的程琳( 2 0 0 6 煨出的可变步长的投影梯度算法是对投影梯度算法的一个丰富，其运算 效率和运算精度都达到了一个新的台阶l “ 1 3 研究目标及主要内容 1 3 1 研究目标 本文主要针对h i l l c lb a r - g c r a 提出的分层算法进行研究研究着重于理解该算法的运算流程， 掌握其流量转移的原理；同时，在分析算法运算条件的前提下，编制程序实现算法，主要解决数据 结构、算法策略等问题。在程序成熟之后，采用现有的成熟例子对算法的运行效率、运算精度进行 检验，借以探讨收敛标准，并对现有的一些常见的收敛标准进行分杯找到种能真实反映分配精 度的收敛标准。根据随机用户平衡配流理论提出实践中收敛度取值的原则。最后，为使算法在考虑 转向延误的网络上也能适用，本文对算法提出一些改进建议 1 3 , 2 研究内容 ( 1 ) 探讨算法高效率的内在原因 本文目标就是研究起点算法的原理，理解，并掌握起点算法的本质内容，为以后将该算法用于 实践扫清障碍为了把握算法的核心，就必须从算法的流量转移原理入手清楚如何确定解释算法 收敛迅速、精度高和避免路径存储的内在机理，同时，文章还对起点算法和b u s h 算法进行了比较， 明确了二者的优缺点 ( 2 ) 用计算机语言实现起点算法 在充分掌握算法原理的基础上，本次研究计划用c h 语言编制程序实现算法，检验算法在计算 机上的实现难易程度和占用内存的大小并且为实证起点算法做好先期准备。 设计适合起点算法的收敛准则 设计适用于起点算法的收敛精度判断标准，设计的标准应该是意义明确、容易实现，并且不能 过多的增加计算量，对算法的效率应该有改善作用 ( 4 ) 用实例检验起点算法的效率 利用本次研究编制的程序采用一些国际上通行的标准网络检验算法的时问效率和空间效率，分 析算法对于不同规模、不同类型网络的适应性，并且明确起点算法能够达到精度极限和达到这样精 度需要耗费的时间。 ( 5 ) 提出改进算法的方向使之适用“边到边”阿络 3 东南大学硕士学位论文 在分析起点算法的优缺点的基础上，提出今后继续研究的方向，今后的研究的目标是使起点算 法能够适用于边到边”网络。 1 3 3 论文章节安捧 本文总共分为六章，除第一章序论和第五章结论和展望外论文的主体部分是第二，三，四章 第二章主要研究起点算法的基本原理，突出起点算法高效收敛，求解精度高，无需路径存储的内在 机理，并将其与b u s h 算法进行比较，明确二者的异同点；第三章介绍算法的程序实现，包括输入 输出数据文件格式、数据存储结构和几个关键部分的计算策略；第四章主要对不同的收敛标准进行 比较，提出实践中收敛标准的取值，设计出适合起点算法特点的收敛标准并且用实例验证不同收敛 标准对算法效率的影响；第五章用多个不同规模，不同类型的实际网络检验算法的效率，检验内容 包括解的精度及其时间耗赞。文章盼整体布局结构如凰1 1 所示 圈1 - 1 论文章节结构图 4 第二章算法的摹本原理 2 1 算法描述 2 1 1 算法概要 第二章算法的基本原理 w a r d r o p 用户均衡原理提出：拥挤网络上的交通以这样一种方式分布，即任意o d 对之间的所 有被利用的路径具有相同的最小费用，而其余所有未被利用路径的费用则大于或等于此最小费用。 b e c k m a n n 等( 1 9 5 6 ) 首次用数学模型表示并证明了w a r d r o p 的最优化条件该模型由一个最小化的 目标函数和几个线性约束组成。为了得到满足这样条件的交通分布格局，交通工程师提出了许多的 算法来求解该模型。最初的f r a n k - w o l f e ( 1 9 5 6 ) 算法把网络上的交通量看成是无差别的交通流，不 考虑路段上的交通量来自何方，它总是把路段交通量当作一个整体来考虑它只是把目标对准 b e x k m a n n 数学模型，不断进行流量更新的目的就是为了使目标函数达到最小值，而不理会该模型 是来自于w a r d m p 的最优化条件f r a n k - w o f f e 算法在计算过程中不断地从当前流量出发，得到使耳 标函数下降的路段流量向量的搜索方向，最后根据最优步长和搜索方向得到路段流量向量新的解 本文研究的算法之所以叫做起点算法是因为它考虑了路段上的流量是来自于哪个特定的起点， 每次只更新来自于同一个起点的流量它把交通网络上无差别的交通量按起点分成不同的层次，即 来自不同的起点的交通分别属于不同的层，算法按照一种次序，独立地考虑来自每个起点地流量n 塞 时，将来自其它起点的交通量看成是背景流量k 同时，不同的层之间由于流量叠加会产生互相影响， 因此，通过反复的更新各层的交通量达到最后的均衡状态。在每个层上到达每个结点的流量都是来 自于同个起点的，根据w a r d r o p 用户均衡原理，来自同一个起点的交通流量当它们到达同一个结 点的时候，它们所走路径的费用应该是相等的，并且都应该等于最小路径费用，如果发现有不等的 情况，就要将高费用路径上的流量部分转移到低费用的路径上这就是起点算法的思想，起点算法 的形象表示见图2 - 1 所示 圈2 - l 起点算法流量加载示意 5 东南大学硕士学位论文 我们把交通分配问题拆分为两个问题：哪些路段该被选用? 有多少流量该分配到这些路段中? 对第一个问题的回答，起点算法用一个限制子网络g oe g 来表述，定义g 。之外任何路段流量为0 对于第二个问题，起点算法通过流量反复地从高费用路径向低费用路径转移，使路径流量不断的向 最终的均衡状态逼近，每次确定转移流量的大小时都充分利用目标函数的二阶导数信息，从而保证 了解的高精度和快速收敛。因此，起点算法主体就是由两步组成：更新限制子网络、更新基于起点 的路段流量。 这个算法的关键点是限制子网络总是无环的；也就是说，它们不包含任何有向回路限制子网 络为无环的有几个优点：第一，它允许简单路径流量的定义，即不含有环的路径上的流量，从起点 出发的所有路径流量都是简单路径流量；第二，它能够允许定义最大费甩c 见2 2 1 ) 第三它允许 定义拓扑顺序c 见2 2 2 ) 。 2 1 2 算法的流程 算法的流程可以分成两个部分，即初始化和主循环，见图2 - 2 在算法的开始阶段首先进行初 始化，其目的就是先将c ) d 交通量粗略的分配到交通网络上，为接下来的交通量转移奠定基础。初 始化时依次考虑各个起点，寻找从各起点出发的最短路径树，然后将全部o d 交通量都分配到最短 路径树上( 全有全无分配) 一个起点分配完彻始化) 以后可以无须更新路段费用。初始化得到的结果 是各路段的初始起点交通量和初始起点通路比例c 见2 1 3 ，定义4 ) ，两者为算法进入主循环提供了 充分条件。 进入主循环以后，算法的主要工作就是反复地进行限制子网络和起点路段流量的更新，直到满 足规定的精度或者达到了最大循环次数。两者具体操作过程在后续章节叙述 广一一一 i i i i i 主 循 环 图2 - 2 起点算法流程 6 i l l i i l i j 一一一一 ，l 一 一 一 一一 一 一 一一一一一一一一一 吲川川川一，。 雪畛窜 初始化 第二章算法的基本原理 2 1 3 算法当中的定义 定义1 头结点和尾结点：任何一条路段都是由前后两个结点组成，记为4 一f ，】，我们把路 段口的终点就叫做头结点，记为吒。a k 一，；同时，路段4 的起点就叫做尾结点，记为4 。，4 ，一f 定义2 起点区问流量，r ：来自起点。利用路径区问s 的总流量，也就是： f 。乏基落 ( 2 1 ， 定义3 起点结点流量，? 和起点路段流量- f e e ：它们是起点区间流量的特例，对于每个结 点，- 0 ，下式成立； 彤。荟 j f ： - 捆唯 厣彳。荟n 三彳 ( 2 2 ) 定义4 起点通路比例( o r i g i n - b a s e da p p r o a c h ) 。o ：把路段4 看成是进入4 的头结点- ，的 一条通路，我们把从起点d 出发到达结点j 的流量中由路段4 到达的比例叫做路段口的起点通路比 例当起点结点流量，非零时，起点通路比例口：一0 ，# 否则起点通路比例可以任意选择 无论如何，起点通路比例必须满足下列条件： 口：一1w ；，一0 - j a 。o 一0v a 隹g o 口。o 乏0 定义5 基本通路和非基本通路：对于每个结点，一0 ，可能有多条路段以它为头结点，我们选 择具有最小平均费用的一条通路作为基本通路，记为，b j g ：p ，) - ，：同时，把所有其它 7 东南大学碗上学位论文 通路作为非基本通路，记为n b ，n b - 忙g o ：一j , a - 6 j 定义贡献路段和使用路段：这两个概念是针对特定的起点0 才有实际意义的，离开特定的 起点而空洞的说某条路段是贡献路段或使用路段是没意义的所谓使用路段，顾名思义，就是该路 段4 披从起点d 出发的交通所使用了，也就是 0 ：而贡献路段是指路段通路比例严格正的路段， 即a 。o ，0 。 舣储解檄用吖矾熊础刎黼威解蝴肌彤。兹。疆昏 定义8 路段平均费用以。如果一【f ，力，我们把路段4 增加到从d 到f 的每条区间上，就得 到一个从d 到结点，- a 的区间集合，这些区间都从路段4 到达结点，从路段4 到达结点，的区 问平均费用就是路段平均费用。-q 兀口；根据结点平均费用和路段平均费用的 姻r 嘱p 口d 口i k 定义，我们可以得到二者之间的相互关系： 订- 0 o j 。曼鲁圮 q q p ：一f | + a ： 2 2 更新限制子网络 2 2 1 算法的初始化 b e e k m a n n 等人建立的用户均衡模型对于几个结点的小型网络当然可以通过数学方法求解，但 是，实际的交通网络都是规模较大，结构负责的网络，只能通过数值的方法求解。任何交通分配算 法进行的开始一般都有一个初始化的过程，起点算法也不例外起点算法初始化的目的就是将出行 8 第二章算法的基本原理 交通量分配到网络上，得到一个初始的分配结果，为后续的流量更新做准备对于每一个起点，初 始化以后都会得到一组分配结果，包括起点路段流量和起点通路比例。具体的初始化过程如下： 从起点网终中的任意一个起点d 出发，根据路段自由流旅行时间搜寻最小路径树。 根据“全有全无交通分配将从起点o 出发的所有交通出行分配到最小路径树上：最小路径树 上所有路段的起点通路比例全为1 ，不是最小路径树上的路段起点通路比例为0 更新路段费用 根据当前费用，换另一个起点重复 的过程 2 2 2 更新限制子网络的内容 初始化以后或每次更新起点路段流量以后记录下来有关分配结果的信息有起点路段流量和起点 通路比例。通过这些信息我们可以很筒单地就得到交通分配路径流量的解。我们的工作就是根据上 次更新相同起点路段流董的结果，决定本轮循环当中针对当前起点的流量更新哪些路段需要选用、 哪些路段没有必要选用 更新限制予网络过程中，假设当前起点为0 ，首先，根据上一次更新起点0 的路段流量的结 采，即根据口的起点通路比例口：，参照上2 1 3 中关于贡献路段的定义6 ，把起点口的贡献路段全 部找出来组成一个贡献子网络：嘭c a ) - 扣e a ：口： 0 ，这里存在一个问题：为什么不选用使 用路段而是选用贡献路段? 如果选用使用路径，那么。对于那些起点结点流量为0 的结点就没有路 段与之连通，限制子网络的连通性就得不到保证 得到起点。的贡献子网络以后，接下来的工作就是根据贡献子网络计算各个结点的最大贡献 费用矛“。所谓最大贡献费用是指在贡献子网络上，根据当前路段费用，从起点。出发到各个结点 的最大费用。 计算得到屉大贡献费用以后，接下来我们根据g o - 饼u p ，l 彳：孑“( t ) 石可( t ) 得到 起点。的限制子网络这里我们会提出这样一个问题：为什么应该把满足条件石“( t ) 方一( t ) 的路 段p ，j 】加上? 因为结点f 的最大贡献费用小于结点j 的最大贡献费用，那么，从起点d 出发到达结 点，的流量中使用最大贡献费用路径的部分流量可以部分地转移到经过f 到j 的路径上来，这样可 以达到平衡路径费用，减小目标函数值的目的。 9 东南大学硕士学位论文 得到新的起点限制子网络以后，为了后续计算能够顺利进行，算法还要求及时更新起点结点流 量、结点拓扑顺序和最后共同结点( 2 2 3 详述) 。 2 2 3 结点拓扑顺序和最后共同结点 确定了起点。的限制子网络以后，我们还需及时更新结点的拓扑顺序。起点算法的核心就是从 非最优通路向最优通路的牛顿型流量转移，流量转移的集记产生了一个搜索方向，搜索方向和边界 搜索( z 3 4 介绍) 提供一个算法策略，最终达成单起点非约束平街 牛顿型转移流量是通过目标函数的一阶导数和二阶导数的比值获得的目标函数的一阶导数计 算需要用到路段平均费用；而目标函数的二阶导数盼计算比较复杂，一般是对它作一企合理的近似， 近似地计算目标函数的二阶导数需要用到两个参数和最后共同结点( 具体计算过程见z 3 2 ) ，起点 算法采用一个递归过程来实现这两个参数的求解，递归计算过程依据的计算顺序就要靠结点的拓扑 顺序来确定所以，在限制子网络最终确定以后，我们需要及时地确定结点的拓扑顺序和最后共同 结点，为后续的计算做足准备。 拓扑顺序是一组结点与顺序序号对应的函数n d o ) ，雄- 1 , 2 , 3 , ，l i 。特别d ( d ) - 1 ， 如果【f ，力瓯，l 黻n o q ) n o ( i ) 从拓扑顺序的定义我们可以清楚地看出限制子网络决定了 拓扑顺序。同时，根据拓扑顺序的定义，我们发现它不是一个严格的定义，也就是说特定的限制子 网络倪决定的结点拓扑顺序不是唯一的，它只要求确定有限的几对结点的相互顺序事实上，结 点拓扑顺序是为后续的递推计算傲准备的，为了使计算能够顺利进行下去，前面的计算必须能够为 后面的计算提供充分的条件，拓扑顺序只要能满足这个条件就够了，至于没有条件结果关系的结点 之间的相互顺序就无关大局了具体实现结点拓扑顺序计算的方法将在后续3 3 详述 为了说明最后共同结点，假设结点f 是起点。到结点，的所有路径的一个共同结点，即 i e k v k e k 巧 g 0 1 注意，对结点，来说，其自身和起点。总是共同结点我们把g 。中的结点j 的最后共同结点定义为：不包含，的具有最高拓扑顺序的共同结点，记为勋具体计算过程见后 续3 3 2 2 a 实例详解 为了理解更深刻，我们用实倒来说明 实例已知条件如图2 - 3 所示，正体数字表示路段通行能力，斜体加粗数字表示自由流旅行时间。 1 0 兰三兰苎鲨塑苎查堕墨 岛嘞) _ f 如o 1 5 印) 图2 - 3 网络特性、b p r 函数和出行矩阵 在经过一次循环以后，各起点的起点路段流量和起点通路比例如下所示： 表2 1 路段交通量、起点通路比倒和路段费用 号量路段流量起点l起点3起点6 起点8用导数 1 - 4 1 - 2 2 5 2 - 4 2 - 3 2 - 1 3 - 8 3 - 5 3 - 2 4 - 7 4 - ，6 4 - 2 4 1 5 - 8 5 - 7 5 - 3 5 - 2 6 - 卯 0 0 j 0 肿3 5 2o 0 1 o j d 00 o 0 0 6 2 1 o 0 3 0 舯o 2 3咖 3 3 0o o 咖 0 2 73 j b 90 j d o 0 o 2 0 o - 0 01 4 0 50 1 0 1 册o 0 0 0 2 51 3 o j d 9 0 ，8 5o 0 0 09 9 40 0 7 1 j d oo m 6 2 80 0 3 0 9 7o o 8 0 40 j 0 6 0 0 1 2o 2 4 30 肿 0 4 7o j d o o 阉b1 9 6o o 1 o 3 1 2o o 伽b 0 7 53 9 10 0 1 o 1 5o o j d o3 0 2o 0 0 1 0 加o 1 2 3 7 5o 0 口 o o o 0 94 4 2o 0 1 0 0 肿 1 0 03 0 50 0 0 o 舯 o 8 8o 0 02 1 2 1o 1 4 垒! !堑!壁 ! ：丝! 塑! ：竺! ：竺 ! ：堑! ：塑 l l 埘瑚堋哪啷咖哪咖咖埘哪咖哪蝴哪哪哪哪 狮螂瑚。姗o o o o m 酊o o 懈o n o o狮姗研斟懈栅m珊蕃柳抛研挪枷蛳懈拼：鲁 东南大学硕士学位论文 对于起点1 ，根据其起点通路比例确定的贡献子网络以及各结点的最大贡献费用如图2 4 和表 2 2 所示： 图2 - 4 贡献子网络及路段费用 袭2 2 各结点最大贡献费用 根据计算得到的最大贡献费用，最终我们得到起点1 的限制子网络如图2 - 5 所示 图2 - 5 起点1 的限镧子网络 起点1 的限制子网络确定以后，我们计算结点的拓扑顺序和最后共同结点，其结果如表2 3 所 1 2 第二章算法的基本原理 2 3 更新起点路段流量 2 3 1 已知条件 在上一节完成之后，我们假设给定了一个连通的、无环的限制子网络瓯g 所谓连通是指瓯 至少包含一条从口到每个结点，的路径1 所谓无环是指倪不包含任何有向回路该子网络是 单起点的，即网络上所有流量都是从唯一的一个起点0 出发。以后的更新起点路段流量的工作就在 g 。上完成。 实际网络在计算的过程中都可以临时转化成起点为0 的单起点问题，只要把来自其余起点的流 量固定在当前值即可来自起点d 的流量依然是解变量，而其它流量看成背景流量毛。， 同时，路段费用仅仅看作是来自当前起点d 的流量的函数，屯阮) - t 。( ) - f 似+ 毛) 2 3 2 更新流量的程序 所谓更新起点路段流量就是指根据当前路径费用和起点交通量在网络上的分布格局，运用准牛 顿型流量转移实现单起点非约束平衡 牛顿型转移流量是通过目标函数的一阶导数和二阶导数的比值获得的，目标函数的二阶导数实 际计算比较复杂，我们一般都是通过近似计算得到。通过推导( 具体见【1 7 】，4 0 5 - 4 0 9 ) ，最终得到目 标函数对非基本通路的通路比例的一阶和二阶导数如下： 薏咿( 以硼 毒w 竹种鸭) ( 2 5 ) 东南大学硕士学位论文 其中，、以在2 1 3 已经做过详细说明，这里主要对、纸的计算做一个说明。 以、p h o 是计算近似i i c 鹞i 姐矩阵的两个参数，其计算是通过个类似于路段平均费用和结点 平均费用计算的递推过程得到，递推公式如下： - 0 p ；- a - i ：2 以 ( 2 刀 - f ：+ p ： 其中f ：是指路段流量对路段费用的导数，即c - ( i t a 根据公式2 7 ，只要知道当前起点的路 叽 段通路比例和路段费用导数就可以轻松地求得o 、p ；，进而求得目标函数的二阶导数 观察目标函数的一阶和二阶导数，对于其中的一阶导数应该没什么疑虑，它的计算也十分容易， 只要有足够的已知条件就可以轻松地求得。 对于目标函数的二阶导数，我们根据上述公式2 6 和2 7 求解。但是在实际计算中，如果p ：。足 够大，并且。o 和a ；足够的接近1 2 ，那么我们就会得到一个负的目标函数的二阶导数，这种情况 在实际计算当中就出现过。观察目标函数的二阶导数的推导如下： 首先，根据起点路段流量和起点通路比例之间的关系，我们可以很容易得出非基本通路的通路 比例对起点路段流量的导数，该导数根据路段之间的拓扑关系分不同情况表示。结果如式2 8 皇l a 口：埘 f ； a t n ，ah - i f ；n f - b i ，a k j o 4 ：- 4 ，口一口，4 一b j ( 2 8 ) a 疗c 磋，一z 三叶) r d ( 4 ：) tn o ( a 。) o n o o d n o ( a ) 然后根据起点路段流量的导数，推出非基本通路的通路比例对目标函数的一阶导数如下： 嚣。盖薏薏吒厅飞+ 。碱熹篇警厂疗一一镌呻) ( 2 9 ) 1 4 第二章算法的基本原理 有了目标函数的一阶导数，就可以推出目标函数的二阶导数这里我们还必须先知道一个已知 条件，那就是a 2 ，a 口：2 2 x a - l a a ：一0 毒。盖岛隹) 2 + 虿a t 斜0 2 x a , ”i c 彤2 + f ：疗2 。峨：嘉盆铲厅2 坛1 一旄咱) 2 观察目标函数的二阶导数，我们发现它应该是严格地非负的，但是由于近似计算的缘故，实际 计算当中出现了负的情况，这就说明这时的目标函数二阶导数的真实值应该很小，以致计算误差掩 盖了真实值，这时我们就应该取个足够小的正数g ，( 可以取l o - 7 代替目标函数的真实值。 考虑一个到结点，- 吼的非基本通路口和一个可替代的基本通路6 ，6 i ，。按照假设，存在 以p ：，则从口：到嵋的牛顿型转移流量( 比例) 可以由下式给出： z 。m 击雾 ， ，? m a x ( e ，嵋+ 嵋一2 p 二) ”一 其中，是一个微小的正常数，即，0 。 屯m 是连续函数，它的涵义是：为了均衡费用。应当从非基本通路口到基本通路6 的期望转移 流量( 比例) 此时并没有考虑可行性要求。边界搜索( 2 3 3 具体说明) 要求我们应用步长o t a 1 确 保可行性 为了简便起见a 只是取几个离散的值，a 一2 - * , k - o ，1 2 ，从最初a 一1 一直取下去，直到 满足社会压力条件为止当a 值确定以后。根据公式2 1 2 就可以得到从非基本通路盯到基本通路b 的可行转移流量( 比例) 。 e ：由- 曲( a 而鬟汪耐 和。 a ： ，? i o ，p ： 一： ( 2 1 2 ) 【o a ：l厅i o