文章快速检索 高级检索

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.
Key words: public transit     subway     optimal path     semi-tensor product     label     mapping network graph     bipartite graph

1 高维数组的表示

S={Si1,i2,…,ik|i1=1,2,…,n1;…;ik=1,2,…,nk}

S的大小，即S中元素的个数，记作|S|。且|S|=n1×n2×…×nk
σ(1),σ(2),…,σ(k)是1,2,…,k的一个排列，若它能排成一个

nσt×nσ1nσt－1nσt+1nσk

2 公交地铁网络优化模型 2.1 公交地铁网络图

 图 1 公交地铁网络 Fig. 1 Bus and subway network
2.2 公交地铁网络的二分图模型

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

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

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

 图 4 站点映射网络图 Fig. 4 Site mapping network graph
3 最优路选择算法

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

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

1)给出任两站点SiSj，构造直达检验向量αij=Weiej，其中W=[wi,jk]n×n×mei表示第i个元素为1，其余全为0的n维单位向量，若αij=(wi,j1,wi,j2,…,wi,jm)|T≠0，则Si站点与Sj站点可以直达，若v=arg{wi,jk}，则wi,jvSiSj站点之间的最小直达距离，最优路径为Lv

2)若Si站点与Sj站点不可直达，根据站点映射网络图，记与Si站点邻接的站点集合Si={Si1,Si2,…,Sik}与Sj站点邻接的站点集合Sj={Sj1,Sj2,…,Sjl}，若SiSj≠∅，则表示Si站点与Sj站点转乘一次可到达，记SiSj={Sr1,Sr2,…,Srp}，则SiSj可经p种方法到达，则d(Si,Sj)=min{wi,rl+wr,jl}，LlL,Ll′∈L′，根据公交网络二分图，LL′分别为连接SiSrSrSj站点的线路，其对应的路线为最优出行路线。

3)若SiSj=∅，即一次转乘不可达，则检验SiSj中有无可直达的两站点，若N(Sip)∩N(Sjq)≠∅，SipSiSjqSj，则站点Sip与站点Sjq之间有直达线路，d(Si,Sj)=min{wi,ipl1+wip,jql2+wjq,jl3}，Ll1L1Ll2L2Ll3L3，其中L1L2L3根据公交地铁网络二分图确定，且L1L2L3分别为连接SiSipSipSjqSjqSj站点的线路，其对应方案为最优出行方案。

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

1)考虑站点S2到站点S3的最短路问题，构造直达检验向量α23=We2e3,可得到α23=(w2,30,w2,31,w2,32,w2,33,w2,34)T≠0，若v=arg{w2,3k}=1，即w2,31=6为最小直达距离，L1为所选乘车路线，途径6站。

2)考虑站点S1到站点S5的最短路问题，α15=We1e5=0，即不可直达，根据站点网络映射图，如图 8，得到与S1站点邻接的站点集合S1={S2,S3,S4,S6}，与S5站点邻接的站点集合S5={S3,S4,S6,S7,S8}，由于S1S5≠∅，表示S1站点与S5站点转乘1次可到达。又S1S5={S3,S4,S6}，则S1站点与S5站点可经3种1次转乘的方案到达，d(S1,S5)=min{w1,31+w3,52,w1,40+w4,52,w1,60+w6,53}=min{9+3,2+6,3+3}=6，对应最优路径为从S1站点乘坐地铁线路L0到达S6站点，转乘公交线路L3到达S5站点，途经6站。

3)考虑站点S4到站点S9的最短路问题，S4在线路L0与线路L2上，S9在线路L4上，α49=We4e9=0，即不可直达，S4={S1,S3,S5,S6,S7},S9={S8}，S4S9=∅，即1次转乘不可达。下面考虑2次转乘的情况，根据线路网络映射图，L0L2线路与L4线路之间有L3连接，即从L0线路或L2线路需转乘L3到线路上，再转乘到L4线路上。

d(S4,S9)=min{w4,52+w5,83+w8,94,w4,60+w6,83+w8,94}=min{6+7+5,1+4+5}=10

5 结束语

 [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, LV 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.
DOI: 10.3969/j.issn.1673-4785.201404036

0

#### 文章信息

XU Yong, JIA Xin, WANG Zhe, WANG Cuiliu

Transit network models and optimal path selection algorithm for the integrated bus and subway system

CAAI Transactions on Intelligent Systems, 2015, 10(03): 482-487.
DOI: 10.3969/j.issn.1673-4785.201404036