（系统工程专业论文）混合交通网络设计双层优化模型及其求解算法研究.pdf

东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：垒生丝垒日期：j 硝 东南大学学位论文使用授权声明 东南大学、中圊科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生虢槛聊繇瞪壑j 期：一y 混合交通网络设计双层优化模型及其求解算法研究 研究生：杜培全导师：陈森发教授东南大学 摘要 本文在现有的交通网络设计问题研究基础上，通过对路段进行等级划分、类 别划分，将混合网络离散化，建立了混合交通网络设计的双层优化模型。其中上 层模型综合考虑了网络阻抗、投资额、以及c o 的排放总量三方面因素，建立了 以三者之和最小为目标的优化函数；下层模型为交通流分配的用户均衡模型。 根据所建模型的特点，本文分别利用遗传算法、改进粒子群算法以及自适应 小生境遗传算法来对其求解。其中改进的粒子群算法是将一种使用自适应变异概 率的变异算子引入基本粒子群算法，通过实验表明改进后算法的寻优能力大幅提 高。另外，自适应小生境遗传算法是在遗传算法的基础上引入了自适应交叉、变 异概率以及小生境技术而形成的一种算法。 通过一个例子证明，自适应小生境遗传算法的收敛效率是三种算法里最高 的，其次是遗传算法，最后是改进粒子群算法，从而说明，自适应小生境遗传算 法更适合用来求解所建的双层优化模型。 通过分析求解出来的最优改善方案可知，所建的双层优化模型对于研究混合 交通网络设计问题是有效地、合理的，在现实的道路网改造中，具有很好的应用 前景。 关键词：混合交通网络设计；双层优化模型；遗传算法；改进粒子群算法；自 适应小生境遗传算法 r e s e a r c ho nb i - l e v e lp r o g r a m m i n gm o d e lf o rm i x e d t r a n s p 0 1 t a t i o nn e t w o r kd e s i g na n d i t sa i g o r i t h m g r a d u a t e ：d u p e i q u a ns u p e r v i s o r ： c 艇ns e n - f as o u t h e 觞tu n i v e r s i t y a b s t r a c t b a s e do ne x i s t i n gr e s e a f c ho ft r a i l s p o n a t i 伽n e m o r kd e s i 印， ab i l e v e l p r o g r a m m i n gm o d e l i su s e dt os o l v em i x e dt r a n s p o n a t i o nn e t 、) l ，o r kd e s i g l lp r o b l e m s i no r d e rt ob u i l dt h eb i - l e v e lp m 伊a m m i n gm o d e lf o rm i x e dt r a n s p o n a t i o nn e t w o r k d e s i g i l ，t h er o a di sc l a s s i f i e da n dt h er a n g e0 fd e c i s i o nv 撕a b l e si sr e s t r i c t e d i nt h e u p p e rl e v e l ，m i n i m i z a t i o no fs u m m a t i o no fn e t w o r ki m p e d a n c e 、 i n v e s t m e n ta n dt o t a l w e i g h to fc oa f eu s e da st h eo b j e c t i v e t h el o w e rm o d e li st h eu s e re q u i l i b r i u m a s s i g n m e n tm o d e l a c c o r d i n gt 0 t h ec h a r a c t e r i s t i c s0 ft h em o d e l ，g e n e t i ca 1 9 0 r i t h m 、m o d i f i e d p a r t i c l es w a n no p t i m i z a t i o na n da d a p t i v en i c h eg e n e t i ca l g o r i t l l l l la r eu s e dt o s o l v e t h eb i l e v e lp r o g r a m m i n gm o d e l i nt h em o d i f i e dp a n i c l es w a 彻 o p t i m i z a t i o n ， a d a p t i v em u t a t i o no p e r a t o ri si n t r o d u c e dt oe n h a n c et h es e a r c hz i b i l i t y t h ee x p e r i m e n t s h o w st h a tm o d i f i e dp a n i c l es w a 册o p t i m i z a t i o nh a sb e t t e rs e a r c ha b i l i t y a n di n o r d e rt of o 咖a d a p t i v en i c h eg e n e t i ca l g o r i t h m ，t h ea d a p t i v ec r o s so p e r a t o r 、t h e a d a p t i v em u t a t i o no p e r a t o ra n dn i c h et e c l l l l o l o g y a r eu s e di nt h eb a s i cg e n e t i c a l g o r i t h m as i m u l a t i o ne x a m p l ei su s e dt oi u u s t r a t et h a tt h ec o n v e r g e n c eo fa d 印t i v en i c h e g e n e t i ca l g o r i t h mi st h eb e s ti nt h r c ea n i f i c i a l i n t e l l i g e n c ea l g o r i t h m s s ot h ea d a p t i v e n i c h eg e n e t i ca l g o r i t h mi st h eb e s ta l g o r i t h mt os o l v et h em o d e l a tl a s t ，i ti s p r 0 v e d t h a tt h eb i l e v e l p r o g r a m m i n gm o d e l i se f i e c t i v ea n d r e a s o n a b l ef o rs t u d y i n gm i x e dt r a n s p o n a t i o nn e t w o r kd e s i g np r o b l e m sb ya n a l y z i n g t h eo p t i m u mp r o p o s a l a n dt h em o d e lh a sb e t t e ra p p l i c a t i o np r o s p e c t si nr o a dn e t w o r k t r a n s f o 肌a t i o np r o j e c t s k e yw o i d s ：m i x e d ，i h n s p o r t a t i o n n e t w o r kd e s i g n ；b i - i e v e l p m g r a m m i n g m o d e l ；g e n e t i ca l g o “t h m ；m o d i f i e dp a r t i c l es w a mo p t i m i z a t i o n ； a d a p t i v en i c h eg e n e t i ca l l g o r i t h m 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 研究的背景及意义1 1 2 国内外研究现状2 1 2 1 交通网络设计研究现状2 1 2 2 交通网络设计双层优化模型的求解算法研究现状3 1 2 3 遗传算法研究现状4 1 3 研究的目标与内容6 1 3 1 研究目标? 6 1 3 2 研究内容6 1 4 论文结构7 第二章混合交通网络设计双层优化模型9 2 1 用户平衡配流模型9 2 1 1 符号定义9 2 1 2 用户平衡配流模型1 0 2 1 3 用户平衡配流模型的求解算法1 1 2 2 混合交通网络设计双层优化模型的构建1 3 2 3 本章小结1 5 第三章求解混合交通网络设计双层优化模型的智能算法1 6 3 1 求解混合交通网络设计问题的遗传算法1 6 3 1 1 遗传算法介绍1 6 3 1 2 求解模型的算法设计1 8 3 1 3 计算步骤1 9 3 2 求解混合交通网络设计问题的改进粒子群算法2 0 3 2 i 粒子群算法介绍2 0 3 2 2 求解模型的算法设计2 2 3 2 3 计算步骤2 4 3 3 求解混合交通网络设计问题的自适应小生境遗传算法2 5 3 3 1 自适应小生境算法介绍2 5 3 3 2 求解模型的算法设计2 6 3 3 3 计算步骤2 7 3 4 本章小结2 9 第四章数值算例分析3 0 4 1 算例介绍3 0 4 2 遗传算法求解结果分析3 3 4 3 改进粒子群算法求解结果分析3 4 4 4 自适应小生境遗传算法求解结果分析3 5 4 5 网络优化方案分析3 6 4 6 本章小结3 6 第五章智能优化算法收敛效果对比分析3 8 5 1 三种智能算法多次试验的收敛情况对比分析3 8 5 2 三种智能算法求解效率对比分析3 9 5 2 1 收敛性能评价指标3 9 5 2 2 三种智能算法对比分析4 0 5 3 本章小结4 1 第六章总结与展望4 2 致谢4 4 参考文献4 5 在读期间完成的论文4 9 i v 1 1 研究的背景及意义 随着经济的发展和生活 越来越多的交通矛盾，随处 车速低造成的大量的交通尾气的排放，空气质量越来越差等等。交通问题已经成 为困扰城市可持续发展的主要障碍之一，严重影响了人们的生活质量以及整个城 市的工作效率。 目前大部分城市已经丌始重视交通问题，不断加大交通基础设施的投资力 度，通过修建新的道路，改扩建以前旧的道路，规划快速公交线路，建设地铁、 轻轨等方式来缓解城市的交通拥挤状况。但效果有限，由于缺乏先进的交通规划 理论指导，不能从城市整体布局上考虑交通网络的优化，导致即使新修建了路段， 还是有大量的车流集中到少数的道路上，造成少数道路的拥堵，其他路段却不能 充分利用等现象。所以为了缓解交通矛盾，不仅仅要加大基础设施的投资力度， 而且还必须有先进的交通规划理论作为指导，从城市的总体布局上，考虑城市的 中远期发展规划，优化现有的交通网络，在能够充分满足交通需求，提高交通网 络服务水平的情况下，能够从整体上节约投资、减少土地资源的浪费，以及充分 降低空气污染程度，同时提高交通网络的整体利用率。 交通网络设计问题( n e t w o r kd e s i g np r o b l e m n d p ) 1 1 j 研究的主要内容是： 对于一个已经存在的交通网络，用定量方法确定添加一些新的路段，或者对某些 已有路段加以改造以提高其通行能力。通常n d p 问题分为两种形式：离散网络设 计问题( d n d p d i s c r e t en d p ) ，是指在现有交通网络中添加新的路段来提高 交通网络的通行能力；连续网络设计问题( c n d p - c o n t i n u o u sn d p ) ，是指通 过改进现有某些路段的通行能力来提高整个交通网络的通行能力。混合网络设计 问题( m n d p m i x e dn d p ) 是指同时考虑在网络中添加新的路段和改进现有 路段的通行能力。混合网络设计问题被认为是更切合实际的问题【2 1 。现有的关于 n d p 问题的研究主要考虑在资金约束的条件下，通过新建或改进路段来减少交 通网络的总的出行时间1 6 j 。也有单独从土地的使用以及环境污染限制的角度来对 离散网络进行优化设计的【1 0 d2 1 。但还没有论文从节约投资、充分降低空气污染程 东南人学硕士学位论文 度，同时提高交通网络的整体利用率的角度，对混合网络进行优化，即同时考虑 新建新的路段和扩建旧的路段。本文的主要研究内容就是从上述三个角度综合考 虑，对现有的交通网络进行优化设计，建立混合交通网络双层优化模型，利用智 能算法对其求解，获得综合最优的改进方案。 因此，研究混合交通网络设计问题不仅在理论研究上有着重要的意义而且能 够用于解决实际的交通拥堵问题，在实际应用中有着广阔的应用前景。 1 2 国内外研究现状 1 2 1 交通网络设计研究现状 1 9 7 3 年m o r l o k 首次提出定量的交通网络设计问题，此后逐渐成为交通规划 领域中新的研究热点和方向。1 9 7 5 年，k b l 锄c 首先开始比较系统地研究城市道 路交通网络设计问题，并用混合整数规划模型研究离散网络设计问题【1 3 】。1 9 7 9 年a b d u l a a l 和k b l a n c 在i 曲l a n c 离散网络设计问题研究的基础上进行了改进， 提出了一个新的交通网络设计模型，使用连续变量作为决策变量，在模型中用平 衡流量约束表示网络中用户的路径选择行为【1 4 】。此篇文章为以后的连续型网络设 计研究奠定了基础。 目前，解决交通网络设计问题通常采用的方法是双层规划方法，如f r i e s z ( 1 9 8 5 ，2 0 0 1 ) 【3 卅、b o y c e ( 1 9 8 4 ) 【5 1 、y a n g 和b e l l ( 1 9 9 8 ) 【、高自友等( 2 0 0 4 ) 【2 1 、 刘灿齐( 2 0 0 3 ) 【引。其中下层规划模型最常用的是固定需求的用户平衡配流模型 ( u e ) ，也有学者使用基于l o 西t 分布的随机用户平衡配流模型( s u e ) ( c h e n 和舢f a ，1 9 9 1 ；d a v i s1 9 9 4 ) 等。由于交通网络是一个长期性的投资，也有学者 使用弹性需求的u e 和s u e 模型作为下层模型( y a n g 和b e l l ，1 9 9 8 ) ，上层模 型一般以固定需求下的网络总阻抗最小为目标函数，也有考虑将总阻抗与投资额 之和最小作为目标函数。 最近国内外的研究主要集中在考虑投资预算、环境污染、土地利用、公平约 束( m e n g 和y a n g ，2 0 0 2 ) 以及网络可靠性分析( b e l l 和c a s s i r ，2 0 0 0 ；y i n 和 l e d a ，2 0 0 2 ；舡a k u r a 等，2 0 0 3 ；c h o o t i n a n 等，2 0 0 5 ) 等方面，并取得了一定成 果。同时相比于静态的流量平衡，动态的平衡网络设计问题，动态的非平衡网络 设计问题也成为另一个研究的热点( f r i e s z 等，1 9 9 8 ；s h a h ，1 9 9 9 ；f r i e s z 和s b 柚， 2 第一章绪论 2 0 0 1 ) 。 对于离散网络设计问题，刘灿齐提出了预算约束的离散交通网络设计的数学 规划模型并在忽视b r a e s s 诡异的前提下，开发了启发式算法求解该模型i 剐；桂 岚采用双层规划模型描述问题，其中上层规划模型是有建设资金约束，下层优化 模型则是使交通出行达到用户最优，并且针对模型设计了s a g p 算法对其进行 求解【9 1 。赵彤、高自友对环境污染限制及最优控制条件下的离散交通网络设计问 题1 1 1 】和考虑土地利用问题的离散网络设计问题进行了研列1 2 1 。 对于连续网络设计问题，张国强、陆键以现代遗传算法为基础，设计了适于 解决连续网络设计问题的计算方法【4 1 】；许良、高自友在假设出行时间和出行需求 变动服从正态分布的情况下，建立了基于出行时间可靠性的城市道路交通连续网 络设计模型4 2 l ；邱玉琢、陈森发提出了综合交通运输系统路网连续投资配置的双 层规划模型，其中上层规划者在投资预算及其它约束条件下，考虑环境污染、土 地占用及能源消耗等外部成本，对线路及综合交通运输枢纽做出连续的投资配 置，以实现系统最优；下层网络用户在上层规划者的投资配置下，其路径选择满 足确定用户平衡原则1 1 6 l 。 对于混合网络设计问题，周和平、晏克非、徐汝华等针对现行公路网规划中 存在的主观随意性和网络设计模型的缺陷，提出一种基于遗传算法的公路网络设 计的双层优化模型，可一次性求出路段的技术等级与车道数【1 7 1 。聂伟、邵春福、 杨励雅等在此基础上通过限定决策变量的取值范围，将混合交通网络离散化，建 立了混合交通网络设计的双层模型。其中上层模型以方案总投资额最小为目标函 数，以路段负荷度和可行域为约束条件；下层模型为交通流分配的用户均衡模型。 并利用遗传算法对其进行求解【1 8 1 。 1 2 2 交通网络设计双层优化模型的求解算法研究现状 由于双层规划模型内在的复杂性，以及交通网络设计问题是实际的应用问 题，所以求解模型的算法必须注重计算的效率以及对于实际大规模问题的求解复 杂性，近3 0 年来有大量的学者对网络设计的双层优化模型的求解算法进行长期 的研究。 其中：离散网络设计问题一般被表述成带网络平衡约束的非线性整数规划模 3 东南人学硕士学位论文 型，求解这类模型的常用方法有b e n d e r 分解法、分枝定界法和一些启发式算法， 如极点搜索法、k u l l l l t u c k e “k - t ) 法、隐枚举法、下降法和直接搜索法等等。 k b l a n c ( 1 9 7 5 ) 用分枝定界法求解d n d p 问题，不过它每一步迭代都假设在网络 中添加新路段一定能使系统出行总成本下降。此算法的主要问题是不能求解大型 网络问题。刘灿齐( 2 0 0 2 ) 提出了预算约束的离散交通网络设计的数学规划模型， 探讨了它的隐枚举算法。然后，在忽视b 黜墟s s 诡异的前提下，改进了这个算 法，节省了计算时间l 引。 由于连续网络设计双层优化模型的非凸性和不可微性，所以现在研究的求解 算法多为启发式算法，如迭代优化配流算法( 1 0 a ) ( s t e e n b r i n k1 9 7 4 ) 、路段 使用比例算法( l u p b ) 和灵敏度分析法( s a b )( 尉m ，1 9 9 0 ) 。 近年来，随着智能算法的发展，遗传算法、蚁群算法、粒子群算法、模拟退 火算法等在求解双层优化模型求解过程中的应用已经开始逐步研究。1 9 9 2 年， f r i e s z 等人首次运用模拟退火算法求解了连续网络设计问题的双层规划模型1 4 3 j 。 1 9 9 8 年，c r e e 和m a h e r 用遗传算法求解了连续网络设计问题的双层规划模型， 并获得较好的结果【4 4 1 。2 0 0 7 年张国强、陆键以现代遗传算法为基础，设计了适 于解决连续网络设计问题的计算方法【4 。利用遗传算法求解双层优化模型的还有 周和平、晏克非( 2 0 0 5 ) ；聂伟、邵春福( 2 0 0 7 ) 等。2 0 0 3 年刘灿齐利用模拟 退火算法求解双层优化问题，通过与i o a 算法、h j 算法、e d o 算法相对比， 发现s a 的算法的求解结果由于后三种算法，但求解的时间比后三种方法长1 6 】。 2 0 0 6 年，桂岚对离散交通网络设计上层模型使用s a 算法求解，而下层模型则 采用了基于路径搜索的g p 算法进行求解，以此为基础设计了s a g p 算法对其 进行求解【9 1 。2 0 0 8 年刘炳全，黄崇超对离散网络设计的上层模型采用带自适应正 态变异因子的粒子群算法，而下层问题直接利用l 0 西t 模型求解。杨进分别采用 遗传算法、粒子群算法、模拟退火算法、以及蚁群算法对连续型网络设计问题进 行求解，并比较了四种算法的求解效率，结果是粒子群算法比较适合求解连续型 网络设计问题。 1 2 3 遗传算法研究现状 遗传算法是由美国的j h o l l a n d 教授于1 9 7 5 年在他的专著自然界和人工系 4 第一章绪论 统的适应性中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随 机化搜索算法f 3 3 】。遗传算法的搜索机制是：它模拟自然选择和自然遗传过程中发 生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指 标从解群中选取较优的个体，利用遗传算子( 选择、交叉和变异) 对这些个体进行 组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止【3 4 l 。 遗传算法的主要优点有以下三点：遗传算法适合求解带有多参数、多变量、 多目标和在多区域但连通性较差的n p - h a r d 优化问题；遗传算法在求解很多组合 优化问题时，不需要有很强的技巧和对问题有非常深入的了解；遗传算法同求解 问题的其他启发式算法有较好的兼容性【3 5 1 。虽然有以上的优点，但遗传算法也存 在着“早熟”和收敛速度慢的缺剧3 6 】。例如在复杂优化问题和多峰函数优化中，传 统的遗传算法容易陷入局部优化；遗传算法可以用极快的速度达到最优解的9 0 左右，但要达到真正的最优解则要花费很长的时间1 3 7 1 。为了克服这两个问题，大 量的改进遗传算法被提出来。 改进遗传算法的改进方法主要有三种： ( 1 ) 自适应遗传算法，包括参数白适应；即交叉概率和变异概率能够根据 个体适应度差异适当地调节大小1 2 卜2 4 】；和遗传的选择和交叉顺序自适应调整，即 利用种群早熟判别的熵准则，当种群收敛于局部最优时，转换算法结构为先变异 后交叉【3 8 1 ；以及可自适应调整的变异策略：采用赌轮选择和单点交叉的情况下， 利用一种可伸缩的变异策略使得算法在探测和丌发之间取得很好的平衡，从而能 够用小规模的种群进行有效的全局搜索和局部搜索，避免早熟收敛【2 7 】。 ( 2 ) 小生境遗传算法，小生境方法的基本思想来源于生物在进化过程中总 是与自己相同的物种生活在一起，反映到遗传算法中就是使遗传算法中的个体在 一个特定的生存环境中进化。小生境遗传算法可以避免在进化后期，适应值高的 个体大量繁殖，充满整个群体【删。1 9 7 0 年，c a v i c c h i o 率先在遗传算法中引入了 基于预选择机制的小生境技术。1 9 7 5 年d ej o n g 一般化了预选择机制，提出了 一种称作排挤机制的小生境技术。1 9 8 7 年g o l d b e r g 和r i c h a r d s o n 提出了一种基 于共享机制的小生境技术。这三种小生境技术对保证解的多样性无疑是有效的， 提高了遗传算法进行多峰函数优化时获得最优解的概率【3 9 】。林焰、郝聚民、纪卓 尚等。提出了基于隔离机制的小生境遗传算法研究【2 3 】；亓霞、陈森发在基于隔离 5 东南大学硕上学位论文 机制的小生境遗传算法的基础上，引入迁徙操作和模拟退火方法，用来解决有时 间窗的车辆路径优化问题1 2 6 】；黄聪明、陈湘秀将参数自适应与小生境遗传算法相 结合，提高了搜索速度，有效跳出了局部极小值1 2 0 l 。 ( 3 ) 将遗传算法与其它算法相结合，组成混合遗传算法。刘莉、周晓阳针 对遗传算法爬山能力弱但合局搜索能力强的特点，将遗传算法嵌入到基入传统优 化的拟下降算法中，并对算法的拟下降步骤做了一定的改进，使得整个算法具有 全局收敛性【2 8 1 ；丁建立、陈增强，等提出了将遗传算法与蚂蚁算法相融合的模型 与方法【2 9 】；孙燕、孙峥将模拟退火和隔离小生境技术有机地结合起来，融入到遗 传训练过程中形成了一种混合小生境遗传模拟退火算法，不仅可以有效地避免 传统遗传算法可能出现的不收敛现象，加快进化速度，具有更强的全局寻优能力， 而且计算速度和算法稳定性也得到提耐删。 除了以上三种主要的改进方向外，还有最优保留策略的遗传算法【2 5 1 ，三种群 遗传算法【1 9 】等等。 1 3 研究的目标与内容 1 3 1 研究目标 本文的研究目标是：在现有的关于离散型和连续型交通网络设计的研究基础 上，考虑资金投入、环境以及交通网络服务水平等因素，建立混合交通网络双层 优化模型，并利用遗传算法、改进粒子群算法、自适应小生境遗传算法对其进行 求解，在对比分析三种算法的收敛效果之后给出最适合求解所建模型的算法。 1 3 2 研究内容 围绕研究目标开展的主要研究内容有： 1 混合交通网络双层优化模型的建立 从介绍双层优化模型的下层模型即固定需求的用户配流模型入手，分析交通 网络设计主要考虑的几个重要因素，如：新建或改进路段所需要的投资、对环境 造成的影响以及优化后的交通网络的服务水平，在充分考虑这几个因素的情况 下，建立混合交通网络双层优化模型。 2 求解双层优化模型的智能算法一 6 第一章绪论 求解双层优化模型的算法很多，主要包括启发式算法和智能算法，本文主要 利用智能算法中的遗传算法以及改进粒子群算法进行求解，并且在此基础上，对 遗传算法进行改进，引入现有的几种改进方法包括小生境技术，参数自适应方法 等，提出一种适于求解混合交通网络双层优化模型的算法，它具有更快的收敛速 度以及优秀的全局搜索能力。 3 算例分析 根据上一章的三种智能算法的求解步骤，对一个模拟的交通网络算例进行求 解，分别得到利用每种算法求解出的最优方案，以及其收敛过程。 4 三种智能算法求解效果对比以及网络优化方案分析 在上一章实验结果的基础上，引入三个定量的评价指标，来分析三种智能算 法的求解效率，得出最适合求解所建模型的算法。并且根据三种智能算法求得的 最优方案，分析交通网络改进后的服务水平、投资额、对环境的影响、以及改进 后网络的合理性。 1 4 论文结构 本文共五章，第一章绪论部分介绍选题的研究意义、目前国内外研究的现状 以及本文的主要研究内容和目标。第二章主要是建立混合交通网络双层优化模 型，其中介绍了固定需求的用户配流模型及其求解算法，这是双层优化模型中的 下层模型。第三章是介绍求解所建立的双层优化模型的智能算法，分别是基本遗 传算法，改进粒子群算法，以及自适应小生境遗传算法。第四章利用一个模拟的 算例分别来分析遗传算法、改进粒子群算法以及自适应小生境遗传算法的求解的 最优结果以及其收敛过程，并且对得到的最优解所对应的网络优化方案进行分析 总结，对所建模型的效果进行分析。第五章主要是在前一章的基础上利用性能指 标来对比分析三种智能算法的求解效率及其优缺点，总结出最适合求解所建模型 的算法。最后为总结与展望部分，简要总结本论文的主要创新内容并指出有待于 进一步研究的问题。本论文研究内容的结构安排如图1 1 所示。 7 东南人学硕十学位论文 巳卫 i 第二章混合交通网络设计双层优化模型 土 i 第三章求解混合交通网络设计双层优化模型的智能算法 上 i 第四章数值算例分析 土 l 第五章智能优化算法求解效果对比分析 上 第六章总结与展望 图1 1 论文结构安排 8 第二章混合交通网络设计双层优化模型 第二章混合交通网络设计双层优化模型 混合网络设计问题( m n d p ) 是指同时考虑在现有的道路网络中添加新的路 段和改进已有路段以达到提高道路网络的通行能力的目的。本章在现有的交通网 络设计问题研究基础上，采用双层规划模型来描述混合网络设计问题，其中上层 模型综合考虑了网络阻抗、投资额、以及c o 的排放总量三方面因素，建立了以 三者之和最小为目标的优化函数；下层模型为用户平衡配流模型。本章首先介绍 用户平衡配流模型及其求解算法，然后介绍混合交通网络设计双层优化模型。 2 1 用户平衡配流模型 交通流量分配是将已经预测出的0 d 交通量根据实际情况按照一定的规则 分配到道路网中的各条道路上，并求出各条道路的交通流量。o d 交通量是两点 之间的交通量，即从出发地( o r i g i n ) 到目的地( d e s t i n a t i o n ) 之间的交通量。一 般道路网络中；两点之间( 即o 与d 之间) 有很多道路，如何将o d 交通量正 确合理地分配到o 与d 之间的各条道路上即是交通分配模型要就解决的问题用。 2 1 1 符号定义 本章用到的符号定义如下： 么 道路网络中待新建的路段的集合；口么为任一路段； 口道路网络中待改进的路段的集合；6 b 为任一路段； c道路网络中所有路段的集合，包括现有路段可能要新建的路段；c c 为任一路段； 为网络中节点的集合； m 为投资额的上限； 艺为路段c 上的交通流量，它们组成的向量为x c = ( ，t ，) ； t 为路段c 的长度； y 。为路段a 的决策变量，儿的取值范围为y 。 0 ，1 ，l 】； ( y 。) 表示通行簦力的决策变量y 。的投资需求函数； 9 ( 虼 七 r s 为最大允许的路段交通流饱和度； 展 因走行时间与投资额的物理量纲不同而设置的权系数； 反 因走行时间与c o 排放量物理量纲不同而设置的权系数； t 纯，y 。) 为路段c 的走行时间函数，对于给定的y 。，假设它是关于t 为连续 可微的严格增函数，c c ； 为点对( ，s ) 间第七条路径的交通量，其向量为厂= ( ，) ； 为点对( 厂，s ) 问的出行交通量； 6 0为路段一路径相关变量，如果路段c 在( ，s ) 间的第k 条路径上 畦= 1 ；否则等于o ； r为路段c 的c o 排放率。 2 1 2 用户平衡配流模型 1 9 5 2 年w a r d r o p 提出了道路网平衡的概念和定义，通常称为w a r d r o p 平衡 或w a r d r o p 第一原理。其具体叙述如下：在道路网的利用者都知道网络的状态并 试图选择最短路径时，网络会达到平衡状态，在考虑j j 挤对行走时间影响的网络 中，当网络达到平衡状态时，每组o d 的各条被利用的路径具有相等而且最小的 走行时问，没有被利用的道路的走行时间大于或等于最小走行时问。 由于道路网络平衡的复杂性，自从w | a r d r o p 提出道路网络平衡的概念和定义 之后，如何求解w a r d r o p 平衡成为研究者的重要课题。1 9 5 6 年b e c k m a n n 等提出 了求解交通分配的一种数学规划模型即用户平衡配流模型( u e 模型) 。这组模型 奠定了研究交通分配问题的基础，后来的许多分配模型都是在u e 模型的基础上 1 0 第一二章混合交通网络设计双层优化模型 扩充得到的。 交通流分配问题本身应满足的条件只有交通流守恒条件，即各o d 对之间的 交通量应全部分配到网络中，以及非负约束条件，即某条路径上的流量都是不小 于0 的，同时每条路段的交通量等于所有经过这条路段的路径交通量之和。根据 以上条件，u e 模型表示如下： m i n z ) 2 荟r 乞( ) d 刚；髓吼洲 ( 2 1 ) ( 2 2 ) o ，v ，s ( 2 3 ) x 。= 啦，v c c ( 2 圳 其中模型的目标函数是对各路段的走行时间函数积分求和之后的最小值，没 有什么直观上或经济上的解释。式( 2 2 ) 为流量守恒约束条件，式( 2 3 ) 为流 量非负约束条件，式( 2 4 ) 为路段流量等于所有经过该路段的路径流量之和的 约束条件。 经过对目标函数分析可知：当路径尼上有从厂到s 的交通流量时，路径后的 走行时间等于最短路径的走行时间，当路径忌上没有从，到s 得交通流量时，路 径尼的走行时间大于或等于最短路径的走行时间，这f 是w a r d r o p 平衡准则所要 求的，因此b e c k m a n n 模型的解满足w a r d r o p 平衡准则吲。 2 1 3 用户平衡配流模型的求解算法 在b e c k m a n n 提出关于交通分配的数学规划模型2 0 年后，k b l a n c 等人才 开始用f r a n k w o l f e 算法求解u e 模型，之后发展出了多种求解算法。根据这些 算法所确定解的情况，大致可分为两大类：一类是基于路段的求解算法；类是 基于路径的求解算法。最著名的路段算法就是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 算法。基于路径的求解算法主要有：聚集单纯形分解算法( d s p ) 【4 引、 投影梯度算法( g p ) 1 4 9 】和共轭投影梯度算法( c g p ) 【5 0 1 。本文将利用经典的 东南人学硕：l ：学位论文 f r a i l l 【一w o l f c 算法求解u e 模型。 f r a i l l 【w o l f e 算法的主要是利用线性规划逐步逼近非线性规划的方法来求解 u e 模型的，该方法是一种迭代法，在每步迭代中先找到一个最速下降方向，然 后再找到一个最优步长，在最速下降方向上截取最优步长得到下一步迭代起点， 重复迭代直至找到最优解为止，此法的前提条件是所求解模型的约束条件必须都 是线性的。 经过计算得知：下一步的迭代方向就是在上一步的分配的基础上，进行一次 o 一1 分配，得到一组附加交通量 f ) 。其中0 - 1 分配的步骤为首先求得每个o d 对之间的最短路径，然后将所有的交通量全部分配到此路径即可。求最短路径的 方法可以使用d i j k s t r a 算法。 下一步的迭代步长可通过下式得到： ( y ? 一z ? ) f 。【z ；+ 口( y ：一x ? ) 】= o 。( 2 5 ) 其中为第，z 步分配的交通量，y ：为第 + 1 ) 步分配的附加交通量， “+ 口( y ：一) 】为第( n + 1 ) 步的路段阻抗，a 即为最佳迭代步长，式中只有a 为未知量，故可以通过二分法来求解口的值，利用求的的a 值，即可计算下一步 迭代起点x ：“，计算公式如下： x ：“一x ? + 口( f x ：) ( 2 - 6 ) 迭代的终止条件可以设为如果前后两次分配的交通量变化非常小即可终止。 综上所述f r a n k w o l f e 算法的步骤如下f 7 】： s t e p0 ：初始化。按照t f c ( 0 ) ，v c ，实行一次0 1 分配，得到各路段的交通流 量 x ： ，令聆= 1 ； s t e p1 ：更新路段走行时间。令f ? = f ：( x ? ) ，v c ，计算o d 间最短路； s t e p2 ：寻找下一步迭代方向。按照【e ) 实行一次o - 1 分配，并得到一组附加 向量 f 】； 一 s t e p3 ：确定步长。求满足下式的。 1 2 ( y ：一x m 【x ： s t e p4 ：确定新的迭代 s t e p5 ：终止条件检验。如果满足终止条件，则结束迭代，输出 群+ 1 ) ，此即 为分配好的交通量，否则令n = n + 1 ；返回s t e p1 。 利用上述求解算法即可求得满足w | a r d r o p 平衡准则的各路段交通量，根据此 交通量即可求出每条路段的阻抗函数。从而整个网络的阻抗即可得出。 本节主要介绍了交通流量分配中非常重要的w a r d r o p 平衡准则，以及依据次 准则建立起的用户平衡配流模型即u e 模型，并对u e 模型的各种求解算法进行 了简单的叙述，之后重点介绍了其中一种经典的算法：f r a n k w o l f e 算法，利用 此算法可以求出满足u e 模型的交通流分配方案。 2 2 混合交通网络设计双层优化模型的构建 混合交通网络设计研究的是在现有网络中如何通过同时新建某些路段和增 加另外一些路段的通行能力来改善现有网络的通行状况。为减少计算的复杂性， 在建立模型之前，在现有公路网络中选出可能需要建立的新路段的集合彳，路段 口为其中可能要新建的某条路段，砭为路段口上的交通流量，它们组成的向量为 一= ( 一，吃，) ，y 。为路段口的决策变量，y 。的取值范围为y 。 o ，1 ，肌) ， 岛( y 。) 表示通行能力的决策变量虼的投资需求函数；同理在现有网络中选出可 能要进行改进的路段的集合b ，路段6 为其中某条需要改进的路段，吃为路段6 上的交通流量，它们组成的向量为= ( ，) ，虼为路段6 的决策变量， 的取值范围为蚝 0 ，1 ，l 】- ，鼠( 虼) 表示决策变量虼的投资需求函数。c 为网络 中所有路段的集合，包括待修建路段，待改进段以及维持不变的路段。 本文以区域公路网络为对象，建立双层优化模型，其中上层模型综合考虑了 网络的总阻抗、改善方案的总投资额、以及整个改善后的交通网络排放的c o 总 量三方面因素，并利用遗传算法求得了三者之问的权系数，从而建立以三者总和 1 3 东南大学硕上学位论文 最小为目标的函数；下层模型为交通流分配的用户均衡模型i 刀。 所建模型如下： 上层： m i n z ) 5 荟。f c 化以) + 屈( 荟( y n ) + 荟( ) ) + 殷( 荟t r 乞)忽忽魁忽 ( 2 8 ) “薹g 。( y 口) + 薹( 儿) s m ( 2 9 ) 口爿6矗 丸 o 时，则表示会修建那条路，公路的等级用数值表示，投资额( 儿) 是公路的长度 乘以该等级公路的每公里投资额；当虼 0 时，则表示会改进那条路，改进后 的公路等级是在原来的基础上加上y 6 ，投资额( 儿) 是改进后的每公里投资额 减去原来每公里的投资额然后再乘以公路的长度。根据交通部的公路工程技术 标准和研究的需要，可将决策变量取值范围和对应的公路等级情况列为表 2 1 【9 l o 表2 1决策变晕及其对应公路等级 123 4 5 67 y 。 等级 四级三级二级一级一级高速高速 车道数 2224646 设计时速( 1 【1 1 1 1 1 )2 04 08 0 1 0 0 1 0 0 1 2 01 2 0 适戍交通量( p c u d ) 2 0 ( ) 06 0 0 01 5 0 0 03 0 0 0 05 5 0 0 05 5 0 0 08 0 0 0 0 投资额( 万元公里) 8 01 0 06 0 01 0 0 03 0 0 03 0 0 05 0 0 0 2 3 本章小结 本章主要介绍了平衡配流模型的发展过程，并详细描述了其数学模型，对其 求解算法也进行了介绍。然后在现有研究的基础上提出了混合网络设计双层优化 模型，其中上层模型综合考虑了网络阻抗、投资额、以及c o 的排放总量三方面 因素，建立了以三者之和最小为目标的优化函数；下层模型为用户均衡模型。下 面两章将分别介绍如何利用遗传算法、改进粒子群算法、自适应小生境遗传算法 来求解已建好的双层优化模型，并利用一个例子来验证它们之间的优缺点。 1 5 第三章求解混合交通网络i 殳计双层优化模型的智能算法 第三章求解混合交通网络设计双层优化模型的智能算法 由于所建双层优化模型属于大规模的混合整数规划模型，具有n p 难题性质， 如果利用传统优化方法，如极点算法、分枝定界法、下降算法等很难在合理的时 间内求得模型最优解。为此，本章