（系统分析与集成专业论文）求解城市交通连续网络设计问题的智能优化算法：比较与分析.pdf

北京交通大学硕士学位论文 中文摘要 摘要：设计求解城市交通连续网络设计问题的有效算法是交通研究领域的热点问 题之一。本论文在分析和总结现有研究成果的基础上，深入探讨了求解城市交通 连续网络设计问题的四种智能优化算法，具体如下： ( 1 ) 采用双层规划模型来描述固定需求下的城市交通连续网络设计问题，其 中上层问题的目标函数为整个网络的总阻抗和总投资额之和，下层问题则是用户 平衡配流模型。并运用目前受到较多学者广泛关注的遗传算法、粒子群算法、蚁 群算法和模拟退火算法求解该双层规划模型。实验表明，四种智能优化算法均能 求解连续网络设计问题，但是由于各个算法的参数设定以及算法结构特性不同， 使得求解精度和时间都有较大差异。 ( 2 ) 采用了灵敏度分析方法分析了不同的参数选择对各个智能优化算法性能 的影响，比较了各个参数对结果及时间影响的重要程度，确定了参数的选择原则。 实验表明，根据上述分析方法得到的参数选择原则来设定参数的取值，能够大大 提高算法的执行效率和收敛精度。 ( 3 ) 运用混沌时间序列分析方法分析了遗传算法求解过程的复杂程度。实验 表明，运用混沌时间序列分析方法分析遗传算法求解过程的复杂程度具有可行性， 其中混沌特征量一最大李雅普诺夫指数有效地表征了遗传算法求解过程的复杂程 度。此外，通过比较不同规模的网络算例的混沌特征量可知当网络规模增大时， 算法的求解过程更加复杂。 ( 4 ) 文章从定性和定量两个方面分析比较了上述四种智能优化算法求解双层 规划模型的差异性。综合考虑各个算法的收敛精度、执行效率等指标可知，粒子 群算法较适合于求解城市交通连续网络设计问题，而遗传算法略弱于粒子群算法， 蚁群算法虽然收敛精度较高但是所需的搜索时间较长，模拟退火算法则不仅收敛 精度较差且搜索时间也最长。 关键词：连续网络设计问题；用户平衡配流；智能优化算法；灵敏度分析；混沌 时间序列分析；算法性能 分类号：u 4 9 1 1 + 2 ；t p 2 0 2 ；t p 3 0 1 1 摘要 a bs t r a c t a b s t r a c t ：d e s i g n i n ge f f e c t i v ea l g o r i t h m sf o rc o n t i n u o u sn e t w o r kd e s i g np r o b l e mi s a ni m p o r t a n tp r o b l e mi n t r a n s p o r t a t i o n s t u d i e s i nt h i s t h e s i s ，f o u ri n t e l l i g e n t o p t i m i z a t i o nm e t h o d sf o rc o n t i n u o u sn e t w o r kd e s i g np r o b l e ma r ed i s c u s s e db a s e do n e x i s t i n gs t u d i e s t h ew o r k sm a d ei nt h i ss t u d ya r es u m m a r i z e di sa sf o l l o w s ： ( 1 ) ab i _ l e v e lp r o g r a m m i n gm o d e lf o rc o n t i n u o u sn e t w o r kd e s i g np r o b l e mi s i n t r o d u c e d t h eo b je c t i v ef u n c t i o na tt h eu p p e rl e v e li sd e f i n e da st h es u mo ft h et o t a l t r a v e lt i m eo nt h en e t w o r k ，a n dt h et o t a li n v e s t m e n tc o s t so fl i n kc a p a c i t ye x p a n s i o n s ； t h el o w e rl e v e lp r o b l e mi st h eu s e re q u i l i b r i u ma s s i g n m e n tm o d e l f o u r p o p u l a r i n t e l l i g e n th e u r i s t i co p t i m a lm e t h o d s ，i n c l u d i n gt h eg e n e t i ca l g o r i t h m ，p a r t i c l es w a l t n o p t i m i z a t i o n , a n tc o l o n ya l g o r i t h ma n ds i m u l a t e da n n e a l i n ga r eu s e dt os o l v et h e b i l e v e lp r o g r a m m i n gm o d e l n u m e r i c a le x p e r i m e n t ss h o wt h a tt h ef o u rm e t h o d sc a n s o l v et h ec o n t i n u o u sn e t w o r kd e s i g np r o b l e m h o w e v e r , t h ec o n v e r g e n c el e v e la n d i m p l e m e n t a t i o nt i m eo fe a c hm e t h o dh a v ec l e a rd i f f e r e n c eu n d e rt h ed i f f e r e n ts e t t i n go f t h ep a r a m e t e r sa n dt h ea l g o r i t h ms t r u c t u r e ( 2 ) t h es e n s i t i v i t ya n a l y s i sm e t h o di sf i r s tt i m eu s e dt oa n a l y z ea n dc o m p a r et h e i n f l u e n c eo ft h ed i f f e r e n ts e l e c t i o no fp a r a m e t e r st o t h ei m p l e m e n t a t i o no fe a c h i n t e l l i g e n to p t i m i z a t i o nm e t h o d s u g g e s t i o n so ft h es e l e c t i o no fp a r a m e t e r sa r eg i v e n n u m e r i c a le x p e r i m e n t sd e m o n s t r a t et h ee f f i c i e n c ya n dp r e c i s i o no ft h e s em e t h o d sc a n b ei m p r o v e dg r e a t l yw i t ht h ep r o p o s e ds u g g e s t i o n s ( 3 ) c h a o st i m es e r i e sm e t h o d sa r ei n t r o d u c e dt oa n a l y z et h ec o m p l e x i t yo ft h e s o l u t i o np r o c e s so ft h eg e n e t i ca l g o r i t h m e x p e r i m e n t sd e m o n s t r a t ei ti saf e a s i b l ew a y t ou s ec h a o st i m es e r i e sm e t h o d st oa n a l y z et h ec o m p l e x i t yo ft h es o l u t i o np r o c e s so f g e n e t i ca l g o r i t h m t h el a r g e s tl y a p u n o ve x p o n e n tc a nb eu s e dt om a n i f e s tt h e c o m p l e x i t yo fg e n e t i ca l g o r i t h me f f e c t i v e l y c o m p a r i n gd i f f e r e n te x a m p l e s ，i ti s c o n c l u d e dt h a tg e n e t i ca l g o r i t h mb e c o m em o r ec o m p l e xw i t ht h ei n c r e a s eo ft h es c a l eo f n e t w o r k ( 4 ) t h ed i f f e r e n c e so ft h ef o u ri n t e l l i g e n th e u r i s t i co p t i m a lm e t h o d sf o rt h eb i 1 e v e l p r o g r a m m i n gm o d e lo fc o n t i n u o u sn e t w o r kd e s i g np r o b l e ma r ec o m p a r e df u r t h e rf r o m t h eq u a l i t a t i v ea n dq u a n t i t a t i v ea n a l y s i s w i t ht h ec o m p r e h e n s i v e l yc o n s i d e r a t i o no f i n d i c a t o r s i n c l u d i n gc o n v e r g e n c ea c c u r a c ya n di m p l e m e n t a t i o ne f f i c i e n c y ,i ti s c o n c l u d e dt h a tp a r t i c l es w a r mo p t i m i z a t i o ni st h eb e s tm e t h o dt od e t e r m i n et h eo p t i m a l 北京交通大学硕士学位论文 s o l u t i o n ，g e n e t i ca l g o r i t h mi sl e s se f f i c i e n t t h ea n tc o l o n ya l g o r i t h mc a l lr e a c hh i 曲 c o n v e r g e n c ea c c u r a c yb u tc o m p u t a t i o nt i m ei sm o r el o n g e r t h es i m u l a t e da n n e a l i n g a l g o r i t h mi st h ew o r s tb o t hf r o mt h ec o m p a r i s o no fc o n v e r g e n c ea c c u r a c ya n dt h e i m p l e m e n t i n gt i m e k e y w o r d s ：c o n t i n u o u sn e t w o r kd e s i g np r o b l e m ；u s e re q u i l i b r i u ma s s i g n m e n t ； i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ；s e n s i t i v i t ya n a l y s i s ；c h a o st i m es e r i e sm e t h o d s ； a l g o r i t h mp e r f o r m a n c e c l a s s n 0 ：u 4 9 1 1 + 2 ：t p 2 0 2 ：t p 3 0 1 m 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：扬匙 签字日期：必谚年多月e t 、 导师签缸乙， 签字日期：沪召年月f t 北京交通大学硕士学位论文 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：犬匀) 盛二箜字日期：勿弼罗年多月乡日 l o l 致谢 我首先要感谢导师高自友教授给了我这样一个机会，使我能到北京交通大学 来学习，我的人生之路也由此发生了决定性的转折。高教授的人格魅力和治学态 度使我敬畏，在他身上我看到了一个真正的科研工作者应该具备的品格，那就是 平实严谨、不务虚华，任何时候都保持清醒的头脑和独立思考的精神，对每一种 理论和观点都要秉持客观的、批判性的眼光来加以吸收和消化。在此衷心感谢高 老师两年来对我的关心和指导。 其次，我要感谢实验室的徐猛老师。徐老师对我的论文从开始选题，到全文 的终结起到了至关重要的作用。近两年来，徐老师在学术上不断带给我启迪，悉 心指导我完成了实验室的科研工作，在学习上和生活上都给予了我很大的关心和 帮助，在此向徐老师表示衷心的谢意。此外，李克平老师对于我的科研工作提出 了许多的宝贵意见，在此表示衷心的感谢。 在实验室工作及撰写论文期间，张好智、郑建风等师兄对我论文的研究工作 给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。 本论文在完成的过程中，得到了国家重点基础研究发展计划( 9 7 3 计划， 2 0 0 6 c b 7 0 5 5 0 3 ) 和国家自然科学基金项目( 7 0 7 7 1 0 0 5 ) 的资助，在此表示感谢。 北京交通火学硕十学位论文 1 绪论 近年来，随着经济的快速发展，机动车拥有量急剧增加，带来了大范围内城 市交通的空前拥挤，造成了能源大量的消耗、环境污染等一系列社会问题。其实 产生交通拥挤的根本原因在于道路所能提供的通行能力低于道路的交通流量，而 出行方式的不合理分布和缺乏严格的交通管理，使得道路资源更加匮乏；其次， 道路建设缺乏远见，只针对一条路去考虑，而忽略了道路的相互作用，这也将导 致交通拥挤状况的恶化；再者就是建设资金的严重不足，而资金不足是交通运输 发展的最大障碍【l j 。 有效合理的解决这些问题将有助于国家经济的更快发展。但是目前所面临的 主要困难是在资金有限的情况下，如何更好的改善交通基础设施。因此，提出一 个科学的、系统的交通投资方案，可以促进城市交通状况的改善。而研究现代城 市交通网络设计问题就是最为迫切且行之有效的科学方法。 现代城市道路交通网络设计问题研究的主要内容就是通过优化计算方法寻找 最优的用于改善道路网络拥挤、减少交通污染及合理利用现有道路资源等诸方面 的投资方案，即研究在现有投资规模下，通过在现有交通网络中增加新的路段或 改善已有路段的能力，从而达到使整个交通网络某种系统性能最优，从而为交通 规划决策部门和有关人员提供科学、系统、合理、有效的决策方案和决策依据， 使政府的有限资金投入能取得最佳的投资效益1 2 】。 综上所述，研究现代城市交通网络设计问题的重要性有以下三点。第一，研 究现代城市交通网络设计问题是解决目前在我国大中城市普遍存在的交通拥挤、 交通污染及土地利用等问题的最行之有效的方法；第二，研究现代城市交通网络 设计问题能够为交通规划部门和决策、研究人员提供参考；第三，研究现代城市 交通网络设计问题可以使政府有限的资金投入取得最佳的经济和社会效益。 1 1 城市交通连续网络设计问题的研究现状 城市交通连续网络设计问题的研究已经有了3 0 年的发展历史。1 9 7 5 年， l e b l a n c 3 】首先开始比较系统地研究城市道路交通网络设计问题，并用混合整形优 化模型表示网络设计问题，这个模型是一个离散网络设计模型，其中的整型决策 变量用于表示是否新建一条路段。a b d u l a a l 和l e b l a n e ( 1 9 7 9 ) 【4 j 对l e b l a n e 的工作 进行了改进，提出了一个新的城市道路交通网络设计模型，并使用连续变量作为 决策变量，在模型中用平衡流量约束表示网络中用户的路径选择行为。这个模型 绪论 就是著名的城市道路交通连续平衡网络设计模型的鼻祖，为后续的研究奠定了基 础。此后，各学者研究城市道路交通网络设计问题主要采用的研究模型就是连续 平衡网络设计模型。 在过去的3 0 年里，国际上对城市道路交通网络设计问题的研究和探讨取得了 很大的进展，并提出了很多的模型及求解算法，其中有些模型及算法在现实中得 到了广泛的应用，b o y c e 5 】等人曾分别对n d p ( n e t w o r kd e s i g np r o b l e m ，简称n d p ) 模型与算法发展的研究成果做了综述。其中对于城市交通连续平衡网络设计问题 的研究主要集中在路段能力的改进、信号配时、土地利用等问题。 2 0 世纪9 0 年代以来，我国的一些学者也开始了交通网络设计问题的研究。高 自友等出版了国内首部城市道路交通连续平衡网络设计方面的专著城市交通连 续平衡网络设计一理论与方法，该专著对城市道路交通连续平衡网络设计的定 义、模型及求解算法做出了较为详细的描述。黄海掣6 1 、陆化普【7 1 、刘灿齐【8 】和王 炜p j 等学者也进行了道路交通网络设计问题的研究。 城市交通网络设计问题是基于整体的道路网络设计，它避免了从一条道路去 解决交通拥挤问题带来的弊病，而且合理的利用了现有的资金。通常城市交通网 络设计问题被分为三种形式：改进现有路段供给能力的连续网络设计问题，在现 有交通网络中添加新路段的离散网络设计问题以及同时采用改进现有路段和在网 络中添加新的路段这两种手段的混合网络设计问题。研究城市交通连续网络设计 问题是解决目前城市交通拥挤状况及减少交通带来的环境污染等诸多问题的行之 有效的方法，它不仅为交通规划部门提供了有效的、科学的决策支持，还使得政 府有限的资金投入取得最佳的经济和社会效益。因此，研究城市城市交通连续网 络设计问题能够用于解决实际中的交通问题 1 0 】。 在现有的城市道路交通连续网络设计的优化模型中，比较符合实际且使用较 广泛的是双层规划模型【1 1 1 。该模型考虑了政府部门决策和公众出行行为两个层次 上的规划与管理问题。上层根据自身的情况给下层一定的信息，下层获得信息并 按自己的偏好做出决策，下层的决策再反馈回上层，上层做出适当决策调整以获 得全局利益。双层规划模型的求解是一个完全n p h a r d 问题。至今关于求解城市 交通连续网络设计问题双层规划模型的研究仅有一些初步结果。设计大规模双层 规划模型的高效的全局优化算法仍然是学者们努力研究的课题之一【l 2 1 。 1 2 城市交通连续网络设计问题求解算法的研究现状 哪种模型能在实际当中获得成功的应用，相当程度上依赖于其求解算法的效 率及计算复杂性。因此，设计城市道路交通连续网络设计问题的有效求解算法成 2 北京交通人学硕士学位论文 为研究c n d p ( c o n t i n u o u sn e t w o r kd e s i g np r o b l e m ，c n d p ) 问题中一项最为重要 的研究工作。由于双层规划问题内在的复杂性，该问题的求解长期以来被认为是 交通优化研究领域中难度最大的问题之一。 现有的c n d p 研究文献中绝大部分都是研究用户平衡( u s e re q u i l i b r i u m ，u e ) 约束下现有路段拓宽的决策问题。因为其决策变量是连续的，相对比较容易设计 算法。但由于c n d p 双层规划模型的非凸性和不可微性，到目前为止，学者们所 设计的c n d p 求解算法中绝大部分均为启发式算法。这些启发式算法的不同之处 在于线性近似上下层反应函数的方法的差异。较早的三种算法是迭代优化配流算 法( i t e r a t i v e o p t i m i z a t i o n - a s s i g n m e n t a l g o r i t h m ，i o a ) 、路段使用比例算法( l i n k u s a g ep r o p o r t i o n - b a s e da l g o r i t h m ，l u p b ) 和灵敏度分析法( s e n s i t i v i t y a n a l y s i s b a s e d a l g o r i t h m ，s a b ) 。i o a 算法由s t e e n b r i n k ( 1 9 7 4 ) 【j 3 】首先提出，后来被a s a k u r a 和s a s a k i ( 1 9 9 0 ) 1 4 】充分利用以求解连续网络设计问题。l u p b 算法常用来求解某 些0 d 需求作为上层决策变量的c n d p 。s a b 算法利用了下层决策向量对上层决 策变量的梯度信息，从理论上比i o a 算法、l u p b 算法更精确。s a b 算法已经成 功应用于各种连续网络设计问题【l 引。 一 1 9 7 9 年，t a n 等人设计出m 玳o s ( m o d u l a ri n c o r en o n l i n e a ro p t i m i z a t i o n s y s t e m ) 算法【1 6 1 ，被认为是求解城市交通连续平衡网络设计问题的最为精确的算 法，但是该算法要求计算所有的路径流量，因此只适应于求解很小的网络。a b d u l a a l 和l e b l a n c 则使用基于h o o k ej e w e s 搜索的直接搜索算法求解连续平衡网络设计问 题，又称h j 算法【4 】。s u w a n s i r i k u l 、f r i e s z 和t o b i n 于1 9 8 7 年设计了一个求解城 市交通连续平衡网络设计问题的启发式算法，即e d o ( e q u i l i b r i u md e c o m p o s e d o p t i m i z a t i o n ) 算法【1 。7 1 。k i m 和s u n d u c ks u h 于1 9 8 9 年设计了b d a ( b i l e v ed e s c e n t a l g o r i t h m ) 算法【l 引，利用灵敏度分析法通过反复的、顺序的求解上层问题和下层 问题来求解问题。高自友、宋一凡等于2 0 0 0 年则利用路段能力增加量的差商作为 流量对路段能力增加量的微商近似值，从而设计了b l a b d ( 2 0 0 1 ) 算法【l 】。 也有少数学者设计了若干收敛的c n d p 求解算法。c h i o u ( 1 9 9 9 ，2 0 0 5 ) 2 0 】【2 l 】 设计了基于梯度信息的下降投影算法。m e n g 等( 2 0 0 1 ) 1 2 2 】利用最优值函数工具和 l a n g r a n g e 乘子法设计了c n d p 局部收敛算法。g a o 等( 2 0 0 6 ) 【2 习在相当强的假设 条件下，利用最优值函数工具和系统最优( 上层目标函数) 与用户平衡( 下层目 标函数) 之间的关系将该双层规划模型转化为一个凸规划问题，然后基于连续平 均算法( m e t h o do fs u c c e s s i v ea v e r a g e ，m s a ) 设计了一个求解c n d p 的全局收敛 算法。但是，该算法将双层规划模型转化为单层优化问题时，必须利用上下层目 标函数之间的关系，这使得该算法具有应用上的局限性。 此外一些智能优化算法也是求解c n d p 的有效算法。这类方法主要包括模拟 3 绪论 退火算法、遗传算法、蚁群算法、粒子群算法、禁忌搜索算法和进化算法等。这 些智能优化算法目前在求解城市道路交通连续、离散及混合网络设计中取得较好 的使用效果( f r i e s z 等，1 9 9 2 、1 9 9 3 2 4 】【2 5 】；c r e e 和m a h e r ，1 9 9 8 2 6 】；蔡金和高自 友，2 0 0 2 2 7 】；刘灿齐，2 0 0 3 2 8 】；c e y l a n 和b e l l ，2 0 0 4 b 、2 0 0 5 2 9 】 3 0 1 ：桂岚，2 0 0 6 1 3 1 1 ； 张好智等，2 0 0 5 、2 0 0 6 3 2 】【3 3 】；聂伟，2 0 0 7 州；周和平，2 0 0 7 t 3 5 】【3 q ；z h a n g 和l u ， 2 0 0 7 3 7 1 ；h o s s a i n 和o m i d ，2 0 0 7 f 3 3 】：x u 和w d 等，2 0 0 8 3 9 1 ) 。但由于此类算法求 解双层规划模型时的具体参数等难以确定，其收敛性一般难以保证，况且在实践 应用中可解释性也不理想，所以这方面的研究还属于探索阶段【4 0 1 。因此，本文将 对这些智能优化算法在求解连续网络设计问题时的计算效率、计算复杂性、参数 灵敏度及系统总体性能方面进行分析研究，为今后此类算法的应用提供参考。 1 3 论文主要框架 基于前述内容，本文将围绕求解城市交通连续网络设计问题的智能优化算法 而展开研究。本文采用了双层规划模型来描述固定需求下的城市交通连续网络设 计问题，其中上层问题的目标函数为整个网络的总阻抗和总投资额之和，下层问 题则是用户平衡配流模型。并运用四种智能优化算法，包括模拟退火算法、遗传 算法、蚁群算法和粒子群优化算法求解不同网络规模下的描述交通连续网络设计 问题的双层规划模型。之后对四种智能优化算法的求解结果进行比较，并分析各 算法的执行效率以及算法求解过程的复杂程度，其中对于各个算法在求解c n d p 问题时参数的灵敏度以及参数间的相互作用进行了较为详细的分析。 本论文共五部分。第一部分为绪论，介绍了城市交通网络设计问题的研究现 状，以及本论文的研究内容和结构。第二部分为城市交通连续网络设计问题的双 层规划模型，首先介绍了城市交通网络平衡配流模型及其求解算法，然后介绍了 双层规划模型及其在城市交通连续网络设计问题中的应用。第三部分为求解城市 交通连续网络设计问题的智能优化算法，主要介绍遗传算法、粒子群算法、蚁群 算法及模拟退火算法这四种智能优化算法的原理和基本流程，并实现了各个智能 优化算法对不同规模下的双层规划模型求解。第四部分主要为智能优化算法的参 数选取研究，此处运用灵敏度分析方法重点分析了各个算法的参数的灵敏度及参 数的相互作用，并总结了算法参数选取原则，此外还介绍了运用混沌时间序列分 析方法来研究算法求解过程复杂程度的可行性，在本章的最后分析了四种智能优 化算法的差异性，比较了四种智能优化算法求解双层规划模型的执行效率及适应 程度。第五部分为结论与展望。 4 北京交通大学硕十学位论文 论文结构安排如下图1 1 所示。 图1 1 论文结构 1 a b l e1 1t h es t r u c t u r eo ft h et h e s i s 5 城市交通连续网络设计问题的舣层规划模型 2 城市交通连续网络设计问题的双层规划模型 2 1 城市交通连续网络平衡配流模型 城市交通连续网络设计问题就是在网络用户的路径选择行为符合用户平衡准 则的前提下，通过改进现有网络中的某些路段从而使整个网络中某种性能指标达 到晟优的目的【。因此，本章将首先介绍城市交通连续网络平衡配流问题的模型及 求解算法。 2 1 1 符号定义 本章及后续章节中使用的符号定义如下： 考虑节点集和有向路段集彳组成的城市交通网络g ( m 彳) 。令 彳 网络中路段集合，口彳为任一路段； 尼s 分别为起始点集合和终讫点集合； 厂 任一起始点，r ； s 任一终讫点，s s ； 只。 连接起讫点，和s 的所有路径的集合； 路段a ，口彳上的交通流量，x = ( ，工。，) 为其向量表示； 表示起讫点，ms 之间路径p ，p 匕上的流量，厂= ( ，) 为 其向量表示； g 。起讫点，和s 之间的交通需求量，g 为当前o d ( o r i g i n - d e s t i n a t i o n ) 矩阵： 路段路径关联因子；若路段口在起讫点，和s 之间的路径p 上， ，= 1 ，否则为零； y 。上层决策变量，路段a 彳的能力增量，向量j ，= ( ，y 。，) 表示一 个决策方案； y 路段a 彳的能力增量的下限，已知； 萝。 路段d a 的能力增量的上限，已知； g 口( y 。) 拓宽现有路段a 的投资费用函数，口彳； f 。( x 。，y 。) 路段口上的时间函数，对于给定的y 。，假设它是关于屯为连续可微 的严格增函数，口爿： 匹配投资费用与系统阻抗单位的系数。 6 北京交通人学硕士学位论文 2 1 2u e 配流的数学规划模型 交通分配就是将已经预测出的o d 需求量按照一定的准则分配到路网中的各 条路段上。求出各条路段上的交通流量，以判断各条路段的负荷水平。交通分配 可以为路网规划、设计与决策提供依据。显然，对于这个问题的基本要求就是， 所得到的路段交通量应该最大限度的符合实际交通情况。在实际研究过程中人们 逐渐认识到，正确的交通分配方法应能较好地再现实际交通状态，而这种实际的 交通状态是交通网络用户路线选择的结果。基于这种认识，以使用者路线选择行 为分析为基础的交通平衡配流理论逐步发展起来。1 9 5 2 年，w a r d r o p t 4 l 】提出平衡分 配原则后，才使交通网络平衡概念从描述转化为严格刻画。1 9 5 6 年，b e c k m a n n 等 人【4 2 1 成功建立了平衡理论的数学极值模型，才首次提出了用于描述u e 原理的数 学规划模型。随着计算机技术的飞速发展，平衡模型已在交通分配理论研究中占 据了主导地位。 w a r d r o p 平衡配流原则描述如下： 在起讫点之间所有可供选择的路径中，使用者所利用的各条路线上的出行费 用全都相等，而且不大于未被利用路径上的出行费用。这里的出行费用可以被理 解为包括所有影响出行的因素，如时间、运行费用、方便舒适性等。满足上述原 则的交通状态被定义为w a r d r o p 平衡状态。在平衡状态下，系统达到稳定，此时 任何一个用户在起讫点之间都不能找到一条费用更小的路线。b e c k r n a n n 采用以下 数学形式描述w a r d r o p 平衡状态： 憎一够 三爱；三三 v ，月，j s ，p 匕 ( 2 一， 其中。为平衡状态下o d 对，ms 之间的出行费用，c ? 为o d 对，和s 之间的 第p 条路径上的费用。 通常u e 配流被归纳为一个凸规划问题【1 】【4 2 】。b e c k m a n n 提出的具有固定需求 的用户平衡配流模型如下所示： ( p 2 1 ) m i n z ( x ，j ，) = s t a ( v , y o ) a v ( 2 - 2 ) 5 j f = ，v ，月，s s ( 2 - 3 ) o ，v r r ，s s ，p ，：( 2 - 4 ) x o = 片，v 口彳 ( 2 - 5 ) 约束( 2 3 ) 代表路径流量与o d 之间的交通需求量之间的守恒关系，( 2 - 4 ) 7 城市交通连续网络设计问题的双层规划模型 保证所有的路径流量一定是j 下值，而约束( 2 5 ) 是路段流量与路径流量之间的关 联关系。在这个模型中有两个假设条件，一是假定路段费用仅仅是该路段流量的 函数，与其它路段上的流量无关；另外还假定路段费用是流量的严格增函数。 模型( p 2 1 ) 是非线性凸规划问题，其目标函数是所有网络中的路段费用函数 积分的和，目标函数本身没有什么直观的经济意义，但( p 2 1 ) 的一阶必要条件表 达了用户平衡原则，即：连接o d 对的路径可分为两类，一类路径上有流量，其 费用总是等于最小o d 费用；另一类路径上没有流量，其费用总是大于或等于最 小o d 费用。当流量分布达到平衡状态时，再没有一个用户能够通过单方面改变 行驶路径而减少费用。此即说明了模型( p 2 1 ) 的解与用户平衡条件之间的等价性。 2 1 3 u e 配流模型的求解算法 交通分配问题的算法可以分为基于路段的搜索算法和基于路径的搜索算法两 类。早期的研究以路段搜索算法为主。路段搜索算法的最大的好处是用路段流量 作为决策变量，而不必关心交通流量的路径选择具体信息。例如以f r a n k w o l f e 4 3 】 算法为基础的方向搜索算法。在f r a n k w o l f e 算法等凸组合算法中，路径流量解并 没有直接给出。要得到精确的路径流量解，需要额外进行路径储存。随着近年来 计算机计算和存储能力的飞速提高，交通分配问题不再受到这一因素的困扰。尽 管路径流量的解并不一定唯一，但它能够为o d 估计、环境影响分析、诱导系统 等提供路径流量信息。相对于路段配流算法，路径配流算法需要在计算时耗费更 多地存储空间，但能够提供更多地交通流信息，同时求解效率很高。g p ( g r a d i e n t p r o j e c t i o n ) 是典型的路径配流算法，将它应用到交通分配问题的是j a y a k r i s h n a n ( 1 9 9 4 ) 4 4 1 。算法直接使用路径作为优化变量，在每一个迭代步骤，解的改进方 向是二阶导数h e s s i a n 矩阵的相反方向。同时为了避免在非可行区域搜索，对求解 过程中的更新流量解使用非负约束。本文借鉴了文献 4 4 】、 4 5 和 4 6 】中g p 算法的 求解流程，具体形式如下。 g p 算法的框架包括初始化，列生成，平衡流量，终止条件几个步骤组成。当 每一次平衡配流后，都要进行终止条件的检查。在产生新的路径新集后，使用下 面( 2 1 0 ) 式和( 2 1 2 ) 式的路径流量更新策略进行更新流量。终止条件通常是最 大的非最短路径阻抗的导数不大于某一个事先设定的容许值g ，这个终止准则直接 反映t w a r d r o p 平衡状态的精确程度。 将平衡配流模型( p 2 1 ) 的路段流量用路径流量表示，目标函数可以改写为 m i n z = p 击赢昂乞也) 出= z ( 厂) ( 2 6 ) j n ” 北京交通人学硕十学仲论文 其目的是在搜索过程中为简化问题而松弛掉( 2 3 ) 式路径流量和的约束。在 g p 算法中，对每一o d 对( ，j ) ，将当前最短路径添加入路径集合p ，并对最短 路径流量名和非最短路径流量最通过下式表达路径流量约束： 篪= q 。一最，v ，r ，s s ( 2 - 7 ) p e 厶 添加约束条件( 2 7 ) 到目标函数( p 2 1 ) ，我们获得了一个目标函数是关于非 最短路流量的，仅仅包括路径流量非负约束的新模型( p 2 2 ) ： m i n z = z ( 厂) ( 2 8 ) 0 ，v s s ，v r 足，v p e ，, v p 歹。 ( 2 9 ) 目标函数z ( 厂) 是关于所有o d 对的非最短路流量厂的表达式。该转化形式只 有路径流量的非负约束。根据路径费用在路径之间转移流量，g p 算法将直接使用 列生成得到的最短路径结果作为参照路径定义搜索方向。在每一步的迭代时，根 据下式进行路径流量的迭代更新： 班+ 1 ) _ f t ( k ) - 器( d t t k ) _ ) + ( 2 - 1 0 ) v s s ，v r r ，跏匕，v p 瓦 ( 2 - 1 1 ) z ( i ) ( 七+ 1 ) = q 巧一f 7 ( 后+ 1 ) ( 2 1 2 ) j 口厶( t ) p 芦厅( 上) v s s ，v r r ( 2 1 3 ) 式中，k 表示迭代步数，口( 露) 表示步长，d 歹( 后) 和d ( 。) ( 尼) 分别是目标函数z 关于路径流量的一阶导数( 即路径阻抗) ，s ：( 七) 是目标函数的二阶导数海赛矩阵 的非负对角元素。式( 2 1 0 ) 和式( 2 1 2 ) 将非最短路径上的流量转化到最短路上 去。但由于步长a ( k ) 的选取可能使流量出现负值，故式( 2 1 0 ) 中使用 】+ 代表法 线的正的正交方向。在算法中，通过列生成的方法，不断的把路径添加入路径集。 为提高率，在每一步的迭代过程中，通过采用“列清除 策略将很少使用的路径( 即 路径流量接近0 ) 从路径集中剔除。 g p 算法的详细计算步骤如下【删： 第一步：初始化对每一客流o d 对，生成初始路径。 1 1 v 口，设置初始路段流量x o ( 0 ) = 0 ，阻抗t 。= t a ( o ) 】；v r ，j ，o d 对r s 的路 径集足( o ) 1 2 j ，并置当前迭代步数k = 1 ： 1 2求解最短路径问题， 得到最短路径集歹。( 七) ， 只( 七) = 死( 七) u 只( 七一1 ) ，协s ，v r 足； 1 3 执行全有全无配流：层( ”= g 。，v s s ，v r r ； 1 4 更新路段流量：吒( 七) = 芹( 尼嵫，v a a ； 9 城市交通连续网络设计问题的双层规划模型 第二步：路径集生成。生成o d 对之间的最短路径，如果该路径不在路径集中， 则将其加入。 2 1 增加迭代步数k = k + 1 ，更新路段阻抗：t 。( 七) = t a 【( 后一1 ) 】，v a a ； 2 2 求解最短路径问题【1 1 ，得到最短路径集p 一。( 尼) ，v s s ，v r r ； 2 3 女口果芦。( 尼) 仨，l ( k - 1 ) ，贝0 ，l ( j j ) = p 一。( 尼) u ，：( k - 1 ) ，v s s ，v r r ，否贝0 在p 。( k - 1 ) 中标记最短路径，并设匕( 尼) = 磊( 七一1 ) ； 第三步：平衡配流。在路径集内求解基于路径的交通分配问题。 3 1 计算路径分用的一阶二阶导数略( 后) 、d ( 。) ( 尼) 和s ；( 尼) ，即 t i t ( k ) = 乞( 七) ，跏足( 后) ，p p r s ( 七) ，v s s ，v r r d z ( 后) = t 。( 后) ) ，v s s ，v r r s ；( 七) = f ：( 尼) ( 万0 一万麓( 。) ) 2 ，印足( 后) ，p 死( 尼) ，v s s ，v r r 3 2 更新非最短路径流量： 胖+ 1 ) - - m a x f f f ；( k ) - 器( d t ( k ) - ) 】o ) 3 3 如果疗( 后+ 1 ) = 0 ，去掉路径p ，巴( 后) = 巴( k ) - p ； 3 4 更新最短路径流量塌( t ) ( 尼+ 1 ) = 一石( 七+ 1 ) ； p e 厶( ) p * p 。( t o 3 5 更新路段流量吒( 七+ 1 ) = f ( 尼+ 1 ，v a a ； 第四步：收敛判断，满足收敛条件时结束算法。 4 1 如果m a x 趔 竺兰堕掣】s ，终止算法，否则跳转第二步。 。m ，。铝t ) d t ( k ) 。 一一一。 一 研究表吲4 4 1 ，g p 算法的在收敛速度上的表现不仅优于基于路段f r a n k w o l f e 算法，也优于其他基于路径的算法。 2 2 城市交通网络设计问题的双层规划模型 由于实际的规划、决策问题都是庞大而异常复杂的系统，涉及到各种各样的 影响因素，关系着各个部门、单位和个人的具体利益，因此所采用的决策方法应 该是多层次的系统决策方法。双层规划问题是多层规划问题的一种特例，其中只 有两个层次，两种决策者。由于交通投资决策过程涉及到政府部门和公众的相互 作用或者他们之间的联合决策行为，是一个典型的双层决策问题。因此双层规划 模型成为交通投资决策过程的理想工具【l 】。 l o 北京交通人学硕士学位论文 2 2 1 双层规划模型的定义 一般来说，双层规划模型具有如下形式： ( p 2 2 ) ( u 2 2 ) m i n z ( y ，戈( j ，) ) s 2 g ( j ，x ( j ，) ) 0 其中x ( y ) 由下述规划求得： ( p 2 2 ) ( l 2 2 ) m i n z (