林　娜　李建明

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

?

基于浮動車數(shù)據(jù)的公交車路線規(guī)劃研究與實現(xiàn)

林娜李建明

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

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

浮動車數(shù)據(jù)候選車站集公交車路線集相關(guān)性啟發(fā)式搜索算法

0　引　言

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

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

1　技術(shù)路線

1.1數(shù)據(jù)的預(yù)處理

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

1.2確定候選車站

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

1.2.1網(wǎng)格單元與城市劃分

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

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

1.2.2聚集區(qū)的合并和分離

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

算法1聚集區(qū)的合并和分離算法

輸入：分區(qū)列表 {Pi};

輸出: 聚集區(qū)列表{Ci};

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

//按照它們的PDR數(shù)量進行分類處理

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)

//我們設(shè)置th為150m

9: Ci=Ci∪Pj;

//合并靠近的分區(qū)，形成聚集區(qū)

10： P=P{Pj};

//從P中把Pj移除

11:end if;

12:end for;

13:i=i+1;

14:end while;

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

(1)

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

1.2.3候選車站地點的選擇

經(jīng)過合并和分割的操作，得到一定數(shù)量的面積小于500 m×500 m的“熱點”聚集區(qū)，下一步是在聚集區(qū)內(nèi)選擇一個代表性的網(wǎng)格單元作為候選車站。

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

(2)

1.3公交車路線的生成

1.3.1產(chǎn)生公交車路線簡圖

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

規(guī)則1兩車站的距離要合適：

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

(3)

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

規(guī)則2保證公交車是向前行駛的：

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

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

(4)

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

規(guī)則3公交車每一站要遠離出發(fā)點：

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

(5)

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

dis(si+1,sn)

(6)

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

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

(7)

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

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

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

1.3.2生成公交車路線的方法

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

(2) 相關(guān)性啟發(fā)式搜索算法(SXQ)

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

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

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

(8)

(9)

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

算法2相關(guān)性啟發(fā)式搜索算法

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

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

1:R=?

//開始為空集

2：Repeat

3:curR=s1

//起始地

4: Repeat

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

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

//目的地

8: R*=R∪R

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

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

10：直到R*保持不變

(10)

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

(11)

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

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

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

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

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

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

(12)

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

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

輸入：候選車站集、訓(xùn)練集

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

1:R=?

//開始為空集

2：Repeat

3:curR=s1

//起始地

4: Repeat

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

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

//目的地

8: R*=R∪R

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

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

10： 比較整條路線的總?cè)藬?shù)和總時間，選取性能較好者

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

2　實驗分析與比較

2.1實驗基礎(chǔ)

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

2.2候選車站篩選

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

2.3理想公交車路線選擇

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

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

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

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

圖4　提高訓(xùn)練集BYS得到的路線

(2) 兩種算法統(tǒng)計分析

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

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

圖5　時間對比

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

圖6　SXQ與BYS的對比

3　結(jié)　語

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

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

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

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

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

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

[5] 鄭年波,李清泉,徐敬海,等.基于轉(zhuǎn)向限制和延誤的雙向啟發(fā)式最短路徑算法[J].武漢大學(xué)學(xué)報·信息科學(xué)版,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īng)驗路徑的城市可達性計算方法[J].地理科學(xué)進展,2012,31(6):711-716.

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

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

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

[16] 李剛,馬良荔,郭曉明,等.交互式拆卸引導(dǎo)裝配路徑規(guī)劃方法研究[J].計算機應(yīng)用與軟件,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。遼寧省高等學(xué)校優(yōu)秀人才支持計劃項目(LJQ2012011)；遼寧省自然科學(xué)基金聯(lián)合基金項目(2015020008)。林娜，副教授，主研領(lǐng)域：智能交通，無人機航跡規(guī)劃。李建明，碩士生。

TP393

A

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