一種基于區(qū)域規(guī)劃換乘點(diǎn)查找的公交換乘方案算法

王杉

摘要：該算法針對(duì)城市公交路網(wǎng)的特點(diǎn)，充分利用城市公交基礎(chǔ)數(shù)據(jù)庫(kù)，基于對(duì)城市公交區(qū)域規(guī)劃，查找經(jīng)行起終站點(diǎn)的公交線路的換乘點(diǎn)，根據(jù)換乘點(diǎn)類型和數(shù)量進(jìn)行換乘方案的計(jì)算，按優(yōu)化規(guī)則換乘方案的優(yōu)先權(quán)值后獲得最優(yōu)方案。在很大程度上降低了公交換乘算法的時(shí)間復(fù)雜度，并提高了方案的準(zhǔn)確率。

關(guān)鍵詞：公交換乘；算法研究

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A

1 緒論

公交乘車方案也叫公交換乘方案，主要目的是為用戶提供從甲地到乙地如何乘坐公交車的方案，給用戶出行帶來(lái)方便。一個(gè)城市的公交線路網(wǎng)是一個(gè)典型的圖結(jié)構(gòu)，公交站點(diǎn)作為圖的結(jié)點(diǎn)，站點(diǎn)與站點(diǎn)之間有多條線路相聯(lián)系。從甲地到乙地的公交換乘在圖結(jié)構(gòu)中可描述為兩結(jié)點(diǎn)間最短路徑的查找，其典型算法為求取圖中最短路徑的Dijikstra算法和Floyd算法。此類算法及其改進(jìn)算法都常被用于公交換乘方案的求取。但是，Dijikstra算法和Floyd算法也存在局限性，當(dāng)問(wèn)題規(guī)模較大時(shí)，算法循環(huán)及窮舉次數(shù)較多，其算法的時(shí)間復(fù)雜度高，將會(huì)降低查詢的效率。同時(shí)，求取的路徑雖然是最短路徑，但有可能會(huì)產(chǎn)生多次公交的換乘，這在實(shí)際生活中是完全不適用的。[1][2]

因此，以昆明市為例，經(jīng)過(guò)對(duì)城市公交路網(wǎng)的分析，認(rèn)為大多數(shù)中型規(guī)模以上的城市在城市公交路網(wǎng)的建設(shè)上都具備較好的規(guī)模，公交線路覆蓋率較高，在主城區(qū)公交路網(wǎng)輻射范圍內(nèi)，90%以上的任意兩個(gè)站點(diǎn)，最多只需一次換乘即可到達(dá)。能保證主城區(qū)范圍內(nèi)任意站點(diǎn)最多兩次換乘可到達(dá)。

考慮以上兩個(gè)因素，提出一種基于區(qū)域規(guī)劃換乘點(diǎn)查找的公交換乘方案算法，基于城市公交路網(wǎng)的特點(diǎn)，對(duì)路網(wǎng)數(shù)據(jù)進(jìn)行分析和整理，實(shí)現(xiàn)了較為快速的公交換乘方案查詢。

2 算法思路

設(shè)A點(diǎn)為起始點(diǎn)，B點(diǎn)為終到點(diǎn)，A點(diǎn)和B點(diǎn)均有若干線路經(jīng)過(guò)。經(jīng)過(guò)A點(diǎn)的線路設(shè)為L(zhǎng)A={La1、La2、……LaN}，經(jīng)過(guò)B點(diǎn)的線路設(shè)為L(zhǎng)B={Lb1、Lb2、……LbN}，且有La∈LA，Lb∈LB，則A點(diǎn)到達(dá)B點(diǎn)的路徑有以下三種情況：

① La=Lb，即La與Lb為同一條線路，則表示A點(diǎn)到B點(diǎn)為一線到達(dá)，不需要換乘。

② La≠Lb，但La和Lb有交點(diǎn)，即La和Lb至少存在一個(gè)相同的經(jīng)過(guò)站點(diǎn)F，此站點(diǎn)即為“換乘點(diǎn)”，那么A點(diǎn)經(jīng)過(guò)La到達(dá)F點(diǎn)，再經(jīng)過(guò)Lb到達(dá)B點(diǎn)。

③ La和Lb之間沒(méi)有交點(diǎn)，即不能通過(guò)一次換乘使A點(diǎn)到達(dá)B點(diǎn)，那么換乘點(diǎn)數(shù)量將會(huì)大于等于二?；趯?shí)際情況，若換乘點(diǎn)數(shù)量大于二，說(shuō)明該路程較復(fù)雜，需要進(jìn)行2次以上的換乘，總乘坐線路數(shù)會(huì)在4趟以上，已不適合乘坐公交車，通常建議選擇其他交通方式。因此這里只考慮換乘點(diǎn)數(shù)量等于二的情況，即存在C點(diǎn)和D點(diǎn)和線路Lc，并使A點(diǎn)能經(jīng)過(guò)La到達(dá)C點(diǎn)，在C點(diǎn)經(jīng)過(guò)Lc到達(dá)D點(diǎn)，再?gòu)腄點(diǎn)經(jīng)過(guò)Lb到達(dá)B點(diǎn)。

A點(diǎn)到達(dá)B點(diǎn)的路徑上所有經(jīng)過(guò)的站點(diǎn)，計(jì)為方案共經(jīng)站點(diǎn)數(shù)PassCount，作為方案性能判斷的主要標(biāo)準(zhǔn)。最終的方案性能將由換乘點(diǎn)數(shù)量、共經(jīng)站點(diǎn)數(shù)、換乘點(diǎn)權(quán)值、線路權(quán)值按規(guī)則進(jìn)行計(jì)算。一般情況下，換乘點(diǎn)數(shù)和共經(jīng)站點(diǎn)數(shù)少的方案為較優(yōu)方案。

3 按區(qū)域規(guī)劃換乘點(diǎn)

通常在中大型城市的建設(shè)過(guò)程中，城市都會(huì)被劃分為區(qū)，每個(gè)區(qū)都會(huì)有相應(yīng)路網(wǎng)的規(guī)劃特點(diǎn)。同時(shí)，公交線路的設(shè)計(jì)與運(yùn)營(yíng)也是符合區(qū)劃與路網(wǎng)特點(diǎn)的。以昆明市為例，城市區(qū)劃與公交線路有較鮮明的特征，通過(guò)對(duì)昆明市300條公交線路及2000個(gè)站點(diǎn)進(jìn)行數(shù)據(jù)分析，能得出以下幾點(diǎn)結(jié)論：

·公交運(yùn)營(yíng)線路有區(qū)域性，每一條線路都可以分析出其行駛的主要區(qū)域。按公交路網(wǎng)的運(yùn)行區(qū)劃昆明市可劃分為9個(gè)區(qū)域。為：北市區(qū)片區(qū)（北區(qū)）、東站片區(qū)（東區(qū)）、滇池路片區(qū)（南區(qū)1）、關(guān)上片區(qū)（南區(qū)2）、梁家河片區(qū)（西區(qū)1）、眠山片區(qū)（西區(qū)2）、市中心1區(qū)、市中心2區(qū)、呈貢新區(qū)。

·每一個(gè)區(qū)域都有稱為“公交樞紐點(diǎn)”的站點(diǎn)，這些站點(diǎn)的特點(diǎn)是?？炕蛐薪?jīng)的線路較多，甚至有個(gè)別站點(diǎn)行經(jīng)了該區(qū)域的所有線路。比較典型的例如：黃土坡站、北市區(qū)公交樞紐站、金馬坊站、小西門(mén)站、東站站、昆明站站、潘家灣站、小菜園立交站等。

·如果在樞紐點(diǎn)進(jìn)行換乘時(shí)，將會(huì)有較多的線路進(jìn)行選擇，能提供更為優(yōu)化的換乘方案。

因此在本算法中，把公交線路按區(qū)域規(guī)劃，同時(shí)在查找換乘點(diǎn)時(shí)對(duì)樞紐站進(jìn)行優(yōu)先取權(quán)計(jì)算，可快速地得到換乘方案，并能做到方案的最優(yōu)性。

4 算法實(shí)現(xiàn)

根據(jù)算法思路，該算法實(shí)現(xiàn)換乘方案計(jì)算的核心就在于對(duì)換乘點(diǎn)的查找，根據(jù)起終站點(diǎn)及經(jīng)行的線路進(jìn)行分析，然后判斷換乘點(diǎn)數(shù)量，并根據(jù)換乘點(diǎn)數(shù)量進(jìn)行換乘方案的計(jì)算，最后按優(yōu)化規(guī)則計(jì)算換乘方案的優(yōu)先權(quán)值，排序后可獲得最優(yōu)方案。

Step1.確定查詢的起始站點(diǎn)和終到站點(diǎn)（如果客戶端提交的是“地點(diǎn)——地點(diǎn)”，那么通過(guò)地點(diǎn)信息查詢獲得地點(diǎn)周邊的站點(diǎn)，再把這些站點(diǎn)作為查詢的起始站點(diǎn)和終到站點(diǎn)）。聲明QueryStation類型的起始站點(diǎn)對(duì)象StartSat和終到站點(diǎn)對(duì)象EndSat

Step2.獲得行經(jīng)起點(diǎn)的線路集合QueryLine[]StartQl和行經(jīng)終點(diǎn)的線路集合QueryLine[]EndQl，對(duì)這兩個(gè)線路對(duì)象數(shù)組進(jìn)行遍歷，判斷線路的換乘點(diǎn)數(shù)量

for（int i = 0； i < StartQl.Length； i++）

{

for（intj = 0； j < EndQl.Length； j++）

{

if（StartQl[i]== EndQl[j]）

{換乘點(diǎn)數(shù)量為0，一線直達(dá)無(wú)需要換乘，方案最優(yōu)，權(quán)值為1×PassCount+線路權(quán)值}

else

{查找換乘點(diǎn)，聲明QueryCrossSatation對(duì)象，請(qǐng)求getCrossSat（）方法，計(jì)算換乘點(diǎn)數(shù)量}

Step3.若換乘點(diǎn)數(shù)量大于0，查找換乘點(diǎn)并計(jì)算換乘點(diǎn)數(shù)量。首先確定行經(jīng)起點(diǎn)的線路和行經(jīng)終點(diǎn)的線路的劃分區(qū)域，按區(qū)域查找該區(qū)域的樞紐站點(diǎn)S，如果行經(jīng)起點(diǎn)的線路A和行經(jīng)終點(diǎn)的線路B均通過(guò)了該樞紐站點(diǎn)，則換乘點(diǎn)數(shù)量為1，需乘線路A在樞紐站點(diǎn)換乘線路B，通過(guò)一次換乘到達(dá)目的地，此時(shí)的方案權(quán)值為2×PassCount+線路權(quán)值。

Step4.若在上一步中行經(jīng)起點(diǎn)的線路A和行經(jīng)終點(diǎn)的線路B沒(méi)有共同經(jīng)過(guò)任何站點(diǎn)，也即兩條線路無(wú)交點(diǎn)，那么意味著起點(diǎn)和終點(diǎn)間將需要進(jìn)行多次換乘，換乘點(diǎn)數(shù)量大于1。首先首先確定行經(jīng)起點(diǎn)的線路A和行經(jīng)終點(diǎn)的線路B的劃分區(qū)域，分別查找區(qū)域內(nèi)的線路A經(jīng)過(guò)的樞紐站點(diǎn)Sa和線路B經(jīng)過(guò)的樞紐站點(diǎn)Sb。然后再確定樞紐站點(diǎn)Sa與樞紐站點(diǎn)Sb之間的線路C，若C存在，那么方案為在起點(diǎn)乘線路A到達(dá)站點(diǎn)Sa，換乘線路C到達(dá)站點(diǎn)Sb，再換乘線路B到達(dá)終點(diǎn)，此時(shí)換乘點(diǎn)數(shù)量為2，方案權(quán)值為3×PassCount+線路權(quán)值。若線路C不存在，則表示起點(diǎn)至終點(diǎn)需要經(jīng)過(guò)3次以上的換乘才能到達(dá)，已不適合選擇共交車方式，查詢返回方案無(wú)法確定的消息，客戶端會(huì)建議用戶選擇其他的交通出行方式。

Step5.進(jìn)行換乘點(diǎn)查找并獲得方案后，形成方案集合，以方案權(quán)值對(duì)方案集合進(jìn)行由小到大的排序，并順序輸出，形成按最優(yōu)排序的方案。

5 結(jié)論與示例

該算法被應(yīng)用于“昆明市智能公交項(xiàng)目”中，為系統(tǒng)提供了公交換乘方案的查詢。經(jīng)過(guò)三個(gè)月的系統(tǒng)試運(yùn)行，以短信、網(wǎng)頁(yè)、APP等方式完成了近14000次公交換乘查詢，得到有效結(jié)果的查詢比例為98.7%，查詢的平均響應(yīng)時(shí)間在一秒以內(nèi)，用戶反應(yīng)良好。

以下示例展示了兩類有效的公交換乘查詢，得到了準(zhǔn)確的結(jié)果。

①查詢“南屏步行街”到“昆明世博園”：

·獲得“南屏步行街”應(yīng)選擇的站點(diǎn)“南屏街東口”，“昆明世博園”應(yīng)選擇的站點(diǎn)“世博園”；

·行經(jīng)“南屏街東口”的線路有71路、108路、118路，行經(jīng)“世博園”的線路有47、69、71、95、182、194、A1等線路。

·其中有相同路線71路，因此“南屏街東口”到“世博園”可一線直達(dá)，無(wú)需任何換乘，此為最優(yōu)方案：“在“南屏街東口”站乘坐<71路>（回程）至“世博園”站?！?/p>

②查詢“南屏步行街”到“昆醫(yī)附二院”：

·獲得“南屏步行街”應(yīng)選擇的站點(diǎn)“南屏街西口”，“昆醫(yī)附二院”應(yīng)選擇的站點(diǎn)“西園路口（昆瑞路）”；

·行經(jīng)“南屏街西口”的線路有10路、82路、84路，行經(jīng)“西園路口（昆瑞路）”的線路有26、55、90、106、113、127路。

·其中無(wú)相同路線，需要換乘，確定以上線路的區(qū)域，并查找區(qū)域內(nèi)的樞紐站，得到結(jié)果“小西門(mén)”站、“黃土坡”站等。

·通過(guò)計(jì)算發(fā)現(xiàn)10路和26路均經(jīng)行“小西門(mén)”站，因此選擇“小西門(mén)”站作為換乘點(diǎn)，得到最優(yōu)方案：“在‘南屏街西口站乘坐<10路>（去程）至‘小西門(mén)站，換乘<26路>（回程）至‘西園路口（昆瑞路）站。”

以上的示例是基于昆明市的公交路網(wǎng)數(shù)據(jù)庫(kù)，如果對(duì)其他城市的公交路網(wǎng)數(shù)據(jù)進(jìn)行分析與整理，本算法也可適用于其他類似大中型城市的公交換乘方案查詢。

參考文獻(xiàn)：

[1]韓慧玲，胡紅萍.公交換乘最短路徑算法研究[J].硅谷，2012（4）：9192.

[2]高嵐.一種改進(jìn)的最短路徑算法在公交查詢系統(tǒng)中的應(yīng)用研究[J].科技視界，2015（25）：33.