基于复杂网络理论的上海市公交网络优化研究

VIP免费
3.0 陈辉 2024-11-19 5 4 845.75KB 63 页 15积分
侵权投诉
第一章 绪 论
1
第一章 绪 论
§1.1 选题背景
近年来，随着小世界效应(small-world effect)和无标度特性(scale-free property)
的被揭示，激起了物理学、社会学、经济学、计算机通信等多领域学者对复杂网
络的研究兴趣，掀起了其在不同学科的研究热潮[1..4]。复杂网络的研究之所以受到
了不同学科的广泛关注，其原因主要在于[5]：
(1)随着计算机运行能力的不断提高和计算机网络的普及，世界上已逐渐建立
起了一些有关大型复杂网络的拓扑结构数据库，进而激发了人们从理论、仿真和
实际数据验证三个方面研究复杂网络的浓厚兴趣；
(2)学科之间的相互交叉和融合的趋势不断加强，促进了对复杂网络共有特征
和性质的揭示；
(3)对复杂网络的深刻理解和认识，有助于人们深刻理解“复杂系统之所以复
杂”这一至关重要的基础问题；
(4)将复杂网络理论、动力系统理论和现代控制理论三种科学理论有机地结合
起来，探索现实复杂网络的演化过程，尤其是深入地探讨现实中复杂网络的时空
演化规律，以达到对现实复杂网络进行有效分析与控制的目的。
因而，对网络复杂性问题从定量和定性两方面进行研究与分析，以及开展网
络拓扑结构对其动力学行为影响的研究，是一项极其重要而又富有挑战性的科研
课题，被认为是 21 世纪科学技术前沿战略性研究课题之一。
20 世纪以来，复杂网络的研究进入了迅速发展时期。1960 年，数学家 Erdǒs
和 Rényi 提出了随机图理论（random graph theory）,开创了研究复杂网络中貌似
随机的拓扑复杂性的纪元，ER 随机网络模型由此一直成为研究复杂网络的基本模
型[1]。然而，近几年来人们发现，在对一些现实网络的实际数据进行研究后得到
的许多结果都与随机图理论相背离，因此要用新的复杂网络模型来合理的描述这
些实际网络中所显现出来的特性。其中之一就是 Watts 和Strgatz 提出的 WS 小世界
（small-world ）网络模型[6..8] ，刻画了现实世界中网络所兼具的大的聚簇
（clustering）与短的平均路径距离（average-path-length）小世界特性。实际的复
杂网络中还被发现具有普适的“富者更富”的现象，因此，Barabási 和Albert 提
出了无标度（scale-free）模型，所产生的复杂网络分布是幂律
3
~)(
kkp
的形式
[9-11]。BA 无标度网络模型指出了决定互联网、万维网和科学家合作网研究等具有
无标度特性的两个基本原理：指数增长和节点择优连接。Krapivsky、Render 和
基于复杂网络理论的上海市公交网络优化研究
2
Leyvraz 研究了非线性择优连接模型，提出了新的节点与度为
i
k
的节点
i
相连的
概率满足非线性关系
ii kk ~)(
，其中
为正的常数。Dorogovstsev 和Mendes 研
究了在有向网络中的加速增长现象，他们更早的一个研究工作已经发现衰减的增
长约束会影响网络的标度指数[12]。
在国内，刘宗华、来颖城等人在 2002 年发表文章[13]，认为自然界中的许多复
杂网络应该介于无标度网和随机网之间。他们举出了科研合作网作为一个例证，
并且提出了一个可以生长这类网络的模型。李翔、陈关荣在 2002 年发表文章[14]，
针对确定性和随机性共存的机制提出了一个非常重要的新思想，他们举出世界贸
易网为例子，说明许多网络中存在“优先相互作用”的“局域世界”。他们假设在
这类网络中，优先连接法则只适用于局域世界内部，而每个顶点的局域世界是随
机的选取一部分顶点构成的。这就是确定性和随机性共存的具体机制。
在交通研究领域中，公交网络设计问题一直是公共交通领域公认的难度最大、
最具有挑战性的问题。解决城市公交网络设计问题不仅要考虑到政府部门的利益，
而且需要考虑公交用户旅行行为，两者相互作用，相互影响。只有如此才能得出
切合实际的设计结果，而做到这一点具有相当大的难度，主要原因在于如何提出
包含各种影响因素的网络设计模型，并设计行之有效的求解方法。迄今为止，各
国对于公交网络设计问题的研究仍处于初级和探索阶段。在国外，已经有一些研
究人员和规划者在这方面进行了大胆的尝试和研究，并提出了一些富有建设性的
模型和算法，在线路选定方面，比较有代表性的有 Newell 和Ceder 等[15]。这些研
究只是局限于单一线路的设计和重新设计，而没有考虑整个公交网络的设计或重
新设计，也没有考虑公交用户的路径选择行为。关于频率设置方面的研究主要有：
Furth 和Wilson,Koutsopoulus 和Wilson[16,17]，Ceder(1983)等[18]，他们是根据已知
的需求通过一个供给模型或需求模型来确定各公交线路的频率，而没有考虑供需
双方的相互作用，均属于单层次的网络设计模型，因而得出的结果与实际要求具
有一定的偏差，很难在实际中应用。可见目前所提出的网络设计问题的模型和算
法在实际应用中均存在不同的局限性。在国内，对公交网络的设计的研究和探索
还非常的滞后，急需要在该领域进行深一步的研究。
§1.2 选题意义
随着上海市城市的不断发展，公交路线和公交车辆急剧增加，但是相应的交
通问题也日益严重和显露出来，给居民的出行造成很大的不便，研究公交网络设
计问题能够有效的缓解实际城市交通拥挤、环境污染及能源浪费等问题，并能产
生重大的社会效益，因此进一步研究公交网络设计问题具有十分重要的理论意义
第一章 绪 论
3
和现实意义。
本文从复杂网络理论出发，对上海市公交网络的网络结构进行研究。由于自
然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典型的网
络是由许多节点与连接两个节点之间的一些边组成的,其中节点用来代表真实系
统中不同的个体,而边则用来表示个体之间的关系,通常是当两个节点之间具有某
种特定的关系时连一条边,反之则不连边. 有边相连的两个节点在网络中被看作
是相邻的. 例如,神经系统可以看作是大量神经细胞通过神经纤维相互连接形成
的网络[19-21] ;计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双
绞线、同轴电缆等相互连接形成的网络[22]。类似的还有电力网络[23] 、社会关系
网络[24-30]，交通网络[31-34]等等。本文把公交站点和公交线路分别作为节点，以公
交线路的运输关系为边，以不同的连边方式构成三种形式的上海市公交网络。对
这三种网络的研究可以了解上海市公交站点的分布网络结构，以及公交运输线路
网络的网络特征，从而发现上海市公交网络中存在的一些结构方面的问题，对公
交网络的设计及优化提供重要的理论支持。
§1.3 现实世界网络的研究成果
近来关于网络的数学研究工作的开展很大程度上是由观察实际网络属性所推
动，试图对它们进行建模，所以从收集网络数据这个起点开始，对网络进行拓扑
结构分析，进而进行建模是很有意义的举措。近来此领域的主要突破之一是对来
自不同学科分支的网络的对比研究，主要是针对这些网络大部分所具有的共同属
性以及反映这些属性的科学进展，现针对四个松散的网络类别进行一下简单的总
结：社会网络、信息网络、技术网络和生物网络。
社会网络是人或人的群体的集合，这些人之间具有某一接触或相互作用模式
[24,25]。个体之间友谊模式[26,27]，公司之间商业关系模式[28,29]，以及家族之间联姻模
式[30]，这些都是过去已被研究过的例子。在众多学科中，社会科学对现实世界网
络进行实质的定量研究的历史是最长的。与此主题有关的早期研究中特别值得一
提的包括：Jacob Moreno 在二十世纪 20 年代和 30 年代对小群体中的友谊模式进
行的研究[24]；Davis 等人所谓的“南方女性研究”，其关注 1936 年美国南方一个未
知名的城市中妇女的社交圈。ARpoport 和其他人对校童的友谊网络进行的研究[26]。
最近，有关商业团体的研究[18,27]和性接触模型的研究[35,36]吸引了特别的注意。
传统的社会网络研究经常会遇到不准确、主观性和小样本的问题。除了一些
精巧的间接研究，如 Milgram 的研究[37]外，通常是通过利用问卷或面谈的方式直
接询问参与者来收集数据的。这些方法的工作量大，因此限制了能被观察的网络
基于复杂网络理论的上海市公交网络优化研究
4
规模的大小。此外，调查数据受到回答方的主观偏见影响：例如一个回答者定义
其朋友的方式与另一位回答者可能有很大的不同。虽然在消除可能的不一致源头
方面付出了很多的努力，但一般性，认为这些研究中的大多数都存在大的、本质
上无法控制的错误。Marsden 撰写了关于这些问题的述评[38]。
由于这些问题的存在，很多研究者转向用其它方法来探究社会网络。一个丰
富且相对可靠的数据源是协作网络。它们是典型的隶属网路，在其中参与者按一
种或另一种方式分群合作，并且个体对之间的联系是通过共同的群成员资格建立
的。此种类型网络一个经典而意义不甚大的例子是电影演员的合作网络，这些数
据在因特网电影数据库中有详细记载。该网络中演员在电影里合作，两位演员如
果他们一同在电影里出现则认为他们之间有联系。很多学者对该网络的统计属性
进行了研究。此种类型网络另一些例子包括公司董事网络，其中两位董事如果属
于同一个董事会，则认为他们是关联的；学术合作网络，其中个体如果他们曾合
作过一篇论文或多篇论文则是关联的；同时露面网络，其中个体如果他们在同一
处被提及则是关联的，特别是在网页或报纸文章上。
第二种网络类别是我们将称之为信息网络的类别（有时也称为“知识网络”）。
信息网络经典之例是学术论文之间的引文[38]。大部分学术论文都经由相关主题的
其它文章来引用以前做的工作。这些引用就形成了一个网络，其中顶点代表论文，
从论文 A 到论文 B 的有向边代表 A 引用 B。则引文网络的结构反映了存贮在它的顶
点上的信息的结构，即术语“信息网络”，当然论文的引用模式也有社会的方面因
素在内[39]。
引文网络是非循环的，因为论文仅能引用已写好的其它文章，而不能引用还没
写的文章。因此，网络中的所有的边都同时向后指，使得闭合环不可能存在，或
至少是极少存在的。
信息网络另一个非常重要的例子是万维网，它是一个由包含各种信息的网页所
构成的网络，这些网页由一张页面到另一张页面的超链接联结。不要将万维网和
因特网相混淆，后者是一个由通过光缆和其它数据连接物联结在一起的计算机形
式的网络。不像引文网络，万维网是循环的，不存在地址的自然排序，没有限制
闭合环的出现。万维网自从二十世纪 90 年代首次出现以来，有相当多的研究是关
于它的，特别有影响力的包括 Albert 等人，Kleinberg 等人以及 Broder 等人的研究
[40]。万维网也具有幂律分布的入度和出度，以及各种其它有趣的属性。
偏好网络提供了一个双向信息网络的例子。偏好网络有两种顶点，分别代表个
体和他们的偏好物，如书或电影，每一个体通过一条边和他们喜欢的书或者电影
连接起来，偏好网络也可加权重来显示喜欢或者不喜欢的程度。偏好网络的一个
第一章 绪 论
5
被广泛研究的例子是电影偏好的 Eachmovie 数据库。这种网络构成了协作渗流算
法和介绍人系统的基础，这些技术用于在比较个体偏好和其他人偏好的基础上预
测新的偏好和厌恶[41]。协作渗流技术获得了相当大的商业成功，包括产品推销和
目标广告，特别是同在线零售商一起。偏好网络也可被视作是社会网络，不仅把
人和物连接在一起，还把人和与之有相似偏好的其他人连接在一起[42]。
网络的第三种类别是技术网络，这是人造网络，其设计的典型目的是分配一
些商品或资源，如电或信息。电力格子是一个很好的例子，这是一个高伏电压三
相传输线的网络，跨越一个国家或者国家的一部分（与地方上低伏电压电力传输
线相对比，后者跨越的是个别附近的几个地方）。有关电力格子的统计有一些学者
作过此方面的研究，例如，Watts、Strogatz 和Amaral 等人[30]。有研究的其它分配
网络包括航空路线网络、道路网络、铁路网络以及人行交通网络。河流网络被视
为是分配网络的自然出现形式（实际上是一个托收网络）[43]，就像血管网络一样。
电话网络和诸如邮局或包裹递送公司使用的那些递送网络也都属于这一类别，并
且在学术研究者之前，相关企业就进行了研究。
另一个研究的非常广泛的技术网络是因特网，即计算机之间物理连接的网络。
由于因特网上计算机的数量庞大且经常变动，因此对此网络结构的研究通常是粗
略的，针对路由器---网络上控制着数据运动的有特殊目的的计算机,或“自治系
统”---即计算机群，群中互联网是局部处理的，而群之间数据在公共因特网上流
动。单个公司或大学的计算机可能形成一个自治系统----此自治系统经常利用域
名进行简单联系。
事实上，对因特网上物理连接网络不容易观察，因为其基础结构部分是受很
多分隔开的组织控制的。因此典型的做法是，研究者通过从点对点数据通道的大
型样本中的推理来重构网络。所谓的“踪迹路线”程序能够报告网络顶点的顺序，
即数据包在两个点之间游走时经过的顺序，如果我们假设网络中沿着这样一条路
径上任意两个连续顶点之间存在一条边，那么足够大数目的路径样本将为我们提
供整个网络的一个相当全面的描绘。然而，可能存在一些从未被抽样的边，因此
依次重构出来的网络虽然比较好，但不能够完美的代表因特网的真实物理结构。
其他一些学者也对因特网结构进行了研究，包括 Faloutsos 等人[44]，Broida、Claffy
和Chen 等人[45]。
很多生物系统可以被表示成网络，这就是我们所说的生物网络。生物网络的
典型例子是代谢路径网络，它是代谢基质和代谢产物的刻画，如果一已知代谢反
应存在，其作用于给定基质并产生指定产物，两者之间由有向边连接。多数人都
可能看过分子生物学家钉在墙上的代谢路径巨图。一些学者对代谢网络的统计学
基于复杂网络理论的上海市公交网络优化研究
6
属性进行了研究，例如，Jeong 等人[46,47]。一个不同的网络是蛋白质相互作用网络。
很多学者对相互作用网络进行了研究[48]。
生物网络另一个研究的很多的例子是食物网，其中顶点代表生态系统中的物
种，从物种 A 到物种 B 的有向边表明 A 捕食 B，有时按相反方向来画关联关系，因
为生物学家倾向于根据流经食物网的能量流或炭流来考虑；因此，捕食者----猎
物关联关系被画为从猎物指向捕食者的箭头，表明当猎物被吃时能量从猎物流向
捕食者。完全的食物网的构建是工作量非常大的，但今年来可获得了很多广泛的
数据集。一些学者对食物网的拓扑结构进行了统计研究，他们包括 Sole 和Montoya，
Camacho 等人以及 Dunne[49]等人,Jordano 等人[50]对植物和食草动物网络进行了特
别彻底的研究，包括对不少于 53 个不同网络的统计。
§1.4 本文研究目的和主要内容
20 世纪 90 年代以来，上海市交通取得了显著的进步，有力的推动了城市的
迅速发展。但是，交通行业和城市发展比较，相对滞后的问题尚未解决，城市交
通还存在诸多不足，比如说交通便捷性、通达性和舒适性与世界相比还存在很大
的差距。本文主要对上海市公交网络进行相关网络结构分析和优化，现把上海市
公交网络分为公交站点全连通网、公交线路网以及公交站点邻近连接网三种公交
网络，主要对该三种网络进行网络的拓扑结构分析、阻塞的演化机制研究及在此
基础上进行网络调整优化。
截至 2004 年底上海有运营企业 40 余家，950 多条公交路线，公共汽车 17481
辆，电车 602 辆，总共线网长度 1804 万公里，每日的客运总量 780 万人次，承担
着 65%的市域公共客运量。以公交车站为节点，公交车站在一条公交路线运行之
中的合作运输关系为边，就可以抽象成一个公交网络。
面对复杂得交通问题，本文主要把复杂网络的理论应用到上海公交网络中，
发现和分析公交网络结构中存在的问题，从而对上海市公共交通网提出改善意见。
通过对上海市公交站点网络的实证分析，本文的主要研究内容：
第一，对复杂网络理论进行研究探讨，分析现今比较常用的网络属性。
第二，对上海市公交网络的拓扑结构进行分析，从实际的公交网络中抽象出
公交站点全连通网、公交线路网、公交站点邻近连接网，计算这三种网络的静态
几何量及其统计性质，如度、群聚系数、最短路径、介数等以及对网络的聚类分
析。通过计算得出的静态几何量来断定上海市公交网络的网络类型。
第三，运用 SIR 模型对上海市公交站点邻近连接网的阻塞机制进行模拟。
第四，通过阻塞优化模型，对上海市公交网络进行线路优化。
第二章 复杂网络理论及其数字特征
7
第二章 复杂网络理论及其数字特征
在今天的生活中，我们经常可以听到“网络”这个词，打开电脑，上网浏览
一下当天的新闻已经成了很多人每天的习惯。当然，Internet只是网络的一种，仔
细观察一下周围的事物：画在纸上的电路，一个城市的供电供水系统，这个世界
上所有相识或陌生的人，生物之间捕食和被捕食的关系，细胞中的化学物质发生
反应的关系⋯⋯你会发现生活中几乎到处都是网络，这些网络是规则的？混乱的？
还是混乱中隐藏着某种秩序？在过去的八年里，借助功能强大的计算机，人们对
网络的认识发生了巨大的改变，新奇的规律、优美的结构、最新的研究成果为我
们揭示了其中的种种奥妙，本章节我们就来介绍一下复杂网络的理论知识，为后
续章节内容做好准备。
§2.1 复杂网络理论概述
复杂网络主要是指具有复杂拓扑结构和动力学行为的大规模网络,它是由大
量的节点通过边的相互连接而构成的图。例如,英特网、万维网、超文本传输协议、
食物链网络、生物网络、脱氧核糖核酸、无线通讯网络、高速公路网、航空线路
网、电力网络、细胞神经网络, 超大规模集成电路,人体细胞代谢网络,流行病传
播网络等都是复杂网络[52] 。复杂网络的节点可以是任意具有特定动力和信息内涵
的系统的基本单位，而边则表示这些基本单位之间的关系或联系。由于我们生活
中存在着大量的复杂网络，这促使我们去研究这些复杂网络的行为。
这些网络所具有的特征主要表现为: (1)网络中节点与节点之间连接的多样性。
复杂网络是由活性节点构成的,各个节点具有不同的特性,并按非线性方式进行状
态转化；同时,节点之间的连接内容是多样化的,连接结构是立体动态的。(2)网络
具有动态演进特性。复杂网络中的局部互动关联性,涌现出网络整体上的动态演化
行为模式,而这种行为模式又导致网络结构的不断变化与更替。
(3)网络之间的交互
影响性。各种各样的复杂网络相互连接起来,以复杂的耦合方式进行互动并影响各
自的行为模式。基于复杂网络的这些特征,人们利用了一定的数学模型,如ER随机
图模型、小世界网络模型和无标度网络模型等,来分析复杂网络的统计特性,稳定
性,柔性以及演化动力学特征等。
具有不同拓扑结构的复杂网络可以分类为规则网络、随机网络、小世界网络、
无标度网络等。规则网络是指我们常见的具有规则拓扑结构的网络，如完全连接
图、星状网络、邻近节点连接图等，关于规则网络的研究已经建立了比较完善的
摘要：

第一章绪论1第一章绪论§1.1选题背景近年来，随着小世界效应(small-worldeffect)和无标度特性(scale-freeproperty)的被揭示，激起了物理学、社会学、经济学、计算机通信等多领域学者对复杂网络的研究兴趣，掀起了其在不同学科的研究热潮[1..4]。复杂网络的研究之所以受到了不同学科的广泛关注，其原因主要在于[5]：(1)随着计算机运行能力的不断提高和计算机网络的普及，世界上已逐渐建立起了一些有关大型复杂网络的拓扑结构数据库，进而激发了人们从理论、仿真和实际数据验证三个方面研究复杂网络的浓厚兴趣；(2)学科之间的相互交叉和融合的趋势不断加强，促进了对复杂网络共有特征和...

展开>> 收起<<
基于复杂网络理论的上海市公交网络优化研究.pdf

共63页,预览7页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：陈辉 分类：高等教育资料 价格：15积分 属性：63 页 大小：845.75KB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

推荐作者

热门标签

/ 63
评分 收藏
分享
立即下载 VIP免费下载
客服
关注