公交地铁一体化下的网络模型与最优路选择算法

2016-01-15徐勇,贾欣,王哲等

智能系统学报 2015年3期

网络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150526.1415.002.html

徐勇，贾欣，王哲，王翠柳

(河北工业大学理学院，天津 300401)

摘要：公交地铁网络出行线路优选问题是公交网络系统研究的核心问题之一。为此研究了公交地铁一体化条件下的公交网络出行优化模型与算法。构造公交地铁网络的标号模型及映射网络模型，以适当倍数缩小地铁线路上站点之间的权值，进而可将公交与地铁进行一体化处理，缩小后可使地铁线路具有明显的优势以达到优选地铁的目的。运用映射网络图、二分图、半张量积等理论给出了公交地铁一体化网络的最优路选择算法。最后实证了该方法在公交地铁网络线路优选的有效性。

关键词：公交；地铁；最优线路；半张量积；标号；映射网络；二分图

DOI:10.3969/j.issn.1673-4785.201404036

中图分类号：TP18; U491 文献标志码：A

收稿日期：2014-04-18. 网络出版日期：2015-05-26.

基金项目：河北省自然科学基金资助项目(A2013202198)；国家大学生创新创业训练计划项目(201310080030).

作者简介：

中文引用格式：徐勇，贾欣，王哲，等. 公交地铁一体化下的网络模型与最优路选择算法[J]. 智能系统学报, 2015, 10(3): 482-487.

英文引用格式：XU Yong, JIA Xin, WANG Zhe, et al. Transit network models and optimal path selection algorithm for the integrated bus and subway system[J]. CAAI Transactions on Intelligent Systems, 2015, 10(3): 482-487.

Transit network models and optimal path selection algorithm

for the integrated bus and subway system

XU Yong, JIA Xin, WANG Zhe, WANG Cuiliu

(School of Science, Hebei University of Technology, Tianjin 300401, China)

Abstract：In this paper, the travel optimal model and algorithm of public transit network for the integrated bus and subway system are studied. First, a label model and mapped network model are constructed for the bus and subway network. The weight between two subway stations is appropriately reduced to deal with the bus and subway integration problem. The subway has obvious advantages after reduction and subway becomes the preferred option. Next, the optimal path selection algorithm of the integration network of bus and subway is given using the mapping network graph, bipartite graph, and semi-tensor product theory. Finally, the effectiveness of the proposed method in optimized selection of the public transit network is illustrated by a numerical example.

Keywords：public transit; subway; optimal path; semi-tensor product; label; mapping network graph; bipartite graph

通信作者：徐勇. E-mail: xuyong@hebut.edu.cn.

日益现代化的交通方式给人们出行带来很大便利，其中公交与地铁是大型城市中的主要交通工具。考虑到我国人口众多，城市交通拥堵问题日益严重，对公交地铁系统的研究已成为一个热门又困难的课题。公交地铁系统的研究主要包括网络构建、公交配流与最优路选择算法3个方面，而查询算法在其中起到核心作用，它为人们提供出行的路径选择，切身关系到整个公交地铁网络是否高效运作，是公交系统研究的核心问题之一。

目前虽然有一系列针对公交网络的最短路径搜索算法[1-11]，主要包括基于图论的查询算法[1,9]，基于数据库的查询算法[2,5]和基于矩阵运算的查询算法[11]。目前针对地铁主导下的公交网络的最短路径搜索算法却不多见。

考虑到地铁在大城市公交系统中日益占主导地位这一事实，在文献[9]的基础上，将优选地铁出行作为基本出发点，对公交与地铁站点标号的同时，将地铁线路上站点间的权值成倍缩小，再依次按照换乘次数、乘车距离进行路径选择时就达到了优选地铁的目的，且一体化后的模型更加清晰、简便。

1高维数组的表示

S的大小，即S中元素的个数，记作|S|。且|S|=n1×n2×…×nk。

2公交地铁网络优化模型

2.1公交地铁网络图

例如，某公交地铁网络由1条地铁线路、2条公交线路、2个地铁站点(地铁站点都为公交站点)和2个公交站点(不包含前述地铁站点)组成，他们分别为地铁线路L0，公交线路L1、L2，地铁站点S1、S2，公交站点S3、S4，如图1。

图1　公交地铁网络 Fig. 1　Bus and subway network

2.2公交地铁网络的二分图模型

具有2种属性的复杂网络可用二分图表示[14-15].公交地铁网络的站点和线路2种属性决定了它可以反映到二分图上。将顶点集合S看作二分图的上顶点集，线路集合L看作二分图的下顶点集，公交线路L′经过站点S′，则在L′线路与S′站点之间有边相连。图2是图1的公交网络对应的网络二分图。

图2　网络二分图 Fig. 2　Bipartite network graph

由图2看出，S1与S2可直接到达，S1与S3需经过S2转乘，S1与S4需经过S2,S3转乘到达。二分图比网络图更加直观地显示出换乘次数。

2.3公交地铁网络图的映射图

公交地铁网络图的映射图包括线路映射网络图和站点映射网络图，可以由二分图得到。

图3为图2的线路映射网络图，图4为图2的站点映射网络图。由图3可以看出，L1与L0、L2之间分别为一条边，即若出发站点在L1站点上，目的地站点在L0站点或L2站点上，转乘1次公交或者地铁即可到达。若出发站点在L0线路上，目的地站点在L2线路上，则需在L1线路上的某2个站点处转乘，乘坐3次公交或地铁即可到达目的地。由图4可以看出，S1与S2有一条边相连，即两站点在一条线路上，可以直达。S1与S3之间有2条边，且经过S2站点，则从S1站点到达S3站点必须在S2站点转乘，即坐2次公交或地铁到达。S1与S4之间有3条边相连，从图可直接看出，由S1站点出发，需在S2和S3站点转乘，以到达S4站点。

图3　线路映射网络图 Fig. 3　Line mapping network graph

图4　站点映射网络图 Fig. 4　Site mapping network graph

3最优路选择算法

首先对每条线路上的站点进行一体化标号，考虑到地铁的快捷性、准时性、舒适性等优点，优选地铁出行是大势所趋。这样，将地铁线路上两站点间乘车距离权值适当减小，这样就达到了优选地铁出行的目的。

3.1标号公交地铁网络的模型

3.2基于标号网络模型最优路选择的算法

调查表明，在一个成熟的公交地铁网络中，2次换乘可以实现绝大多数出发地与目的地之间的连接。

3.3算法的复杂性分析

4算例

图5　公交地铁网络 Fig. 5　Bus and subway network graph

图6　网络二分图 Fig. 6　Bipartite network

图7　线路映射网络图 Fig. 7　Line mapping network

图8　站点映射网络图 Fig. 8　Site mapping network graph

建立图5的公交地铁网络二分图，如图6。图7为图6的线路映射网络图，图8为图6的站点映射网络图。

可看出，从S1站点到S5站点与从S2站点到S3站点都是经过6站地，而网络图中明显看出S1,S5站点的距离是远远大于S2,S3站点的距离，这是减少地铁站点标号的权值的结果。结果显示出地铁的优越性。

min{6+7+5,1+4+5}=10

对应最优路线为从S4站点乘坐地铁线路L0到达S6站点，转乘公交线路L3到达S8站点，再转乘公交线路L4到达S9站点，途径10站。

5结束语

在文献[10]的基础上，将公交地铁进行一体化标号，缩小地铁两站点间的路径距离以达到优选地铁的目的。据乘客出行心理，依次以换乘次数少、出行距离短为优化目标，利用高维数组运算，根据公交地铁网络图与二分图、线路映射网络图、站点映射网络图得到两站点间的最优路径的选择算法。

公交网络的寻径问题一直以来被认为是NP难问题，而日益发达的公交系统对最优路径选择算法的要求也越来越高。因此，改进和创新算法在整个公交系统中至关重要。本文尚未将地铁的时变性考虑在内，可对此进一步研究，使得人们无论何时出行都有一个对应此时间点的方案，使查询更加精确可靠。

参考文献:

[1]闫小勇, 尚艳亮. 基于二部图模型的公交网络路径搜索算法[J]. 计算机工程与应用, 2010, 46(5): 246-248.

YAN Xiaoyong, SHANG Yanliang. Path-finding algorithm of public transport networks based on bipartite graph model[J]. Computer Engineering and Applications, 2010, 46(5): 246-248.

[2]梁虹, 袁小群, 刘蕊. 一种新的公交数据模型与公交查询系统实现[J]. 计算机工程与应用, 2007, 43(3): 234-238.

LIANG Hong, YUAN Xiaoqun, LIU Rui. Novel model and realization of public transport route inquiring system[J]. Computer Engineering and Applications, 2007, 43(3): 234-238.

[3]王海帅, 冀振燕, 王森. 公交线路查询算法[J]. 计算机系统应用, 2013, 22(2): 88-91.

WANG Haishuai, JI Zhenyan, WANG Sen. Bus transport transfer algorithm[J]. Computer Systems and Applications, 2013, 22(2): 88-91.

[4]王昉旸, 于丽娜, 郑保华, 等. “集合燃烧”算法在公交网络查询中的应用[J]. 辽宁工程技术大学学报: 社会科学版, 2008, 10(4): 380-382.

WANG Fangyang, YU Lina, ZHENG Baohua, et al. “Aggregate-combustion” arithmetic and its application in the query system of transit network[J]. Journal of Liaoning Technical University: Social Science Edition, 2008, 10(4): 380-382.

[5]伍雁鹏, 彭小奇, 杨恒伏. 改进的基于关系数据库技术的公交查询算法[J]. 中南大学学报: 自然科学版, 2009, 40(3): 763-766.

WU Yanpeng, PENG Xiaoqi, YANG Hengfu. Improved algorithm based on relational database technology for querying transit network[J]. Journal of Central South University: Science and Technology, 2009, 40(3): 763-766.

[6]刘健, 徐维祥, 刘旭敏. 公交出行最优路线查询系统设计[J]. 计算机应用, 2009, 29(S2): 110-112.

LIU Jian, XU Weixiang, LIU Xumin. Design of urban public transit optimal route inquiry system[J]. Journal of Computer Applications, 2009, 29(S2): 110-112.

[7]伍雁鹏, 彭小奇, 黄同成. 基于路径集合运算的公交网络寻径算法研究[J]. 计算机科学, 2009, 36(6): 239-240, 272.

WU Yanpeng, PENG Xiaoqi, HUANG Tongcheng. Research on path set operation based algorithm for path searching in public transit network[J]. Computer Science, 2009, 36(6): 239-240, 272.

[8]刘作虎, 黄明和, 邹小云, 等. 一种网络公交查询系统的改进算法[J]. 计算机与信息技术, 2009, (4): 29-31.

[9]徐勇, 李杰, 张军芳, 等. 新型公交网络模型与最优线路选择算法[J]. 系统工程理论与实践, 2011, 31(11): 2234-2240.

XU Yong, LI Jie, ZHANG Junfang, et al. New urban transit network models and optimal path searching algorithm[J]. Systems Engineering—Theory and Practice, 2011, 31(11): 2234-2240.

[10]刘旭浩, 徐勇. 基于半张量积理论的公交网络查询[J]. 复杂系统与复杂性科学, 2013, 10(1): 38-44.

LIU Xuhao, XU Yong. An inquiry method of transit network based on semi-tensor product[J]. Complex Systems and Complexity Science, 2013, 10(1): 38-44.

[11]张林峰, 范炳全, 吕智林. 公交网络换乘矩阵的分析与算法[J]. 系统工程, 2003, 21(6): 92-96.

ZHANG Linfeng, FAN Bingquan, LÜ Zhilin. Transfer matrix of public transit network and algorithm[J]. Systems Engineering, 2003, 21(6): 92-96.

[12]程代展, 齐洪胜. 矩阵的半张量积理论与应用[M]. 北京: 科学出版社, 2007.

[13]YAO Baozhen, HU Ping, LU Xiaohong, et al. Transit network design based on travel time reliability[J]. Transportation Research, Part C: Emerging Technologies, 2014, 43(3): 233-248.

[14]张译, 靳雪翔, 张毅, 等. 基于二分图的城市公交网络拓扑性质研究[J]. 系统工程理论与实践, 2007, 27(7): 149-155.

ZHANG Yi, JIN Xuexiang, ZHANG Yi, et al. Topological analysis of urban transit networks using bipartite graph model[J]. Systems Engineering—Theory & Practice, 2007, 27(7): 149-155.

[15]王炜, 杨新苗, 陈学武. 城市公共交通系统规划方法与管理技术[M]. 北京: 科学出版社, 2002.