（运筹学与控制论专业论文）混合交通网络流量均衡分配模型及算法.pdf

摘要 交通分配是城市交通规划中的一个重要组成部分，在城市交通规 划中占有核心地位。1 9 5 2 年w a r d r o p 等提出的用户平衡系统是在固定 需求及交通网络上任何出行者都能正确掌握道路所有信息的假设下 建立的。然而交通行为往往是随机性的，故1 9 7 7 年由d a g a n z o n 和 s h e f f i 等提出的随机用户平衡系统统一了随机分配和w o r d r o p 平衡的 概念。但是在我国城市交通中，以混合交通居主要地位，即在一个路 面上各种交通模式并存，所以用单一模式的s u e 模型来描述实际的交 通状况是不够的。 基于此，本文在系统介绍交通分配模型的基本理论框架和研究进 展的基础上，针对现有研究中存在的主要问题，运用数学规划的方法， 研究了混合交通平衡分配问题。 文章首先简要介绍了交通分配的基本模型及模型解法；在此基础 上，建立了与随机用户平衡条件等价的混合交通随机用户平衡分配模 型，证明了在一定条件下数学规划模型解的惟一性；同时，针对出行 方式间存在相互影响，建立了考虑出行方式影响对称的混合交通平衡 分配模型，证明了其与随机用户平衡条件的等价性及解的惟一性，并 尝试利用遗传算法求解两个数学规划模型；最后进行了算例检验分 析，证实了算法的有效性。 关键词交通分配，混合交通，随机用户平衡，影响对称，遗传算法 a b s t r a c t t r a f f i ca s s i g n m e n ti sac r u c i a lp a r to fu r b a nt r a n s p o r t a t i o np l a n n i n g u n d e rt h ea s s u m p t i o nt h a te v e r yt r a v e l e rc a nk n o wa l li n f o r m a t i o no ft h e r o a dw e l li nt h ef i x e dd e m a n dn e t w o r k , w a r d r o ph a dp u tf o r w a r du s e r e q u i l i b r i u ms y s t e m i n19 5 2 h o w e v e r , t r a f f i cb e h a v i o ri s a l w a y s s t o c h a s t i c ，s os t o c h a s t i cu s e re q u i l i b r i u ms y s t e mw h i c hh a du n i f i e dt h e c o n c e p t i o no fs t o c h a s t i ca s s i g n m e n ta n dw a r d r o pe q u i l i b r i u mh a db e e n p u tf o r w a r db yd a g a n z o nm a ds h e f f i ci n 19 7 7 i no u rc o u n t r y , m i x e d t r a f f i ch a sp l a y e dam a i nr o l ei nu r b a nt r a f f i c s os u em o d e lt h a t c o n t a i n so n l yo n et r a f f i cm o d ec a nn o td e s c r i b et h ea c t u a lt r a f f i cs t a t e w e l l t h et h e s i ss t u d i e st h em i x e dt r a f f i c a s s i g n m e n tp r o b l e m sb y m a t h e m a t i c a lp r o g r a m m i n gm e t h o d f i r s t , t h i st h e s i si n t r o d u c e st h et r a f f i ca s s i g n m e n tm o d e l sa n dt h e i r s a l g o r i t h mb r i e f l y s e c o n d ，i tg i v e st h es t o c h a s t i cu s e re q u i l i b r i u mf l o w s p l i tm o d e lb a s e do nm i x e dt r a f f i cn e t w o r ke q u a t i n gt ot h ee q u i l i b r i u m c o n d i t i o n s ，a n dp r o v e st h eu n i q u e n e s so fm a t h e m a t i c a lp r o g r a m m i n g m o d e l ss o l u t i o n a tt h es a m et i m e ，b e c a u s eo ft h ei n t e r a c t i o n sb e t w e e n t h et r a v e l i n gm o d e s ，t h ee q u i h q ，r i u mf l o ws p l i tm o d e l 晰t l ls y m m e t r i c t r a 衢ci n t e r a c t i o n sb a s e do nm i x e dt r a f f i cn e t w o r ki sf o r m u l a t e d t h e e q u i v a l e n c et ot h ee q u i l i b r i u mc o n d i t i o n sa n dt h eu n i q u e n e s so ft h e r e s o l u t i o nt ot h em o d e la lep r o v e d m o r e o v e r , g e n e t i ca l g o r i t h mi st r i e d t ow o r ko u tt h et w om o d e l s f i n a l l y , t w oe x a m p l e sa r ep r o v i d e d ，a n dt h e e f f e c t i v e n e s so ft h i sa l g o r i t h mi si l l u s t r a t e d k e yw o r d st r a f f i c a s s i g n m e n t , m i x e dt r a f f i c ，s t o c h a s t i c u s e r e q u i l i b r i u mt h e o r y , s y m m e t r i ci n t e r a c t i o n ，g e n e t i ca l g o r i t h m 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：型薹堑 日期：圭塑年月兰l 日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文； 学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：立生羔堑导师签名：丝日期：坐i - 年卫月土日 硕七学位论文 第一章交通分配概滤 第一章交通分配概述 交通分配模型是城市交通系统分析和设计中最基础的工具之一，在城市交通 规划中占有核心地位。通过交通分配所获得的路段，交叉口交通量资料是检验道 路霹络规划是否合理的主要依据之一。 1 1 交通分配体系概述 1 1 。1 交通分配的一般涵义【1 】口1 交通量分配即是将已经预测出的o d 交通量按照一定的规则符合实际地分 配到道路网中的各条道路上，并求出各条道路的交通流量。0 1 9 交通量是两点之 闻的交遴量，霹从出发地到譬的地之间的交通量。一般的道路瘸中，两点之闯( 即 d 与d 之间) 有很多条道路，如何将0 1 9 交通量正确合理地分配到d 与d 之间的 各条道路上即是交通分配模型要解决的阀题。 如果两点之间有很多条道路而这两点之间的交通量又很少的话，这些交通量 显然会沿着最短的道路行走。随着交通量的增加，最短路径上的交通流量也会随 之增加。增加到定程度后，这条最短路径的走行时间会因为拥挤或堵塞而变长， 这一部分道路利用者会选择次短的道路。随着两点之间的交通量继续增加。两点 之间豹所有道路都有可能被利用。 1 1 2 交通分配的作用【3 j ( 1 ) 把现状的o d 需求量分配到现状的路网上，就可以分析现状的交通负 荷，可以检验模型( 交通分配模型) ； ( 2 ) 把未来的o d 需求量分配到现状的路网上，可以检验现状的路网是否 合理，是否满足未来要求，即评价现状路网； ( 3 ) 把未来的o d 需求量分配到未来的路网上，评价规划方案，比选规划 方案，确定交通设施的建设顺序，确定设计交通量和服务水平。 1 1 3 交逢分配模型的分类1 p i p 4 1 如图i - 1 1 3 所示，显示了交通分配模型的分类结构。根据对交通流时变特性 的假设不同，分为静态交通分配和动态交通分配两大类别；静态交通分配模型以 年平均臼交通流量为描述对象，说明的是种路网交通处于稳定时的交通情况； 动态交通分配模型描述的是时变交逶流，与静态交通分配模型不弱，它需要说骥 车辆由于受到交通阻塞影响在路网上的滞留情况。一般交通规划中采用静态交通 硕七学位论文第一章交通分配概述 图卜l 交通分配模型的分类 分配模型已能够说明我们面临的问题，只有在详细方案可行性研究及交通管理规 划中才产生使用动态交通分配模型的需要。有关交通信息情况的假设分为两种基 本情况：用户掌握确定自己交通选择所需的路网交通情况，因而确切知道自己应 该走哪条道路，对应形成确定型模型；用户并不掌握确切的交通情况，而是根据 有限的信息选择自认为是正确的路线，由此建立了概率型模型。交通费用与交通 流量关系假设是说明交通线路上的交通费用( 指广义交通费用，包括交通时间和 狭义交通费用) 是否随交通流量变化，均衡分配模型认为交通费用随交通流量的 增加而增大。o d 选择特征假设说明o d 交通流量是否随路网动态交通费用的变 化而变化，这里路网动态交通费用是指随相应交通线路上流量而变化的交通费 用。在城市中居民的购物出行往往根据交通拥挤情况改变目的地，弹性o d 分配 模型能够说明这样的交通状态。模型不同的数学形式仍对其作用性有巨大的影 响，不动点模型需要的附加假设最少，适用性强，但这是以复杂的算法( 这种复 杂的算法由于受到计算机能力的限制而无法在大规模网络上实现) 为代价的；变 分不等式模型在不动点模型基础上附加了费用函数的一阶连续性的需求，以此换 取模型求解算法的简化；极值模型在变分不等式模型基础上增加了费用函数的雅 2 硕士学位论文 第一章交通分配概述 可比行列式对称的要求( 这意味着费用函数往往不能反映其他路段流量的影响， 例如在交叉口一条进口道的通过时间要受到相交的另一条道路流量的影响) ，通 过牺牲模型对部分问题的适用性获取模型的可解性。 在上述模型中，目前在交通规划中得到较为广泛应用的有：最短路分配模型、 多路径概率分配模型、确定型均衡分配模型、随机用户平衡分配模型。 1 2 交通分配模型的研究进展【1 】【2 】【3 1 【4 】【5 】【6 】 交通分配是交通规划的核心技术。所谓交通分配就是如何将o d 需求量分配 到交通网络的各条路段上去。几十年来，许多学者对此进行了不懈的研究。在实 际生活人们早就认识到：所需出行时间、距离及费用等是选择路径的重要标准。 但早期由于缺乏系统理论和计算手段，人们不得不依靠实际作业者的个人经验和 判断。进入5 0 年代以后，美国b p r ( b u r e a uo fp u b l i cr o a d s ) 和h r ( h i g h w a y r es e a r c hb o a r d ) 在研究高速道路交通转移率时提出了转移概率曲线方法，该 方法认为：当行程时间与其他路径的时间相差1 0 分钟时，则有5 的车辆可能被转 移到新路径上去，其数学计算模型1 2 】为： q - 5 0 + 丽5 0 丽x ( d + 0 s t ) 其中q 一转移到新路径交通量的百分率；d 一新路径所节约的距离；r 新路径 所节约的时间。这可以说是交通分配理论系统发展的最初尝试。1 9 5 7 年m o o r e 和 d a n t z i n 发表了寻找网络中两点间最短路方法的论文，这一成果对交通分配理论 的发展产生了重大的影响。经过c a r r o l l ，s c h n e i d e r 等人的努力，5 0 年代后期 建立在最短路方法基础上的“全有全无一法( a l l o r n o t h i n g ) 在交通分配中 得到了实际应用。全有全无一法实际上是一种以规划者意愿为中心的交通量分 配方法。根据这一原则设计的网络加载机制就是将每一个o d 对需求量全部分配 到连接该o d 对的最小出行费用的路径上，显然其结果与实际交通状态相差甚 大。为了改进这一不足，在此后的研究中又有多种新的分配模型被提出，其中具 有代表性的是m c l a n g h l i n 方法、交通容量限制法和概率分配法。m c l a n g h l i n 方法 通过搜索节点之间的第1 n 位的最短路，应用线性图理论分配各条路径的交通 量交通容量限制法是一种迭代的交通分配方法，在分配流量时考虑了道路容量同 负荷超出之间的关系，比较符合实际情况；概率分配法由b u r e l l ，d i a l 等在6 0 年代后期至7 0 年代初期提出，该方法以个人选择概率为基础，确定各条路径的 选择比率。 在实际研究过程中，人们逐渐认识到，正确的交通分配方法应能较好地再现 3 硕士学位论文第一章交通分配概述 实际交通状态，而这种实际的交通状态是交通网络用户路径选择的结果。基于这 种认识，以用户路径选择行为为基础的交通平衡分配理论逐步发展起来。 1 9 5 2 年，w a r d r o p 提出了著名的平衡分配原则，之后，b e c k m a n n 于1 9 5 6 年 建立了平衡理论的数学极值模型，1 9 7 9 年s m i t h 在对平衡原理进一步详细分析的 基础上，提出了变分不等式模型。他们的研究工作使得平衡理论形成了比较完整 的体系，在交通分配理论研究中占据了主导地位。 然而，在w a r d r o p 的确定性用户平衡理论中，不但假设用户都力图选择出行 费用最小的路径，而且假设用户能随时掌握整个网络的交通状况，即能精确计算 每条路径的出行费用，从而作出完全正确的择路选择。事实上，用户只能对路径 出行费用作一估计，对同一条路径，不同的用户有不同的估计值。 d a g a z n o 和蝴( 1 9 7 7 ) 将用户对路径的出行费用的估计值与实际值之间 的差别视为随机变量，定义了随机用户平衡分配原则，其路径被选择的概率就是 其估计出行费用为最小的概率，在随机用户平衡点，某个o d 对之间所有已被选 用的路径上并不一定具有相同的测定出行费用( 即实际出行费用) ，这为研究随 机用户平衡分配模型奠定了基础。显然随机用户平衡分配原则满足现实生活中用 户在路径选择中具有一定的随机性的要求，比确定性用户平衡分配原则更为有 用。事实上，确定性用户平衡分配原则是随机用户平衡分配原则的一种特殊情形， 只要设路径的估计出行费用的方差为零，随机用户平衡分配原则就变成确定性用 户平衡分配原则了。 4 硕士学位论文第二章交通分配模型 第二章交通分配模型 2 1 非弹性o d 需求的确定型均衡分配模型 确定型均衡分配认为交通分配网络各边的交通费用随交通流量而变化，用户 能够掌握路网上的交通情况，并都试图按照自己费用最小的原则选择路线，这种 选择行动产生了系统的自组织运动，最终两点之间被利用的各条道路的走行时间 会相等，没有被利用的道路的走行时间更长，这种状态被称之为道路网的平衡状 态。而这一平衡状态就是确定型均衡分配模型所描述的状态 2 1 1 用户均衡分配模型( u s e re q u i l i b r i u ma s s i g n m e n t ) 符号定义： 呶：起讫点，一s 间的o d 交通量； 瓦：路段a 上的交通流量； l ：路段a 上的期望阻抗； t o ( - ) ：路段口上的期望阻抗函数，因而乞= t o ( x o ) ； 露： o d 对，一s 间的第k 条路径上的交通流量； t ：o d 对r - $ 间的第k 条路径上总阻抗； 豫：0 - 1 变量，如果路段a 在o d 对，j 间的第k 条路径上，则畦= l ，否则 畦= 0 ； n ：网络中节点的集合； l ：网络中路段的集合； r ：网络中出发地的集合； s ：网络中目的地的集合； 丸：，一s 间的所有路径的集合。 定义2 1 1 【4 】如果所有的道路利用者都准确知道各条道路所需的行走时间并选 择走行时间最短的道路，最终两点之间被利用的各条道路的走行时间会相等。没 有被利用的道路的走行时间更长。这种状态被称之为道路网的平衡状态。 在道路网的利用者都知道网络的状态并试图选择最短路径时，网络会达到 平衡状态。 定理2 1 1 1 4 】耽咖第一原理( 定义) 在考虑拥挤对路径阻抗影响的网络中，当网络达到平衡状态时，每组o d 的 各条被利用的路径具有相等而且最小的阻抗；没有被利用的路径的阻抗大于或者 等于最小路径阻抗。 5 硕士学位论文 第二章交通分配模型 w a r d r o p 提出他的平衡准则之后，曾经在很大一段时间里没有一种严格的 方法可求出满足这种平衡准则的交通量分配法。后来由b e c l o n a n n 提出了一种满 足w a r d r o p 准则的数学规划模型。 b e c k m a n n 采用以下数学模型描述w a r d r o p 均衡状态7 1 嘲 一u 。- o , 名f ： ：。o i ( 2 1 1 ) 式中以表示均衡状态t o d 对，一s 间的路径阻抗，即最小路径阻抗。 而正是这组数学规划模型奠定了研究交通分配问题的基础。后来的许多模 型，诸如弹性需求交通分配模型、分布一分配组合模型等都是在b e c k m a n n 模型 的基础上扩充得到的。下面介绍b e c k m a n n 的交通量分配模型。 对于分配问题本身应满足的条件只有交通流守恒条件。即各o d 间的交通量 应该全部分配到网络中去，或者说o d 间各条路径上的交通总量等于o d 交通量。 用公式则表示为： 同时露 o , v k ，j 。 露= ，v ，s ( 2 1 2 ) i e 毛 其它的约束条件则是变量之间的关系式。路径交通量露与路段交通量毛之 间的关系式为： 屯= 露，v a e l ( 2 1 3 ) ，k 其次，总路径阻抗与路段阻抗的关系式为： = 乞豫，v 七丸，v r e r ，v s e d ( 2 1 4 ) 上述三式只是几组基本的限制条件，并未涉及到平衡的概念，而且约束方程 的个数比未知数的个数少，只凭这几组约束条件通常求不出路段的交通流量。 b e c k m a n n 把上述条件作为基本约束条件，用取目标函数极小值的办法来求平衡 分配的解。提出的平衡分配模型如下 4 1 ： m i r , z ( x ) = 7 , f 乞( 力) 如 ( 2 1 5 a ) 胄： 露= g 糟，v r ，s i e b 髭 o , v k ，j 吃= 露豫，v a ，jk ( 2 1 5 b ) 以上模型的目标函数是对各路段的走行时间函数积分求和之后取最小值。很 6 硕士学位论文第二章交通分配模黧 难对它作赉直观的或经济上的解释，一般认为它只是一种数学手段，借助于它来 求解平衡分配问题。 2 。2 系统最优平衡分配模型【l 】喇网( s y s t e mo p t i m i z a t i o n ) 定义2 1 2 【4 1 路网中所有用户共同决定其出行路线，使系统的总阻抗达到最小， 这种状态称失系统最优状态。 与用户平衡状态不同的是系统最优状态中用户可以通过单方面改变路线而 达到改变路径阻抗的霉的。 定理2 1 2 1 4 w a r d r o p 第二原理( 定义) 在考虑拥挤对路径阻抗影响的网络中，网络中的交通量应该按某种方式分配 以使网络中交通量的总阻抗最小。出行者单方面改变其出行路线，不会改变系统 总阻抗。 、 第一原理反映了道路溺利用者选择路线的一种准则。按照第一原理分配出来 的结果应该是道路网上交通利用者实际路径选择的结果。而第二原理则反映了一 种冒标，帮按转么样的方式分配是最好的。在实际网络中不可能出现第二氦理所 描述的状态，除非所有的道路利用者互相协作为系统最优化而努力。这在实际中 是不可能的。但第二原理为靓划管理人员提供了一种决策方法。 系统最优化比较容易用数学规划来表达。其目标函数是对系统的总阻抗取最 小值。约束条件则与u e 模型完全一样。因此，该阀题可归纳为下述模型。 m i n 2 ( x ) = x o t = ( x o ) ( 2 1 6 a ) s j ： ? j 露拦，v r ， ( 2 1 6 b ) 露o , v k ，s ( 2 1 6 c ) 该模型称为系统最优模型s o ( s y s t e mo p t i m i z a t i o n ) 。 。 2 1 3u e 模型与s o 模型之间的关系， 下面分折系统最优( s o ) 模型与用户最优( u e ) 模型之闻的关系。 令 艺( 屯) ：t a x 口) + 掣 ( 2 - l - 7 ) k 则 f 乏) 妇= f 瓯( 国) 国尝咖= f 瓯( 疽o ) d t o 蛾和= f 露吃( 妫掰】= 砒 7 硕士学位论文 第二章交通分配模型 因此，如果以艺( 毛) 作走行时间函数进行利用者平衡分配，得到的解即是系 统最优模型的解。即模型 m i n 2 ( x ) = f 艺( 国m 、( 2 1 8 a ) j j ： 露= ，v r ，s ( 2 1 8 b ) 七 露o ，v k ，j ( 2 1 8 c ) 。、 的解即是系统最优模型的解。而模型式( 2 1 8 ) 实际上是利用者平衡分配模型。 因此，在系统最优模型的解时，只需按式( 2 1 7 ) 对走行时间函数进行变换后， 完全按利用者平衡模型的解法求解即可。 t 另一方面，如果令 ， 乏( 屯) = 土r ，口( 国) d 国 ( 2 1 9 ) 。，j曩” 则系统最优模型的目标函数- n l i l l z = 乏= f 乞( 国) 如 即按式( 2 1 9 ) 对路段阻抗函数进行修改后，系统最优模型即可转化为用 户最优模型。因此，对路段阻抗函数进行不同的修改，u e 模型与s o 模型可以 相互转换 2 1 4 算法【9 1 0 】 b e c k m a n n 提出的关于交通分配的数学规划模型沉睡可2 0 年之后才由 l e b l a n c 等学者将f r a n k w o l f e 算法用于求解b e c l a a n n 模型，最终形成了目前 的广泛应用的一种既严格又实用的解法，该解法通常称为，一形法。 模型( 2 1 5 ) 是一组非线性规划模型。而对非线性规划模型即使现在也没 有普遍通用的解法。只是对某些特殊的非线性规划模型才有可靠的解法。而模型 ( 2 1 5 ) 正是一种特殊的非线性模型。 f 一矽法是用线性规划逐步逼近非线性规划的方法( c o n v e xc o m b i n a t i o n m e t h o d ) 来求解式( 2 1 5 ) 的。该方法是一种迭代法。在每步迭代中，先找到 一个最速下降方向，然后再找到一个最优步长，在最速下降方向上截取最优步长 得到下一步迭代的起点。重复迭代直至找到最优解为止。此法的前提条件是模型 的约束条件必须是线性的。f 一形法( 平衡分配法) 求解u e 、s o 问题的步骤可 归纳如下： s t e p0 初始化。按照鳄= 乞( o ) ， c a ，实行一次0 1 分配，得到各路段的交通 流量 艺) ，令一= l ； 8 硕士学俄论文第二章交通分配模凝 s t e p1 更新。令嚣乇蝶) ，v a ； s t e p 2 寻找下步的迭代方向。按照 ) 实行一次。一1 分配，并得到一组附 加交逶流量 z ； s t e p3 确定步长。求满足下式的 ( z 一地k + ( 以一) 】= o ，o 瓯l 毒 s t e p4 确定新迭代点。令拦+ 一) ，v a s t e p5 收敛性检验。如果 # ) 已满足规定的收敛准则，停止计算。 譬1 帮 是要求的平衡解；否则令n = n + l ，否则返回s t e p1 。 按照上述步骤，缀容易编制嬲相应的计算规程序。一般靓模酶实际城市道路 网的交通量分配计算，普通微机上即可进行。 2 2 弹性o d 需求的确定型均衡分配模型 上匿介绍酶u e 模型、s o 模型是在o d 交透量已知并且为常量的前提下建壹 的模型。但实际上o d 交通需求往往由于备种原因发生变化。以下将介绍弹性需 求( 变需求) 下的平衡分配模型，来满足这一情况下交通需求预测的需要。 2 2 1 模型f 4 1 在现实孛，o d 交通量的大小霹麓会受网络运行情况的影响。例如，在交通 堵塞严重时有些道路网利用者可能会放弃自己开车而乘坐公交车，有的甚至取消 原计划的出行。为了反映这种现象，o d 交i 藿量彗描可假定成，和葶之闻路径阻抗 的函数，即 蟊= 玻纸) ，v r ，s 上式中，：，一s 之间的最短路径阻抗； 臻0 ：尹一s 间的需求丞数。 显然巩应该随，一s 问路径阻抗变化的单调递减函数，并且有上限。 这种问题便是弹性需求( v a r 渤瑟d e m a n d ) t 的平衡分配问题。即，求一 组满w a r d r o p 平衡的路段交通量和o d 交通量。同时，o d 交通量也满足需求函 数。 该问题可表达为下列的数学规划模型 m i n z ( x , g ) = f 乞( 国) 如一r 础( ) d 出 ( 2 2 1 a ) 对： 露= ，计，墨 ( 2 2 1 b ) 9 硕士学位论文 第二章交通分配模型 露o ，v 七，s q 。o ，v r ，s 模型中删是需求函数的反函数。模型的约束条件和所采用的变量基本上 与u e 模型一致，主要的差别是目标函数 2 2 2 算法【1 1 1 3 1 1 4 1 该模型解法的步骤与固定需求下的模型基本相同，即采用迭代法。在每步迭 代中，采用一次全有全无分配而决定下一步迭代的方向。然后再根据目标函数的 极小化决定最优迭代步长。但在该方法中，由于o d 交通量也是变量，也应在迭 代中根据o d 间的走行时间作相应的调整。 即使在弹性需求的条件下，任意两地间的交通量总需求是有上限的。例如不 会超过两地间的总人口数量。因此对任意一组o d ，需求函数总是有上限函数， 我们设此上限为瓦。 s t e p0 初始化。找到一组初始可行的路段交通量缱，o d 交通量 吐 ，令 刀= l ，例如，可以根据o d 交通量的上限磊，确定一组吐，然后根据吐进行0 - 1 分配的结果而得到一组z 。 s t e pl 更新。令艺= t o ( x d ，v a ，计算碟( 破) 。 s t e p 2 根据e 计算o d 组厂一s 间的最短路线，确定迭代方向。计算得o d 对 ，一墨间最短路线的所需时间为c ：，按下式进行计算而确定附加交通量。 如果d 二l ( 靠) ，则令甜：= 瓦，沿最短路线上将“。进行0 - 1 分配，即将u 席 全部分配到计算所得的最短路线上，并增加相应的附加路线交通量虻：如果 c ： 珑- ! l n ) ，则令= o 。相应最短路线上各路段的附加路线交通流量不变。 各组均计算完毕后，得到附加交通流量 ” ，o d 交通流量 甜：) 。 s t e p3 根据下面的一维极小问题求最优步长瓯： 。m 钒i n 盈z ( 口) = f 坞倪q t o ( 缈) d 国一r + ，雠d 一1 ( 国) d 彩 s t e p4 更新流量。令 “= + ( 以一# ) = 靠+ q ( 吒- q d s t e p5 收敛性检验。如果下式成立 ；唑掣+ ；甲七 1 0 硕士学位论文 第二章交通分配模型 则停止计算；否则，令r = n + l ，返回s t e p1 。 2 3 随机均衡分配模型 2 3 1 模型1 4 】【1 1 】【1 2 】 d i a l 模型虽然能够进行随机分配，但其路段实际阻抗是与交通量无关的， 并没有考虑拥挤因素。这里我们假设估计路段阻抗的期望值是路段流量的函数， 即乞= t o ( x a ) ，e 7 0 】_ ，乙是路段a 的估计阻抗，并引入随机用户均衡的概念。 定义2 3 1随机用户均衡s u e ( s t o c h a s t i cu s e re q u i l i b r i u m ) 是指这样一 种交通流分布形态，在这个状态下，任何一个出行者均不可能通过单方面改变出 行路径来减少自己的估计行驶阻抗。 随机用户均衡分配中出行者的路径选择行为仍遵守w a r d r o p 第一原理，只不 过用户选择的是自己估计阻抗最小的路径而已。由此可知，连接o d 对，一j 的路 径k 被选择的概率硭，就是其估计阻抗在该o d 对间所有可能路径的估计阻抗中 为最小的概率【4 】，即 ? 硭= 磁o ) = r r ( c 厅k ，v l k 丸l r ) ( 2 3 1 ) 其中，砹是表示估计阻抗的随机变量，磷= 瓦吩，v r ，s ，k 。 应该注意到，上述选择概率是一个条件概率，即它是在平衡态的路段阻抗期 望值的条件上确定的概率。 研究随机用户均衡定义可知，在该均衡状态下，某个o d 对之间所有已被选 用的路径上，并不一定有相同的实际阻抗值，而只满足下述条件： 露= 硭，v k ，s ( 2 3 2 ) 在此式中，路径流量露与硭有关，而礞与估计路径阻抗大小有关，估计路 径阻抗大小与估计路段阻抗有关且是随机变量，实际路段阻抗又是流量的函数， 如此循环相依，达到s u e 的条件。s u e 更具有普遍性，u e 仅是s u e 的一种特 殊情况，当估计阻抗的方差为0 ，s u e 就变成u e 了。 我们仍然沿用已经讨论过的交通分配基本规划模型的建模思路，先构造出一 个数学规划模型，然后证明其与s u e 条件之间存在等价性，并进一步说明该极 小值问题存在唯一极小解。 该模型如下： m i n z ( x ) = 一啦【卿 磁 i 气( z ) 】+ , x o t o ( x o ) 一f 乙细) ，国 ( 2 3 3 ) 同样，上述模型没有任何直观的行为或经济上的解释，仅是一个无约束的极 硕士学位论文 第二章交通分配模型 小化问题，可证明其解满足s u e 条件，且在解点上满足网络的所有守恒约束。 2 3 2 算法【4 】【1 2 】 我们可以采取求解无约束极小化问题的最速下降法等方法来求解模型 ( 2 3 3 ) ，这类算法基本的运算步骤是寻找下降方向和迭代步长，即 r “= 矿+ d ” 其中矿是第，1 次迭代时的路段流量向量，是需要确定的迭代步长，而矾是 目标函数在，点的下降方向。 对于s u e 问题，采用常规的确定下降方向并沿此方向搜索目标函数极小值 的迭代方法并不容易实现。因此我们采用二次加权平均法( m s a ， m e t h o do fs u c c e s s i v ea v e r a g e s ) 。二次加权平均法是一种介于增量分配法和平衡 分配法之间的一种循环分配方法。其基本思路是不断调整已分配到各路段上的交 通流量而逐渐到达或接近平衡分配。在每步循环中，根据已分配到各路段上的交 通流量进行一次随机分配，得到一组各路段上的附加交通量。然后用该循环中各 路段的分配交通流量和该循环中得到的附加交通量进行加权平均，得到下一循环 中的分配交通流量。当相邻两个循环中的分配交通流量十分接近时，即可停止计 算。最后一循环中得到的分配交通量即是最终的交通量。这时，每次随机分配的 附加交通量少与前一次计算得到的交通量矿之差y ”一矿为下降方向，而迭代步 长预先给定。具体步骤如下： s t e p0 初始化。按照各路段的初始走行时间磁) 进行一次随机分配，得到各 路段的分配交通流量屯。令n = l 。 s t e p1 按照当前各路段的分配交通量计算各路段的走行时间。 s t e p2 按照s t e pl 计算的路段走行时间 f ：) 和o d 交通量进行一次随机分 配，得到各路段的附加交通流量虻。 s t e p3 用加权平均的方法计算各路段的当前交通流量： 1 + 1 = + 二( ”一) ，v 口 n s t e p4 如果与- 1 的差值不太大，停止计算。即为分配交通流量。否则 令刀= n + l ，返回s t e p1 。 上述算法中迭代时进行的随机分配可应用d i a l 算法等进行分配 1 2 硕士学位论文 第二章交通分配模型 2 4 相关数学基础知识 2 4 1 特殊约束最优问题的极值条件n o l 1 、非负约束 定理2 4 1 设f ( x ) 是可微函数，若，是优化问题 ( p 1 ) i r f i n ：厂( x ) s jx 0 的最优解，则，满足： 夥( ，) 0 ，o ( 2 1 4 1 ) ，町( x ) = 0 ( 2 4 2 ) 反之，若f ( x ) 是凸函数，x 满足( 2 4 1 ) 和( 2 4 2 - ) ，则x 是最优化问题 ( p 1 ) 的最优解。 2 、非负和线性等式约束 本文中处理的很多最优化问题均为带有非负和线性等式约束的情形，它的。 般标准形式为： ( p 2 )m i n ：厂( 功 j j 薯= 6 ， ( 2 4 3 ) 一q i j 玉0 ( 2 4 4 ) 为了得出问题( p 2 ) 的最优解的一阶必要条件，首先构造如下拉格朗日函数： l ( x ，甜) = 厂( x ) + u j 哆一薯) f 其中为对应于约束( 2 4 3 ) 的拉格朗日乘子。 为了求得问题q 2 ) 的最优解，须有： ( p 3 )m i n ：l ( x ，材) s l 毛0 若，为( p 3 ) 的一个最优解，材为相应的拉格朗日乘子，则由定理2 6 1 可 知优化问题( p 3 ) 的最优解的一阶必要条件为： # 骂堕：0 ，骘堂o , v f l喝c 丝鲨丛：o ，v ， o u j 。 且有而0 ，从而得到： 定理2 4 2 问题( p 2 ) 的最优解得一阶必要条件为： 1 3 硕士学位论文 第二章交通分配模型 # i 警一渺) - 0 m 掣一“轮0 ，v f a ) c i 厶j j ：j ；# 2 屯， # - o , v i ( 2 4 5 ) ( 2 4 6 ) ( 2 4 7 ) ( 2 4 8 ) 2 4 2 凸集、凸函数、凸规划【1 3 】 定理2 4 3 若规划问题 ( p 3 )r a i n ：( 功 “ g i ( x ) 0 f = 1 ，2 ，m 其中厂( x ) ，& ( 功为凸函数，则 ( 1 ) 问题( p 3 ) 的可行解集合d 为凸集，因而p 3 ) 为凸规划。 ( 2 ) 问题( p 3 ) 的最优解集合矿为凸集 ( 3 ) 问题( p 3 ) 的任何局部最优解都是( 整体) 最优解。 定理2 4 4 若厂( 功是严格凸函数，g j ( x ) 0 为凸函数，又规划问题( p 3 ) 的 最优解集合d ( 空集) ，则其最优解惟一。 定理2 4 。5 设dc 掣是非空凸集。 ( 1 ) 若f ：f r 1 是d 上得凸函数，名 0 ，则；t f 是d 上的凸函数。 ( 2 ) 若f l ，五：掣_ r 1 都是d 上的凸函数，则石+ 石也是d 上的凸函数。 定理2 4 6 设dcf 是非空开凸集，厂：d r 1 二阶可微，如果的 强珊加矩阵v 2 厂( x ) 在d 上是正定的，则厂是9 _ i ：的严格凸函数。 1 4 第三章基于随机用户平衡的混合交通网络流量分离模型 第三章基于随机用户平衡的混合交通网络流量分配模型 1 9 5 2 年w a r d r o p 等提出的用户平衡( u e ) 系统是在固定需求及交通网络上 任何使用者都能正确掌握道路信息的假设下建立的，但交通行为往往是随机性 的，故1 9 7 7 年由d a g a n z o n 和s h e ：等提出的随机用户平衡系统( s u e ) 统一了 随机分配和w a r d r o p 平衡的概念，但是用单一类型的s u e 模型来描述实际的交通 状况是不够的。 在我国城市交通中，以混合交通居主要地位，即在一个路面上各种交通模式 并存。在同一o d 对，- 一s 间，人们可以选择公交车、私家车、摩托车，甚至自行 车、步行等方式出行，而人们对每种出行方式的偏好程度因为其舒适度、花费、 方便性、出行时间等因素的考量而各不相同。 基于以上考虑本文提出了一个混合交通均衡分配模型。 符号定义： 纵起始节点，到终讫节点s 总的o d 流量； g ：第k 种出行方式从起始节点，到终讫节点j 的o d 流量； 第七种出行方式在弧口上的流量； 名糟第七种出行方式在路径m 上的流量； 艺第七种出行方式在弧口上的期望阻抗； t j ，第七种出行方式在路径m 上的期望阻抗； 磷月第七种出行方式在路径m 上的阻抗； 如第七种出行方式选择路径胁的概率； 硭出行者选择第k 种出行方式的概率； 3 1 混合交通网络流量均衡分配模型 3 1 1 出行者交通方式的选择 一般情况下，出行者是从费用最小原则出发来选择交通方式的，即被选择的 某种交通方式是所有交通方式中出行费用最小的。而影响出行费用的因素是多种 多样的，包括可测量因素( 如出行时间、方便性、舒适性、费用等) 和随机因素 ( 如个人偏好、随机拥挤、天气情况等) ，因此交通方式的出行费用值应是一个 随机变量。另外，交通方式的出行费用函数应是其o d 流量的单调递增函数。本 硕士学位论文第三章基于随机用户平衡的混合交通网络流量分离模型 文考虑下式来表示城市混合交通网络中o d 对，一s 之间第k 种交通方式总的出 行费用硭，硭= 乞kl g 糟k ) 一k ，式中r ：表示对，一s 间第七种交通方式的可测量 的费用，s 三为随机误差项。 其中可测量的费用吃可用下式表示喽= 嵋，式中嵋表示第七种交通方 式的第刀种特性值，如出行时间、费用、方便性、舒适性等；口：表示其统计参数， 可用统计理论估计出来。 由于不同的交通方式的出行费用是一个随机变量，所以出行者对于交通方式 的选择问题实际上是一个概率问题，即出行者以多大的概率选择某种交通方式。 很明显，这种选择概率取决于费用函数的特性以及随机误差项s 三的分布。假定 随机误差项占兰独立同服从于参数为0 的g u m b e l 分布，则从费用最小原则出发， 可知某种交通方式被选择的概率为【1 4 1 硭= p r ( 硭砭，v l k 九) ( 3 1 1 ) 命题3 1 1 不同交通方式之间的流量分离满足蛐函数模型，即 。一硝 磋2 考两 ( 3 1 2 ) 么一。 ， 证明独立同分布，e ( ) = o ，密度函数厂( 曲= 良一妇一e p r 鲥 - 露= 以露砭，v l 七) = p 破一一艺，v ，七) = 尸( 蠢匕一+ ，v l 七) 互相独立 硭= n p ( 艺一艺+ ) i 乒k 。= p ( 艺一艺+ 协p = 珥p ( 吒一删= 珥r 陇一e 一砂 令r = p 一沪层，则y = 一丁i n t + e ，砂= 一去出， 铱，珥肪“，m - t = 驴。叫。缸。：量 硭= r 出 硭= 亡出爿厂( x ) 出= 亡 。 舾 出 令f = e - o x - e ，则 1 6 硕士学位论文第三章基于随机用户平衡的混合交通网络流量分离模型 磋：r p 一彩靠钆一，去衍，磋：r p - ，f 砖萎r 以州西 令名= 驴虻+ l ，则磋= f e 劫出= 去 露= 焘上下同乘盯啦 删= 毒杀= 景 j r j ，一 证毕。 假定在城市混合交通网络中o d 对r - s 之间总的0 d 量保持不变，则根据 随机用户平衡理论，不同交通方式之间的流量分离关系必须满足的基本约束条件 为 g ：=