（交通运输规划与管理专业论文）适应多种交通需求结构的连续路网设计.pdf

摘要 城市的交通拥堵源于交通供求的不平衡，交通网络设计的目的在 于通过交通网络的完善来适应交通需求的变化。近年来，随着国民生 活水平的提高和文化生活的丰富，城市大型活动的举办频率越来越 高。与日常交通需求相比，大型活动期间城市交通量和出行选择行为 变化己成为城市交通拥堵的重要原因。因此在交通网络设计中应考虑 多种交通需求结构的影响，更好地实现交通路网供求关系的协调，缓 解和解决城市交通拥堵问题。 本文从供需两个角度出发，分析了不同交通需求结构对路网容量 的影响程度，同时也分析了路网出行者的出行决策行为对路网均衡状 态的影响。将交通需求区分为日常交通需求和大型活动交通需求，并 对两者进行了比较。在此基础上，在路网设计中考虑大型活动的影响， 确定了路网设计的目标函数，并建立了连续网络设计的双层规划模 型，其下层规划包括针对日常交通需求和大型活动交通需求两个用户 均衡模型。同时设计了基于混沌模拟退火算法的求解方法。算例分析 结果表明，在路网设计中全面考虑各种交通需求结构，能够使网络交 通流量分布更加合理，达到交通网络适应能力的提高和缓解网络拥堵 的目的。 关键词连续路网设计，多种交通需求，双层规划，混沌模拟退火 a bs t r a c t t r a m cc o n g e s t i o nn o mt h ee s s e n c ei sb e c a u s eo ft h ei m b a l a n c e b e t w e e nt r a 伍cs u p p l ya n dt r a m cd e m a n d t h ea i mo ft h et r a m cn e t w o r k d e s i g ni s t oa d 印tt ot h ev 撕a n c eo ft r a 伍cd e m a n d sm r o u 曲p e r f e c t i n g t h e 把a f | e i cn e t w o r kd e s i g n i nr e c e n ty e a r s ，w i t ht h ei m p r o v e m e n to f l i v i n gs t a n d a r d s ，t h e h o s to fc i 够m a jo re v e n t si sm o r e f 琵q u e n t c o m p a r e dt ot h ed a y - t o - d a yt r a f ! f i cd e m a n d ，t h ev a r i a n c eo ft h et r a 所c d e m a n da n dt h en e t w o r ku s e r sr o u t ec h o i c eb e h a v i o rd u r i n gt h ec i t y m a jo re v e n t sb e c o m eo n eo ft h em o s ti m p o n a n tr e a s o n so ft r a f j e i c c o n g e s t i o n t h e r e f o r ew es h o u l dc o n s i d e rt h ei n f l u e n c eo f d if r e r e n tt r a 箍c d e m a n d si nn e t l ，o r kd e s i g ns ot h a ti tc a nm a k et h en e t w o r kc o o r d i n a t e d w i t ht h et r a f | f i c s u p p l y a n dt r a 伍c d e m a n d ， a l l e v i a t eu r b a n 仃a m c c o n g e s t i o n i nt h i sp 印e r ，肺ms t a n d p o i n to ft h et r a m cs u p p l ya n dt r a f j f i c d e m a n d ，t h ei n n u e n c eo fd i f f e r e n tt r a m cd e m a n d st on e t w o r kc 印a c i 够 w a sa n a l y z e d a tt h es a m et i m e ，t h ei n n u e n c eo ft h en e t w o r ku s e r sr o u t e c h o i c eb e h a v i o rt ot h et r a 衔cn e t w o r ke q u i l i b r i u ms t a t ew a sa l s oa n a l y z e d d i v i d i n g 仃a 伍cd e m a n d si n t od a y t o d a yt r a 伍cd e m a n da n dt h et r a m c d e m a n do ft h ec i t ym a j o re v e n t s o nt h i sb a s i s ，t h ep a p e rc o n s i d e r e dt h e i n f l u e n c eo ft h ec i t ) rm a jo re v e n t sw h e ni n c r e a s et h et r a m cs u p p l ya n d f i x e dt h eo b j e c t i v ef h n c t i o n ab i l e v e lp r o g r a mw h i c hh a dt w ol o w e r u s e r s e q u i l i b r i u mm o d e l sw a se s t a b l i s h e d m e a n t i m e ，a na i g o r i t h mo f c h a o ss i m u l a t e dw a sd e s i g n e d t h et e s tw o r kr e s u l t ss h o w e dt h a tt h i s m o d e lc a no b t a i nam o r er a t i o n a ld i s t r i b u t i o no ft h en e t w o r l ( t r a f n ca n d i m p r o v et h ea d a p t a b i l i t yo ft h et r a 佑cn e t w o r ka n da l l e v i a t et h et r a m c c o n g e s t i o n k e yw o r d sc o n t i n u o u sn e t w o r kd e s i g n ，d i f - f e r e n tt r a f n cd e m a n d s ，b i l e v e l p r o g r a m ，c h a o ss i m u l a t e da n n e a l i n g 硕士学位论文第一章绪论 1 1 选题背景及研究意义 第一章绪论 社会经济的快速发展和交通需求的迅猛增长给城市路网带来了巨大的压力， 很多城市出现了交通拥堵和阻塞现象。城市的交通拥堵降低了城市居民的出行效 率和出行质量，阻碍了国民经济的进一步发展和人民生活质量的提高。一方面， 城市交通需求的增长速度远大于道路的建设速度。据国务院发展研究中心统计， 我国已进入汽车拥有率迅速上升时期，截至2 0 0 8 年6 月，全国汽车保有量为6 1 2 2 万辆，其中私人小汽车为3 8 8 5 万辆，预计到2 0 1 0 年，汽车保有量将突破8 0 0 0 万辆，年平均增长1 5 2 ，私人小汽车保有量达5 0 7 6 万辆，年平均增长1 6 3 。 汽车数量的增长速度已经远远超过城市道路以及相关设施的建设速度，交通供需 不平衡的矛盾变得日益尖锐，道路日益拥堵。另一方面，交通拥堵从本质上来说， 源于交通供求的不平衡，因此，道路管理部门在增加交通供给时，若不考虑交通 需求结构和网络用户的路径选择行为，单从加强交通供给这一点出发来解决交通 拥堵问题是不可能的。 路径选择在过去的2 0 多年是交通和区域科学领域研究最多的问题之一【i 】。 在一般的路径选择模型中，可以根据静态还是动态，确定型还是随机型，平衡和 非平衡等分类1 2 】。影响用户路径选择行为的因素有很多，主要有时间因素( 出行 时间和稳定性) 、心理因素( 行驶的安全性、舒适感、偏好等) 和经济因素( 出行费 用) 等。在不同的需求结构下，路网出行者在获得全部或部分路网信息的条件下， 这些影响因素的影响程度将会发生变化，整个路网的流量分布和拥挤程度也会发 生变化。因此，结合行为科学和心理学已有成果，分析不同需求结构和信息影响 下的路网出行者的路径选择行为及对路网流量分布的影响，不但可以完善出行行 为模型理论，而且也能更为准确地反映路网出行者的出行决策，为道路管理部门 制定相应的管理措施提供依据，具有理论和现实意义。 近年来，随着国民生活水平的提高，人们精神文化生活日益丰富，城市大型 活动的举办频率越来越高。相关研究表明，大型活动已成为城市交通拥堵的重要 原因。大型活动的举办使得城市的交通需求结构发生了改变，人们的出行选择行 为变得更为复杂。 城市道路网络容量反映了道路网对交通需求的处理能力，是城市道路网络在 规模和布局上能否满足交通需求的极限状剁3 1 。而道路网络容量和交通需求与路 网的匹配程度、交通个体的路径选择行为等密切相关。也就是说，同一个道路网 络在承载不同的d d 需求分布时，即使所有对之间的交通需求总和相等，其 硕士学位论文 第一章绪论 实际路网容量也不一定相同。这意味着即使进行路网改造，若不考虑大型活动所 带来的需求分布的差异，扩容后的道路网络也可能承担不了大型活动时的交 通需求，造成局部路段拥挤，从而影响活动的顺利举行。 因此，为缓和城市交通拥堵问题，在增加交通供给的同时，应考虑多种交通 需求结构影响下，路网用户的路径选择行为、路网流量分布等，以期在适当的投 资下，使得改造后的城市路网能承担多种交通需求结构，提高道路网络的实际容 量，保证路网在承担不同需求结构时的稳定性和可靠性。 本课题的研究意义在于，找出在多种交通需求结构的影响下，城市之间 不同的交通需求分布对路网中的流量分布的影响，进而在进行路网改造时，考虑 多种交通需求结构的影响，使改造后的路网能适应多种交通需求结构。本文主要 研究了日常需求结构和大型活动需求结构下的路网设计优化模型及算法，算例结 果表明，与传统路网设计模型相比，本模型能更好地适应日常需求结构和大型活 动需求结构，能为大型活动时的交通管理减轻压力，缓和大型活动时的路网拥挤， 保证大型活动的顺利举行。 大型活动已成为城市生活中的一个重要组成部分，其对城市路网的影响日益 显著。研究大型活动影响下的城市道路网络设计问题将为决策部门提供更为符合 中国城市实际交通状况的决策依据，对于政府投资与交通方面的财政支出具有现 实的指导意义。 1 2 国内外研究现状 1 2 1 路径选择国内外研究现状 c h e n 和i 沁c k e r 【4 l 认为路径选择模型可以按以下两类因素分类：一是引入理 解误差来表示出行者对不完美信息掌握程度；二是将路网不确定性包括在随机效 用中( 出行时间) 。 这样，路径选择模型可以归为以下四类1 5 j ： 第一，确定型网络确定型用户平衡( d e t e n n i n a n tn e t w o r k d e t e n i n a mu s e r e q u i l i b r i 啪，简称d n d u e ) 模型： 第二，第二，确定型网络随机型用户平衡( d e t e n n i n a n tn e t 、v o r k s t o c h a s t i c u s e re q u i i i 晰u m ，简称d n s u e ) 模型； 第三，第三，随机型网络确定型用户平衡( s t o c h a s t i cn e t 、0 r k d e t e m l i n a l l t u s e re q u i l i b r i u m ，简称s n d u e ) 模型； 第四，第四，随机型网络随机型用户平衡( s t o c h a s t i cn e t w o r k s t o c h a s t i cu s e r e q u i l i b r i u m ，简称s n d u e ) 模型。 硕士学位论文第一章绪论 除了理解误差和网络不确定型因素外，a v m r i 和p r a s h k e r 【6 】认为应该还包括 以下两种因素： 第一，决策准则的类型。决策准则就是决策者评价路径选择方案的属性并做 出决定的过程。大多数路径选择行为模型基于期望效用理论( e x p e c t e d u t i l i t ) rn e o 巧，简称e u l ) 和随机效用理论( r 如d o mu t i l i t yt h e o r y ，简 称r u t ) 建立。其它的则基于消除方法，前景理论( p r o s p e c t1 1 1 e o 巧) ， 模糊逻辑或快速模糊启发理论等建立。 第二，动态静态模型。文献中大多数路径选择模型基于出行者了解道路属 性的假设，因而是静态的。然而，路径选择( 包括一些信息获知和学 习积累) 决策过程更是一个动态的过程。 由于现实中在不确定条件下进行路径选择是出行者的日常决策，智能交通系 统( i t s ) 中如何处理不确定行对出行行为的影响已经成为交通工程和规划领域中 一个重要主题【4 l 。因此，研究不确定条件下的用户出行行为( 路径选择行为) 有着 重要的作用和现实意义【5 l 。 d ep a l m a 和p i c a r d 【6 j 将影响路网出行者的路径选择因素分为三类，路径选择 属性的变化；出行者可见但建模者不可见的因素；出行者也不可见的因素。以前 对这些不确定性的研究一般都采用均值和方差来表示，并且假设这些分布事先已 经确定。b o n s a l l 【7 】认为不确定性是由变化引起的，在现实中各种影响因素都会引 起变化，因此不确定性一定存在。国内外学者通过各种模型来反映并揭示这种不 确定性。目前使用最多的是期望效用理论和随机效用理论，但也有其它理论对其 补充和完善，如累积前景理论，学习理论及模糊集理论等。n o l a n d 等【。7 1 、c h e n 和r e c k e r 【4 1 、n o l a n d 和p o l a l ( 【8 1 、d ep a l m a 和p i c a r d 【6 1 以及t s e n g 等【9 】从出行时间 不确定性的各个角度研究了用户路径选择行为。b o s 等i lo 】考虑了出行时间不确定 性和信息提供对路径选择的影响，分析了信息在路径选择中的作用。y i n 和 i e d a 】、d ep a l m 和p i c a r d 【1 2 】根据风险理论对不确定性条件下的用户路径选择进 行了研究。石小法和王炜【l3 】利用不确定性对策理论，研究了出行者在不确定意 义下的路径选择行为。c h e n 和j i l l 4 j 应用遗传算法研究了不确定条件下的最优路 径选择问题。z h a n g 纠1 5 】引入相对效用( 效用只是对某些参考点有意义) 和相对兴 趣( 由多属性群决策理论引出) 的概念，建立了改进型的m n l 和巢式m n l 随机 效用模型。b o g e r s 等1 1 6 】提出了一个集成信息提供、风险态度、习惯和学习等路 径选择影响因素的概念框架，并证实了在路径选择中的习惯和路径在途信息起重 要作用。蒲琪，杨晓光等【j 7 】以解析交通信息对驾驶员路径选择的影响为目的， 研究总结出描述性信息在运用中的特征，并初步建立提供旅行时间信息条件下驾 驶员的路径选择模型。李志纯、黄海军【l8 】研究了a i t s ( 先进的旅行者信息系统) 硕士学位论文第一章绪论 的市场渗透率和信息质量对出行者选择行为的影响。黄海军、吴文祥【1 9 】在线性 成本函数的假设条件下，研究了交通信息系统对交通行为的影响，交通信息系统 不一定能降低驾车者的个人行驶费用，它取决于网络的实际交通情况和路径的通 行能力。 道路网络客观条件的限制，道路管理法律法规的限制和出行者个人的偏好会 导致出行者对网络结构认知的差异【2 0 1 。因此，不同出行者在同一网络中所形成 的认知地图可能是不同的，而出行者所形成的认知地图将对出行者路径选择产生 实质性的影响。网络结构认知差异性产生的路径旅行时间之间的偏差，可达到同 一d d 对、所有实际使用路径上旅行时间平均值的2 0 【2 0 1 。 k a h n e m a l l 和t v e r s k y 采用了一种更符合现实行为的模型【2 1 】：前景理论，国内 也译作视野理论或预测理论。前景理论是基于行为科学的实证科学，它假设人们 在做出决策时，面对获得是风险厌恶的，面对损失时是风险偏好的；并且有过高 估计小概率事件，过低估计较大概率事件的倾向。k a t s i k o p o u l o s l 2 l j 等人发现在路 径选择的实验中，出行者对于风险的态度与k a 1 1 1 e m a l l 和t v e r s k y 的“前景理论 相符合。b o g e r s 和v 抽z u y l e n l 2 2 】也发现类似的证据：当出行者能够在一条较短但 具有不确定性的路径和一条较长但是比较确定一些的路径之间做出选择的话，他 们表现出风险规避的行为。s a t o s h if u i i i 【2 3 j 运用“前景理论”来分析出行者在不 确定的交通网络状况下对出发时间的选择；e r e l a v i n e r l 2 4 j 使用“累积前景理论 来对旅客行为进行建模；r o n g c h 锄gj o u 【2 5 】研究了“前景理论”的“参照点假设 在出行者对于出发时间选择中的适用性等；d eb l a e i ja t 和v a l lv u u r e nd j i z 6 j 使用 前景理论来分析出行者的风险感知问题。赵凛，张星斟2 。7 】研究了先验信息条件 下出行者路径选择的理论模型。 1 2 2 路网设计国内外研究现状 一般地，城市交通网络设计问题( n e 铆o r kd e s i g l lp r o b l e m ，简称n d p ) 研究 的主要内容就是通过优化计算方法寻找最优的用于道路网络新建或改善的交通 建设投资方案，即研究如何能用最少的资金投入达到使整个交通网络中某种指标 最优的目的，这些指标可以是使整个交通网络中的系统总阻抗最小，也可以是使 整个交通网络所能容纳的出行量最大等等，从而为交通规划决策部门和有关人员 提供科学、系统、合理、有效的决策方案和决策数据，使政府的有限资金投入能 取得最佳的投资效益。因此，研究城市交通网络设计问题不仅在理论研究上有着 重要的价值，而且能够用于解决实际的交通问题，在实际应用中有着广阔的应用 前景【2 引。 通常n d p 被分为三种形式：改进现有路段供给能力的连续交通网络设计问 4 硕上学位论文第一章绪论 题( c o n t i h u 0 1 l sn 舐o r kd e s i 龋p r o b l e m ，简称c n d p ) ；在现有交通网络中添加新 路段的离散交通网络设计问题( d i s c r e t en e t w o r kd e s i g l lp r o b l e m ，简称d n d p ) ； 以及同时采用改进现有路段和在网络中添加新路段这两种手段的混合交通网络 设计问题( m i x e dn 印o r kd e s i 皿p r o b l e m ，简称m n d p ) 。 在城市交通系统中，政府部门在一定的投资预算约束下，为满足日益增长的 交通需求而增加交通供给，公众则调节自己的出行行为以适应这些给定的交通设 施。也就是说在政府部门为出行者提供交通基础实施之后，出行者根据具体的交 通状况来决定是否出行以及选用何种交通方式和具体的交通路线等。由于n d p 决策过程中涉及到政府部门和公众的相互作用，是一个典型的主从递阶决策问 题，因此双层规划方法成为描述n d p 的理想工具1 2 引。n d p 可以用数学模型描述 如下【2 8 ，2 9 】： m i n z ( y ，x ( j ，) ) y s t g ( y ，x ( y ) ) so 其中，_ x ( y ) 由下述规划求得： m i n z ( y ，x ) j g ( y ，x ) o ( 1 1 ) ( 1 _ 2 ) ( 1 3 ) ( 1 4 ) 其中：z 和z 分别代表上层问题和下层问题的目标函数，g 和譬分别代表上层问 题和下层问题的约束条件，y 和x 分别代表上层问题和下层问题的决策变量，并 且x 是) ，的隐函数，即x = x ( ) ，) 。 一般来说，交通网络设计是通过增加交通供给的方式来满足日益增长的交通 需求，缓解交通拥挤，根据研究目的的不同，上层目标函数主要有1 2 8 j ：固定需 求条件下的系统出行阻抗最小；固定需求条件下的网络备用能力最大；弹性需求 条件下的用户盈余和多目标优化。交通网络设计中有一个著名的b r a e s s 诡异现 象，即如果不考虑网络用户的出行行为，单纯地增加道路或增加道路的通行能力 不一定能达到改善交通状况的目的，有时反而可能导致整个交通网络拥挤程度的 增加。因此，下层规划一般使用用户平衡( u s e re q u i l i b r i u m ，简称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 ，简称u e ) 配流模型等。除此之外， 学者们还研究了考虑其他因素的用户平衡分配问题，如运量分布和流量分配的组 合模型【3 1 。3 2 1 、基于网络能力可靠性的概率用户平衡配流模型1 3 3 j 、部分路段上有 一氧化碳排放量限制的用户平衡配流模型【3 4 1 、考虑环境因素的广义用户平衡和 广义系统最优配流模型【3 引、考虑对公平的用户平衡配流模型1 3 6 】等。在实际的 路网中，路段之间应该是相互影响的，基于路段之间是相互独立的这一假设在某 硕士学位论文 第一章绪论 些情形下是不太合理的。一般情况下路段相互影响的非对称平衡配流模型可用变 分不等式方法来描述。f r i e s z 【3 8 。9 1 、l i m 【删等研究了下层为变分不等式的n d p 双 层规划模型及求解算法。下层为路段相互影响的非对称平衡配流模型的一般的形 式是【3 7 】： 寻找平衡路段流量x q ，使得对所有的z q 有： ，( 工，x ) 7 ( x x 。) 0 ( 1 5 ) 其中：约束空间q = xi 石= 鲈，人厂= g ，厂o ) ，f ( ) 为路段阻抗向量函数，厂为路 径流量，口为需求量，为路段和路径的关联矩阵，若路段f 位于路径，上， 则( f ，) = l ，否则，( f ，) = o ，人为对与路径关联矩阵，若路径f 是0 d 对， 之间的可行路径，则人( f ，) = 1 ，否则，人( f ，) = o 。 随着智能交通的发展，动态配流模型受到了越来越多的关注，近年来动态的 平衡网络设计问题、动态的非平衡设计问题逐渐成为网络设计问题中的另一个研 究热点【4 1 埘1 。 由于双层规划问题内在的复杂性，设计求解n d p 问题的有效算法长期以来被 认为是交通优化领域中难度最大且最具挑战性的问题之一。根据网络设计问题的 分类，其求解算法可以分为离散网络设计问题求解算法、连续网络设计问题求解 算法和混合网络设计问题求解算法。求解离散网络设计问题的常用方法有b e n d e r 分解法、分支定界法和一些启发式算法。由于连续网络设计问题的决策变量是连 续的，相对比较容易设计算法，国内外学者在这方面的研究最为成熟。这些算法 归纳起来大致可以分为三类：迭代优化配流算法、路段使用比例算法和灵敏度分 析法。混合网络设计问题的求解算法主要有分枝定界法和其它启发式算法。模拟 退火算法、遗传算法、神经网络算法、粒子群算法等启发式算法在求解城市道路 交通连续、离散及混合网络设计中取得了较好的使用效果1 4 孓5 1 j 。 混沌是自然界中一种常见的非线性现象。混沌运动具有遍历性、随机性、“规 律性等特点，混沌运动能在定范围内按其自身的“规律”不重复地遍历所有 状态。因此，利用混沌变量的随机性、遍历性及规律性可以进行优化搜索1 5 引。 高自友等1 5 3 5 4 l 利用混沌优化方法求解了离散和连续路网设计问题，但是单纯的混 沌搜索具有一定的盲目性，当初始解的选择不好或搜索空间很大时，搜索结果不 一定能令人满意。因此，很多优化领域的研究工作试图将其他算法引入混沌搜索 优化方法中，或将混沌搜索与其他算法组合进行迭代优化计算。模拟退火算法是 一种有效的全局优化方法，利用混沌变量来构造模拟退火算法中的邻域系，结合 混沌优化方法与模拟退火优化方法的优点，形成混沌模拟退火方法( c s a ) j 王子 彳等1 5 5 j 利用混沌模拟退火算法求解了一个单层全局优化问题，但其在双层规划 6 硕士学位论文 第一章绪论 中的应用很少。 1 3 本文的主要研究内容 1 3 1 研究目标 交通网络设计是为缓和城市交通拥堵而增加交通供给的优化决策方案。交通 网络设计中的影响因素众多，如何分析、辨别其主要因素，并建立符合实际的数 学模型，直接影响其缓解交通拥堵效果的发挥。本文的目标是在分析交通网络设 计影响因素的基础上，建立适应多种交通需求结构的交通网络设计模式，以保证 交通网络设计效果的稳定性、可靠性以及适应性。为交通网络设计在工程实践中 的丰富应用提供一些参考和借鉴。 1 3 2 研究内容 本文的研究内容主要分为以下四部分： 第一章介绍了本论文的选题背景和研究意义，引出了所要研究的问题，对交 通网络设计问题及交通分配中路径选择问题的研究进展及研究现状进行了综述， 进而阐述了本论文研究的目标、内容及所采取的方法。 第二章基于模拟退火算法处理双层规划问题的优越性及混沌优化在构造连 续变量的简便性、有效性等，设计了用混沌变量构造邻域系的混沌模拟退火算法， 并用一个算例进行了测试。 第三章分析了基于“效用理论”原则和“前景理论”原则的路网用户路径选 择行为和整个出行过程的出行决策行为。比较了不同决策行为对交通分配中“均 衡解 的影响。 第四章对不同需求结构下的同一路网物理容量进行了比较分析，利用混沌优 化方法进行了算例的求解，并对算例进行了分析，得出需求结构对路网物理容量 的影响程度，为第五章建立的双层模型提供了依据。 第五章在前面章节分析的基础上建立了基于两种交通需求结构的连续路网 设计模型，并设计了基于混沌的模拟退火求解算法。 第六章对基于两种交通需求结构的连续路网设计问题进行了较为详细的算 法了分析。 第七章对本论文的研究结论进行了总结，并提出研究的不足以及以后需进一 步研究的方向。 本论文的章节结构如图1 1 所示。 7 硕士学位论文 第一章绪论 1 3 3 采取的研究方法 图卜l 本论文的章节结构 交通网络设计问题是一个系统问题，应该以系统的观点来分析和解决，其研 究涉及到交通规划与管理、双层规划理论、非数值优化理论、以及系统工程等多 领域的知识内容。本论文的研究基于系统的分析方法，从供需两个角度分析城市 交通拥堵的原因，在国内外相关研究成果的基础上，采用双层规划技术、混沌模 拟退火技术等方法，建立了解决适用与多种交通需求结构的连续路网设计问题的 思路框架及相应的数学模型。 8 硕士学位论文第二章基于混沌模拟退火的双层模型求解算法 第二章基于混沌模拟退火的双层模型求解算法 2 1 概述 由于双层模型的复杂性，其求解较为困难，一般采用非数值最优算法进行求 解。基于混沌的优化方法由于其自身较好的特性，在优化研究领域得到了越来越 多的关注。混沌是非线性系统中的一种较为普遍的现象，其具有随机性、遍历性 和规律性的特点，能在一定的搜索空间内不重复地遍历整个空间，并且，其可以 进行并行运算，这使得其在大型问题中的应用成为可能，因此，在非数值优化领 域，混沌现象的遍历性特点可以作为搜索过程中避免陷入具有最优的一种优化机 制。混沌优化方法在单层规划模型中已得到较为成功的应用，但同时也出现了一 些应用问题。如单纯的混沌搜索在搜索空间较大时，其搜索时间较长。因此，基 于混沌搜索的优化方法成为人们的研究热点，并取得了一些应用成果。但基于混 沌的优化算法在双层模型中的成功应用很少，本文应用混沌优化思想，结合模拟 退火的跳出局部最优机制，设计了基于混沌的模拟退火算法求解双层模型，并用 算例进行了对比分析，验证算法的有效性。 2 2 混沌模拟退火算法简介 近年来，混沌理论受到了广泛的关注，随着对其研究的飞速发展，混沌优化 方法已广泛渗透到各个领域，并展现出广阔的应用与发展。 混沌是存在于非线性动力学系统中的一种较为普遍的现象，混沌系统具有一 些独特的动力学性质。混沌系统可以再特定的范围内按自身规律不重复地遍历所 有状态，具有遍历性。基于混沌理论的混沌优化方法是一种新型的直接搜索优化 算法，其具有直接搜索算法的通用性特点，对计算资源的要求不高，能在允许解 空间内直接利用优化问题的一些点的值进行搜索而不管其解析性质如何，可以克 服传统优化方法的缺点。对于多维变量、具有复杂约束的优化问题，混沌优化方 法算法简单，实现方便，可以充分利用对问题的某些先验知识( 如变量的可能变 化范围等) ，适应性强，具有一定的优越性。 2 2 1 混沌的数学概念 混沌现象的数学概念如下【5 9 】： 若采用拓扑的方法，可以将混沌定义为： 9 硕士学位论文 第二章基于混沌模拟退火的双层模型求解算法 设y 为一集合，厂：yjy 称为在y 上是混沌的，若它满足如下条件： ( 1 ) 厂有对初始条件的敏感依赖性； ( 2 ) 厂是拓扑传递的； ( 3 ) 周期点在y 中稠密。 系统对初始条件的敏感依赖性说明了混沌系统的长远不可预测性，拓扑传递 特性意味着系统的不变集不能被分解，不变集内周期点稠密表明了混沌系统的内 部规律性。 混沌系统的初值敏感依赖性是混沌产生的特点之一，可以通过如下一个简单 的动力系统来分析其产生的原因： x 。：2 x o x 一 o( 2 3 ) n 则称在s 上是混沌的。 此定义中，由于前两个极限说明了子集的点置，x ：s 相当分散而又相当集 中；第三个极限说明子集不会趋近于任意周期点，所以这个定理本身只预言有非 周期轨道存在，既不涉及这些非周期点的集合是否具有非零测度，也不涉及哪个 周期是稳定的。 l o 之 小1 1 = )j川 p p 一 一 ) b p i 叫 罨一g 一 硕上学位论文第二章基于混沌模拟退火的双层模型求解算法 2 2 2 几种常用的混沌序列 目前，混沌优化方法已经成为一种新颖的优化技术。其应用主要有以下3 种方式【1 4 1 ： ( 1 ) 基于混沌搜索的优化方法，该方法直接利用混沌变量进行搜索； ( 2 ) 基于混沌神经网络的优化方法，通过将混沌力学引入神经网络构成混沌 神经网络进行优化； ( 3 ) 基于混沌分形的优化方法。 李兵等【5 2 】首次提出了一种混沌优化方法，其基本思想就是利用混沌运动能在 一定范围内按其自身的“规律不重复地遍历所有状态，然后将混沌变量映射到 优化变量的取值范围。 一般应用中常用到的混沌序列如下： ( a ) 有限折叠次数迭代混沌自映射( l o g i s t i c 映射) 言三主兰j x n ( 1 一x ”：二? 1 2 ， c 2 4 ， o 1= 4j 、7 ( b ) 有限区域范围内折叠次数无限的一维迭代混沌自映射 x 川= s i n ( 2 x 。) 一l x 。l ( c ) 立方映射 ( 2 2 ) 鸳- 叫饥蚬三嚣：； ， 一l 少l口【3 3 ，4 】j 。 基于混沌序列动态的搜索过程分为2 个阶段，首先，基于混沌序列的遍历性， 对整个解空问进行一定程度的搜索；当满足一定的终止条件时，认为搜索过程发 现了最优解或已接近问题的最优解，并以此作为第二阶段的搜索起始点。其次， 以第一阶段得到的结果为中心，通过附加小幅度的扰动进一步进行局部区域内的 细搜索，直至算法终止准则满足。 在依混沌序列进行搜索时，为提高搜索效率，可以通过不断的缩小需要搜索 的空间，且在搜索时不断改变搜索进程中的搜索调节系数。这个搜索调节系数是 缩小搜索空间的幅度，一般束说，迭代次数越多，越接近最优解，此时应减少搜 索调节系数，缩小搜索空问。这个过程可以由图2 1 直观的表示。 、l，j 乙 l 以o = 聍 k 硕士学位论文 第二章基于混沌模拟退火的双层模型求解算法 ，b 而x 2 x 图2 1 搜索空间优化示意图 设厂( x ) 为图2 一l 所示的函数，优化目标是最小化( x ) 值。若一，( 一) 分别为 前一次迭代的最优解和最优值，则下一步搜索是以厂( 一) 为当前最优值，以一为 中心，混沌搜索范围在 口。，6 l 】；若得到最优值厂( x ：) 厂( ) ，则以x ：为中心，搜 索空间也减少到 口，6 ，】。 在一些实际应用问题中，为提高搜索效率，可以将不同的混沌序列组合使用， 采用并行计算的方式进行优化。也就是说，利用两种或几种不同的混沌机制或混 沌序列同时在搜索空间进行独立搜索，根据它们搜索到的最优点之间的“距离 情况来缩小搜索空间。以用两种混沌序列搜索为例唧j ，首先，在已知的搜索空 间彳中，利用两种混沌序列x 。，y 。进行独立并行搜索，若各自搜索到的最优解x 和y 的距离足够小( 如同时在c 空间) ，那么，按照最大似然估计的思想，可以 估计真正的最优解就该空间附近( 如在b 空间中) ，因此，可以将搜索空间从彳空 间缩小到b 空间。同样，在b 空| 、日j 按上述过程继续缩小搜索空间，直至满足某种 终止搜索条件。其过程如图2 2 所示。 图2 2 双混沌序列搜索示意图 1 2 硕士学位论文 第二章基于混沌模拟退火的双层模型求解算法 为了提高搜索效率，还可利用混沌优化搜索方法与其它优化方法相结合。如与 变尺度法、最速下降法、遗传算法、模拟退火算法、神经网络法等相结合，以避 免混沌优化方法的一些缺陷，提高搜索效率。 2 2 3 混沌模拟退火算法框架 模拟退火算法( s a ) 是8 0 年代发展起来的一种随机性组合优化方法。它模 拟高温金属降温的热力学过程，并广泛应用于组合优化问题。s a 使用范围广， 算法思想比较简单，便于实现，是一种有效的全局优化方法。s a 区别于单纯随 机搜索方法的方面主要在于它不但接受较好解，而且以一定的概率接受较差解， 从而使算法跳出局部最优成为可能。模拟退火寻优效率的关键在于随机搜索变量 的产生方式和温度下降策略的确定。 本算法( c s a ) 以混沌序列为随机搜索变量的产生方式，温度下降策略采用常 用的指数下降方式，瓦+ ，= 7 瓦，其中y 1 ，根据相关研究，其取值一般为o 9 2 至0o 9 9 9 之间，即y f 0 9 5 ，0 9 9 9 1 。 初始温度的选取采用l i n 的思路来确定【6 ，假设取开始时接受较差点的概率 为只，则只= e x p ( 一c 瓦) ，其中，c 为新点的函数值减去老点的函数值。那 么有瓦= 一c l n 只。因此，先按混沌寻优方法的第一个阶段搜索个可能解， 并记录这点所对应的目标函数值的最大值和最小值，并令c = 厶。一厶；。可 看作是对随机两个点对应函数值之差最大值的近似估计。因此可确定初始温度瓦 如下： 瓦= 等争 应用混沌模拟退火算法求解如下双层规划模型： m i n z ( y ，x ( y ) ) y s t g ( y ，x ( y ) ) 0 其中，工( y ) 由下述规划求得： m i n z ( y ，x ) s t g ( y ，x ) 0 ( 2 7 ) 可以将该双层规划模型看成是单层模型，下层规划只起到传递变量的作用， 硕上学位论文 第二章基于混沌模拟退火的双层模型求解算法 其混沌模拟退火算法框架如图2 3 所示： 图2 3 混沌模拟退火算法基本流程图 硕上学位论文第二章基于混沌模拟退火的双层模型求解算法 利用混沌模拟退火算法求解双层规划模型的具体步骤可归纳如下： 第0 步初始化。随机初始化混沌向量c 0 ，给定初始接受概率r 和初始迭代 步长，细搜索参数口，口 1 ，温度参数厂 0 9 5 ，o 9 9 9 ，同一温度下的迭代次 数，并置七= 0 ，z m i l l = i n f ，z 。科= o ； 第l 步根据混沌序列产生下一个混沌变量c 。，并映射到解向量x 。，通过 求解下层模型计算上层目标函数值z ，若z z 。，则z 。瓤= z ；令尼= 七+ l ； 第2 步若七 ，返回第l 步；否则，计算初始温度瓦= ( z m 。一z 。i 。) l nr ： 第3 步令c ：= ( 1 一口) c + 以i ，并映射到解向量x 女，置足= 1 ； 第4 步根据混沌序列产生下一个混沌变量g + 1 ，并映射到解向量x ，通 过求解下层模型计算上层目标函数值z ，若z ，口珂面m ( 0 ，1 ) ，则c = g + l ；令后= 后+ 1 ； 第5 步检查是否满足终止条件，若满足，则转第7 步；否则，转第6 步； 第6 步若七 g ，甜( m ) 相比之下，前景理论认为人们在作选择时所比较的是期望预期( e ( p ) ) ，即 可能受益值( v ) 与该收益发生的心理概率( 嵋) 的内积之和。它规定了两个函数的 存在，即y 万( g ，少( 心) 从以上期望效用理论与前景理论的选择原则可以看出，前景理论是用两种函 数来描述人的选择行为：一种是价值函数v ( x ) ，替代了期望效用理论中的效用函 数；另一种是决策权重函数万( p ) ，用决策权重代替了期望效用函数中的概率。 图3 1 为期望效用理论的效用曲线与前景理论的价值函数曲线的比较，从图 中可以看出，该价值函数呈s 形，凹的部分是损失，图形显示了价值对两种方向 上变化的敏感性的逐步降低。而且，它在0 的位置上有个拐弯，少量损失比少量 收益上的函数更加陡峭。而期望效用理论中的效用函数在任一点都是平滑的、凹 陷的。 1 9 硕士学位论文第三章路网用户出行行为分析 0x j y 前景理论 厂 损失 o 受益 ， 图3 1 价值函数比较 图3 2 为前景理论的决策权重函数曲线，它是目标概率p 和g 的变形。这个 函数单调上升，在o 、l 处间断，它系统性地给小概率过多的权重，给大概率过 小的权重。 ，、 鼠 、- ， k 悯 辎 搓 卷 既定概率p 图3 2 前景理论的决策权重函数曲线 前景理论对期望效用理论的发展主要在于让人们的经济行为更加精确，更加 贴近实际，更为准确地描述不确定性条件下的个人行为。根据前景理论，人们对 不确定性的态度不是由效用函数决定，而是由价值函数和权重函数联合决定的。 概括起来，l j i 景理论的主要结论有以下四点： ( 1 ) 人们不仅看重财富的绝对量，更看重财富的变化量。与投资总量相比， 投资者更加关注的是投资的盈利或亏损数量。 ( 2 ) 人们面临条件相当的损失前景时更倾向于冒险赌博( 风险偏好) ，而面临 条件相当的盈利前景时更倾向于实现确定性盈利( 风险规避) 。 ( 3 ) 一定量的财富减少产生的痛苦与等量财富增加给人带来的快乐不相等， 硕上学位论文第三章路网用户出行行为分析 前者大于后者。 ( 4 ) 前期决策的实际结果影响后期的风险态度和决策，前期盈利可以使人的 风险偏好增强，还可以平滑后期的损失；而前期的损失加剧了以后亏损的痛苦， 风险厌恶程度也相应