張 凱,張 強(qiáng),莊 梁

(南京信息工程大學(xué)信息與控制學(xué)院,南京210044)

基于矢量匹配的人口稀疏區(qū)域乘車出行算法研究

張 凱*,張 強(qiáng),莊 梁

(南京信息工程大學(xué)信息與控制學(xué)院,南京210044)

郊區(qū)及新建市區(qū)等人口稀疏區(qū)域的人們乘車出行多有不便,為消除這類區(qū)域乘車出行的缺陷,進(jìn)行了出行算法研究.本文提出了矢量匹配算法和接載路徑算法.首先,對(duì)出行者請(qǐng)求的出發(fā)地和目的地位置信息與服務(wù)區(qū)域道路網(wǎng)主路線進(jìn)行方向匹配;其次,對(duì)所有匹配成功的請(qǐng)求位置信息進(jìn)行全局最優(yōu)路徑規(guī)劃;最后,根據(jù)路網(wǎng)模型并結(jié)合出行算法給出實(shí)驗(yàn)數(shù)據(jù)分析和結(jié)論.研究結(jié)果表明:本文提出的出行算法具有常規(guī)公交車所不具備的人性化的點(diǎn)到點(diǎn)服務(wù)特征,服務(wù)品質(zhì)高,乘車費(fèi)用較出租車費(fèi)用實(shí)惠,平均每位出行者的乘車時(shí)間在可接受范圍內(nèi),乘客滿意度較高,可以很好地滿足人們出行方便快捷的意愿.

城市交通;出行算法;矢量匹配;稀疏區(qū)域;小型公交車;接載路徑規(guī)劃

1 引 言

近幾十年,我國(guó)政府制定了一系列相關(guān)政策,明確以公共交通為主的城市交通發(fā)展策略.當(dāng)前,盡管我國(guó)城市公共交通網(wǎng)絡(luò)覆蓋面越來越廣,但依然存在亟待解決和完善的問題[1-4],最明顯的地域是在郊區(qū)、新建市區(qū)等人口稀疏區(qū)域.長(zhǎng)期以來,由于這些地區(qū)公交車班次少,路線稀疏,發(fā)車時(shí)間長(zhǎng),缺乏靈活性等原因,常常給依靠公交車出行的人們帶來不便與困擾,人口雖相對(duì)稀疏,但仍需要一個(gè)良好運(yùn)營(yíng)的公交系統(tǒng)或全新的公交運(yùn)營(yíng)模式.如何有效地改變此類區(qū)域當(dāng)前交通出行落后的現(xiàn)狀,提升公交出行服務(wù)品質(zhì),是城市相關(guān)部門需要深入研究的實(shí)際問題,也是相關(guān)學(xué)者值得探究的問題之一.

目前研究人口稀疏區(qū)域乘車出行的文獻(xiàn)并不多見.Cortes和Jayakrishnan在2002年提出高覆蓋點(diǎn)到點(diǎn)公交系統(tǒng)[5].Khattak和Yim在2004年對(duì)舊金山港灣面向消費(fèi)者需求個(gè)性化的響應(yīng)服務(wù)(PersonalizedDemand-ResponsiveTransit,簡(jiǎn)稱PDRT)進(jìn)行了調(diào)查[6],大約60%被調(diào)查的人樂意選擇PDRT,大多數(shù)人愿意為調(diào)度靈活的PDRT服務(wù)支付額外費(fèi)用.許多文獻(xiàn)調(diào)查顯示,將固定路線公交服務(wù)改進(jìn)為不固定公交服務(wù)時(shí),公交車的載客量穩(wěn)定增長(zhǎng),如在威斯康星洲美林市Merrill-Go-Round的公交示例[7]以及在漢普頓、紐波特紐斯和約克郡的半島公交[8].遺憾地是,以上相關(guān)文獻(xiàn)只是研究區(qū)別于普遍意義下公交服務(wù)的一些變化和改進(jìn),并沒有具體研究人口稀疏區(qū)域下的行車服務(wù).

本文針對(duì)性地以郊區(qū)、新建市區(qū)為研究區(qū)域,依靠小型公交車,對(duì)出行者請(qǐng)求的出發(fā)地和目的地兩點(diǎn)位置信息和區(qū)域主行駛路線進(jìn)行算法匹配分析,研究是否滿足前去接載的要求.最后,對(duì)所有滿足接載要求的位置點(diǎn)進(jìn)行全局最優(yōu)接載路徑規(guī)劃,用得到的算法結(jié)果來指導(dǎo)小型公交車的行駛.通過算法研究,實(shí)現(xiàn)了一種方便可行的乘車出行接載服務(wù)方法,很好地滿足人們?cè)诖祟悈^(qū)域普通多樣化的出行需求.

2 出行算法研究

研究基礎(chǔ)設(shè)定:小型公交車在服務(wù)區(qū)域中單向往返運(yùn)行；服務(wù)區(qū)域中所有道路干線比較規(guī)范,不存在形狀不規(guī)則干線；服務(wù)區(qū)域有一條主行駛參考路線；研究的出行者請(qǐng)求位置點(diǎn)都在行車位置前方,行車位置后方的不予考慮；對(duì)于所有符合接載條件的請(qǐng)求者允許小型公交車偏離參考路線去進(jìn)行接載服務(wù).

此外,由于地圖中道路網(wǎng)錯(cuò)綜復(fù)雜,所以綜合各種人口稀疏道路情況考慮,最終選擇了算法更具普遍意義的服務(wù)區(qū)域?yàn)榫匦?、主行駛參考路線為直線或近似直線的路網(wǎng)模型.

2.1 矢量匹配算法研究

關(guān)于矢量匹配算法研究:出行者的兩點(diǎn)位置信息在服務(wù)區(qū)域內(nèi)與服務(wù)車輛的主行駛參考路線進(jìn)行矢量匹配判斷,主要是起止經(jīng)緯度構(gòu)成的矢量與主行駛參考路線方向矢量的匹配.若結(jié)果在匹配的接載范圍內(nèi),則斷定其符合接載要求,予以接載服務(wù).

如圖1,w和w′分別表示請(qǐng)求的位置點(diǎn)和請(qǐng)求到達(dá)的目標(biāo)位置點(diǎn),mdd為車主行駛參考路線直線化后的矢量方向,mddp為車主行駛參考路線直線化后矢量方向的垂線方向,β為的夾角.

β可表示為和

式中 ww′lat=w′lat-wlat,ww′long=w′long-wlong；

wlat,wlong——出行者當(dāng)前位置點(diǎn)的經(jīng)度和緯度；

w′lat,w′long——出行者目的地位置點(diǎn)的經(jīng)度和緯度；

mddx,mddy矢量mdd方向的兩個(gè)方向值.

圖1 矢量匹配分析Fig.1 Vector matching analysis

此外,令

式中 α——區(qū)域車輛的服務(wù)閥值.

服務(wù)閥值α的大小決定車服務(wù)接載率的高低,影響出行者請(qǐng)求接載成功率的高低,對(duì)整個(gè)系統(tǒng)的運(yùn)作很重要.α越大,接受服務(wù)請(qǐng)求的人數(shù)越多,車服務(wù)接載率就越高.

式(2)中,d的正負(fù)決定出行者的請(qǐng)求服務(wù)是否會(huì)被接受,矢量匹配的成功與否.當(dāng)d＞0時(shí),β在服務(wù)閥值α之內(nèi),車接受出行者的請(qǐng)求服務(wù),匹配成功；當(dāng)d＜0時(shí),β超越服務(wù)閥值α,意味著放棄此出行者的請(qǐng)求,車輛不會(huì)接受出行者的請(qǐng)求服務(wù),匹配失敗.此時(shí),出行者可以向其它車輛提出請(qǐng)求服務(wù),每輛車的服務(wù)都是相互獨(dú)立的.

一般來講,具體服務(wù)閥值的大小需根據(jù)具體稀疏區(qū)域加以設(shè)定.

2.2 接載路徑描述

由于本文的研究地區(qū)是人口稀疏區(qū)域,所以不涉及道路堵塞問題,整個(gè)研究的區(qū)域道路時(shí)刻暢通.總體接載行車路徑[9]如圖2所示.

圖2 總體接載行車路徑Fig.2 Overall pick-up driving path

圖2中,兩相鄰位置點(diǎn)間路徑條數(shù)可表示為

式中 path(n-1→n)——位置點(diǎn)n-1與n間的路徑；

t(n-1)——位置點(diǎn)n-1與n間路徑數(shù)目.

總體行車接載路徑為

式中 Path(1→n)min——從位置點(diǎn)1開始,途經(jīng)位置點(diǎn)2,3,…,n-2,n-1并到達(dá)位置點(diǎn)n的最短路徑.

2.3 接載路徑算法研究

引入步步逼近路徑[10]概念:從車輛當(dāng)前位置沿著路徑向目標(biāo)點(diǎn)移動(dòng)的過程中不會(huì)出現(xiàn)距離“倒退”現(xiàn)象,車輛位置和目標(biāo)點(diǎn)總在不斷逼近中,直至抵達(dá)目標(biāo)點(diǎn),由此產(chǎn)生的當(dāng)前路徑即為步步逼近路徑.公式為

式中 Dpn(x)t——車在位置點(diǎn)n-1和n間某一條路徑x上行駛在t時(shí)刻與位置點(diǎn)n的距離；

Dpn(x)(t+1)——車在位置點(diǎn)n-1和n間某一條路徑x上行駛在t+1時(shí)刻與位置點(diǎn)n的距離；

Dpn(x)——車在位置點(diǎn)n-1和n之間某一條路徑x上行駛與位置點(diǎn)n的距離；

Tn——到達(dá)位置點(diǎn)n的時(shí)刻.

圖3 算法搜索區(qū)Fig.3 Algorithm search area

算法基本步驟如下:

第1步限制算法搜索區(qū).

利用起點(diǎn)和目標(biāo)點(diǎn)的位置信息,將搜索過程限定在起止點(diǎn)方向上,并把搜索區(qū)域縮減為一個(gè)橢圓,在小范圍內(nèi)進(jìn)行搜索[11,12].構(gòu)建限制搜索區(qū)的方法為

Li+e(i,d)≤E(o,d)(7)

式中 Li——車位置點(diǎn)o到當(dāng)前節(jié)點(diǎn)i的最短路徑的長(zhǎng)度；

e(i,d)——節(jié)點(diǎn)i到目標(biāo)位置點(diǎn)d的路徑長(zhǎng)度估計(jì)；

E(o,d)——車位置點(diǎn)o到目標(biāo)位置點(diǎn)d的最短路徑長(zhǎng)度上界的估計(jì).

如圖3虛線橢圓所示,在車位置點(diǎn)▲和目標(biāo)位置點(diǎn)1間構(gòu)建了一個(gè)橢圓的限制搜索區(qū)域,從而大大提高了算法效率.

第2步確定相鄰位置點(diǎn)間的步步逼近路徑,若無步步逼近路徑,確定普通路徑.

在位置點(diǎn)▲和位置點(diǎn)1間共有7條路徑,其中步步逼近路徑有4條,如圖4左側(cè)圖所示,右側(cè)圖所示為3條普通路徑.

第3步

(1)對(duì)確定的步步逼近路徑逐一進(jìn)行路徑求距,通過最后的分析比較確定最優(yōu)路徑.

圖4中,通過對(duì)交叉節(jié)點(diǎn)位置信息的提取,計(jì)算出各個(gè)節(jié)點(diǎn)間的距長(zhǎng)(最短距長(zhǎng)定為1,其它的距長(zhǎng)均以最短的距長(zhǎng)1為參照標(biāo)準(zhǔn)),從而計(jì)算出4條步步逼近路徑的距長(zhǎng).

通過比較確定,最優(yōu)路徑為路徑2.

(2)若相鄰位置點(diǎn)間步步逼近路徑不存在,則從普通路徑中尋求最優(yōu)路徑.

如圖4右側(cè)圖所示的3條路徑則為位置點(diǎn)▲和位置點(diǎn)1間的普通路徑,如果前4條路徑不存在,則從路徑5,路徑6和路徑7中確定最優(yōu)路徑.

第4步位置點(diǎn)加1,重復(fù)上面三步,直到最后一個(gè)位置點(diǎn),最終求解出全局最優(yōu)路徑.

前三步是以車當(dāng)前位置點(diǎn)▲和位置點(diǎn)1為相鄰的兩個(gè)位置點(diǎn)加以討論.根據(jù)前三步,對(duì)位置點(diǎn)1和2,位置點(diǎn)2和3(圖5中的1'),…,位置點(diǎn)n -1和n進(jìn)行相同的操作,得到各自最優(yōu)路徑,全局最優(yōu)路徑則是它們的集合,最優(yōu)路線[13]如圖5所示.

在系統(tǒng)運(yùn)行中,當(dāng)有新請(qǐng)求來臨并得到接受時(shí),假設(shè)新請(qǐng)求兩個(gè)位置點(diǎn)為q和q′,根據(jù)其在整個(gè)路網(wǎng)中所處的位置與相鄰的位置點(diǎn)間重新進(jìn)行最優(yōu)路徑計(jì)算,計(jì)算得到的最優(yōu)路徑將取代這一計(jì)算中用到的原有位置點(diǎn)間的路徑并插入整合到當(dāng)前總體行駛路徑中,達(dá)到每當(dāng)有新的接載服務(wù)時(shí)總能夠?qū)崟r(shí)地更新最優(yōu)路徑.

圖4 位置點(diǎn)間的行車路徑Fig.4 Driving path between points

圖5 最優(yōu)路線Fig.5 The optimal route

3 實(shí)驗(yàn)結(jié)果

3.1 實(shí)驗(yàn)前提

前提一:實(shí)驗(yàn)支持.

出行者通過手機(jī)客戶端將當(dāng)前出發(fā)地位置和目的地位置發(fā)往公交公司后臺(tái)中心；后臺(tái)中心對(duì)數(shù)據(jù)進(jìn)行匹配處理；匹配成功的信息添加整合到區(qū)域中最合適的公交車；后臺(tái)中心對(duì)該公交車進(jìn)行動(dòng)態(tài)最新路徑規(guī)劃,并將規(guī)劃結(jié)果通過無線發(fā)送給對(duì)應(yīng)的公交車.

前提二:實(shí)驗(yàn)假設(shè).

(1)小型公交車所在服務(wù)區(qū)域?yàn)榫匦螀^(qū)域,主行駛路線為直線或近似直線；請(qǐng)求的出行者隨機(jī)分布在服務(wù)區(qū)域中,隨機(jī)地提出服務(wù)請(qǐng)求；出行者提出的服務(wù)請(qǐng)求是一種正向請(qǐng)求,非與主行車方向相反,以服務(wù)閥值α=90°為上限.

(2)小型公交車座位數(shù)為15個(gè),綜合油耗為12升/百公里,汽油價(jià)格取7元/升,服務(wù)區(qū)域的橫向跨度為10 km,服務(wù)區(qū)域縱向跨度為橫向主行駛參考路線兩側(cè)各1.5 km,平均行駛速度為30 km/h.

3.2 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)從小型公交車服務(wù)接載率,單向總體運(yùn)行時(shí)間,出行者付出的接載費(fèi)用,以及乘客(出行者)滿意度四個(gè)方面對(duì)出行算法進(jìn)行了比較和分析.實(shí)驗(yàn)結(jié)果圖6所示.

圖6 服務(wù)閥值為30°、60°和90°時(shí)車服務(wù)接載率Fig.6 Pick-up rate of small bus service in the service threshold of 30°、60°and 90°respectively

圖6為實(shí)驗(yàn)中具體地一組服務(wù)閥值和車服務(wù)接載率的關(guān)系圖,圖中折線表明:在同一個(gè)服務(wù)區(qū)域,隨著服務(wù)閥值的增大,車服務(wù)接載率也將隨之增大.

為了滿足高品質(zhì)服務(wù)的特點(diǎn),小型公交車的總體接載人數(shù)需動(dòng)態(tài)維持在滿座15人以內(nèi),以確保人人有座,因此,服務(wù)閥值大小的確定成了實(shí)驗(yàn)最關(guān)鍵的問題.實(shí)驗(yàn)中的小型公交車位于區(qū)域的正向起始端,實(shí)驗(yàn)過程中,當(dāng)預(yù)設(shè)區(qū)域均勻隨機(jī)地動(dòng)態(tài)布置20個(gè)有出行需求的出行者時(shí),為讓公交車上下車人數(shù)動(dòng)態(tài)地維持在15人,實(shí)驗(yàn)中服務(wù)閥值需設(shè)為50°；當(dāng)預(yù)設(shè)區(qū)域均勻隨機(jī)地動(dòng)態(tài)布置15個(gè)有出行需求的出行者時(shí),為讓公交車上下車人數(shù)動(dòng)態(tài)地維持在10人,實(shí)驗(yàn)中服務(wù)閥值需設(shè)為45°.顯而易見,在正常情況下,服務(wù)閥值決定了車服務(wù)接載的人數(shù),閥值的大小影響了服務(wù)接載率的高低.

圖7 服務(wù)閥值60°時(shí)運(yùn)行時(shí)間、接載費(fèi)用和乘客滿意度在不同請(qǐng)求接載人數(shù)下的比較Fig.7 Comparison about running time,pick up fee and passenger satisfaction under different number of requesting to pick-up in the service threshold of 60°

圖8 服務(wù)閥值90°時(shí)運(yùn)行時(shí)間、接載費(fèi)用和乘客滿意度在不同請(qǐng)求接載人數(shù)下的比較Fig.8 Comparison about running time,pick up fee and passenger satisfaction under different number of requesting to pick-up in the service threshold of 90°

服務(wù)閥值取60°和90°兩種情況.通過實(shí)驗(yàn),分別給出請(qǐng)求接載人數(shù)在5、10、15、20四種情況下,出行者付出的接載費(fèi)用、單向總體運(yùn)行時(shí)間、乘客滿意度的比較圖7、圖8所示.

圖7和圖8表明:

(1)請(qǐng)求接載人數(shù)相同的情況下,服務(wù)閥值越大,運(yùn)行時(shí)間越長(zhǎng),但接載費(fèi)用會(huì)降低.

(2)隨著請(qǐng)求接載人數(shù)的不斷增大,接載費(fèi)用隨之降低,但運(yùn)行時(shí)間會(huì)不斷加長(zhǎng).

(3)當(dāng)請(qǐng)求接載人數(shù)在由10變?yōu)?5后,乘客滿意度由上升趨勢(shì)變成下降趨勢(shì),說明在請(qǐng)求接載人數(shù)超過15人后,隨著服務(wù)閥值的加大,小型公交車已不能完全保證人人有座,且此時(shí)總體的運(yùn)行時(shí)間過長(zhǎng),雖然接載費(fèi)用降下來了,但依然影響了乘客滿意度的提升.

(4)服務(wù)閥值60°下請(qǐng)求接載人數(shù)為10時(shí),乘客滿意度最高,為95.4%.

根據(jù)以上實(shí)驗(yàn)結(jié)果分析得出:服務(wù)閥值的設(shè)定尤為重要.服務(wù)閥值太小,會(huì)導(dǎo)致服務(wù)接載率降低,接載費(fèi)用增加,且在請(qǐng)求人數(shù)較多時(shí),會(huì)導(dǎo)致部分出行者二次請(qǐng)求的麻煩；服務(wù)閥值太大,整體運(yùn)行時(shí)間就會(huì)太長(zhǎng),尤其在請(qǐng)求接載人數(shù)超過15人的情況下,無法再滿足快捷出行的特點(diǎn).

此外,若要贏得最佳乘客滿意度,保證整個(gè)系統(tǒng)的健康運(yùn)作.需根據(jù)具體的稀疏區(qū)域類型合理地設(shè)計(jì)矢量匹配算法中的服務(wù)閥值α,在保證公交運(yùn)營(yíng)收益良好的前提下,使服務(wù)閥值、總體運(yùn)行時(shí)間、接載費(fèi)用間達(dá)到綜合最優(yōu),從而確保系統(tǒng)高品質(zhì)個(gè)性化服務(wù)的順利進(jìn)行.

4 研究結(jié)論

本文針對(duì)人口稀疏區(qū)域,提出了基于矢量匹配的乘車出行算法.作為一種全新的公交出行方式,它改變了以往常規(guī)公交的運(yùn)營(yíng)模式和服務(wù)理念,通過對(duì)矢量匹配算法和矢量匹配下接載路徑規(guī)劃算法的研究,得到了更符合人口稀疏區(qū)域下的乘車出行方法,豐富了現(xiàn)有的公共交通出行方式.研究所依靠的小型公交車具有常規(guī)公交車所不具備的點(diǎn)到點(diǎn)服務(wù)的特征,人性化十足,服務(wù)品質(zhì)高.根據(jù)實(shí)驗(yàn)結(jié)果顯示,區(qū)域中乘客搭載小型公交車的費(fèi)用要比日常的出租車費(fèi)用更加合理實(shí)惠,接近于普通公交車的乘車費(fèi)用,平均每位出行者的乘車時(shí)間也在可接受范圍內(nèi),總體乘客滿意度較高.

本文的研究基礎(chǔ)是服務(wù)區(qū)域?yàn)榫匦?主行駛路線為直線或近似直線的人口稀疏區(qū)域,由于實(shí)際的人口稀疏區(qū)域類型較多,且服務(wù)區(qū)域中道路干線形狀各異,因此對(duì)于其它類型的人口稀疏區(qū)域的乘車出行算法研究將是后續(xù)進(jìn)一步研究的課題.另外,后續(xù)研究中,在本文研究的基礎(chǔ)上還可以加入更多細(xì)微的貼心服務(wù),適當(dāng)增加小型公交車接載費(fèi)用,從而更好地優(yōu)化提升公交車服務(wù)品質(zhì),這對(duì)于公交出行的人們來講,必然是最佳選擇.

[1] 蔡敬艷.加快新郊區(qū)公共交通發(fā)展的建議[J].上海公路,2006(3):59-62.[CAI J Y.Suggestion on fastening development of public transit system in new suburb[J].Shanghai Highways,2006(3):59-62.]

[2] 陸磊,李霞飛,周俊紅.上海市郊區(qū)公共交通發(fā)展問題研究[J].城市公用事業(yè),2007,21(4):3-5.[LU L,LI X F,ZHOU J H.Research on suburb public transportdevelopmentinShanghai[J].Public Utilities,2007,21(4):3-5.]

[3] Cervero R,Day J.中國(guó)城市的郊區(qū)化與公交導(dǎo)向開發(fā)[J].上海城市規(guī)劃,2010,4(93):50-59.[Cervero R,DayJ.Suburbanizationandtransitoriented development in China[J].Shanghai Urban Planning Review,2010,4(93):50-59.]

[4] 楊明,楊濤,凌小靜,等.交通引領(lǐng)下的南京城市規(guī)劃編制探討[J].規(guī)劃師,2012,28(8):38-42.[ YANG M,YANG T,LING X J,et al.Transportationled Nanjing urban planning compilation[J].Planner, 2012,28(8):38-42.]

[5] Cortes C E,Jayakrishnan R.Design and operational conceptsofahigh-coveragepoint-to-pointtransit system[J].Transportation Research Record,2007, 1783(2002):178-187.

[6] Khattak A J,Yim Y.Traveler response to innovative personalized demand-responsive transit in the San Fran-ciscoBayArea[J].UrbanPlanningand Development,2004,130(1):42-45.

[7] Durvasula P K,Smith B L,Turochy R E,et al.Peninsula transportation district commission route deviation feasibility study[M].Virginia Transportation Research Council,FHWA/VTRC 99-R11,Charlottesvile,1998.

[8] Durvalula M,Priya K.A gis-based support tool for route deviation transit scheduling and servicedesign [M].Charlottesvile:University of Virginia,1999.

[9] Rahmani M,Koutsopoulos H N.Path inference from sparse floating car data for urban networks[J]. TransportationResearchPartC:Emerging Technologies,2013,30:41-45.

[10] Li Q Q,Zeng Z,Zhang T,et al.Path-finding through flexible hierarchical road networks:An experiential approach using taxi trajectory data[J].International JournalofAppliedEarthObservationand Geoinformation,2011,13:110-119.

[11] Fu L,Sun D,Rilett L R.Heuristic shortest path algorithms for transportation applications:State of the art[J].Computers&Operations Research,2006,33: 3324-3343.

[12] Liu B.Route finding by using knowledge about the road network[J].IEEE Transactions on Systems,Man,and Cybernetics-part A:Systems and Humans,1997,27 (4):436-448.

[13] Quadrifoglio L,Hall R W,Dessouky M M.Performance anddesignofmobilityallowanceshuttletransit services:bounds on the maximum longitudinal velocity[J].Transportation Science,2006,40(3): 351-363.

Bus Travel Algorithm Based on Vector Matching in Sparsely Populated Areas

ZHANG Kai,ZHANG Qiang,ZHUANG Liang
(School of Information and Control,Nanjing University of Information Science&Technology,Nanjing 210044,China)

People in sparsely populated areas such as suburbs and new cities traveling by bus have much inconvenience.To eliminate the defect of bus travel in these areas,a travel algorithm research is conducted. This paper proposes two algorithms,vector matching and pick-up path.Firstly,to match the direction between traveler's departure and destination location information and main road network route of service area. Secondly,a global optimal path planning is conducted for all successful matched request location information. Finally,experimental data analysis and conclusion are given based on the road network model and travel algorithm.The result shows that travel algorithm have the characteristic of humanized and point-to-point services to be different form regular bus,service quality is high,and travel cost is cheaper compared with taxi fee.In addition,average traveler's journey time is also within acceptable range,passenger satisfaction is higher,and the algorithm can well satisfy the wishes of people to travel conveniently and quickly.

urban traffic；travel algorithm；vector matching；sparsely populated areas；small bus；pickup path planning

U492.4

A

U492.4

A

1009-6744(2013)06-0127-07

2013-06-06

2013-07-15錄用日期:2013-08-14

張凱(1965-),男,山東泰安人,教授,博士.

*通訊作者:zkark@163.com