基于浮動車數據的公交車路線規劃研究與實現

林　娜　李建明

(沈陽航空航天大學計算機學院　遼寧 沈陽 110136)

?

基于浮動車數據的公交車路線規劃研究與實現

林娜李建明

(沈陽航空航天大學計算機學院遼寧 沈陽 110136)

公交路線規劃的傳統方法主要是依靠人力調查，雖然這種方法被證明是可行的，但在這期間花費了大量的人力和物力。此外，這種方法也不適應城市的快速發展所導致的路網頻繁變化。針對這種情況，根據收集到大量的出租車GPS數據，提出一種夜間公交車路線規劃方法。主要包括三個部分：首先，在提取有效軌跡數據的基礎上，找出聚集區確定候選車站集。然后，設定規則把復雜的候選車站集簡化為有效公交車路線集。最后，提出兩種算法選取最為理想的一條路線。結果表明，相關性啟發式搜索算法得到的路線綜合考慮候選車站間的相關性，是在規定時間內載客量最大的路線。

浮動車數據候選車站集公交車路線集相關性啟發式搜索算法

0　引　言

在各個城市中，公交車出行是一種便利經濟的出行方式，與其他出行方式相比而言，使用公交車出行更加綠色環保，因為它有助于減少交通擁堵，降低燃料消耗、出行費用以及尾氣的排放。因此為了城市的可持續發展，鼓勵人們盡量選擇公交車出行[1-3]。白天的公交路線是由交通部門考慮各方面因素的基礎上精心設計而成，然而在深夜，大多數公交車是不出行的，私家車和出租車成了主流的出行方式。為了給市民提供便利的交通條件，對設計出交通便利的公交車路線提出了需求[4]。現在公路上有到處可見的出租車，它們一般裝有GPS設備和無線通信設備，從而可以收集到大量乘客乘坐出租車的GPS信息。通過這些GPS數據可以獲得出租車的行駛路線、出發地、目的地、行駛速度、運行狀態等[5]。如果對這些數據進行提取、分析、挖掘，就可以了解到人群的出行和流動規律，這就為規劃出合理的公交車路線提供了可能性。

本文主要包括兩部分：第一部分是候選車站集合的選取。因為乘客的上下車地點是隨機分布的，但某些地點分布是相對集中的。這里沒有提供一個明確的方式對這些地點標出，因此要尋求一個方法，通過GPS 的出租車軌跡集去尋找候選車站集。第二部分就是以出發地為起始點從候選車站集里篩選出合適的路線到達目的點。因為篩選出的候選車站很多且分布也很廣，需要定義出很多規則提取從出發地到目的地有效的候選車站，使它們組成一個有向無循環的路徑圖，這樣就把問題簡化成在這個有向無循環圖上找出使用時間、最少載客量最多的路徑問題[6,7]。以前這方面的算法主要有手工統計方法和k-means方法等，本文提出了相關性啟發式搜索算法(SXQ)和基于貝葉斯搜索算法(BYS)。它們結合了相關性算法和啟發式算法的優點，能夠準確方便找出理想的公交車路線。

1　技術路線

1.1數據的預處理

由于 GPS 衛星定位、大氣層、操作錯誤和 GPS 設備等因素的影響，所獲取的 GPS 原始數據存在較大的誤差[8]。利用這種原始數據處理得到的交通信息質量必然較差，因此需要對原始的 GPS 數據進行預處理。現有的 GPS 數據預處理方法大多是針對 GPS 系統原理進行數據的識別與修復，將在此基礎上充分考慮已有 GPS 數據特點和車輛運行狀態進行數據優化，以達到更好的預處理目的。出租車GPS產生誤差的原因很多，主要有：GPS設備故障，一段時間內返回相同數據，或者返回數據錯誤；障礙物遮擋信號，主要原因是被高層建筑物遮擋或者進入停車場或隧道導致信號中斷；人為原因，出租車司機在短時間內重復打表，產生重復無效的數據；另外可能還有其他方面的原因，這里不再逐一列舉。在篩選過程中主要針對：一是經緯度數據顯示越界，本文用的是北京市地圖數據，北京市的經緯度坐標范圍是北緯39°28′～41°05′，東經115°25′～117°35′。所以，不在該范圍內的數據，都是不符合要求的數據，應該予以去除。二是車輛靜止。車輛靜止需要對此類數據進行分析，將原數據排序，排序第一要素為車輛ID升序排列，第二要素為GPS時間升序排列，也就是將GPS瞬時速度持續為零的剔除。三是車輛持續空載，也就是車輛運營狀態長時間靜止或者空車運行。這部分數據也是沒有意義的。另外就是短時間經緯度跳躍過大。通過投影計算，如果短時間行駛的距離過大，這部分是錯誤的數據[9-12]。

1.2確定候選車站

在夜間公交車路線規劃過程當中，首先利用乘客的上下車記錄數(PDR)確定候選車站集，整個過程包括三步：(1) 根據乘客的上下車記錄數把整個城市劃分成許多大小相等的網格單元，這些網格單元為以后的應用做準備；(2) 合并鄰近的網格單元形成“熱點“區域，如果區域過大則將其劃分成合適大小的聚集區；(3) 然后在聚集區內找到一個合適網格單元作為候選車站，假設周圍的地區能夠容易到達這個候選車站。

1.2.1網格單元與城市劃分

在這步工作中，把整個城市劃分成許多大小相等的網格單元，每個網格的大小是100 m×100 m。用這個方法，整個城市總共被劃分成6000×3000個網格。在所有的網格之外，超過95%的地方是沒有出租車乘客上下車記錄的，它們可能是湖泊、山脈、建筑物或高速公路，出租車不能到達或者停車，或者是城郊市民很少到這些地方。如果只記錄深夜的時間段，這里面僅僅有0.11%平均每小時上下車記錄數超過0.2，因此取名這些網格單元為“熱點”網格單元。

每個網格單元最多和八個網格單元相鄰。如果定義一個網格單元的連接度是連接周圍網格單元的數量，則網格單元連接度的范圍是0～8。網格單元連接度是0的稱為獨立網格單元。城市是由“普通“網格單元和“熱點”網格單元混合組成，由“熱點”網格單元和“普通“網格單元形成的區域分別叫做“熱點”區域和“普通“區域，它們之間彼此連接在一起。這些“熱點”區域也叫做城市分區。為了合理規劃出公交車候選車站的地點，統籌安排城市分區，把靠近大的“熱點”區域的小分區劃分進去，下面提出一個簡單的策略把彼此靠近的分區規劃形成大的聚集區。

1.2.2聚集區的合并和分離

提出聚集區的合并和分離算法如下：

算法1聚集區的合并和分離算法

輸入：分區列表 {Pi};

輸出: 聚集區列表{Ci};

1:P<-sort(P) (i=1,2,3,…,n);

//按照它們的PDR數量進行分類處理

2：i=1 ;

//初始化

3: while(P≠φ) do;

4: Ci={P1};

5:P=P{P1};

//從P中把P1移除

6:k=|P|;

7：for j:=1 to k do;

8: if dist(Ci,Pi)

//我們設置th為150m

9: Ci=Ci∪Pj;

//合并靠近的分區，形成聚集區

10： P=P{Pj};

//從P中把Pj移除

11:end if;

12:end for;

13:i=i+1;

14:end while;

獲取所有的城市分區后，根據乘客上下車的記錄數量按照降序分類,反復迭代合并彼此靠近的分區。提出使用“熱點”分區去吸收它附近的分區，直到附近沒有合適的分區進行合并(8行)，這樣形成大的分區稱作聚集區。這時選擇下一個熱點分區反復使用相同的程序直到所有分區全部遍歷到(8行-12行)，形成i個聚集區。每一個聚集區的候選車站地點的確定通過計算里面所有網格單元的平均權重來確定，使用式(1)計算。

(1)

其中，loc(gi)代表網格單元gi的經度/緯度,形成一個聚集區后，再吸收合并相鄰的分區(10行)。直到沒有分區被合并到此聚集區中，算法終結。然而，一些形成的聚集區面積可能太大，可以設置多個公交車候選車站，因此對大的分區要進行合適的劃分。一般來說，形成的聚集區根據它們的大小被分為三組(聚集區的大小被定義為覆蓋所有網格單元的最小矩形的面積)：(1) 矩形的長和寬超過500 m；(2) 長或寬超過500 m;(3) 長和寬都少于500 m。只有少量的聚集區需要分割操作(大約10%)。在處理第(1)組聚集區時，在水平和垂直兩個方向進行切割，將一個大的聚集區劃分為幾個小的聚集區。為了對出租車上下車的記錄的影響降到最低，對于第(2)組聚集區只需要在水平或垂直方向上進行分割。

1.2.3候選車站地點的選擇

經過合并和分割的操作，得到一定數量的面積小于500 m×500 m的“熱點”聚集區，下一步是在聚集區內選擇一個代表性的網格單元作為候選車站。

為了選擇代表性的網格單元，要考慮聚集區內每個網格單元的連接度和出租車上下車的記錄數。一個網格單元的連接度代表了這個網格的可達性，上下車的記錄數代表了它的熱點性。這個網格單元具有的最大權重根據式(2)進行計算，在每個聚集區內選擇權重最大的作為聚集區中心，成為候選車站。設置ω1=ω2=0.5，最后得到579個公交車候選車站。

(2)

1.3公交車路線的生成

1.3.1產生公交車路線簡圖

從這些車站里選擇合適的路線是非常復雜的過程，必須確保兩個原則：一是確保路線經過所篩選的候選車站，二是能夠在規定的時間內載到最大數量的乘客。如果直觀地從起始點開始選擇具有最大客流量的車站，這樣一直選下去必然導致兩個問題：一是公交車可能繞圈而無法到達終點，二是可能未在規定時間內載到最大數量的乘客。因此在車站選擇時必須遵循以下幾個規則:

規則1兩車站的距離要合適：

dis(si+1,si)<θi=1,2,…,n

(3)

其中，θ是一個常數,代表相鄰兩車站不超過的最大距離，這里設定θ為2 km。

規則2保證公交車是向前行駛的：

χ(i+1)>χ(i)i=1,2,…,n-1

χ(i)=χ(i)cosθ+y(i)sinθ

(4)

本文所使用的坐標系為WGS84，式(4)代表公交車移動的兩點在X軸上的投影的計算，保證公交車是朝著目的地行駛。

規則3公交車每一站要遠離出發點：

dis(si+1,s1)>dis(si,s1)i=1,2,…,n-1

(5)

規則4公交車每一站都靠近目的點：

dis(si+1,sn)

(6)

規則5保證候選車站的順序整體向前，防止出現尖刻的“之”字形回路：

argmin{dis(si+1,sj)}=sij=1,2,…,i

(7)

式(7)確保所有車站投影在從前到后的一條直線上。

通過以上規則的篩選，得到了一個從出發點到目的點的有向無環圖，如圖1所示。另外，顯然從出發地到目的地的有向路段要求每一個結點出度和入度都不為0，簡化后如圖2所示。

圖1　候選車站簡圖　　　　　　圖2　公交車路線圖

1.3.2生成公交車路線的方法

(1) 客流量和運行時間的估計

(2) 相關性啟發式搜索算法(SXQ)

盡管通過定義的規則對圖進行了修剪，移除無效的結點和邊，但是若給定出發地和目的地，枚舉所有可能路線也非常困難。事實上，沒有必要枚舉所有可能的路線然后比較它們，因為大多數路線是被少數路線所決定。

定義1Ri決定Rj的條件：1) T(Ri)≤T(Rj);2) Num(Ri)>Num(Rj)。

這里T和Num表示統計走過候選車站總的乘客累積量和總的運行時間，如式(8)、式(9)所示。

(8)

(9)

其中，t0表示在候選車站間的停留時間，設為1.5分鐘。主要目標是找出運行時間少、載客累積量多的理想路線，這里提出了相關性啟發式搜索算法算法如下：

算法2相關性啟發式搜索算法

輸入：候選車站集、客流量矩陣

輸出：起始地到目的地的公交車路線R*

1:R=?

//開始為空集

2：Repeat

3:curR=s1

//起始地

4: Repeat

5:利用式(10)計算選取下一個應通過的車站。

//把要走的車站加入集合

//目的地

8: R*=R∪R

//表示可能提取多條路線，得到路線集

9: 得到理想的路線集 R*

10：直到R*保持不變

(10)

定義2相似度表示兩個集合的交集與并集的比值即：

(11)

通過實驗證明，對于給出任何一對確定的出發地、目的地(OD)，當算法2連續執行到5000～15 000步時，兩個集合的相似度逐步達到1，意味著理想路線逐步覆蓋到1條，這就說明該算法是收斂的。為了和以分析內部相關性為主的算法2形成鮮明對比，下面提出了以整體相關性為主的基于樣本的基于貝葉斯分類搜索算法。

(3) 基于貝葉斯分類搜索算法(BYS)

貝葉斯分類器的分類原理是通過某對象的先驗概率，利用貝葉斯公式計算出其后驗概率，即該對象屬于某一類的概率，選擇具有最大后驗概率的類作為該對象所屬的類。也就是說，貝葉斯分類器是在最小錯誤率上的優化[13,14]。應用貝葉斯分類器進行分類主要分成兩個階段：第一階段是貝葉斯網絡分類器的學習，即從樣本數據中構造分類器，包括結構學習和條件概率表學習；第二階段是貝葉斯網絡分類器的推理，即計算類節點的條件概率，對分類數據進行分類[15,16]。

在實驗中提取大量候選車站的屬性(FM和TM)構建一個訓練集，然后根據這個訓練集構建一個貝葉斯分類器，將該分類器作為判斷選取下一個候選車站的依據。假設路網E中候選車站的屬性集X={x1,x2,…,xn}(n>0)可以用來確定出經驗上m個下一個候選車站集C={c1,c2,…,cm}(m>1)，則由貝葉斯定理知：

其中,P(cj)為描述類別cj的先驗概率, P(cj|X)為后驗概率。判別函數gj(X)可以寫成：

gj(X)=p(X|cj)P(cj)

(12)

基于貝葉斯分類搜索的算法如下：

算法3基于貝葉斯的分類算法

輸入：候選車站集、訓練集

輸出: 起始地到目的地的公交車路線R*

1:R=?

//開始為空集

2：Repeat

3:curR=s1

//起始地

4: Repeat

5:利用式(12)計算選取下一個應該通過的車站中的概率較大者

//把要走的車站加入集合

//目的地

8: R*=R∪R

//表示可能提取多條路線，得到路線集

9: 選擇過程中可能某幾個車站概率一樣，產生多條候選路線

10： 比較整條路線的總人數和總時間，選取性能較好者

該算法特點是：隨著訓練集的精度不斷提高，數量不斷增大，相似度越來越接近1，算法運行步數逐漸減少并趨向于收斂。但是構建出高質量的訓練集還是一個比較困難的過程。

2　實驗分析與比較

2.1實驗基礎

為了驗證本文方法和算法的有效性和準確性，我們做了大量對比實驗。實驗采用Eclipse+ArcMap平臺和Java語言來實現，根據真實的北京1萬輛出租車共計200萬條在一定范圍內的兩個月的出租車GPS數據來完成。

2.2候選車站篩選

用前文提及的方法篩選出的車站比單純使用數據挖掘的方法好，例如經典的k-means方法。假設k的取值等于前面篩選出的車站數量即k=579，比較而言，本文方法有兩個優勢：首先，k-means的中心區域一般是隨機分布在整個區域中，這樣就帶來了許多問題，可能落在一些不可達的區域，例如河流、樹林等。用本文方法篩選出的是最好路段，以及路段中最好的人群聚集地。其次，使用k-means方法可能導致一些候選車站擠在一起或相鄰候選車站的距離過大，然而用本文方法會讓候選車站均勻分布在公交線路上。

2.3理想公交車路線選擇

(1) 兩種算法在現實中的比較

這里給定一個確定的出發地-目的地(文津街-工人體育場)。根據ArcMap生成的北京市地圖，提取這個范圍內所有候選車站的簡圖，在Eclipse搭建環境運行兩種算法得到選擇的路線，如圖3所示。

圖3　SXQ和BYS算法選擇路線比較

兩種算法主要都是對下一個車站進行選擇，且兩者都是以啟發的方式逐個進行篩選。SXQ算法的優點是整體把握乘客的流動性，突出分析內部的關聯性。BYS算法的關鍵是對樣本訓練集的選擇，如果訓練集選擇數量少、精度不高，會導致算法的性能大大降低，這樣也不是收斂的。如果選擇的訓練集數量巨大、精確度高，得到的結果很接近SXQ，這點非常困難。下面是提高訓練集樣本質量、數量后BYS得到的路線，如圖4所示。

圖4　提高訓練集BYS得到的路線

(2) 兩種算法統計分析

另外，實驗還針對每一個OD對在100天內某個時間段內統計的結果求得均值，從運營時間和載客數量兩個方面對兩種算法進行了比較。

因為公交車夜間行駛速度不是一個主要的限制參數，所產生的時間差主要是由車站乘客上下車導致的，如圖5所示。

圖5　時間對比

兩種算法人數的增加主要集中在中部車站，SXQ主要選擇人數相對較多且距離適中的候選車站；而BYS算法在訓練集條件的限制下，選擇人數較為集中的候選車站，這樣就導致車站間距離過大，可能使經過的車站數量相對較少，如圖6所示。

圖6　SXQ與BYS的對比

3　結　語

本文的目的是把先進的計算機技術應用到中小城市的公交車路線規劃當中。因為提出的方法和取得的數據有一些缺陷，所以使得這項工作存在一些限制：首先，通過出租車GPS軌跡去分析整個城市人群的流動規律帶有偏見且不完整的，在實際操作中也不能完全正確地反映出公交車的客流量。一些人可能由于各種原因不愿意乘坐公交車出行，這樣就可能導致規劃出的路線不是最好的。其次，在操作過程中，本文對某些公式或結論做了一些假設。例如，在選擇候選車站時，乘客到達公交車站可接受的距離范圍是500米，聚集區的合并和分離的臨界參數是150米，顯然這些參數的假設會影響到最終結果。但是因為現實中整體空間的限制，本文無法研究參數敏感度所帶來的問題。最后，目前本文僅僅是探索給定確定的出發地和目的地的公交車路線問題，還不能整體考慮整個路網中公交車路線的規劃。

在以后的工作中，將從以下幾個方面拓寬和加深研究：第一，去做更多的實際調查，研究統計實際生活當中公交車的運行距離、運行頻次以及容量等，為以后規劃出更加理想的公交車線路做準備。第二，研究在操作當中改變某些參數對線路的影響，以及在線路的候選車站增加出租車叫車服務。第三，盡力把研究應用到更多城市的路徑規劃當中，為智慧城市的發展貢獻一份力量。

[1] 李清泉,鄭年波,徐敬海,等.一種基于道路網絡層次拓撲結構的分層路徑規劃算法[J].中國圖象圖形學報,2007,12(7):1280-1285.

[2] 鐘慧玲,章夢,石永強,等.基于路網分層策略的高效路徑規劃算法[J].西南交通大學學報,2011,46(4):645-650.

[3] 張照生,楊殿閣,張德鑫,等.車輛導航系統中基于街區分塊的分層路網路徑規劃[J].中國機械工程,2013,24(23):3255-3259.

[4] 胡繼華,黃澤,鄧俊,等.融合出租車駕駛經驗的層次路徑規劃方法[J].交通運輸系統工程與信息,2013,13(1):185-192.

[5] 鄭年波,李清泉,徐敬海,等.基于轉向限制和延誤的雙向啟發式最短路徑算法[J].武漢大學學報·信息科學版,2006,31(3):256-259.

[6] Yu Z K,Ni M F,Wang Z Y,et al.Dynamic Route Guidance Using Improved Genetic Algorithms[J].Mathematical Problems in Engineering,2013,2013:1-6.

[7] Pan G,Qi G D,Wu Z H,et al.Land-Use Classification Using Taxi GPS Traces[J].IEEE Transactions on Intelligent Transportation System,2013,14(1):113-123.

[8] Long Q,Zeng G,Zhang J F.Dynamic route guidance method facing driver’s individual demand[J].Journal of Central South University (Science and Technology),2013,44(5):2124-2129.

[9] Castro P S,Zhang D Q,Li S J.Urban Traffic Modelling and Prediction Using Large Scale Taxi GPS Traces[C]//Lecture Notes in Computer Science (including subseries Lecture Note in Artificial Intelligence and Lecture Notes in Bioinformatics).Berlin:Springer,2012,7319:57-72.

[10] Aslam J,Lim S,Rus D.Congestion-aware Traffic Routing System Using Sensor Data[C]//2012 15th International IEEE Conference on Intelligent Transportation Systems,2012:1006-1013.

[11] 胡繼華,鐘廣鵬,謝海瑩.基于出租車經驗路徑的城市可達性計算方法[J].地理科學進展,2012,31(6):711-716.

[12] 蘇岳龍,路鷺,姚丹亞,等.經典交通流模型在城市車路不均衡發展評價中的應用[J].公路交通科技,2010,27(11):108-112,117.

[13] 張紅彥,趙丁選,陳寧,等.基于遺傳算法的工程車輛自動變速神經網絡控制[J].中國公路學報,2006,19(1):117-121.[14] 伊華偉.基于改進蟻群算法的機械手三維操作路徑規劃[J].計算機應用與軟件,2014,31(4):302-304,307.

[15] 周峰.基于Tent混沌粒子群算法的滾動窗口路徑規劃[J].計算機應用與軟件,2013,30(5):76-79.

[16] 李剛,馬良荔,郭曉明,等.交互式拆卸引導裝配路徑規劃方法研究[J].計算機應用與軟件,2012,29(10):248-249,290.

RESEARCH AND IMPLEMENTATION OF BUS ROUTE PLANNING BASED ON FLOATING CAR DATA

Lin NaLi Jianming

(SchoolofComputerScience,ShenyangAerospaceUniversity,Shenyang110136,Liaoning,China)

Traditional way of bus route planning mainly depends on manpower surveys. Though this method has been proved to be feasible, a great deal of manpower and material resources are taken in this process however. What is more, such method does not adapt to the frequent changes of road network as the result of rapid urban development. To solve this problem, this paper proposes a method for night bus route planning according to the collected huge taxi GPS data. The method mainly consists of three sections. First, we find out the collection area to determine the candidate stations set based on the extracted effective trajectory data. Secondly, we set the rules to simplify the complex candidate bus stations set to the effective bus route set. Thirdly, we propose two algorithms to select the most ideal bus route. Result shows that the bus route derived from correlation heuristic searching algorithm takes the relevance among candidate bus stations into comprehensive consideration, and is the route with maximum passengers load within the set time.

Floating car dataCandidate station setBus route setCorrelation heuristic search algorithm

2015-06-22。遼寧省高等學校優秀人才支持計劃項目(LJQ2012011)；遼寧省自然科學基金聯合基金項目(2015020008)。林娜，副教授，主研領域：智能交通，無人機航跡規劃。李建明，碩士生。

TP393

A

10.3969/j.issn.1000-386x.2016.10.060