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

林　娜　李建明

(沈陽(yáng)航空航天大學(xué)計(jì)算機(jī)學(xué)院　遼寧 沈陽(yáng) 110136)

?

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

林娜李建明

(沈陽(yáng)航空航天大學(xué)計(jì)算機(jī)學(xué)院遼寧 沈陽(yáng) 110136)

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

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

0　引　言

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

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

1　技術(shù)路線(xiàn)

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

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

1.2確定候選車(chē)站

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

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

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

每個(gè)網(wǎng)格單元最多和八個(gè)網(wǎng)格單元相鄰。如果定義一個(gè)網(wǎng)格單元的連接度是連接周?chē)W(wǎng)格單元的數(shù)量，則網(wǎng)格單元連接度的范圍是0～8。網(wǎng)格單元連接度是0的稱(chēng)為獨(dú)立網(wǎng)格單元。城市是由“普通“網(wǎng)格單元和“熱點(diǎn)”網(wǎng)格單元混合組成，由“熱點(diǎn)”網(wǎng)格單元和“普通“網(wǎng)格單元形成的區(qū)域分別叫做“熱點(diǎn)”區(qū)域和“普通“區(qū)域，它們之間彼此連接在一起。這些“熱點(diǎn)”區(qū)域也叫做城市分區(qū)。為了合理規(guī)劃出公交車(chē)候選車(chē)站的地點(diǎn)，統(tǒng)籌安排城市分區(qū)，把靠近大的“熱點(diǎn)”區(qū)域的小分區(qū)劃分進(jìn)去，下面提出一個(gè)簡(jiǎn)單的策略把彼此靠近的分區(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ù)量進(jìn)行分類(lèi)處理

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)

//我們?cè)O(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ù)乘客上下車(chē)的記錄數(shù)量按照降序分類(lèi),反復(fù)迭代合并彼此靠近的分區(qū)。提出使用“熱點(diǎn)”分區(qū)去吸收它附近的分區(qū)，直到附近沒(méi)有合適的分區(qū)進(jìn)行合并(8行)，這樣形成大的分區(qū)稱(chēng)作聚集區(qū)。這時(shí)選擇下一個(gè)熱點(diǎn)分區(qū)反復(fù)使用相同的程序直到所有分區(qū)全部遍歷到(8行-12行)，形成i個(gè)聚集區(qū)。每一個(gè)聚集區(qū)的候選車(chē)站地點(diǎn)的確定通過(guò)計(jì)算里面所有網(wǎng)格單元的平均權(quán)重來(lái)確定，使用式(1)計(jì)算。

(1)

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

1.2.3候選車(chē)站地點(diǎn)的選擇

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

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

(2)

1.3公交車(chē)路線(xiàn)的生成

1.3.1產(chǎn)生公交車(chē)路線(xiàn)簡(jiǎn)圖

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

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

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

(3)

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

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

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

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

(4)

本文所使用的坐標(biāo)系為WGS84，式(4)代表公交車(chē)移動(dòng)的兩點(diǎn)在X軸上的投影的計(jì)算，保證公交車(chē)是朝著目的地行駛。

規(guī)則3公交車(chē)每一站要遠(yuǎn)離出發(fā)點(diǎn)：

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

(5)

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

dis(si+1,sn)

(6)

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

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

(7)

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

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

圖1　候選車(chē)站簡(jiǎn)圖　　　　　　圖2　公交車(chē)路線(xiàn)圖

1.3.2生成公交車(chē)路線(xiàn)的方法

(1) 客流量和運(yùn)行時(shí)間的估計(jì)

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

盡管通過(guò)定義的規(guī)則對(duì)圖進(jìn)行了修剪，移除無(wú)效的結(jié)點(diǎn)和邊，但是若給定出發(fā)地和目的地，枚舉所有可能路線(xiàn)也非常困難。事實(shí)上，沒(méi)有必要枚舉所有可能的路線(xiàn)然后比較它們，因?yàn)榇蠖鄶?shù)路線(xiàn)是被少數(shù)路線(xiàn)所決定。

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

這里T和Num表示統(tǒng)計(jì)走過(guò)候選車(chē)站總的乘客累積量和總的運(yùn)行時(shí)間，如式(8)、式(9)所示。

(8)

(9)

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

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

輸入：候選車(chē)站集、客流量矩陣

輸出：起始地到目的地的公交車(chē)路線(xiàn)R*

1:R=?

//開(kāi)始為空集

2：Repeat

3:curR=s1

//起始地

4: Repeat

5:利用式(10)計(jì)算選取下一個(gè)應(yīng)通過(guò)的車(chē)站。

//把要走的車(chē)站加入集合

//目的地

8: R*=R∪R

//表示可能提取多條路線(xiàn)，得到路線(xiàn)集

9: 得到理想的路線(xiàn)集 R*

10：直到R*保持不變

(10)

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

(11)

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

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

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

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

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

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

(12)

基于貝葉斯分類(lèi)搜索的算法如下：

算法3基于貝葉斯的分類(lèi)算法

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

輸出: 起始地到目的地的公交車(chē)路線(xiàn)R*

1:R=?

//開(kāi)始為空集

2：Repeat

3:curR=s1

//起始地

4: Repeat

5:利用式(12)計(jì)算選取下一個(gè)應(yīng)該通過(guò)的車(chē)站中的概率較大者

//把要走的車(chē)站加入集合

//目的地

8: R*=R∪R

//表示可能提取多條路線(xiàn)，得到路線(xiàn)集

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

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

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

2　實(shí)驗(yàn)分析與比較

2.1實(shí)驗(yàn)基礎(chǔ)

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

2.2候選車(chē)站篩選

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

2.3理想公交車(chē)路線(xiàn)選擇

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

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

圖3　SXQ和BYS算法選擇路線(xiàn)比較

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

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

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

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

因?yàn)楣卉?chē)夜間行駛速度不是一個(gè)主要的限制參數(shù)，所產(chǎn)生的時(shí)間差主要是由車(chē)站乘客上下車(chē)導(dǎo)致的，如圖5所示。

圖5　時(shí)間對(duì)比

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

圖6　SXQ與BYS的對(duì)比

3　結(jié)　語(yǔ)

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

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

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

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

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

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

[5] 鄭年波,李清泉,徐敬海,等.基于轉(zhuǎn)向限制和延誤的雙向啟發(fā)式最短路徑算法[J].武漢大學(xué)學(xué)報(bào)·信息科學(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] 胡繼華,鐘廣鵬,謝?，?基于出租車(chē)經(jīng)驗(yàn)路徑的城市可達(dá)性計(jì)算方法[J].地理科學(xué)進(jìn)展,2012,31(6):711-716.

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

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

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

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

TP393

A

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