一種基于區域規劃換乘點查找的公交換乘方案算法

2018-07-09 12:52:01王杉

科技風 2018年30期

王杉

摘要：該算法針對城市公交路網的特點，充分利用城市公交基礎數據庫，基于對城市公交區域規劃，查找經行起終站點的公交線路的換乘點，根據換乘點類型和數量進行換乘方案的計算，按優化規則換乘方案的優先權值后獲得最優方案。在很大程度上降低了公交換乘算法的時間復雜度，并提高了方案的準確率。

關鍵詞：公交換乘；算法研究

中圖分類號：TP311文獻標識碼：A

1 緒論

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

因此，以昆明市為例，經過對城市公交路網的分析，認為大多數中型規模以上的城市在城市公交路網的建設上都具備較好的規模，公交線路覆蓋率較高，在主城區公交路網輻射范圍內，90%以上的任意兩個站點，最多只需一次換乘即可到達。能保證主城區范圍內任意站點最多兩次換乘可到達。

考慮以上兩個因素，提出一種基于區域規劃換乘點查找的公交換乘方案算法，基于城市公交路網的特點，對路網數據進行分析和整理，實現了較為快速的公交換乘方案查詢。

2 算法思路

設A點為起始點，B點為終到點，A點和B點均有若干線路經過。經過A點的線路設為LA={La1、La2、……LaN}，經過B點的線路設為LB={Lb1、Lb2、……LbN}，且有La∈LA，Lb∈LB，則A點到達B點的路徑有以下三種情況：

① La=Lb，即La與Lb為同一條線路，則表示A點到B點為一線到達，不需要換乘。

② La≠Lb，但La和Lb有交點，即La和Lb至少存在一個相同的經過站點F，此站點即為“換乘點”，那么A點經過La到達F點，再經過Lb到達B點。

③ La和Lb之間沒有交點，即不能通過一次換乘使A點到達B點，那么換乘點數量將會大于等于二。基于實際情況，若換乘點數量大于二，說明該路程較復雜，需要進行2次以上的換乘，總乘坐線路數會在4趟以上，已不適合乘坐公交車，通常建議選擇其他交通方式。因此這里只考慮換乘點數量等于二的情況，即存在C點和D點和線路Lc，并使A點能經過La到達C點，在C點經過Lc到達D點，再從D點經過Lb到達B點。

A點到達B點的路徑上所有經過的站點，計為方案共經站點數PassCount，作為方案性能判斷的主要標準。最終的方案性能將由換乘點數量、共經站點數、換乘點權值、線路權值按規則進行計算。一般情況下，換乘點數和共經站點數少的方案為較優方案。

3 按區域規劃換乘點

通常在中大型城市的建設過程中，城市都會被劃分為區，每個區都會有相應路網的規劃特點。同時，公交線路的設計與運營也是符合區劃與路網特點的。以昆明市為例，城市區劃與公交線路有較鮮明的特征，通過對昆明市300條公交線路及2000個站點進行數據分析，能得出以下幾點結論：

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

·每一個區域都有稱為“公交樞紐點”的站點，這些站點的特點是停靠或行經的線路較多，甚至有個別站點行經了該區域的所有線路。比較典型的例如：黃土坡站、北市區公交樞紐站、金馬坊站、小西門站、東站站、昆明站站、潘家灣站、小菜園立交站等。

·如果在樞紐點進行換乘時，將會有較多的線路進行選擇，能提供更為優化的換乘方案。

因此在本算法中，把公交線路按區域規劃，同時在查找換乘點時對樞紐站進行優先取權計算，可快速地得到換乘方案，并能做到方案的最優性。

4 算法實現

根據算法思路，該算法實現換乘方案計算的核心就在于對換乘點的查找，根據起終站點及經行的線路進行分析，然后判斷換乘點數量，并根據換乘點數量進行換乘方案的計算，最后按優化規則計算換乘方案的優先權值，排序后可獲得最優方案。

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

Step2.獲得行經起點的線路集合QueryLine[]StartQl和行經終點的線路集合QueryLine[]EndQl，對這兩個線路對象數組進行遍歷，判斷線路的換乘點數量

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

{

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

{

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

{換乘點數量為0，一線直達無需要換乘，方案最優，權值為1×PassCount+線路權值}

else

{查找換乘點，聲明QueryCrossSatation對象，請求getCrossSat（）方法，計算換乘點數量}

Step3.若換乘點數量大于0，查找換乘點并計算換乘點數量。首先確定行經起點的線路和行經終點的線路的劃分區域，按區域查找該區域的樞紐站點S，如果行經起點的線路A和行經終點的線路B均通過了該樞紐站點，則換乘點數量為1，需乘線路A在樞紐站點換乘線路B，通過一次換乘到達目的地，此時的方案權值為2×PassCount+線路權值。

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

Step5.進行換乘點查找并獲得方案后，形成方案集合，以方案權值對方案集合進行由小到大的排序，并順序輸出，形成按最優排序的方案。

5 結論與示例

該算法被應用于“昆明市智能公交項目”中，為系統提供了公交換乘方案的查詢。經過三個月的系統試運行，以短信、網頁、APP等方式完成了近14000次公交換乘查詢，得到有效結果的查詢比例為98.7%，查詢的平均響應時間在一秒以內，用戶反應良好。

以下示例展示了兩類有效的公交換乘查詢，得到了準確的結果。

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

·獲得“南屏步行街”應選擇的站點“南屏街東口”，“昆明世博園”應選擇的站點“世博園”；

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

·其中有相同路線71路，因此“南屏街東口”到“世博園”可一線直達，無需任何換乘，此為最優方案：“在“南屏街東口”站乘坐<71路>（回程）至“世博園”站。”

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

·獲得“南屏步行街”應選擇的站點“南屏街西口”，“昆醫附二院”應選擇的站點“西園路口（昆瑞路）”；

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

·其中無相同路線，需要換乘，確定以上線路的區域，并查找區域內的樞紐站，得到結果“小西門”站、“黃土坡”站等。