（管理科学与工程专业论文）交通网络复杂性及其优化研究.pdf

中文摘要 复杂网络理论的出现为人们研究复杂系统又提供了一个非常好的方法。现实 世界中的很多复杂系统均可以用复杂网络来描述，应用复杂网络理论来研究复杂 系统具有非常明显的实际应用价值。目前的研究熟点主要是从复杂网络的拓扑特 性出发，进而研究复杂网络上的动力学、同步、传播等特征以及对其建模。相比 非空间网络来说，学者们对于空间网络一直没有给予太多的关注。空间网络中的 节点与连边都有特定的地理位置，因此不仅要研究其拓扑特性，还要进一步探索 其在地理条件限制下的空间特性以及优化设计，进而达到对空间网络进行高效管 理，提高其抗灾变与抗攻击能力的目的。 本文首先介绍了国内外复杂网络理论与应用研究发展动态，在此基础上，本 文主要在探求交通网络的空间特性和优化方面做了如下工作： 1 、经过统计分析，发现了一类度分布符合类高斯分布形式的复杂网络，经 验证，中国铁路网络、世界部分国家高速公路网络、部分主要大都市地铁网络度 分布均具有此特性； 2 、综合分析了部分世界主要城市地铁网络，发现它们拥有如下共性：倾向 于选择短边、平均度数接近于2 、聚集系数接近于0 ，直径较大。经对比分析与 计算机模拟仿真，发现城市地铁网络具有类似最小生成树样的结构。之后以北京 地铁网络为例分析了其鲁棒性与抗毁性，发现其在节点随机故障情况下具有较好 的鲁棒性，但在节点遭受恶意攻击情况下是比较脆弱的； 3 、综合分析了部分国家高速公路网络，经分析与计算，发现他们具有如下 相同特征：倾向于选择短边、平均度数小于4 、小的聚集系数与大的直径。之后 从此类网络的空间地理特性对其拓扑特征的成因进行了分析； 4 、探讨了中国高速公路网络在节点出现随机故障和遭受恶意攻击下的动力 学演化过程并分析了其鲁棒性与抗毁性，结果表明采用动态节点介数降序次序攻 击的方式对网络的毁灭性最强； 5 、改进了高速公路路网布局规划模型，改进后的模型增加了对路网网络特 性的考虑，更贴近于实际需求，之后结合复杂网络与经济学理论，从成本收益分 析的角度对路网布局优化模型进行了改进，最后基于运筹学中的一般算法与遗传 算法，提出了路网结构优化方法，优化之后的路网结构在抗毁能力上有一定的提 高。 关键词：空间网络交通网络度分布介数鲁棒性脆弱性遗传算法 a bs t r a c t t h ee m e 唱e n c eo fc o m p l e xn e 似，o r kt h e o 眄a g o r d su sa n o t h e rn e wa n dg o o d m e t h o dt os t u d yc o m p l e xs y s t e m s m a n yc o m p l e xs y s t e m si nt h er e a lw o r l dc a nb e d e s c r i b e da st h ec o m p l e xn e t w o r k s ，s o ，i ti so b v i o u st h a tt h e r ea r eg r e a tv a l u e st 0 r e s e a r c hc o m p l e xs y s t e m sb yc o m p l e xn e 俩o r kt h e o 巧a tp r e s e n t ，t h eh o t6 e l do f c o m p l e xn e t 、o r k r e s e a r c hi sf o c u s e do nt h e t o p o l o g i cp r o p e r t i e s ， d y n a m i c s ， s y n c h r o n i z a t i o n ，e p i d e m i ca n dm o d e l i n g i nc o m p 撕s o nw i t ha b s t r a c tn e t w o r k s ，l i t t l e a t t e n t i o ni sp a i dt os p a t i a ln e t w o r k s a l lo ft h en o d e sa n de d g e so ft h es p a t i a ln e 觚o r i ( s h a v e s p e c i a lg e o g r 印h i c a lp o s “i o n ， s o ， w em u s tc o n c e n t r a t e0 nt h e i r s p a t a l c h a r a c t e r i s t i c sa n do p t i m a lp l a nu n d e rt h er e s t r i c t i o no fg e o 伊a p h yc o n d i t i o n sb e s i d e s t h e i rt o p 0 1 0 9 i cp r o p e r t i e s t h u sw ec 柚m a n a g et l l es p a t i a ln e 铆o r k se 仃e c t i v e l y 柚d e 伍c i e n t l yt oi m p r o v e t h e i ra b i l i 够o nr e s i s t i n gd a m a g eo ra t t a c k t h ed i s s e r t a t i o ni n 们d u c e st h ec o m p l e xn e t 、v o r kt h e o 巧sd e v e l o p m e n ta n d r e s e a r c ha c t u a l i t ) ，o fi n t e m a t i o n a la n dd o m e s t i c o nt h er e s p e c to fs e a r c h i n gs p a t i a l p r o p e r t i e sa n dt h eo p t i m i z a t i o no f 讹n s p o 似i o nn e t w o r i ( ，t h em a i nw o r k so fm e d i s s e l t a t i o na r ea sf 1 0 i l o w s ： f i r s t ，b ys t a t i s t i ca n a l y s i s ，ak i n do fc o m p l e xn e 甜o r k sw h o s ed e 伊e ed i s t r 渺u t i o n f o l l o w e dag a u s s i a n 一1 i k cd i s t r i b u t i o nw a sp u tf o r v v a r d a f t e rc a s es t u d y ，i tw a sf o u n d t h a tt h ed e g r e ed i s t r i b u t i o no fc h i n e s er a i l w a yn m v o r k ，n a t i o n a ih i 曲w a ys y s t e m o fs o m ec o u n _ t r i e sa n ds u b w a yn e t w o r k so fs o m ec i t i e sa l lf o l l o w e dt h i s 够p e ； s e c o n d ，s o m eb i gc i t i e s s u b w a yn e t w o r k sw e r ea n a l y z e da n di tw a sf o u n dt h a t t h e ys h a r e ds o m ec o m m o nc h a r a c t e r i s t i c s ：t e n d i n gt oc h o o s es h o r te d g e s ，a v e r a g e d e g r e ei sn e a rt o2 ，c l u s t e r i n gc o e f f i c i e n ti sa l m o s t0a n dl a 玛ed i 锄e t e r b yc o m p u t e r s i m u l a t i o n ，i tw a sa l s of o u n dt h a tt h es t r u c t u r eo fs u b 、a yn e w 的r kw a sv e 巧l i k e m i n i m u ms p a n n i n g 仃e e ，a n db e i ji n gs u b w a yn c t w o r kw a sr o b u s tu n d e rr a n d o m f a i l u r eb u tf r a i lu n d e rm a l i c ea t t a c k t h i r d ，s o m ec o u n 仃i e s n a t i o n a lh i 曲w a ys y s t e m sw e r e 卸a l y z e da n di t 、v a s f o u n dt h a tt h e ys h a r ef o l l o wc o m m o nc h a 船c t e r i s t i c s ：t e n d i n gt oc h o o s es h o r te d g e s ， a v e r a g ed e g r e ei ss m a l lt h a n4 ，s m a l lc l u s t e r i n gc o e 币c i e n ta n dl a 唱ed i a m e t e r t h e n ， t 1 1 e g e n e s i so fa b o v ep r o p e r t i e sw a sa n a l y z e d f _ r o mt l l er e s p e c to ft h e i rs p a t i a l g e o g r a p h i cc k 嗽l c t e r i s t i c s ； f o u r t h ，t h ed y n a m i ce v o l v e m e n tp r o c e s so fc h i n e s eh i g h w a yn e t 、) r o r ku n d e r r a n d o mf a i l u r ea n dm a l i c ea t 诅c kw a sd e m o n s t r a t e d ，a r e ra n a l y z i n gi t sr o b u s 伽e s s a n di n v u l n e r a b i l i 吼i tw a sf o u n dt h a tc h i n e s eh i g h w a yn e t w o r ka r ef h i l e s tu n d e rt h e m a l i c ea t t a c ko f d y n a m i cn o d eb e t 、 r e e n n e s sd e s c e n d i n go r d e r ； f i r h ，m o d i 6 e dt h em o d e lo fh i g h w a yn e t w o r kp l a n n i n g ，t h en e t w o r kt o p o l o g i c p r o p e r t i e sw e r ea d d e di nt h en e wm o d e l ，a n di ts a t i s 矗e dt r u ed e m a n dm o r e 。t h e nt h e o p t i m i z a t i o nm e t h o do ft h eh i g h w a yn e t w o r kw a sa l s ob em o d j 行e df r o 瑚t h er e s p e c t o fc o s t - b e n e f i tb a s e do nc o m p l e xn e t w o r ka n de c o n o m i ct h e o r y a tl a s t ，t h es t m c t u r e o fc h i n e s eh i 曲w a yn e t w r o r kw a so p t i m i z e db yg e n e t i ca l g o r i t h m ，a n dt h eo p t i m i z e d s t m c t u r ew a si m p r o v e do ni n v u i n e r a b i l i 够 k e yw o r d s ：s p a t i a ln e 帆o r k ，仃狮s p o r t a t i o nn e t 、o r k ，d e g r e ed i s 仃i b u t i o n ，b e 锕e e n n e s s ， r o b u s t n e s s ，纳n g i b i l i t y ，g e n e t i ca l g o r i t h m m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞墨堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名 签字日期：7 咿年上月谚日 学位论文版权使用授权书 本学位论文作者完全了解苤盗盘堂 有关保留、使用学位论文的规定。 特授权叁注蕉鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 签字日期：讼夕年r 月名日 导师签名： 签字日期：1 年妇形日 第一章绪论 1 1 复杂网络研究概况 第一章绪论 自然界中有许多美丽漂亮的网络，图卜1 中展示了州t e r n e t ( w i i a mr c h e s w i c k ) tw w w ( k cc l a f 珂) ，电信网络( 鼬p h e nge i c k ) - 航空网络，生物 网络与艺术网络( 以上图片来源于香港城市大学陈关荣教授报告) 。 豢 ”髻 零 信刚络 生物网络 琴 艺术网络 固j - l 美丽豹阿络 f i gl - lb u t i m ln e t w o r k s 我们正是生活在这样一个网络的世界，与人打交道离不开关系网络：日常出 霾戮 天津大学博士研究生毕业学位论文 行离不开交通网络；电子邮件、电话、i n t e m e t 等无一不处于网络之中；在生物 体内，新陈代谢的过程也形成一个网络。可以说，网络与我们的生活息息相关， 但我们对网络的了解只是冰山一角，网络在带给我们便利的同时，也偶尔会让我 们处于麻烦之中，生物病菌的传播、网络病毒的肆虐、电力网络发生故障而使得 某地区大范围停电、地铁遭到恐怖袭击，等等这些灾难往往使得人们措手不及。 当代社会，科学技术飞速发展，我们需要而且也有必要去揭开这些复杂网络的神 秘面纱。 1 1 1 复杂网络的发展、研究内容及意义 复杂网络是近些年兴起的科研前端，以图论为研究基础。图论研究始于1 8 世纪数学家欧拉解决哥尼斯堡七桥问题，问题描述如下：欧洲的普瑞格尔河 ( p r e g e l 砌v e r ) 流过哥尼斯堡城中心，河中有两座岛，沿两岛周围筑有七座小桥， 连接了两岛以及岛和河对岸，如图卜2 所示。当时的人们提出这样一个猜想：是 否存在一次性走完七座桥的通路。1 7 3 6 年，数学家欧拉严格地证明了此猜想无 解。我们可以将图卜2 抽象为图卜3 ，图中的节点代表陆地，连边代表桥。欧拉 指出：如果一个图中只存在两个以下奇数度( 度的概念即为一个点的连线数) 的 点，就会存在一次走过所有边的通路u 1 。图1 3 中，四个点的度都是奇数，因此 哥尼斯堡并不存在一次性通过七座桥的通路。 图卜2 哥尼斯堡七桥问题图卜3 哥尼斯堡七桥问题示意图 f i gl - 2 p u z z l eo f 硒n i g s b 啷b r i d g 器 f i g1 3g r a p ho fk 6 n i g s b e 唱研电e s 图论的发展经过了2 0 0 多年，直到2 0 世纪6 0 年代e r d 6 s 和他的同事r 6 n y i 【2 吲 提出了经典的随机网络模型( e r 模型) ，这之后才掀起了复杂网络的研究热潮， 也真正从科学上开始了对复杂网络做理论上的研究。自e r 模型提出后，这个理 论在研究领域统治了近四十年，在这期间对于那些没有明确其生成原理的大规模 网络就主要用这种简单而且易于被人们接受的随机网络来描述，即可以认为在大 规模网络的形成过程中，节点间的连接是完全随机的。直到2 0 世纪末，随着计 2 第一章绪论 算机科学技术的发展，使得人们对于大量的数据处理成为可能，科学家们才发现 现实世界中许多网路并不是完全随机的，而是具有其他一些重要特征。1 9 9 8 年， 当时就读于康奈尔大学的邓肯j 瓦茨( d u n c a nj w a t t s ) 和他的导师史蒂夫斯托 加茨( s t e v es t r o g a t z ) 晦。在na t u r e 杂志上发表文章，提出了复杂网络的小世 界性质，1 9 9 9 年，美国圣母大学物理学教授巴拉巴斯( a l b e r t l 直s z l 6b a r a b 矗s i ) 和阿尔伯特( r 6 k aa l b e r t ) 哺3 在s c i e n c e 上发表文章，提出了无标度网络这一 概念，所谓无标度网络即网络节点度分布符合幂律分布形式。上述两个发现又极 大的推动了复杂网络研究进展，此领域吸引了来自于图论、统计物理学、计算机 网络、社会学、经济学以及生态学等多学科的专家。在我国，国家自然科学基金 委员会自1 9 9 9 年起，专门设立了复杂性科学研究的专项基金。 复杂网络的出现为人们了解与探索复杂系统提供了一个新的方法，随着计算 科学技术的发展，使得人们对于复杂系统的研究成为可能。复杂网络理论的出现 为人们研究复杂系统又提供了一个非常好的方法，现实世界中的很多复杂系统均 可以用复杂网络来描述。各种优化算法与应用软件的结合使得人们对于复杂系统 有了更深刻的认识。 复杂网络的研究中心在于探索网络结构与网络功能之间的关系。网络结构体 现在网络的拓扑性质、形成机制、演化规律以及网络建模等。网络几何性质主要 包括度、特征路径长度、平均聚集系数、直径以及介数等。网络演化包括五种现 象：在网络中进行加点，加边，去点，去边和重连等操作。因此，我们可以说两 点之间的连接关系是复杂网络研究的出发点( s t 叭i n gp o i n t ) 口3 。 复杂网络的复杂性体现在以下方面：结构非常复杂、网络不断演化，连接的 多样性，网络动力学的复杂性( 汪小帆，2 0 0 4 4 9 ，复杂网络研究的主要进展) 。 绝大多数的复杂动力网络具有如下几个特征阳1 ：网络行为的统计性；网络连 接的稀疏性；连接结构的复杂性；网络的时空复杂性；网络节点( 动力系 统) 之间的同步运动( 包括混沌同步) 。 复杂网络理论是跨学科的，涵盖了数学、物理学以及统计力学的基础理论， 其强大之处在于它能非常直观的刻画出生物、自然以及人工系统，通过点与边之 间的关系来描述复杂系统。通过这样一种直观的刻画，我们可以很清楚地了解复 杂系统的内在机理及作用原理，从而深入研究系统构造及功能，以期能提高系统 能力或预防系统出现的问题。 复杂网络如今在管理学阳、经济学n 2 ，1 朝、计算机州 、社会学1 蝴1 、数学3 、 生物学瞻。翻、物理学盥劓、医学口叼以及自动控制领域2 7 1 均有不同程度的应用。本 文现从以下几个方面来简要介绍复杂网络目前的主要研究内容。 一、社会网络 天津大学博士研究生毕业学位论文 社会网络就是人的个体之间或团体之间存在某种方式的联系或相互作用而 形成的关系网络啪，捌，比如个体之间的朋友关系啪3 ，家族之间的联姻关系啪1 ， 公司之间的商务关系n 以船喵】。传统的社会网络研究往往存在这样一些问题：不够 准确、主观性强、而且研究对象也不具有普遍意义或者研究样本规模较小。鉴于 这些问题，许多学者已经开始借助于其它方法来研究社会网络，比如应用现有的 一些数据库来研究演员合作网络啼一m 1 、公司董事关系瞰4 1 删以及科研作者合作 网络溉删。电话与嘶5 7 1 电子邮件联系网络以及b b s 回复网络旧3 在近些年也被 一些学者所研究。应用复杂网络理论可以探索导致网络不稳定的因素，从而保护 网络安全，对诸如网络病毒脚一妇和人类的疾病传播泐洲5 1 等会起到很大程度的积 极作用，k e m a c k 和m c k e n d i r c k 魄1 提出的著名的s i r 和s i s 模型非常有助于研究病 毒传播原理及如何预防与控制病毒传播。 二、信息网络 信息网络，或称为知识网络。最典型的例子就是学术论文引用网络口3 一1 ， 如果两篇论文之间存在引用关系，则视这两篇论文之间有边连接，引用网络的结 构反映了节点的信息存储结构。此种网络中是不存在环的，因为某篇文章只可能 引用已经完成的文章，而不可能去引用还未完成的文章。通过科学引文网络可以 分析出科研热点问题以及科研发展趋势。另外一个典型例子就是万维网幻，万 维网是网页之间的超链接联系m 1 ，它与i n t e m e t 并不相同，后者是由光纤和数据连 接起来的计算机网络，但万维网可以是循环的，这一点又不同于科学引文网络。 三、技术网络 技术网络是一类人造网络，是人们设计出来的流通资源或商品的分布式网 络。电力网络晒瑚，埘是很好的典型例子。其它分布网络包括航空网络汹7 5 】、高速 公路网纠硎、铁路网络口7 、删，河流网络口蛾3 以及i n t c m e t 网络汹删。这些技术网络 的性质都或多或少的受空间或地理因素的影响。技术网络的可靠性是与人类的生 活息息相关的。电力网络与航空网络的崩溃睇1 等都会给人类的生活带来大麻烦， 我们可通过复杂网络理论研究技术网络中节点的最优分布，网络鲁棒性以及网络 效率等问题，并可以对其进行优化、改变结构，以提高网络功能，使相关事故不 再重演。 四、金融网络 基于复杂网络的金融市场研究近些年受到了一定的关注，m a n t e g n a 阻力于1 9 9 9 年首次运用股票价格之间的相关性构建了一类复杂网络，并结合最小生成树分析 法探讨了金融市场中公司间投资组合层级结构问题。其后，耶b 6 l y 抽u 、b o g i n s k i 、 k i m 2 刀、b o n a n i l o 、k i m 削、o n n e l a 蚓等人在此类复杂网络上进行了深入探讨。 k y o u n ge u nl e e 等乜刚以韩国证券市场股票价格之间的相关性构造了相应的复杂 4 第一章绪论 网络，并依据股票价格相关系数提出了阀值的概念，由阀值的大小来调节网络的 规模，当此阀值处于0 4 至0 6 之间时，所构造的网络即具有无标度特性。c h e o l j u n e o m 等呻3 于2 0 0 7 年提出了股票网络形成过程中的决定性因素。在国内，李平、 汪秉宏等嘲3 以香港股票市场恒生指数波动类型为基础构造了一类加权证券指数 网络，并提出了两种运算法则来确定此类网络拓扑结构中的重要节点，以此来获 取恒生指数隐含的重要波动类型。万阳松等嘲1 以我国沪市股票价格为基础分析了 股票价格波动间的影响强度方面的无标度特性。 五、语言网络 相比上述网络，语言网络一直没有受到太多的关注。r a m o nf e r r e r ic a n c h 0 1 与鼬c a r dv s o l 6 旧于2 0 0 1 年首先对语言网络进行了研究，他们将英文单词看作 顶点，如果任意两个英文单词出现在一篇文章中的同一句话里面，即视为这两个 英文单词之间有联系，这种联系用边来定义，这样就构成了一个网络。在这种网 络中，两个单词之间的平均距离在2 3 之间，顶点度分布服从幂律分布。同年， d o r o g o v t s “与m e n d e s 胁1 指出可以将语言看作是不断进化的自组织网络，词汇网 络顶点度分布符合截断式幂律分布并取决于网络的演化。之后，a l l e g r i n i 等阳3 1 从 统计力学角度出发应用时间序列分析方法探讨了人类语言网络的复杂性。 s t e w e r s 嗍，m o t t e r 饽钉，s o a r e s 嘲，李勇9 7 1 ，韩莹卿等人分别对语义网络、词语 概念网络、葡萄牙语言音节网络、汉字词组网络、汉字偏旁字符组合复杂网络进 行了研究，结果表现为上述网络均具有小世界特性，网络顶点度分布符合幂律分 布形式。b a l e s 与m a r k 0 o v 矗n 删分别对大型语义网络与词汇增长网络的特性进行 了研究。 六、生物网络 生物网络研究涵盖范围较广，从对生命体本身，比如新陈代谢网络啼3 1 0 1 q 吲、 遗传调节网络n 0 7 “峨蚓、核糖体r n a 网络n 埘以及蛋白质网络n 1 1 n 对，再到生物之 间的捕食关系，即食物链网络m 3 伽1 。对生命意义的探讨是我们永恒的追求，生 命体内的复杂系统的结构和功能是科学家们梦寐以求要解决的问题，但目前基于 复杂网络的生物网络研究工作主要集中于探讨网络拓扑特性方面。 1 1 2 复杂网络的分类 对于复杂网络，我们可以从多个角度对其进行分类： 第一，按照网络中节点之间相互作用的方向性，可以将网络分为无向网络和 有向网络，有向网络中的连边可以是单向的，也可以是双向的。例如演员合作网 络和科学家合作网络均可看作无向网络，而万维网、科学引文网络和食物链网络 则是有向网络； 天津大学博士研究生毕业学位论文 第二，按照节点之间的作用强度或者网络中连边上的信息量大小不同，可以 将网络分为无权网络和加权网络。人际关系网络可以看为是加权网络，关系的远 近或者说熟悉程度可以被定义为不同的权值，对于交通网络来说，如果仅考虑地 理上的连接，则交通网络为无权网络，若考虑交通网络上的交通量，则可视其为 加权网络； 第三，按照网络拓扑特征，可以分为规则网络，随机网络，小世界网络以及 无标度网络，这将在下文中进行详细分析，现实世界中的网络，既不完全规则， 也不完全随机，更多的是呈现出小世界或者无标度的性质； 第四，我们还可以按照网络中的节点与边有无特定地理位置将复杂网络分为 非空间网络与空间网络，一些网络的节点与边在网络空间中没有特定位置，因此 只能研究其拓扑特性，诸如度、特征路径长度、直径，聚集系数，介数等，这些 网络的代表包括w w w ，合作网络和食物链网络等。而其他一些网络，尤其是交 通运输网络，其中的节点和连边在地理空间中有固定的位置，因此仅研究其拓扑 结构是不够的，我们必须还要在地理或空间限制的情况下探讨其特性以及对其优 化的问题。 现实世界中的网络并不会严格被归于上述哪一类，有时某种网络可以分属于 不同类网络，例如交通网络即可以属于空间网络又属于无向网络，还可以属于加 权网络。 。 1 2 交通网络研究概况 虽然对于空间网络的研究有着几十年的历史n 2 卜1 2 3 1 ，但是最近才逐渐受到重 视n 洲制，然而重视程度还是远远不及非空间网络。当网络中的节点与边有特殊 的地理位置的时候，影响网络功能的就不只是网络的拓扑特性了，因为即使不同 的空间网络拓扑特性一致，其功能也是大不相同的。比如输油管道、污水处理系 统、i n t e m e t 中的光学纤维以及商业设施等，均属于空间网络，如何对这些网络进 行合理规划也对城市建设起着非常重要的作用。 g a s 协c r 和n e w m a n n 州蜘研究了空间分布网络的形状与效率及其最优化设 计，考虑了连接设施的策略来构建空间网络。在他们的研究工作中以美国为例演 示了这种优化网络的特殊的例子以及空间分布网络生长过程中的形态与效率。他 们主要瞄准网络的成本，以及在网络中点对点直接路线方面的效率。网络成本由 网络中所有边的总长度来代表，依据几个真实世界网络的数据，他们提出了两个 网络增长模型来生成最优网络结构。 交通网络属于一类空间网络，其中的节点与连边都对应于特殊的地理位置， 6 第一章绪论 因此对于这类网络光研究其拓扑特性是不够的，还要探讨它们在地理条件限制情 况下的空间特性。严格来说，高速公路网络、铁路网络、城市公交网络、地铁网 络均属于此类网络，而航空网络与航海网络由于其类似于直线的长程连接，则更 多研究的是它们的拓扑特性。下面本文将按照交通网络研究成熟度从强到弱来分 述此领域的主要研究进展。 1 2 1 城市公交网络 2 0 0 5 年，s i e n k i e w i c z 与h o l y s t n 伽研究了波兰2 2 个城市的公共交通网络，分 析了度、特征路径、聚集系数、网络聚类和介数等网络拓扑特性，他们发现尽管 这2 2 个城市的公交网络尺寸有很大的不同( 节点数目从1 5 2 到2 8 8 1 ) ，但它们 却在度分布、特征路径长度分布等特性上存在一些共性，比如度分布遵从幂率或 指数分布，而且所有网络均呈现出了小世界特性。l 酋m m e r 1 蚓等人分析了德国2 0 个最大的城市的公路网络，他们指出当人们主要考虑旅行时间而非路途距离时， 快速路就显得比慢速路要短些，并且发现交通流仅集中于公路的一部分，公路上 的车流分布遵从幂律形式，这意味着公路存在等级次序。 在国内，很多学者对北京和上海等城市公交网络做了大量的研究工作。赵金 山等n 删提出北京市公交网络度分布为指数分布，指出了其不完善之处并提出了 进一步的改进思路；高自有等n 伽测算出北京公交网络具有无标度性质；张鑫等n 删 发现北京公交网络具有小世界现象；张一n 例以二分图为基础验证了北京公交网 络小世界的性质。上述结论并不矛盾，有时候复杂网络节点的无标度分布与指数 分布在网络节点个数不是巨量的前提下，并不好分辨。李英等n 刚提出上海公交 网络具有无标度特性，张晨等u 5 1 1 计算了上海公交网络的累积度分布，发现其具 有随机特性并符合指数分布。顾前等n 剜通过s p a c el 和s p a c ep 方法研究了北京、 上海和杭州3 大城市的公共交通网络特性，发现3 个城市的公交网络均具有较小 的平均路径长度，即具有典型的小世界特征。其节点的度分布，在s p a c el 方法 的描述下具有无标度特性，在s p a c ep 方法的描述下具有指数分布特性。他们通 过对s p a c el 和s p a c ep 两种描述方法的比较，还发现对于同样的公交网络，应 用s p a c ep 方法描述的网络具有更大的聚集系数和更小的平均路径长度，即具有 更强的小世界效应。惠伟等n 嘲以上海、北京等城市的公交线路的部分站点和路 线为例，分别从公交停靠站点网络、公交换乘网络和公交线路网络角度总结了城 市公交网络的复杂特性。对复杂网络的静态特征值如平均路径长度、聚集系数、 节点度分布等方面进行了统计，发现北京和上海的公交网络具有小世界特性，度 分布都符合指数分布，北京和上海居民外出的平均换乘次数分别为1 5 4 次和1 9 次。 天津大学博士研究生毕业学位论文 1 2 2 航空网络 除城市公交网络外，航空网络也是交通网络中的研究热点。m i c h e l eg u i d a 等口朝研究了意大利航空网络并分析了其拓扑性质，结论如下：发现意大利航空 网络度分布和介数向心性分布都遵从幂率分布，即意大利航空网络呈现出了无标 度特性，而且网络中有集散节点，也就是所谓的h u b ；通过详细分析数据，指 出意大利航空网络还显示出了自相似的结构，也就是说，意大利航空网络具有分 形特性，它的特征维数可以很容易由幂律标度指数决定；他们还认为意大利航 空网络可以被归为小世界网络，因为网络中可达节点对之间的距离随机场的个数 呈对数增长；意大利航空网络并没有呈现出社团特性，这个结果也许是其聚集 系数小的潜在原因。r g u i m e r 等n 蚓分析了世界航空网络的全局结构，发现世界 航空网络是具有无标度特性的小世界网络，而且与经典的无标度网络模型对比来 看，拥有航线最多的城市并不是最重要的中心城市，而这种现象是由于网络的多 社团结构特性造成的。g e 礓a n ab o u n o v a 等n 5 印研究了中国国内2 0 家最大的航空公 司的航空网络空间分布形式，分析了它们的度、边集、边介数分布、聚集系数和 网络直径，发现整个中国国内航空网络不具有无标度特性，呈现出的是小世界特 性。他们比较了上述航空网络的鲁棒性，发现一些小的航线网络具有很好的鲁棒 性。 在国内，刘宏鲲、周涛二人n 矧对中国城市航空网络进行了实证研究与分析， 以城市为节点，城市间直航线路为边，结果表明中国城市航空网络具有较小的特 征路径长度和较大的聚集系数，且其度分布服从双段幂律分布，因此网络呈现出 小世界性质。王茹n 刚等从有向和演化的角度分析了美国航空网络，指出美国航 空网络是一个层级网络，池丽萍等人n 删从有向加权和演化的角度分析了美国航 空网络，计算出网络的聚集系数为o 6 1 8 ，这比同等规模的随机网络的聚集系数 ( 0 0 6 5 ) 要大很多。通过数据分析，他们发现美国航空网络度分布服从两段幂 律分布。 1 2 3 铁路网络 p a r o n 2 a m as e n 等n 的3 提出了印度铁路网络具有小世界性质。w l i 等n 删分析了 中国铁路网络，发现其特征路径长度为3 5 ，聚集系数高达o 8 3 5 ，因此中国铁 路网络呈现出明显的小世界特性，此外，网络度分布也遵从幂律分布。k u r a n t 和1 1 1 i r a n n 6 1 3 在他们的文章中提出了一个法则，从公众运输系统的时间表上提取真 实的自然拓扑和交通流网络，它们将此法则应用于三种大型的运输网络，其中之 一是瑞士铁路网络，发现其度分布在双对数坐标下有大部分呈现出了无标度特 第一章绪论 性。 文献 1 6 2 提出中国铁路客运系统可以采用两种不同的网络构建方式来描 述。一种是以铁路的站点作为“节点 ，并以轨道作为“边”，这样生成的网络称 为铁路地理网。统计显示该网络的平均聚集系数c 近似为零，故该网络为树状网 络。另一种是以站点作为“节点”，任意两个站点间只要有同一列车在这两个站 点停靠，就可以认为这两个站点间有连线，这样生成的网络称为车流网。统计显示 该网络有较大的平均聚集系数和较小的平均网络距离z ，而且该网络节点的度分 布基本上服从无标度幂律分布，故车流网为具有无标度性质的小世界网络。 1 2 4 地铁网络 目前对于地铁网络的研究还不多，l a t o r a 口刀分析了波士顿地铁的拓扑特征， 并定义了网络效率等于两节点之间距离的倒数，最后提出小世界特性是地铁网络 的建造法则。a n g e l o u d i s 1 矧提出地铁网络既不具有小世界特征也不具有无标度特 征，并建立了一个模型来分析其研究的地铁网络是否属于同一类。k e u m s o o k 1 叫等 人分析了首尔地铁网络特性，并从客流量角度分析了地铁网络的最大生成树。 2 0 0 7 年，t a k a h i r om a j i m a u 删等对日本五种交通网络进行了分析研究，一个铁路 网络，三个地铁网络和一个水上公共汽车网络，文章主要探讨了寻找一个优化法 则来对这些网络进行优化以减少交通拥塞以及在灾难情况下增加运输系统冗余。 1 2 5 交通网络综合研究 g a s m e r u 删在其研究中指出交通网络模式首先取决于用户在网络中行走的短 边偏好以及建造必须连接的空间约束，研究发现在最小总维护成本的情况下，网 络中一小部分连边承担着巨大的交通量。z e n g w a n gx u 和d a n i e lz s u i n 6 7 1 从网 络自相关角度提出了空间网络的小世界特性的检验方法，并应用这种方法分析了 国家、首都、内城三种交通网络，研究结果发现当相关延迟距离达到某一特定阀 值时，空间网络在这三种尺度上即出现小世界现象，这意味着小世界现象来源于 网络结构和网络上发生的动力学之间的相互作用。 1 3 论文选题背景 网络的表征遍及许多自然系统和人造系统。近期的很多研究都表明有相当数 量的复杂系统并不是随机的混沌结构，而是有效的复杂结构。目前的研究大多数 集中于非空间网络。然而，在现实世界的网络中，还存在着空间网络，此类网络 天津大学博士研究生毕业学位论文 中，节点与边的地理位置以及连边的距离都影响着网络的结构与功能。 交通网络是空间网络中最具有代表性的一类。对于交通网络的研究最近几年 才兴起，因此在这个领域有很多未知值得我们去研究。通过本文上一节的介绍可 以看出，对于交通网络的研究以国外学者居多，国内学者的主要研究方向集中于 城市公交网络与航空网络。 交通运输业的发展为我国的经济发展和社会进步做出了巨大贡献，随着交通 网络的蓬勃发展，一系列的问题也逐渐凸现甚至激化。如何继续发展并完善交通 网络布局，促进交通网络发展与经济增长的互动是我们所亟待解决的问题。 莫辉辉等n 嘲通过分析复杂网络理论在航空、轨道交通( 地铁和铁路) 、城市 交通( 公交和道路) 等中的应用，指出系统复杂性是交通运输网络复杂性的根源， 以及复杂网络分析方法中忽视地理空间性所引起的问题，即一般性地认为交通运 输网络为小世界网络或无标度网络。目前基于统计物理学的交通运输网络的复杂 性研究多为拓扑化的理论分析或数据建模，与实际网络结构特征及动力学机理仍 存在较大差距。研究进一步指出，交通运输网络由需求网络、组织网络、径路网 络和设施网络四种网络结构组成，是一类具有“开放性”复杂系统的网络化复合 结构。交通运输作为一门实践应用性较强的学科，应围绕“理论一模型与方法一 实践模式前向性循环推进。综合分析复杂网络的理论与实践情况，提出未来交 通运输网络的复杂性研究的主要内容：对交通运输系统的网络结构复杂性的基 础认识；以地理空间特性为基础的网络复杂性分析；基于组织与效率的网络 结构复杂性分析及应用；相互作用产生的各种流与网络结构的互动关系；网 络局域结构特征及对广域结构的影响；系统开放性对网络演化的影响。 本文正是基于上述思路，主要分析了城市地铁网络与国家高速公路网络的空 间特性、鲁棒性与脆弱性，并应用遗传算法提出了对高速公路网络进行优化的方 法，力求从地理空间特性方面更加贴近实际地探索交通网络结构与功能，并综合 考虑交通运输网络投资方与使用方的利益平衡以提出理想的交通网络布局模型。 1 4 论文的主要工作与内容安排 1 4 1 论文主要工作及创新点 l 、度分布是复杂网络研究的一个重要统计特征，目前研究表明复杂网络度 分布符合以下四种情况：泊松分布、幂律分布、指数分布和指数截断分布“一州7 2 3 。 本文通过大量的数据分析与计算机仿真模拟，发现随机复杂网络度分布曲线的峰 值不一定与平均度值点相对应，而且其度分布曲线也不全都符合p o i s s o n 分布， 第一章绪论 - f 生丑、ff 蔓生、 并且发现了一类度分布符合形如p ( 砖) 2 喁p h + 锡p 。恐的复杂网络，通过 进一步对实例的验证统计分析，发现中国铁路网络，世界部分国家高速公路网络、 _ l 蚓j l 巡 部分主要大都市地铁网络度分布均符合p ( 岛) 2 p 。五。+ 呸p 。施形式； 2 、对部分世界主要城市地铁网络进行了综合对比统计分析，包括北京、波 士顿、华盛顿、洛杉矶、纽约、上海、圣弗兰西斯科、香港、新加坡与亚特兰大 地铁网络，发现它们拥有如下共性：倾向于选择短边、平均度数接近于2 、聚集 系数接近于o ，直径较大。将上述城市地铁网络与同等规模随机网络和最小生成 树网络进行对比分析，发现城市地铁网络与大部分具有小世界特性或无标度特性 的真实网络不同，它们具有类似最小生成树样的结构。之后以北京地铁网络为例 分析了其鲁棒性与抗毁性，发现其在节点随机故障情况下具有较好的鲁棒性，但 在恶意攻击情况下整个网络非常脆弱； 3 、对世界部分国家高速公路网络进行了综合对比分析，包括中国、美国、 印度、澳大利亚、巴基斯坦、缅甸、斯里兰卡和德国，发现它们具有如下相同特 征：倾向于选择短边、一平均度数小于4 、小的聚集系数与大的直径。之后从此类 网络的空间地理特性对这些网络拓扑特征的成因进行了分析，结果表明高速公路 网络是2 维系统。 4 、以中国高速公路网络为例，从节点随机故障、基于节点度值降序次序的 恶意攻击与节点介数降序次序的恶意攻击三个方面分析了其鲁棒性与抗毁性，在 考查网络鲁棒性与抗毁性时，在传统的两个考查指标最大连通子图和网络特 征路径长度的基础上增加了网络直径演变趋势指标，发现其演化趋势与特征路径 长度演变趋势一样，研究结果表明采用动态节点介数降序次序攻击的方式对网络 的攻击性最强，并且演示了中国高速公路网络在节点遭受恶意攻击下的动力学演 化过程； 5 、传统的路网布局规划模型仅讨论了节点的选取与高速公路通道数量；本 文对其进行了改进，改进后的模型增加了对路网网络特性的考虑，增加了对节点 度值与聚集系数值的限制条件，更贴近于实际需求。之后结合复杂网络与经济学 理论，从成本收益分析的角度对路网布局优化模型进行了改进，平衡考虑了路网 运营的成本与收入，最后主要应用遗传算法对路网进行了优化，并通过j a 、，a 语 言实现，优化后的路网在抗毁能力方面有了一定的提高。 天津大学博士研究生毕业学位论文 1 4 2 论文章节安排 本文共分七章，简述各章内容如下： 第一章首先简要综述了复杂网络的发展过程、研究的内容与方向以及研究意