小世界网络理论在城市公共交通线网优化中的应用

吴亚萍

摘要：随着社会经济的不断发展，城市交通在城市发展中所占据的地位不断提高，其自身存在的问题也在不断地出现，对城市内部的交通进行优先发展可以优化交通资源的利用效率，也可以逐渐解决城市的拥堵问题。优先发展公共交通的关键部分就是对公共交通网络进行优化，从而促使公共交通竞争力得到提高。因为公交线路的聚集性比较高和平均最短站间路径小，从而对小世界效应进行了反映。以小世界网络理论的效率理论为基础，研究了小世界在公交网络中网络理论的拟合问题，在公交网络优化过程中给出小世界网络理论应用方法。并以杭州市主城区中心区公交线网的应用为例说明了该方法的应用。

关键词：小世界网络;公交线网;全局效率;局部效率优化

中图分类号：G434        文献标识码：A

文章编号：1009-3044（2019）19-0263-02

1 引言

在城镇化和交通汽车化的发展环境下，城市交通供给和需求之间的矛盾一天天突出，目前已经发展为在城市长期发展中急切需要解决的问题。通过对国内外相关理论的研究以及对城市交通建设现状进行实地考察，优化现有常规公交系统、建立智能交通网络是解决交通拥堵和环境污染等问题的根本出路。现在，在国内普通的公交线路优化过程中，基本上是建立数学优化模型的理论研究。这些措施对于解决公共汽车规划过程中遇到的实际问题的效果不是很大，因为数据是很难被全部收集到的，这些措施也过于理想化，难以被实际操作。面对这些问题，本文主要在其他学者研究的基础之上，根据公交线网的实际优化成果及目前的研究情况，根据小世界网络理论提出了公交网络优化措施。将小世界网络的统计特性应用到公共交通网络中。以杭州市为例，对公共交通网络的优化进行了研究。经过分析公交网络抽象模型，在众多措施中选择了最好的网络方案，使得公交网络的传输效率得到提高，以及网络的容错能力也被提高了。结合定性和定量分析，根据实际情况提出更具操作性的优化方案，为相关部门和企业提供决策支持。

2 模型与特性分析

2.1 小世界网络模型

1998年，STROGATZ和WATTS提出了小世界网络模型（WS模型）[2]。通过和经典模型相的对比，小世界网络模型可以对很多现实网络自己组织形成的体系进行解释。随着时代的不断发展，关于该研究的深入程度也在不断提高，很多的实际考察结果也现实，很多真实网络包括交通网络具有的世界特征都是比较小的。小世界网络模型能够被定义为：随着环网规则特别是在具有N个节点的情况下被给定，每个节点对称地连接到其最近的m个邻居。然后让每一个节点都以概率P与其他节点进行重连便得到了小世界网络。如图1所示演示了这种重连过程。

若要网络显示为正则网络，则重联概率为0;若要网络显示为随机网络，则要求p为1;若要求网络形成是小世界网络，则要求p处于特殊区间，也就是0与1之间。网络可以表示为G=（V，E），其中V代表给定的节点，是一组网络节点;E表示边，是网络节点关系的集合。N为网络节点数，A=（aij）是相应的邻接矩阵。对于0，1矩阵A来说，若节点i与节点j相连，而且i不等于j，aij=1就会出现，否则aij=0。

2.2 模型特性分析

①小世界网络平均路径长度L和聚集系数C

在常规的网络中，节点和节点间最小的路径的平均值是路径平均长度，同时路径的平均长度也是对节点分离程度的参数的描述;网络中全部节点的聚类系数的平均值是聚合系数，是对网络的容错性能进行描述和对聚合程度尽心表述的参数[2]。在规则性的网络中，因为节点是根据特定的条件进行分布的，这种情况下它们的聚集系数C都是比较大的，只是节点和节点间的平均路径长度L的值也会比较大。随机网络因为它们节点的分布都是比较随意的，所包含的聚集系数一般比较小，以及平均路径长度L也比较小。作为分布于两种网络之间的小世界网络，使得小世界网络同时具备这两种网络的长处，也就是含有较大的聚集系数C，较小的平均路径长度L，从而使得小世界网络具备比较好的网络特性。

②小世界网络的效率

为了使得小世界网络可以被更直接又生动地表现出来，对于引入其他重要的参数效率也是必要的。经过对这个参数的引入，使得小世界网络的效用能够被用一个定值表现出来。基于网络知识和图论，在描述一个公共网络的过程中能够使用两个矩阵：相互关联的矩阵（aij）和一阶邻接矩阵（lij）[3]。当点i和点j的边连通无阻时，aij=1，lij是两点之间的现实距离;当i点和j点没有被直接连通时，aij=0，lij=∞。如图2所示。

在得到aij和lij后，用贝尔曼算法能够取得最短路径矩阵dij[3]，并将i点和j点两点间的效率解释为eij=1/dij，vi，j，如果dij≤lij，那么i点和j点之间的效率也可以被阐释为eij=1/dij，vi，j。若dij=∞，那么aij=0，能够总结出e（g）=[1/（n-1）]1/dij是网络的平均传输效率。理想情况下，它可以被认为是dij=lij，emax=e（g（n，n（n-1）/2）=[1/n（n-1）]1/lij。上面所描述的就是全局效率Eglobe参数[4]，对于完整网络和现实的网络在他们之间的平均路径的对比过程中进行描述，也就是对平均路径在现实网络和完整网络之间到底有多大的相似度，能够得出0≤e（g）≤1，如果e越接近1，那么效率就会变高。

但是，在实际网络中，维持每一个节点都可以正常并同时间进行工作的状态是很难的。如果一个节点在网络中不能和平常情况一样进行工，那么对于提高网络的效率就是必须要做的事情。在对网络中容错性尤其是自治分散板块进行描述时，对另外一个参数进行了定义：局部效率ELOC[4]。如果全局效率gi是除去網络中i点后的，那么局部效率公式就可以被阐释为Eloc=1/NΣE（gi）。

3 模型算例

在城市公共交通网络的建设过程中，其社会性的特点在逐渐的突出，人工规划城市公共交通网络的过程中，所受到的影响因素是多方面的。所以，由此看，总线网络不仅不是完整网络也不是随机网络。从城市交通网络自身的特性来进行了解，发现较小的世界效应都是经过较小的平均站间和较大的聚集度进行反映的。一些研究表明，公交网络是一个小型世界网络，具有通过指数进行分布、明显的社区结构以及较强的通信能力等特点。

为了对公交线网优化中的小世界网络的应用进行研究，对杭州市主城区中心区域公交站点和线路组成的网络进行实例分析。图3见研究区域的公交站点。

在实例分析中，对现有网络进行了抽象描述：（1）将每个车站视为网络中不同的节点;（2）同一条线路作为节点在不同的车站以相同公交站名处理;（3）将公交线路网络中站点间的连接线视为连接网络节点之间的弧线;（4）圆弧两端两个节点和节点间的距离是对圆弧的权重的表示;（5）孤立的车站不存在于公交网络中，因为所有的两个车站都能够被一条或多条线路进行连接，因此网络连接是比较完全的。在上述抽象定义的基础上，通过在杭州主城区中心区布置公交线路和站点，共得到78个节点，即N为78，从而建立了78阶距离矩阵。得到了公交网络的最短路径矩阵。网络系统的全局效率和局部效率分别为0.2864和0.4674。所以，当全局和局部之间的效率越来越接近1时，也是网络整体性能最好的时刻。由于计算结果仍远未达到预期水平，对目前存在的网络进行了重新架构，并通过增加和删除一些总线线路和调整网络节点进行了改进。优化后，总效率为0.4227，局部效率为0.5324，都有一定的提升。公交线网优化的流程图见图4。

4 结论与展望

公交线网优化是系统工程，需要循环往复的进行优化，从而使得在公交线网优化中使用小世界理论给出最直接的参考依据。但是根据本研究所提方法对现有公交线网进行调整涉及方方面面的复杂因素，不一定能起到立竿见影的效果，最多可以给城市交通的管理者提供具有限制的参考价值，因此本研究方法比较适用于新建公交网络的设计。另外在规模较大线网系统中，建立矩阵和计算需要大量的工作量，也可通过对线网系统进行适当分块来解决，怎么样将规模比较大的线网系统进行合理的优化和划分还需要进行深入的探讨。

参考文献：

[1] Christos Valouxis，EfthymiosHousos.Combined bus and driver scheduling.Computer& Operations Research 29，2002：243-259.

[2] WATTS D J， STROGATEZ S H.Collective dynamics of small-world netword[J].Nature，1998，3（5）：393-440.

[3] 樊梦.基于WS小世界网络拓扑特性的自组织PSO算法[J].大众科技，2010（10）：35-37.

[4] 汪小帆，李翔，陈关荣.复杂网络理论及其应用[M].北京：清华大学出版社，2006.

[5] 史路.城市公共交通线路模拟优化[J].公路交通技术，2014（04）：111-118.

【通聯编辑：王力】