公交地鐵一體化下的網(wǎng)絡(luò)模型與最優(yōu)路選擇算法

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150526.1415.002.html

公交地鐵一體化下的網(wǎng)絡(luò)模型與最優(yōu)路選擇算法

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

(河北工業(yè)大學(xué) 理學(xué)院，天津 300401)

摘要：公交地鐵網(wǎng)絡(luò)出行線路優(yōu)選問(wèn)題是公交網(wǎng)絡(luò)系統(tǒng)研究的核心問(wèn)題之一。為此研究了公交地鐵一體化條件下的公交網(wǎng)絡(luò)出行優(yōu)化模型與算法。構(gòu)造公交地鐵網(wǎng)絡(luò)的標(biāo)號(hào)模型及映射網(wǎng)絡(luò)模型，以適當(dāng)倍數(shù)縮小地鐵線路上站點(diǎn)之間的權(quán)值，進(jìn)而可將公交與地鐵進(jìn)行一體化處理，縮小后可使地鐵線路具有明顯的優(yōu)勢(shì)以達(dá)到優(yōu)選地鐵的目的。運(yùn)用映射網(wǎng)絡(luò)圖、二分圖、半張量積等理論給出了公交地鐵一體化網(wǎng)絡(luò)的最優(yōu)路選擇算法。最后實(shí)證了該方法在公交地鐵網(wǎng)絡(luò)線路優(yōu)選的有效性。

關(guān)鍵詞：公交；地鐵；最優(yōu)線路；半張量積；標(biāo)號(hào)；映射網(wǎng)絡(luò)；二分圖

DOI:10.3969/j.issn.1673-4785.201404036

中圖分類號(hào)：TP18; U491 文獻(xiàn)標(biāo)志碼：A

收稿日期：2014-04-18. 網(wǎng)絡(luò)出版日期：2015-05-26.

基金項(xiàng)目：河北省自然科學(xué)基金資助項(xiàng)目(A2013202198)；國(guó)家大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目(201310080030).

作者簡(jiǎn)介：

中文引用格式：徐勇，賈欣，王哲，等. 公交地鐵一體化下的網(wǎng)絡(luò)模型與最優(yōu)路選擇算法[J]. 智能系統(tǒng)學(xué)報(bào), 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.

日益現(xiàn)代化的交通方式給人們出行帶來(lái)很大便利，其中公交與地鐵是大型城市中的主要交通工具?？紤]到我國(guó)人口眾多，城市交通擁堵問(wèn)題日益嚴(yán)重，對(duì)公交地鐵系統(tǒng)的研究已成為一個(gè)熱門又困難的課題。公交地鐵系統(tǒng)的研究主要包括網(wǎng)絡(luò)構(gòu)建、公交配流與最優(yōu)路選擇算法3個(gè)方面，而查詢算法在其中起到核心作用，它為人們提供出行的路徑選擇，切身關(guān)系到整個(gè)公交地鐵網(wǎng)絡(luò)是否高效運(yùn)作，是公交系統(tǒng)研究的核心問(wèn)題之一。

目前雖然有一系列針對(duì)公交網(wǎng)絡(luò)的最短路徑搜索算法[1-11]，主要包括基于圖論的查詢算法[1,9]，基于數(shù)據(jù)庫(kù)的查詢算法[2,5]和基于矩陣運(yùn)算的查詢算法[11]。目前針對(duì)地鐵主導(dǎo)下的公交網(wǎng)絡(luò)的最短路徑搜索算法卻不多見。

考慮到地鐵在大城市公交系統(tǒng)中日益占主導(dǎo)地位這一事實(shí)，在文獻(xiàn)[9]的基礎(chǔ)上，將優(yōu)選地鐵出行作為基本出發(fā)點(diǎn)，對(duì)公交與地鐵站點(diǎn)標(biāo)號(hào)的同時(shí)，將地鐵線路上站點(diǎn)間的權(quán)值成倍縮小，再依次按照換乘次數(shù)、乘車距離進(jìn)行路徑選擇時(shí)就達(dá)到了優(yōu)選地鐵的目的，且一體化后的模型更加清晰、簡(jiǎn)便。

1高維數(shù)組的表示

S的大小，即S中元素的個(gè)數(shù)，記作|S|。且|S|=n1×n2×…×nk。

2公交地鐵網(wǎng)絡(luò)優(yōu)化模型

2.1公交地鐵網(wǎng)絡(luò)圖

例如，某公交地鐵網(wǎng)絡(luò)由1條地鐵線路、2條公交線路、2個(gè)地鐵站點(diǎn)(地鐵站點(diǎn)都為公交站點(diǎn))和2個(gè)公交站點(diǎn)(不包含前述地鐵站點(diǎn))組成，他們分別為地鐵線路L0，公交線路L1、L2，地鐵站點(diǎn)S1、S2，公交站點(diǎn)S3、S4，如圖1。

圖1　公交地鐵網(wǎng)絡(luò) Fig. 1　Bus and subway network

2.2公交地鐵網(wǎng)絡(luò)的二分圖模型

具有2種屬性的復(fù)雜網(wǎng)絡(luò)可用二分圖表示[14-15].公交地鐵網(wǎng)絡(luò)的站點(diǎn)和線路2種屬性決定了它可以反映到二分圖上。將頂點(diǎn)集合S看作二分圖的上頂點(diǎn)集，線路集合L看作二分圖的下頂點(diǎn)集，公交線路L′經(jīng)過(guò)站點(diǎn)S′，則在L′線路與S′站點(diǎn)之間有邊相連。圖2是圖1的公交網(wǎng)絡(luò)對(duì)應(yīng)的網(wǎng)絡(luò)二分圖。

圖2　網(wǎng)絡(luò)二分圖 Fig. 2　Bipartite network graph

由圖2看出，S1與S2可直接到達(dá)，S1與S3需經(jīng)過(guò)S2轉(zhuǎn)乘，S1與S4需經(jīng)過(guò)S2,S3轉(zhuǎn)乘到達(dá)。二分圖比網(wǎng)絡(luò)圖更加直觀地顯示出換乘次數(shù)。

2.3公交地鐵網(wǎng)絡(luò)圖的映射圖

公交地鐵網(wǎng)絡(luò)圖的映射圖包括線路映射網(wǎng)絡(luò)圖和站點(diǎn)映射網(wǎng)絡(luò)圖，可以由二分圖得到。

圖3為圖2的線路映射網(wǎng)絡(luò)圖，圖4為圖2的站點(diǎn)映射網(wǎng)絡(luò)圖。由圖3可以看出，L1與L0、L2之間分別為一條邊，即若出發(fā)站點(diǎn)在L1站點(diǎn)上，目的地站點(diǎn)在L0站點(diǎn)或L2站點(diǎn)上，轉(zhuǎn)乘1次公交或者地鐵即可到達(dá)。若出發(fā)站點(diǎn)在L0線路上，目的地站點(diǎn)在L2線路上，則需在L1線路上的某2個(gè)站點(diǎn)處轉(zhuǎn)乘，乘坐3次公交或地鐵即可到達(dá)目的地。由圖4可以看出，S1與S2有一條邊相連，即兩站點(diǎn)在一條線路上，可以直達(dá)。S1與S3之間有2條邊，且經(jīng)過(guò)S2站點(diǎn)，則從S1站點(diǎn)到達(dá)S3站點(diǎn)必須在S2站點(diǎn)轉(zhuǎn)乘，即坐2次公交或地鐵到達(dá)。S1與S4之間有3條邊相連，從圖可直接看出，由S1站點(diǎn)出發(fā)，需在S2和S3站點(diǎn)轉(zhuǎn)乘，以到達(dá)S4站點(diǎn)。

圖3　線路映射網(wǎng)絡(luò)圖 Fig. 3　Line mapping network graph

圖4　站點(diǎn)映射網(wǎng)絡(luò)圖 Fig. 4　Site mapping network graph

3最優(yōu)路選擇算法

首先對(duì)每條線路上的站點(diǎn)進(jìn)行一體化標(biāo)號(hào)，考慮到地鐵的快捷性、準(zhǔn)時(shí)性、舒適性等優(yōu)點(diǎn)，優(yōu)選地鐵出行是大勢(shì)所趨。這樣，將地鐵線路上兩站點(diǎn)間乘車距離權(quán)值適當(dāng)減小，這樣就達(dá)到了優(yōu)選地鐵出行的目的。

3.1標(biāo)號(hào)公交地鐵網(wǎng)絡(luò)的模型

3.2基于標(biāo)號(hào)網(wǎng)絡(luò)模型最優(yōu)路選擇的算法

調(diào)查表明，在一個(gè)成熟的公交地鐵網(wǎng)絡(luò)中，2次換乘可以實(shí)現(xiàn)絕大多數(shù)出發(fā)地與目的地之間的連接。

3.3算法的復(fù)雜性分析

4算例

圖5　公交地鐵網(wǎng)絡(luò) Fig. 5　Bus and subway network graph

圖6　網(wǎng)絡(luò)二分圖 Fig. 6　Bipartite network

圖7　線路映射網(wǎng)絡(luò)圖 Fig. 7　Line mapping network

圖8　站點(diǎn)映射網(wǎng)絡(luò)圖 Fig. 8　Site mapping network graph

建立圖5的公交地鐵網(wǎng)絡(luò)二分圖，如圖6。圖7為圖6的線路映射網(wǎng)絡(luò)圖，圖8為圖6的站點(diǎn)映射網(wǎng)絡(luò)圖。

可看出，從S1站點(diǎn)到S5站點(diǎn)與從S2站點(diǎn)到S3站點(diǎn)都是經(jīng)過(guò)6站地，而網(wǎng)絡(luò)圖中明顯看出S1,S5站點(diǎn)的距離是遠(yuǎn)遠(yuǎn)大于S2,S3站點(diǎn)的距離，這是減少地鐵站點(diǎn)標(biāo)號(hào)的權(quán)值的結(jié)果。結(jié)果顯示出地鐵的優(yōu)越性。

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

對(duì)應(yīng)最優(yōu)路線為從S4站點(diǎn)乘坐地鐵線路L0到達(dá)S6站點(diǎn)，轉(zhuǎn)乘公交線路L3到達(dá)S8站點(diǎn)，再轉(zhuǎn)乘公交線路L4到達(dá)S9站點(diǎn)，途徑10站。

5結(jié)束語(yǔ)

在文獻(xiàn)[10]的基礎(chǔ)上，將公交地鐵進(jìn)行一體化標(biāo)號(hào)，縮小地鐵兩站點(diǎn)間的路徑距離以達(dá)到優(yōu)選地鐵的目的。據(jù)乘客出行心理，依次以換乘次數(shù)少、出行距離短為優(yōu)化目標(biāo)，利用高維數(shù)組運(yùn)算，根據(jù)公交地鐵網(wǎng)絡(luò)圖與二分圖、線路映射網(wǎng)絡(luò)圖、站點(diǎn)映射網(wǎng)絡(luò)圖得到兩站點(diǎn)間的最優(yōu)路徑的選擇算法。

公交網(wǎng)絡(luò)的尋徑問(wèn)題一直以來(lái)被認(rèn)為是NP難問(wèn)題，而日益發(fā)達(dá)的公交系統(tǒng)對(duì)最優(yōu)路徑選擇算法的要求也越來(lái)越高。因此，改進(jìn)和創(chuàng)新算法在整個(gè)公交系統(tǒng)中至關(guān)重要。本文尚未將地鐵的時(shí)變性考慮在內(nèi)，可對(duì)此進(jìn)一步研究，使得人們無(wú)論何時(shí)出行都有一個(gè)對(duì)應(yīng)此時(shí)間點(diǎn)的方案，使查詢更加精確可靠。

參考文獻(xiàn):

[1]閆小勇, 尚艷亮. 基于二部圖模型的公交網(wǎng)絡(luò)路徑搜索算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 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]梁虹, 袁小群, 劉蕊. 一種新的公交數(shù)據(jù)模型與公交查詢系統(tǒng)實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程與應(yīng)用, 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]. 計(jì)算機(jī)系統(tǒng)應(yīng)用, 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]王昉旸, 于麗娜, 鄭保華, 等. “集合燃燒”算法在公交網(wǎng)絡(luò)查詢中的應(yīng)用[J]. 遼寧工程技術(shù)大學(xué)學(xué)報(bào): 社會(huì)科學(xué)版, 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ìn)的基于關(guān)系數(shù)據(jù)庫(kù)技術(shù)的公交查詢算法[J]. 中南大學(xué)學(xué)報(bào): 自然科學(xué)版, 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]劉健, 徐維祥, 劉旭敏. 公交出行最優(yōu)路線查詢系統(tǒng)設(shè)計(jì)[J]. 計(jì)算機(jī)應(yīng)用, 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]伍雁鵬, 彭小奇, 黃同成. 基于路徑集合運(yùn)算的公交網(wǎng)絡(luò)尋徑算法研究[J]. 計(jì)算機(jī)科學(xué), 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]劉作虎, 黃明和, 鄒小云, 等. 一種網(wǎng)絡(luò)公交查詢系統(tǒng)的改進(jìn)算法[J]. 計(jì)算機(jī)與信息技術(shù), 2009, (4): 29-31.

[9]徐勇, 李杰, 張軍芳, 等. 新型公交網(wǎng)絡(luò)模型與最優(yōu)線路選擇算法[J]. 系統(tǒng)工程理論與實(shí)踐, 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]劉旭浩, 徐勇. 基于半張量積理論的公交網(wǎng)絡(luò)查詢[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 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]張林峰, 范炳全, 呂智林. 公交網(wǎng)絡(luò)換乘矩陣的分析與算法[J]. 系統(tǒng)工程, 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]程代展, 齊洪勝. 矩陣的半張量積理論與應(yīng)用[M]. 北京: 科學(xué)出版社, 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]張譯, 靳雪翔, 張毅, 等. 基于二分圖的城市公交網(wǎng)絡(luò)拓?fù)湫再|(zhì)研究[J]. 系統(tǒng)工程理論與實(shí)踐, 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]王煒, 楊新苗, 陳學(xué)武. 城市公共交通系統(tǒng)規(guī)劃方法與管理技術(shù)[M]. 北京: 科學(xué)出版社, 2002.

徐勇，男，1971年生，教授，博士，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)建模與優(yōu)化。參與或主持省部級(jí)科研項(xiàng)目10余項(xiàng)，發(fā)表學(xué)術(shù)論文30余篇，其中被EI檢索10余篇。

賈欣，女，1991年生，主要研究方向?yàn)閳D論與交通網(wǎng)絡(luò)優(yōu)化。

王哲，男，1990年生，主要研究方向?yàn)閳D論與交通網(wǎng)絡(luò)優(yōu)化。