（交通运输规划与管理专业论文）基于复杂网络理论的快捷货运网络拓扑结构研究.pdf

中文摘要 随着经济不断发展，货运需求规模不断扩大，社会对货物运输网络的时效性、 便捷性和安全性等也提出了越来越高的要求，因此快捷货物运输网络结构的设计 与优化得到了越来越多的重视，并随着综合运输体系的逐步形成而不断发展和完 善。利用网络优化模型，对快捷货运网络拓扑结构进行理论分析和算例验证，有 助于快捷货运网络的长期规划，同时对提高国民经济效益具有重要的意义。 本文应用复杂网络理论，从数学拓扑和物理网络结构角度出发，对不同网络 模型的形成、演化和特点做了简要的概述，并在此基础上对快捷货运网络的定义、 特点、统计测度属性以及与快捷货运网络拓扑结构相关的影响因素一一做了阐述 和分析。 结合复杂网络的统计属性和运输网络自身所具有的特征，对典型的快捷货运 网络结构进行比较分析也是本文的重要内容之一。点对点式货运网络和轮辐式货 运网络都有明显的结构特征和功能特性，其背后所反映的经济效益和社会效应也 各自不同。 在比较结果的基础上，选择轮辐式网络结构进行进一步的结构优化和论证， 是本文的核心内容。以提高货运网络的时效性、便捷性、沟通性和安全性为目标， 利用小世界模型和改进的b a 无标度网络演化模型，利用节点演化算例对模型进行 了验证和分析，建立具有“核心节点、中心节点、周围节点 的层次型快捷货运 网络结构，是本部分的主要研究工作。最后对集装箱快捷货运网络拓扑结构的演 化进行了分析和研究。 关键词：快捷货运；网络拓扑结构；复杂网络：小世界网络；b a 模型 分类号：u 1 1 3 a b s t r a c t w i t ht h ei n c r e a s i n gd e v e l o p m e n to fe c o n o m i c s ，t h es c a l eo ff r e i g h td e m a n d s b u m p su p ，a n ds ot h es o c i e t yc a l l sf o rm o r eh i g h e rd e t a i lr e q u i r e m e n t sf o rt h e e f f i c i e n c y 、c o n v e n i e n c ea n ds e c u r i t y s om o r ea n dm o r ea t t e n t i o ni sb e i n gp a i dt ot h e d e s i g na n do p t i m i z a t i o nf o rt h ef r e i g h te x p r e s st r a n s p o r t a t i o nn e t w o r k ，a n dt h en e t w o r k b e c o m e sm o r ep e r f e c td a yb yd a yw i t ht h ec o m p o s i n ga n dd e v e l o p m e n to fi n t e g r a t e d t r a n s p o r t a t i o ns y s t e m b a s e do nt h em o d e lo fn e t w o r ko p t i m i z a t i o n ，d o i n gt h e o r y a n a l y s i sa n de x a m p l ev a l i d a t i o no ft h en e t w o r kt o p o l o g ys t r u c t u r ew o u l dh e l pf o rt h e l o n gt e r mp l a n n i n go ft h ef r e i g h tt r a n s p o r t a t i o nn e t w o r k ；a n di t i so ff a rr e a c h i n g i m p o r t a n c ef o rt h en a t i o n a le c o n o m i ce f f e c t i v e n e s s m a k i n gf u l lu s eo ft h ec o m p l e xn e t w o r kt h e o r y , t h i sp a p e rs u m m a r i z e st h ef o r m 、 e v o l v e m e n ta n dc h a r a c t e r i s t i c so fn e t w o r km o d e lf r o mt h ev i e wo fm a t h e m a t i c sa n d p h y s i c s b a s e do nt h e s ep o i n t s ，t h ee x p r e s sf r e i g h tt r a n s p o r t a t i o nn e t w o r k sd e f i n i t i o n 、 c h a r a c t e r i s t i c s 、a t t r i b u t e so fs t a t i s t i c a lm e a s u r e m e n ta n dt h ee x t r ac o n t r i b u t i n gf a c t o r s a r es u m m a r i z e da n da n a l y z e di nd e t a i l a ni m p o r t a n tp a r to ft h i sp a p e ri st oc o m p a r i n ga n da n a l y z i n gt h et y p i c a lf r e i g h t t r a n s p o r t a t i o nn e t w o r kc o m b i n i n gw i t ht h es t a t i s t i c a la t t r i b u t e so ft h ec o m p l e xn e t w o r k a n dt r a n s p o r t a t i o nn e t w o r ki t s e l f b o t ht h ep o i n t - t o p o i n tn e t w o r ka n dh u b - a n d - - s p o k e n e t w o r kh a v et h e i ro w no b v i o u sc h a r a c t e r i s t i c si ns t r u c t u r ea n df u n c t i o n a n dt h e i r r e f l e c t i o no fs o c i e t ya n de c o n o m i ce f f i c i e n c ya l s od i f f e r sf r o me a c ho t h e r o nt h eb a s eo ft h ec o m p a r i s o nr e s u l ta b o v e ，w ec h o o s et h eh u b a n d s p o k e n e t w o r kf o rt h ef o l l o w i n go p t i m i z a t i o na n dv a l i d a t i o n ，a n dt h i si st h ek e yp a r to ft h e p a p e r t h em a i nr e s e a r c hw o r ka r ed o n ea sf o l l o w s ：d e m o n s t r a t i n gt h es m a l l - w o r l d n e t w o r km o d e l ，i m p r o v et h eb as c a l e - f r e en e t w o r km o d e l ，b u i l d i n gah i e r a r c h i c a l f r e i g h tt r a n s p o r t a t i o nn e t w o r ko w i n g “k e yn o d e ，c e n t r a ln o d e sa n dr o u n d i n gn o d e s ”，s o t h a tw ec a ni m p r o v et h e e f f i c i e n c y 、c o n v e n i e n c e 、a c c e s s i b i l i t ya n ds e c u r i t y c o n s t r u c t i n ga ne x a m p l en e t w o r kt ov a l i d a t et h em o d a li sp a r to ft h ew o r k a p p l y i n g t h ea d v a n c e db am o d a lo fe v o l v e m e n tt ot h et o p o l o g yn e t w o r ko fc o n t a i n e re x p r e s s f r e i g h tt r a n s p o r t ，t h en e t w o r ka n dt h er e s u l ti sa n a l y z e da tl a s t k e y w o r d s e x p r e s sf r e i g h tt r a n s p o r t a t i o nn e t w o r k ；n e t w o r kt o p o l o g ys t r u c t u r e ； c o m p l e xn e t w o r k ；s m a l l - w o r l dn e t w o r k ；b as c a l e - f r e en e t w o r k c i 。a s s n o ：iy 1 1 3 图目录 图1 1 论文框架图6 图2 1 城市航空网络7 图2 2 形状不同而本质相同的图8 图2 3 规则网络1 l 图2 4 随机网络1 2 图2 5 小世界网络1 2 图2 - 6 无标度网络13 图2 7 快捷货运系统1 4 图2 8p o i s s o n 分布和幂律度分布17 图2 - 9 均匀网络的s i s 模型相位图18 图3 1 快运网络空间示意图2 2 图3 2 联运枢纽与快捷货运枢纽2 3 图3 3 快捷联运时空网络图2 4 图3 4 点对点式网络2 5 图3 5 轮辐式网络2 6 图3 - 6 单枢纽轮辐式网络2 8 图3 7 多枢纽轮辐式网络2 8 图4 1 捷径数相同而结构不同的网络3 3 图4 2 分布在单位圆上的个节点网络3 4 图4 3 计算结果3 6 图4 4l 与三的比较3 7 图4 5b a 无标度网络演化4 0 图4 6 层次网络结构4 3 图4 7s i e r p i n s k i 三角形4 3 图4 8 网络演化。4 5 图5 1 集装箱快运网络结构4 8 图5 2 全国区域布局4 9 图5 3 初始状态5 0 图5 3 演化矩阵51 图5 4 网络演化最终拓扑结构5 l 图5 5 节点度分布5 3 图5 - 6 东北与华北区域5 4 图5 7 华东与华中区域5 5 图5 8 西南与西北区域5 5 表目录 表2 1 经济总量与货运量变化1 9 表2 2 货运线路变化19 表2 3 我国各产业占国内生产总值的份额2 l 表2 4 不通运输方式的货物产品对象2 1 表3 1 典型网络结构的效率和可靠性指标3 0 表4 1 随机网络、规则网络、小世界网络特性比较3 2 表4 2 增加1 个节点时各参数值变化4 5 表4 3 增加至2 0 个节点时各参数值变化4 6 表5 1 各区域城市站点5 0 表5 2 节点演化参数5 2 表5 3 集装箱办理站分布5 4 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果除了文中特别加以标注和致谢之处外论文中不包含其他人已经发表或撰 写过的研究成果也不包含为获得北京交通大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示了谢意。 学位做储躲甜勺签字胁叩年编脚 6 7 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名衲 签字r 期：7 1 年r 月( c ，e i 导师签名： i 狮也韦 签字胁v 芦汐钿吵日 致谢 本论文的工作是在我的导师何世伟教授的悉心指导下完成的，何教授严谨的 治学态度和科学的工作方法给了我极大的帮助和影响。在攻读硕士学位期间，由 于自己的跨专业背景，所以一直心存担忧和紧张，对专业的科学把握没有足够大 的信心。但导师对我一直不倦的谆谆教诲和关怀鼓励，给了我学习工作上莫大的 信心和动力。导师不仅传授专业知识、科研方法，还教会我做人的准则和生活的 态度。由于导师的关切与安排，使我能够参与诸多科研实践活动，并能到车站现 场等学习和实践，不仅加深了交通理论与实践的结合，弥补了我很多专业上的不 足，还让我领悟到实际工作与科研学习之间的共同点和差异，使自己在随后的学 习中学会了更全面、更科学的思考和探索；同时也为今后即将面临的工作做出了 极具价值的参考。在这两年学习期间，我所取得的每一点进步、每一份成绩都包 含着导师无微不至的关怀、鼓励和引导。师恩深如海，再次向导师何世伟教授表 示最衷心的感谢。 研究生学习阶段还得到了宋瑞教授的大力指导和帮助。老师对学术的严谨和 对学生的严格要求使我积极完成学习、科研和论文工作；在生活上宋老师也总是 不忘给予关心和支持。在此表示深深的感激。 感谢王保华、许旺土、申永生师兄对我在学习上的帮助，感谢黎浩东博士在 我论文撰写期间给予的耐心指导；感谢同窗王炜、张戬、权磊磊、郑德署，一起 学习研究、交流探讨的工作和生活给我留下了珍贵的友谊和回忆：对郑锂、刘江 涛等师弟师妹在本人论文修改期间给予的便利和帮助在此也一并表示诚挚谢意。 感谢我的父母和两个姐姐，他们的无私与关爱让我在近二十年来求学生涯中 始终享受着最温馨的亲情；他们的辛苦与期盼是我坚持不断努力奋斗的源泉；他 们的理解和支持是支撑我专心完成学业的最坚强后盾。 最后，向百忙之中审阅本论文的老师们致敬并表示感谢! 1绪论 1 1 研究背景及意义 货物运输是社会经济的关键组成部分，是指借助四通八达的运输网络和不同 功能、形式的交通工具，通过确保原材料和成品的有效移动和及时获取，以有效 支持产品的生产、交换以及消费活动，从而为发展生产、方便生活、沟通城乡、 繁荣社会经济文化服务。但货运交通系统功能的发挥却受到货运网络结构的支配， 合理的运输网络结构是货物运输功能正常发挥的基础和前提。随着经济的不断发 展和地区经济环境的变化，货运需求不断变化，货运供需矛盾紧张、网络分配不 均衡、运输效率低、运输安全威胁扩散等一系列问题也在日益加重，使得货物运 输和经济发展受到严重制约。为了解决这一问题，交通领域的学者们进行了各种 各样的尝试和探索，以提高和保障货物运输的快速性、便捷性和可靠性。 网络拓扑结构与其自身的功能有着密切的关系，研究网络拓扑结构，有助于 理解网络结构和网络行为之间的关系；通过对网络特征的把握，优化网络结构， 改善网络性能，从而对网络规划工作和网络管理工作提供更有效、更可靠的理论 基础。 快捷货运网络是在交通运输网络的基础上定义和发展而来的，是货物运输需 求网络、组织网络和径路网络的综合，是一个巨大而又复杂的系统。其网络结构 的特点是运输系统建设、组织和运营的直接反映，决定着货运系统的运输效益， 对国民经济产生重要的影响。 我国快捷货运网络建设仍在起步阶段，网络建设规模随着社会经济的快速发 展而不断扩大，基于物理网络结构之上的服务网络也处于不断研究和改进中。我 国由于特殊的地域差异，运输需求变化大，网络自身结构复杂，全局运输效率提 高慢，运输服务质量尤其在快捷性和安全性上难以得到有效保证。我国综合交通 运输体系建设虽然已取得重大成就，综合运输体系下的货物运输网络也发展迅速， 但与发展目标相比还有很大差距，如：运输资源配置不够合理；各种运输方式发 展不平衡，运输结构有待调整；综合交通体系建设缺乏系统规划理论指导和强有 力的统一决策协调，造成交通网络区域布局不平衡等。这些都是快捷货运网络结 构发展和演变的决定性因素。 复杂网络的研究从上个世纪末至今，已经取得可人的成果，并已成为当前复 杂性科学、系统科学等多个学科共同研究的热点。其研究内容涉及图论、统计物 理、计算机、生态学、社会学、经济学以及交通科学等诸多领域。复杂网络理论 无论从网络的拓扑结构、形成机制，还是网络的演化规律、统计方法等，都能给 综合运输体系下的快捷货运网络拓扑结构的研究以很好的启迪。本文将复杂网络 理论的研究和快速货运网络有效地结合，以研究快捷货运网络拓扑结构的问题。 如何利用复杂网络理论来分析和评价网络拓扑结构的优劣和适宜程度? 快捷 货运网络拓扑结构的形成和发展都有哪些影响因素? 什么样的网络拓扑结构适宜 快捷货运网络的建设与可持续发展? 如何在典型网络的基础上进一步优化以实现 快捷货运的多目标特性和整体效益? 这些问题的研究与探讨将对我国快捷货运网 络的规划建设及可持续发展提供有意义的理论参考。 1 2 国内外研究现状 我国综合运输体系的发展已经初具规模和成效，快捷货运也在迅速起步和发 展，快捷货运网络正在初步形成，网络规模逐渐扩大。关于综合运输的研究较多 集中在指导性、方向性等宏观层面上，微观的理论研究较少；快捷货运方面关于 铁路行包运输和邮政快递方面有部分文献，但关于综合运输体系下的快捷货运服 务网络研究，目前还没有深入的涉及。胡思继【l 】从客货运两个方面出发，结合运输 工程与经济的发展关系，分别阐述了我国公路、铁路、水运、航空、管道的运输 管理概况，并对彼此结合的综合运输工程做了较为全面的分析和阐述。彭辉的博 士论文【2 】阐述了综合运输系统的形成和发展过程，并对综合运输与社会经济系统的 关系、综合运输系统的需求、构成要素、功能结构、运行及效果等都做了详细的 分析。王志强【3 】贝0 从运输需求、运营设施、运营组织、高速公路网络配置、信息服 务网络、场站建设、管理手段、政策研究等方面对高速公路货运服务体系做了系 统的论述。文献 4 探讨了公路快速货运的经营模式，提出经营公路快速货运应走 网络化、规模化道路的观点，指出企业集团是目前经营公路快速货运的一种较好 模式。文献【5 】从现代物流理论角度出发对公路快速货物运输组织做了探讨。李德 刚【6 】、贾倩【7 1 、乔涛【8 】等分别对综合运输网络中的通道分析和系统配置研究、枢纽 布局规划研究、网络平衡研究做了详细的工作。文献 9 】、【1 0 1 对交通网络一体化研 究做了初步探讨。杨浩【1 3 】阐述了我国铁路快速货运的发展现状和展望；余少鹤【1 4 】 则提出应加强编组站在铁路快速货运中的地位与功能。 文献 1 1 】、 1 2 从微观层面上研究了交通网络中最短路径算法与实现问题。文 献 1 5 】详尽介绍了动态随机交通网络中的模型与求解应用。刘灿齐【l6 】分类介绍了交 通设计问题的常用模型及算法；刘培玉、刘法胜【i7 】将网络最大流问题推广为交通 网络用户平衡环境下的最大流问题，给出了交通u e 条件下两点间最大交通流量的 2 双层规划模型和算法，进而讨论了整个交通网络基于线性增长模型的交通量问题。 文献 1 8 较系统地阐述了交通运输网络规划的评价问题，从评价的目的、内容、方 法和特点出发，讨论了交通运输网络规划的技术评价、经济评价、社会评价和综 合评价的方法。 国外对货运网络设计的研究比较广泛和深入。t e o d o rg a b r i e lc r a i n i c t l 9 】对网络 设计和服务网络设计的模型以及相应的数学规划模型做了简单回顾，并对网络设 计问题提出一种新的分类方法。f r a n ks o u t h w o r t h 和b r u c ee p e t e r s o n t z o 】利用g i s 和路径选择技术对国际多式联运建模问题做了相关探讨。麻省理工学院的d a e k i k i m 2 l 】对大型货运服务网络设计问题进行建模、算法实现和应用，重点研究了行包 快运服务网络设计问题( e p s n d ) 。s us h e n 的博士论文【2 2 】结合u p s 的快递业务对 快递货运网络做了全面而深入的研究。密西西比州立大学的a a r o nc t 2 3 】通过虚拟多 式联运系统( v i t s ) 对公路、水路和铁路货物运输做了详尽的分析和评估，并提 出合理的应用框架。文献 2 4 提出了货物运输中常见的规划和管理问题，分析了区 域、国际间的多式联运系统及多商品流系统问题，并对资源重组与配置( 如空车 调配问题) 构建了运营模型和算法。文献 2 5 t i , - t ：究了涉及多车队间的协作与管理的 服务网络设计问题。 文献 2 8 1 、 2 9 、 3 0 1 分别对随机货运流、随机服务网络设计以及随机运输库 存网络设计问题进行了分析和研究；而文献 3 1 利用双层随机规划模型对运输网络 保护问题进行了最新的探索。t i a n z ex u 、h e n gw e i 等 3 2 1 禾1 用模拟退火算法( s a ) 和遗传算法( g a ) 对连续性网络设计问题( c n d p ) 进行了算例分析，并得到有效验 证。文献 3 3 幂1 j 用双层规划模型和启发式算法，对危险货物运输网络设计问题( 降 低风险) 指出了有效的解决途径。s a n j a yj a i n 3 4 】阐述了分支定界法( b & b ) 在网 络建模中的应用；w e ix i e 、n i k o l a o sv s a h i n i d i s 【3 5 】将分支定界法应用到设备布局问 题当中；而a n d r e a sk l o s e 和s i m o ng o r t z 3 6 l 贝, t j 通过改进的分支定界法即分支定价法 ( b & p ) 应用解决了带容量限制的设备选址问题。 随着科学技术的不断进步和社会经济的不断发展，交通网络规模越来越大， 同时呈现出越来越复杂的结构特性，使得传统的网络研究方法和途径难以解决越 来越复杂的问题。因此，对于复杂网络的研究，已经成为当今交通网络研究领域 越来越重要的热点之一。2 0 世纪末，a l b e r t 等【3 j 7 】在对互联网的研究中发现了无标 度网络，开辟了人类认识复杂网络的新天地。复杂网络的研究不再局限于数学领 域，人们开始研究节点数量众多、连接结构复杂的实际网络的整体特性。长期以 来通信网络、电力网络、交通网络、生物网络和社会网络等分别是通信科学、电 力科学、交通科学、生命科学和社会学等不同学科的研究对象，而复杂网络理论 所研究的则是看上去互不相同的复杂网络之间的共性和处理他们的普适性方法。 文献 3 8 1 通过对无标度网络中b a 模型进行扩展，并利用计算机模拟进行观察，进 一步探索了复杂网络系统的规律。m e j n e w m a n j 详尽地阐述和分析了复杂网络 的结构及功能，回顾总结了一些研究进展，包括小世界网络模型、网络生长模型、 偏好连接模型，以及发生在网络的动态过程。章忠志等【4 0 】按照复杂网络经典模型 发展的先后次序，依次对随机图、小世界网络、无标度网络以及加权网络确定性 模型的研究现状进行较全面的综述，重点介绍了相关模型的构造及主要性质，并 对复杂网络确定性模型未来的部分发展方向进行了展望。 现阶段复杂网络在交通领域的应用已经逐步展开。高自友【4 i 】从城市交通系统 的角度出发，指出应综合利用复杂网络理论、动力系统理论、现代控制理论以及 交通科学和工程等多学科的理论和方法，以探索城市交通网络的时空复杂性及其 演化机理方面给出了重要参考价值。汪小帆等【47 】对复杂网络的基础知识和应用进 展做了系统的介绍，对从事复杂网络研究且极富交叉学科特色的研究人员提供了 很多有用的信息：但是该书中很多叙述没有给出数学上的严格论证，从统计力学 角度研究复杂网络的重要内容也没有给予充分的介绍。何诚【5 2 1 、刘宏鲲、李岸巍 等【5 4 】和蔡嫒媛等【5 7 】分别应用复杂网络理论对铁路网络、航空网络和城市公交网络 的复杂特性进行了分析和研究。关于网络结构演化问题的研究，杨波【5 9 】将复杂网 络理论和基于博弈论的经济网络理论相结合，从个体选择角度出发，以优化网络 中个体价值为网络结构演化动力机制来探讨小世界网络结构的演化；而陈晓【6 0 】等 则从局域世界演化模型的基础上，建立了供应链复杂网络的局域演化生长模型。 但是这两篇文献均没有考虑网络结构演化时网络的整体性与多目标特性。 1 3 论文结构安排 本文依托国家8 6 3 高技术研究发展计划“综合运输体系下快捷货运网络运能 配置与优化技术”( 编号2 0 0 7 a a ll z 2 0 8 ) ，在深入研究国内外交通网络设计问题的 基础上，拟从不同网络结构的特征和属性出发，结合快捷货运网络的目标特性和 测度属性，对快捷货运网络的外部影响因素和典型网络结构做了初步阐述和比较 分析；并结合复杂网络理论，利用小世界网络模型和改进的b a 无标度网络演化模 型对轮辐式快捷货运网络结构进行优化和算例验证。论文具体内容为： 第l 章绪论，分析论文选题的背景和意义，针对国内外对快捷货运网络 的研究以及复杂网络的应用成果概况进行较为详细的分析和论述： 第2 章复杂网络与快捷货运网络理论基础，阐述网络的基本概念，对复 杂网络的基本定义和统计属性加以介绍和分析；对复杂网络常用拓扑模型进行简 要分析；详细概述快捷货运网络的定义和特点：结合复杂网络理论的拓扑结构和 4 统计属性，对快捷货运网络的测度属性进行新的概括和提炼；并对快捷货运网络 拓扑结构的演化布局产生影响的若干因素加以分析和说明； 第3 章基于复杂网络理论的快捷货运网络结构分析，首先对基于综合运 输的快捷货运网络构筑与枢纽运作进行分析：针对两种基本的货运网络拓扑结构 即点对点式拓扑结构和轮辐式拓扑结构，利用快运网络基本测度属性进行分析和 比较得出相应结论；针对轮辐式货运网络拓扑结构作深一步的分类、分析与比较； 第4 章网络结构设计与优化，利用复杂网络理论中的小世界网络模型及 理论对轮辐式拓扑网络的最小化平均路径问题进行了推理，并通过计算机进行计 算、比较和验证；通过对b a 无标度网络演化模型的改进，对网络结构的动念演化 过程进行了分析，提出建立具有多目标特性的、层次型网络结构：并对层次性网 络的自相似性做了形象描述和说明；利用算例对演化模型进行例证和分析； 第5 章集装箱快捷货运网络拓扑结构演化分析，以全国集装箱快捷货运 办理站网络为背景，利用各城市节点所具备的各自环境和条件，进行网络模拟动 态演化过程，并对结果进行分析与总结； 第6 章结论与展望，对本论文的研究工作进行分析与总结；结合社会经 济的更多不确定性和货物运输网络的延续发展性，以及数学物理网络的最新研究 与发展，对未来研究工作做出部分思考。 论文框架结构如图1 1 所示： 5 基于复杂网络理论的快捷货运网络拓扑结构研究 一、绪论 l 二、复杂网络与快捷货运网络理论基础 ft 快快网 复捷捷络 杂货货拓 网运运扑 络 网网 结 基 络络 构 太基测影 理 本 度响 论 理 属 因 论性素 三、基于复杂网络的快捷货运刚络拓扑结构分析 山 1 综合运 货运网 各类轮 输体系 络坫本 辐式快 卜快捷 拓扑结 运刚络 货运网拓扑结 络枢纽 构分析 构分析 i 四、网络拓扑结构设计与优化 平均演 小 路径网络化 世 长度 生长 模 界 的推演化型 理 理与模型算 论 论证例 j 五、集装箱快捷货运网络结构演化算例 六、结论与展望 图1 i 论文框架图 f i g u r e l - if r a m e w o r ko fp a p e r 6 2复杂网络与快捷货运网络理论基础 2 1 复杂网络的基本理论 2 1 1 复杂网络的定义与统计属性 网络可抽象为一个由点集y 和边集e 组成的图g = ( ke ) 。许多实际的网络， 如运输网、电话网、电力网，都可以直观地用“图 的几何图形加以描述和分析。 例如，北京、上海、南京、杭州、西安、郑州、重庆、武汉、长沙、广州这 1 0 个城市和他们之间的航线也可以用一个图形来描述。这l o 个城市分别用k 、k 、 k k 。代表，每个城市在图上用一个点或者圆圈表示。如果两个城市间有航线相 通，就把表示这两个城市的点或圆圈用一条线段连接起来，得到线段e l 、厶、 e 3 e l 。，这样就形成了图2 i 所示的图形。 北京vo 西 重庆v 6 v 5 广州v 1 0 图2 - 1 城市航空网络 f i g u r e 2 一lc i t ya v i a t i o nn e t w o r k 在上面的图中，代表城市的那些点称为图的节点( 或成为顶点，简称点) ，记 作k 、k 、巧k 。连接城市的直线( 段) 或曲线( 段) 称为图的边( 或线) 。 记作p 产 均，嘲。从这个航线图可见，构成一个图的最基本要素是节点以及连接 节点的边。通常图的节点表示具体事物，边表示事物之间的联系。 定义2 1 ：图g = ( 儿目由集合v 和e 构成。集合v 的元素称为节点；集 合e 的元素称为边，它是以【以，吲形式出现的无序对，其中、巧v o 在图2 1 的例子中，图g = ( ”d 的节点的集合是： y = 北京、上海、南京、杭州、西安、郑州、重庆、武汉、长沙、广州) ， 7 用符号表示为：净 h 、圪、巧、) ； 边的集合是： e = ( 北京，西安) ，( 北京，郑州) ，( 北京，南京) ，( 北京，上海) ，( 北京， 武汉) ，( 上海，杭州) ，( 南京，杭州) ，( 南京，武汉) ，( 武汉，郑州) ，( 武汉， 长沙) ，( 武汉，重庆) ，( 长沙，广州) ，( 广州，杭州) ，( 重庆，西安) ，( 西安， 郑州) ) ； 用符号表示为： e = f ( v i ，v 2 ) ，( v i ，1 3 ) ，( v i ，v 4 ) ，( 明，巧) ，( n ，v 7 ) ，( 巧， v 8 ) ，( v 4 ，1 ：8 ) ，( 附，胛) ，( v 7 ，i 3 ) ，( v 7 ，v 9 ) ，( ，v 6 ) ，( 1 9 ，v 1 0 ) ， ( v 1 0 ，v 8 ) ，( 瑙，v 2 ) ，( v 2 ，1 3 ) ) = e 1 ，8 2 ，o9 1 5 o 值得注意的是，描述一个图的图形并不是唯一的。表示节点的点和表示边的 线段的相对位置并不重要，在这里，边的唯一作用是把两个点连接起来。例如图 2 2 所示的图形，尽管他们的形状不同，但本质是相同的，都是由5 个点与连接这 些点的7 条边所组成的。此外，图中两条线除了相交于节点时表示有公共交点外， 其他相交均不表示有公共交点。例如，图2 2 中的图形( c ) 中，边 n ，玖】与边 圪，乃】是互不相交的。 v 4 v l v 4 v 2 v ( b )( c ) v s 图2 - 2 形状刁i 同而本质相同的图 f i g u r e 2 2t o p o l o g i e si ns a m en a t u r eb u td i f f e r e n ts h a p e s 然而在实际网络中，有时仅仅用边来反映两个事物之间的关系是不够的。例 如，某地区从h 到圪的公路是单行线，汽车只能从乃通向巧，不能由乃通向 乃。如果此时仅用边来描述这种特定关系( 即巧一圪) ，就不能全面反映事物之间 的联系；而用带箭头的线段( k - - - ) 巧) 就可以表述清楚了。一个图，如果其边是有 向的，则称这个图为有向图；否则就是无向图。 定义2 2 ：有向图g = ( y ，e ) ，由集合v 和e 构成。集合矿的元素称为起始节 点( 顶点) 和终止节点( 顶点) ；结合e 的元素称为有向边( 或弧) ，它是以 所， r a r e 式出现的有序对，其班、r v o 此外，实际网络中可能包含多种不同类型的节点或边。以上述城市航线网络 8 为例，城市规模大小不同则决定节点的不同；城市间航线里程数( 或运行时间) 不同，决定了网络边长的不同。如果给网络的每条边赋予相应的权值，那么该网 络则称为加权网络( w e i g h t e dn e t w o r k ) ；否则称为无权网络( u n w e i g h t e dn e t w o r k ) 。 所谓复杂网络，就是具有复杂拓扑结构和动力行为的大规模网络，它是由大 量的节点通过边的相互连接而构成的图。例如，因特网，万维网，超文本传输协 议，食物链网络，生物网络，无限通讯网络，高速公路网络，航空线路网络，电 力网络，细胞神经网络，超大规模集成电路，人体细胞代谢网络，流行病传播网 络等都是复杂网络。复杂网络的节点可以是任意具有特定动力和信息内涵的基本 单位，而边则表示这些基本单位之间的关系或联系。 多数实际的复杂网络表现出如下特征： ( 1 ) 网络行为的统计性：网络节点数可以成百上千万，甚至更多，从而使得 大规模性的网络行为具有统计特征； ( 2 ) 节点动力学行为的复杂性：各个节点本身可以是非线性系统，具有分岔 和混沌等非线性动力学行为； ： ( 3 ) 网络连接的稀疏性：一个个节点的具有全局耦合结构的网络的连接数 目为o ( n 2 ) ，而实际大型网络的连接数目通常为d ( ) ； ( 4 ) 网络的时空演化复杂性：复杂网络具有空间和时间的演化复杂性，显示 出极其丰富的复杂行为，特别是网络节点之间不同类型的同步化运动。 这些特征反映出，复杂网络一方面具有无序演化的特性，另一方面，也具有 增加有序程度的演化特征。传统图论对于网络拓扑结构的研究是从节点与节点的 连接度、图的连通度等方面来分析的，而复杂网络的研究使用概率的方法，通过 不同的几何量来描述复杂网络的不同方面的结构特点，从而比较全面的描述复杂 网络的内在特征。下面对三个基本的统计属性做一个简要说明： ( 一) 平均路径长度 网络中两个节点f 和，之间的距离扰j 定义为连接这两个节点的最短路径上的 边数，网络中任意两个节点之间的距离的最大值称为网络的直径，记为d ，即： d = m a x 办 ( 2 - 1 ) 网络的平均路径长度厶定义为任意两个节点之间的距离平均值，即 止南吾办 ( 2 - 2 ) 式中：n 为网络节点数。网络的平均路径长度也称为网络的特征路径长度。为了便 于数学处理，在公式中包含了节点到自身的距离( 当然该距离为零) 。如果不考虑 节点到自身的距离，那么要在公式( 2 2 ) 中右端乘以因子( + 0 ( n 一1 ) 。即： 9 l = t _ 二一办 ( 2 - 3 ) 主( n - 1 ) 晓7 在实际应用中，这么小的差别是完全可以忽略不计的。一个含有个节点和 m 条边的网络平均路径长度l ，可以用简单的广度优先搜索法算出，时间复杂度为 o ( m n ) 。 ( 二) 聚类系数 在某人的朋友关系网络中，其两个朋友很可能彼此也是朋友，这种属性称为 网络的聚类特性。一般地，假设网络中的一个节点i 有忽条边将它和其他节点相接， 这岛个节点就成为节点f 的邻居。显然，在这镌个节点之间最多可能有k , c k , - 1 ) 2 条 边。设岛个节点之间实际存在的边为互，其与总的可能边数砖( 岛- 1 ) 2 之比就定义 为节点的聚类系数g ： g = 2 e , 岛( 岛一1 ) ( 2 - 4 ) 从几何特点上考虑，聚类系数的等价定义为： c ：量盛丛! 垄箜三鱼垄塑塑量f 2 - s 、 q 2 i 丽i 丽甄硅磊面砸 u 。 与点相连的三元组的数量 ” 式中：与节点i 相连的三元组是指包括节点i 的三个节点关联组，并且至少存在从 节点i 到其他两个节点的两条边。整个网络的聚类系数c 就是e 的平均值： c = 万1 ；q ( 2 - 6 ) 其中为网络中节点个数。很明显，0 c 1 。当且仅当所有节点均为孤立节 点，没有任何连接边时c = o ；当且仅当网络是全局耦合的，即网络中任意两个节 点都是直接相连时c = i 。对于完全随机网络，当很大时，c = o ( n 叫) 。 此外关于网络中的节点聚类系数有第二类定义：为节点f 在网络中实际存在的 度数与整个网络可能存在的边数的比例，这里称之为第二类聚类系数d ： c ：= 二l( 2 7 ) n ( n 一1 ) 第二类聚类系数实际上是节点度在整个网络中集团化程度的反应。 ( 三) 度与度分布 度，也称节点度，指与该节点与其他节点相连接的边的数目。有向网络中一 个节点分为出度和入度。节点的出度是指从该节点指向其他节点的边的数目；节 点的入度是指从其他节点指向该节点边的数目。网络中所有节点i 的度岛的平均值 称为网络的节点平均度，记为 感染( i ) _ 易染( s ) 的s i s 模型。令从易染状态到感染状态的概 率为y ，从感染状态恢复到易染状态的概率为万。定义有效传播率如下： a = 詈( 2 - 1 4 )6 考虑均匀网络( 如小世界网络) 和非均匀网络( 如无标度网络) 的特性，得 出在均匀网络中存在一个有限的正的传播临界值无： 1 丸2 南( 2 - 1 5 ) 式中( k ) 为网络的平均度。如图2 - 9 所示，如果有效传播率五大于临界值五， 感染个体能够将病毒或威胁扩散，并使得整个网络感染个体总数最终稳定于某一 平衡状态，此时网络处于激活相态；如果有效传播率小于临界值，则感染个体成 指数衰减，无法大范围传播，此时网络处于吸收状态。 o：k 九 图2 - 9 均匀网络的s i s 模型相位图 f i g u r e 2 9s i sm o d e lp h a s em a po fu n i f o r mn e t w o r k 而对于无标度网络的传播临界值，更多地从免疫策略角度考虑， 免疫和目标免疫下的免疫临界值分别为公式( 2 。1 6 ) 和( 2 1 7 ) ： g 随0 t = 1 一专 一三 锦标= e 以 2 4 快捷货运网络拓扑结构的影响因素 得出在随机 ( 2 - 1 6 ) ( 2 - 1 7 ) 网络是由节点和边组成的，各个节点之间不同的连边将产生不同的网络结构。 而城市节点的社会经济、产业结构、对外运输通道等条件和因素决定和影响着城 市节点的吸引力，对货运网络的组织与构建起着决定性影响。下面章节将通过对 这些影响因素的分析，来探讨各因素在网络结构形成和发展中的连边机制及影响。 2 4 1 社会经济与快捷货运网络 快捷货运网络的网络规模、布局结构、技术支持以及运输的货类品种等都与 社会经济息息相关。 ( 1 ) 社会经济发展影响网络规模。经济总量是货运需求增长的主要因素。交 通运输业是一个产业部门，为满足社会运输需求而存在，并随需求规模的不断扩 大而不断发展。而社会经济的发展所产生的对人、物空间位移的需求，正是运输 业存在和发展的市场。社会经济，运输需求和运输规模不断扩大，货运网络规模 也随之不断发展和扩大。如我国经济总量与货运量、货运线路变化情况如表2 1 和表2 2 所