基于軌跡數(shù)據(jù)的出租車司機(jī)尋客路徑優(yōu)化方法

周 旦,孫家煜,顧國斌,鐘楚捷,王 濤

(1. 桂林電子科技大學(xué) 廣西智慧交通重點(diǎn)實(shí)驗(yàn)室,廣西 桂林 541004 ; 2. 寧波大學(xué) 海運(yùn)學(xué)院,浙江 寧波 315211;3. 深圳大學(xué) 建筑與城市規(guī)劃學(xué)院,廣東 深圳 518060)

0 引 言

隨著GPS定位技術(shù)的發(fā)展,軌跡數(shù)據(jù)的大量采集,大數(shù)據(jù)技術(shù)已深入交通各個(gè)方面。基于軌跡數(shù)據(jù)構(gòu)建出租車尋客路線推薦的研究已較為完善。在軌跡數(shù)挖掘中,多數(shù)文獻(xiàn)采用聚類方法挖掘隱含信息,但聚類方法中參數(shù)難以控制,因此筆者引進(jìn)K-距離曲線選取參數(shù)。周洋等[1]提出一種新型時(shí)空聚類算法AT-DBSCAN來識別軌跡中的停住點(diǎn);針對現(xiàn)有聚類算法缺陷,陸川偉等[2]提出一種基于核距離的車輛軌跡點(diǎn)聚類方法,并通過實(shí)例驗(yàn)證表明該方法的有效性;賽斌等[3]在點(diǎn)密度聚類算法基礎(chǔ)上提出一種基于軌跡相似度的聚類算法,實(shí)驗(yàn)結(jié)果表明該方法能在大規(guī)模數(shù)據(jù)集中有效提取軌跡;針對現(xiàn)有聚類算法和異常值檢測算法參數(shù)選取存在的問題,賀玉海等[4]提出一種基于K-Mediods和DBSCAN組合的聚類算法,結(jié)果表明該方法能更精確地識別異常軌跡;C.ADVANI等[5]基于歷史軌跡數(shù)據(jù)提出一種雙層嵌套結(jié)構(gòu)的聚類算法來構(gòu)建路徑選擇集。

現(xiàn)有文獻(xiàn)對出租車司機(jī)尋客路徑規(guī)劃的指標(biāo)選取多數(shù)以成本為主要目標(biāo),LIU Yizhi等[6]為了減少能源的消耗,提高出租車司機(jī)的收入,提出了一種基于熵的出租車巡航路線推薦模型,并通過實(shí)驗(yàn)證明該方法能夠有效提高出租車司機(jī)的收入;QU Boting等[7]為有效減少出租車的巡游距離提出了一種自適應(yīng)最短期望巡航路線推薦算法,并通過真實(shí)數(shù)據(jù)集對推薦算法進(jìn)行驗(yàn)證,結(jié)果表明該方法能有效減少出租車巡游距離;CHANG Mengmeng等[8]認(rèn)為交通系統(tǒng)運(yùn)行過程中產(chǎn)生大量的碳排放,有悖于當(dāng)今低碳的背景,對此他們提出了一種宏觀路徑推薦方法,有效提高了出租車運(yùn)營經(jīng)濟(jì)效益和達(dá)成碳中和的目標(biāo)。

關(guān)于尋客路徑推薦算法,Y.KIM等[9]針對尋客效率低下問題,提出一種出租車調(diào)度算法,并通過實(shí)驗(yàn)證明該方法能有效增加出租車司機(jī)的收益和利潤;王桐等[10]針對出租車司機(jī)盲目尋客,空載率高的問題提出一種基于循環(huán)神經(jīng)網(wǎng)絡(luò)的分時(shí)段預(yù)測算法和基于馬爾科夫決策過程的尋客推薦模型,并通過實(shí)驗(yàn)證明該預(yù)測與推薦方法的有效性;由于現(xiàn)有的空載車輛的路徑推薦算法,無法全面考慮真實(shí)路網(wǎng)環(huán)境中的各類因素,針對這一問題,陳冬梅等[11]基于候車點(diǎn)規(guī)劃提出了一種空載出租車的尋客路線推薦算法,并通過真實(shí)數(shù)據(jù)集驗(yàn)證該方法的有效性;廖祝華等[12]提出了一種基于稀疏軌跡數(shù)據(jù)的出租車司機(jī)尋客區(qū)域推薦算法。

現(xiàn)有研究雖采用的研究方法各不相同,但本質(zhì)上都是以最小成本為主要目標(biāo)進(jìn)行出租車尋客路徑規(guī)劃,缺乏全局考慮,這可能會導(dǎo)致城市內(nèi)部出租車為追求成本而造成時(shí)空供需不平衡。綜上所述,筆者在改進(jìn)的DBSCAN聚類算法的基礎(chǔ)上,利用成都市滴滴快專車歷史軌跡數(shù)據(jù)進(jìn)行時(shí)空特征分析,重點(diǎn)考慮載客概率、空載行駛時(shí)間和區(qū)域供需比3個(gè)指標(biāo),提出一種出租車司機(jī)尋客路徑推薦方法,對特定時(shí)段內(nèi)的出租車司機(jī)尋客路徑進(jìn)行研究分析。

1 出租車司機(jī)的尋客路徑推薦方法

1.1 尋客問題描述

當(dāng)出租車司機(jī)需進(jìn)行尋客時(shí),由于交通網(wǎng)絡(luò)錯(cuò)綜復(fù)雜,道路交通環(huán)境瞬息萬變,出租車司機(jī)無法全面掌握道路交通現(xiàn)狀以及出租車出行需求,傳統(tǒng)的出租車司機(jī)僅根據(jù)自身經(jīng)驗(yàn)進(jìn)行尋客,導(dǎo)致空載行駛時(shí)間較長,如何為出租車司機(jī)提供較優(yōu)的尋客路徑,做好供需對接匹配,對降低出租車空載率至關(guān)重要。為此,提出一種出租車司機(jī)尋客路徑推薦方法,結(jié)合歷史軌跡數(shù)據(jù),進(jìn)行下一時(shí)段的尋客路徑推薦,尋客問題描述如圖1。

圖1 尋客問題描述示意Fig. 1 Diagram of the problem description of customer seeking

已有的出租車調(diào)度對所花費(fèi)的時(shí)間過度理想化,適用于區(qū)域出租車調(diào)度。針對單個(gè)出租車司機(jī)尋客問題需綜合考慮供需比、空載行駛時(shí)間等指標(biāo)。在出租車司機(jī)尋客過程中首先重點(diǎn)考慮成本因素,對于空載行駛時(shí)間較長的路徑應(yīng)提前剔除。因此,考慮選擇載客概率、空載行駛時(shí)間和區(qū)域供需比作為尋客目標(biāo)點(diǎn)推薦指標(biāo),并采用改進(jìn)的Dijkstra算法確定尋客路徑。

1.2 引進(jìn)K-距離的DBSCAN算法

DBSCAN(density-based spatial clustering of appli-cations with noise)聚類算法是一種基于密度的空間聚類算法,該算法能根據(jù)區(qū)域內(nèi)密度大小將區(qū)域劃分為不同簇,并在存在噪聲點(diǎn)的數(shù)據(jù)當(dāng)中劃分出任意形狀區(qū)域的簇。其中,聚類半徑和最小密度閾值將直接影響聚類的結(jié)果,因此筆者引入k-距離曲線來計(jì)算聚類半徑,以確保參數(shù)選取的合理性以及聚類結(jié)果的準(zhǔn)確性。

K-距離指在一個(gè)給定數(shù)據(jù)集M={m(1),m(2),…m(f)}中,任取一點(diǎn)m(z),計(jì)算該點(diǎn)與數(shù)據(jù)集S中各點(diǎn)的距離,其中S指的是M剔除m(z)后的集合。將距離進(jìn)行排序,形成距離集合Q={q(1),q(2),…,q(f)},K-距離是點(diǎn)m(z)到所有點(diǎn)之間第K近的距離,對數(shù)據(jù)集M中的每個(gè)點(diǎn)以上述方式提取K-距離,最終形成K-距離集合T={t(1),t(2),…,t(f)},考慮數(shù)據(jù)特性,K在此處取值為1。當(dāng)K-距離曲線的斜率突然增加時(shí),即可選取該距離作為聚類半徑。

1.3 出租車司機(jī)尋客線路優(yōu)化

1.3.1 確定出租車司機(jī)尋客目標(biāo)點(diǎn)

灰色綜合評價(jià)法是在灰色關(guān)聯(lián)分析理論指導(dǎo)下對事物進(jìn)行綜合評價(jià)[13],常用于多個(gè)對象的量化比較排序問題。筆者將其用于確定出租車司機(jī)尋客目標(biāo)點(diǎn),從而綜合評價(jià)各個(gè)待選載客目標(biāo)點(diǎn),實(shí)現(xiàn)步驟如下:

步驟1確定待選尋客目標(biāo)點(diǎn)與評價(jià)指標(biāo)

設(shè)待選尋客目標(biāo)點(diǎn)為a個(gè),評價(jià)指標(biāo)為b個(gè),則待選尋客目標(biāo)點(diǎn)為xη={xη(g)|g=1,2,…,a},η=1,2,…,a。

評價(jià)指標(biāo)為:

x0={x0(ψ)|ψ=1,2,…,b}

(1)

為消除評價(jià)指標(biāo)中不同量綱與數(shù)量級影響,需對原始數(shù)據(jù)進(jìn)行規(guī)范處理,以確保結(jié)果的準(zhǔn)確性。筆者采用式(2)進(jìn)行無量綱處理。

(2)

步驟2確定各評價(jià)指標(biāo)權(quán)重系數(shù)

W=[ωψ|ψ=1,2,…,b]

(3)

步驟3計(jì)算灰色關(guān)聯(lián)系數(shù)ζi(k)

ζη(ψ)=

(4)

式中:ζη(ψ)為待選尋客目標(biāo)點(diǎn)xη與評價(jià)標(biāo)準(zhǔn)x0在第ψ個(gè)評價(jià)指標(biāo)上的偏差值,ρ∈[0,1],一般取ρ=0.5。若記

(5)

(6)

則Δmin與Δmax分別代表某個(gè)指標(biāo)中x0與xη的最小絕對值差與最大絕對值差。

步驟4計(jì)算灰色加權(quán)關(guān)聯(lián)度,建立灰色關(guān)聯(lián)度rη為:

(7)

式中:rη為第η個(gè)待選尋客目標(biāo)點(diǎn)對評價(jià)標(biāo)準(zhǔn)的灰色加權(quán)關(guān)聯(lián)度。

步驟5待選尋客目標(biāo)點(diǎn)綜合評價(jià)分析

根據(jù)計(jì)算所得的灰色加權(quán)關(guān)聯(lián)度大小,對各待選尋客目標(biāo)點(diǎn)進(jìn)行排序,關(guān)聯(lián)度的值越大表明該對象的評價(jià)結(jié)果越好。

1.3.2 確定出租車司機(jī)尋客線路

Dijkstra算法是一種計(jì)算最短路徑問題的貪心算法,能有效獲取源點(diǎn)s與各個(gè)節(jié)點(diǎn)之間的最短距離。因此,筆者基于改進(jìn)的Dijkstra算法獲取出租車司機(jī)最佳尋客路徑。其中圖G=(E,V),V為節(jié)點(diǎn)集合,E為邊集合,對圖中各個(gè)節(jié)點(diǎn)進(jìn)行標(biāo)號(di,pi),di為從源點(diǎn)到i點(diǎn)的最短距離,pi代表節(jié)點(diǎn)i的前趨節(jié)點(diǎn)號,實(shí)現(xiàn)步驟如圖2。

圖2 改進(jìn)的Dijkstra算法最短距離計(jì)算流程Fig. 2 Improved Dijkstra algorithm shortest distance calculation flowchart

步驟1參數(shù)初始化。從源點(diǎn)s出發(fā),令ds=0,di=+∞,i≠s,所有pi都為空,Ps={Vs},Ps2=V-{Vs},其中Ps為永久標(biāo)號集合,Ps2為臨時(shí)標(biāo)號集合;同理,從目標(biāo)點(diǎn)e出發(fā),令de=0,di=+∞,i≠e,所有pi都為空,Pe={Ve},Pe2=V-{Ve},其中Pe為永久標(biāo)號集合,Pe2為臨時(shí)標(biāo)號集合。

步驟2最短距離計(jì)算。從源點(diǎn)s出發(fā),對于與永久標(biāo)號集合Ps中的節(jié)點(diǎn)相連的節(jié)點(diǎn)Vi,且Vi∈Ps2,分別計(jì)算di=min(di,dk+lki),其中dk為節(jié)點(diǎn)Vk∈Ps與源點(diǎn)s之間的最短距離,lki為節(jié)點(diǎn)k到節(jié)點(diǎn)i的距離;同理,從目標(biāo)點(diǎn)e出發(fā),對于與永久標(biāo)號集合Pe中的節(jié)點(diǎn)相連的節(jié)點(diǎn)Vi,且Vi∈Pe2,分別計(jì)算di=min(di,dk+lki),其中dk為節(jié)點(diǎn)Vk∈Pe與目標(biāo)點(diǎn)e之間的最短距離,lki為節(jié)點(diǎn)k到節(jié)點(diǎn)i的距離。

步驟3節(jié)點(diǎn)標(biāo)記。從源點(diǎn)s出發(fā),若dj=min(di),則Ps=Ps∪{Vj};若dj=min(di),且節(jié)點(diǎn)Vk∈Ps2同時(shí)滿足dk≤ljk,則Ps=Ps∪{Vj,Vk}。同理,從目標(biāo)點(diǎn)e出發(fā),若dj=min(di),則Pe=Pe∪{Vj};若dj=min(di),且節(jié)點(diǎn)Vk∈Pe2同時(shí)滿足dk≤ljk,則Pe=Pe∪{Vj,Vk}。

步驟4重復(fù)步驟2和步驟3,直至Ps∩Pe≠?,得到源點(diǎn)到目標(biāo)點(diǎn)的最短路徑。

2 載客熱點(diǎn)區(qū)域挖掘

出租車出行需求具有時(shí)間周期性,因此需分時(shí)段進(jìn)行載客熱點(diǎn)區(qū)域挖掘。根據(jù)工作日以及早、晚高峰進(jìn)行分類。其中早高峰和晚高峰分別指08:00-09:00和18:00-19:00。

筆者選取2016年11月1日與2016年11月5日上下客點(diǎn)數(shù)據(jù)進(jìn)行研究,基于改進(jìn)的DBSCAN聚類算法分別挖掘工作日與非工作日中早、高峰上下客熱點(diǎn)區(qū)域,其中搜索半徑借助K-距離曲線確定為300 m,即掃描半徑為=0.002 7 km,最小密度閾值為80個(gè)。獲取的上下客熱點(diǎn)區(qū)域結(jié)果如圖3,其中左側(cè)為工作日熱點(diǎn)區(qū)域,右側(cè)為非工作日熱點(diǎn)區(qū)域。據(jù)圖3,工作日早高峰時(shí)段下車點(diǎn)較為集中,工作日晚高峰時(shí)段中上車點(diǎn)較為集中,且早高峰時(shí)段上車點(diǎn)多為居民區(qū),而晚高峰時(shí)段下車點(diǎn)多為居民區(qū)。在非工作日當(dāng)中,上下客熱點(diǎn)則無明顯規(guī)律。

圖3 工作日與非工作日早高峰時(shí)段上下客熱點(diǎn)區(qū)域Fig. 3 Hot spots for getting on and off passengers in the morning rush hours on weekdays and non-working days

3 出租車尋客路線推薦指標(biāo)構(gòu)建

3.1 出租車載客概率

居民出行需求具有時(shí)間差異性,導(dǎo)致載客熱點(diǎn)區(qū)域發(fā)生變化。因此,綜合考慮各區(qū)域內(nèi)部的出行需求以及出租車的供應(yīng)量,建立區(qū)域載客概率模型作為出租車司機(jī)路徑選擇的一個(gè)重要指標(biāo)[14]。不同區(qū)域內(nèi)載客的概率建立以下模型:

(8)

式中:P(Li)為Li區(qū)域內(nèi)的載客概率;I為載客熱點(diǎn)區(qū)域的個(gè)數(shù);NLi為Li區(qū)域內(nèi)訂單數(shù)據(jù)中上車點(diǎn)的數(shù)量;N為研究范圍內(nèi)所有訂單數(shù)量的總和。P(Li)的值越大,表明該區(qū)域?qū)Τ鲎廛囁緳C(jī)的吸引力越大。

3.2 出租車空載行駛時(shí)間

空載行駛時(shí)間由路段行駛時(shí)間和路口間行駛時(shí)間兩部分組成。路段行駛時(shí)間為從當(dāng)前位置到最近路口的行駛時(shí)間與路口到目標(biāo)點(diǎn)的行駛時(shí)間之和;路口間行駛時(shí)間為兩個(gè)路口間最短行駛時(shí)間。其中路口間的行駛路線由改進(jìn)的Dijkstra最短路徑規(guī)劃算法獲取,行駛速度由路段行駛的理想車速代替,基于此構(gòu)建以下數(shù)學(xué)模型:

(9)

式中:T為出租車司機(jī)從當(dāng)前位置到達(dá)目標(biāo)點(diǎn)的空載行駛時(shí)間;D(0,1)為從當(dāng)前位置到最近的一個(gè)路口的距離;v(0,1)為從當(dāng)前位置到最近的一個(gè)路口的路段行駛速度,以此類推。綜合起來構(gòu)成空載行駛時(shí)間。

3.3 區(qū)域出租車供需比

區(qū)域出租車供需比指在某一時(shí)間段內(nèi)某個(gè)區(qū)域內(nèi)部的出租車出行需求與出租車供應(yīng)量的比值。理想狀態(tài)下的區(qū)域出租車供需比應(yīng)該恒定為1。若區(qū)域出租車供需比值大于1,代表供不應(yīng)求。其中,出租車的出行需求量可使用t時(shí)刻的上車點(diǎn)代替,出租車的供應(yīng)量可使用t-Δt時(shí)刻的下車點(diǎn)代替?；诖?構(gòu)建以下區(qū)域出租車供需比值的模型。

(10)

3.4 尋客推薦約束

為盡可能的減少出租車司機(jī)漫無目的地巡游距離,需要限制出租車司機(jī)尋客距離。多數(shù)滴滴快專車司機(jī)訂單間空載時(shí)間均小于20 min,根據(jù)出租車市區(qū)的平均車速20～25 km/h[15],得出租車最大空載行駛距離約為5 km,因此對尋客目標(biāo)點(diǎn)的推薦建立以下約束:

Lβγ≤5

(11)

式(11)表示出租車當(dāng)前所在位置與尋客目標(biāo)點(diǎn)之間的距離應(yīng)不大于5 km。

與此同時(shí),對目標(biāo)尋客點(diǎn)還應(yīng)進(jìn)行供需比約束,對于供需比大于1的載客熱點(diǎn)區(qū)域應(yīng)進(jìn)行剔除。

Sθ<1

(12)

式(12)表示作為載客熱點(diǎn)區(qū)域的出租車供應(yīng)量應(yīng)小于需求量。

4 實(shí)例分析

4.1 尋客目標(biāo)區(qū)域篩選

為確保尋客路徑選擇指標(biāo)能較好的適用于大部分出租車司機(jī),將下客熱點(diǎn)區(qū)域的質(zhì)心作為出租車司機(jī)的當(dāng)前位置來進(jìn)行尋客路徑推薦。筆者將出租車司機(jī)的當(dāng)前位置設(shè)定為(E104.101°,N30.707°),實(shí)際位置為四川省成都市成華區(qū)成都市動(dòng)物園西側(cè)。

為提高出租車司機(jī)的尋客效率,選擇合適的線路和目的地,將載客熱點(diǎn)作為出租車司機(jī)尋客目的地。同時(shí)為保證時(shí)效性,載客熱點(diǎn)應(yīng)根據(jù)一小時(shí)前歷史軌跡數(shù)據(jù)通過信息挖掘獲取。筆者對2016年11月1日早高峰訂單數(shù)據(jù)進(jìn)行聚類,將上客熱點(diǎn)作為尋客目標(biāo)點(diǎn)。計(jì)算得8個(gè)待選尋客目標(biāo)點(diǎn),對尋客目標(biāo)點(diǎn)進(jìn)行篩選以確定最優(yōu)的目標(biāo)尋客點(diǎn)。

各尋客目標(biāo)區(qū)域的供需比,距離進(jìn)行計(jì)算結(jié)果如圖4、圖5。

圖4 當(dāng)前位置與各待選熱點(diǎn)的距離Fig. 4 The distance between the current position and each candidate hotspot

圖5 各待選熱點(diǎn)周圍區(qū)域供需比Fig. 5 Supply and demand ratio of the surrounding areas of each candidate hotspot

計(jì)算設(shè)定的出租車司機(jī)尋客位置與各個(gè)待選載客熱點(diǎn)之間的直線距離和供需比,如表1。據(jù)表1,結(jié)合上述約束條件,將與當(dāng)前所在位置大于5 000 m的待選載客點(diǎn)進(jìn)行剔除,即剔除C1號待選點(diǎn)和C6號待選點(diǎn)。

表1 各尋客目標(biāo)點(diǎn)的約束指標(biāo)Table 1 Constraint indicators for each customer seeking target point

4.2 基于灰色綜合評價(jià)的尋客區(qū)域選取

4.2.1 評價(jià)指標(biāo)體系構(gòu)建

出租車司機(jī)尋客目標(biāo)區(qū)域的選取,需綜合考慮多方面的影響因素,同時(shí)各指標(biāo)會對結(jié)果產(chǎn)生不同的影響程度[16]。選擇能影響出租車司機(jī)尋客目標(biāo)區(qū)域選擇的4項(xiàng)指標(biāo)。即:第一出租車載客概率,期望的概率越高越好;第二出租車空載行駛時(shí)間,期望的時(shí)間越低越好;第三區(qū)域出租車供需比,期望的比值越低越好;第四距各待選點(diǎn)距離,期望的距離越短越好。對于上述4項(xiàng)評價(jià)指標(biāo),采用專家打分的方式確定權(quán)重系數(shù),最終采用的權(quán)重系數(shù)按上述指標(biāo)的先后順序分別為:W=(0.35,0.20,0.35,0.10)T。

4.2.2 各項(xiàng)指標(biāo)數(shù)據(jù)

剩余6個(gè)待選載客熱點(diǎn)區(qū)域的各項(xiàng)指標(biāo)數(shù)據(jù)如表2。為消除量綱與數(shù)量級不同產(chǎn)生的影響,需對上述指標(biāo)值進(jìn)行規(guī)范化處理,采用均值化處理方式,結(jié)果如表3。其中,理想對象為各待選區(qū)域中每一項(xiàng)評價(jià)指標(biāo)的最優(yōu)值,部分指標(biāo)最優(yōu)值為最小值,而部分指標(biāo)最優(yōu)值為最大值,因此以最優(yōu)值為基礎(chǔ)構(gòu)造各指標(biāo)的評價(jià)標(biāo)準(zhǔn)。

表2 評價(jià)指標(biāo)數(shù)據(jù)Table 2 Evaluation indicator data

表3 規(guī)范化后的指標(biāo)數(shù)據(jù)Table 3 Normalized indicator data

4.2.3 指標(biāo)計(jì)算

1)計(jì)算各項(xiàng)指標(biāo)關(guān)聯(lián)系數(shù)

計(jì)算可得:ζ1(1)=1,ζ1(2)=0.625,ζ1(3)=0.500,ζ1(4)=0.543同理,計(jì)算其余指標(biāo)關(guān)聯(lián)系數(shù),將計(jì)算結(jié)果拼接得到各指標(biāo)的評判矩陣E:

2)計(jì)算各項(xiàng)指標(biāo)加權(quán)關(guān)聯(lián)度

R=E×W=(0.704,0.646,0.894,0.751,0.792,0.554)T

式中:R=(r1,r2,…,r6)T為6個(gè)尋客目標(biāo)待選區(qū)域的綜合評價(jià)結(jié)果向量。根據(jù)計(jì)算所得的關(guān)聯(lián)度進(jìn)行排序,得到關(guān)聯(lián)序?yàn)閞3>r5>r4>r1>r2>r6。

由上述關(guān)聯(lián)序可發(fā)現(xiàn),r3的關(guān)聯(lián)度最大,即選擇C3載客熱點(diǎn)區(qū)域作為出租車司機(jī)尋客推薦目標(biāo)區(qū)域。目標(biāo)點(diǎn)經(jīng)緯度坐標(biāo)為(104.101,30.685),實(shí)際位置為四川省成都市成華區(qū)刃具立交。在進(jìn)行載客點(diǎn)目標(biāo)點(diǎn)的選取后,根據(jù)出租車司機(jī)的當(dāng)前位置進(jìn)行路徑選擇規(guī)劃。

4.3 基于改進(jìn)的Dijkstra算法的尋客路線選取

4.3.1 最優(yōu)路線選取

根據(jù)尋客目標(biāo)區(qū)域選取結(jié)果,對出租車司機(jī)進(jìn)行從當(dāng)前所在位置到目標(biāo)尋客點(diǎn)的路徑規(guī)劃。即從(104.101,30.707)到(104.101,30.685),實(shí)際位置從四川省成都市成華區(qū)成都市動(dòng)物園西側(cè)到四川省成都市成華區(qū)刃具立交附近,兩點(diǎn)間的直線距離約為2 412.99 m,行駛時(shí)間在20 min以內(nèi)。

根據(jù)起終點(diǎn)位置構(gòu)建本文研究所需路網(wǎng)如圖6。該路網(wǎng)共有20個(gè)交叉節(jié)點(diǎn),56條有向路段,其中數(shù)字表示路段長度,出發(fā)地點(diǎn)為節(jié)點(diǎn)1,目的地為節(jié)點(diǎn)20。結(jié)合上述構(gòu)建的路網(wǎng),借助改進(jìn)的Dijkstra算法計(jì)算最短路徑。為驗(yàn)證設(shè)計(jì)的算法。根據(jù)改進(jìn)的Dijkstra算法求得最優(yōu)路徑為1-2-4-10-15-20,行駛距離為3 547 m。

圖6 當(dāng)前位置到目的地路網(wǎng)Fig. 6 Road network from current location to destination

4.3.2 常見方法對比分析

在本實(shí)例分析中,不同節(jié)點(diǎn)數(shù)量情況下,Foyld、Best-first、經(jīng)典Dijkstra和改進(jìn)的Dijkstra算法所對應(yīng)的時(shí)間復(fù)雜度與計(jì)算時(shí)間如圖7。其中,時(shí)間復(fù)雜度是指計(jì)算過程中循環(huán)迭代次數(shù)具體表達(dá)式。由圖7可直觀看出,對相同規(guī)模的數(shù)據(jù)集,筆者所改進(jìn)的Dijkstra算法在最短路徑搜索中具有更快的搜索速度,迭代次數(shù)明顯減少。依據(jù)傳統(tǒng)的Dijkstra算法獲取最短路徑需進(jìn)行20次計(jì)算,而筆者提出的改進(jìn)后的Dijkstra算法獲取最短路徑僅需通過8次計(jì)算,同時(shí)4種方法得到的最終結(jié)果均為同一條尋客線路,因此筆者提出的改進(jìn)的Dijkstra算法能有效提高最短路徑的計(jì)算速度,更加及時(shí)準(zhǔn)確的為出租車司機(jī)提供一條尋客線路。

圖7 常見算法時(shí)間復(fù)雜度對比Fig. 7 Comparison of time complexity of common algorithms

4.3.3 常見線路比選

根據(jù)轉(zhuǎn)彎次數(shù)最少、途經(jīng)紅綠燈最少、途經(jīng)居住地最多等原則共計(jì)篩選得出以下3條路徑,作為備選路徑,與上文計(jì)算得出的路線進(jìn)行對比,結(jié)果如表4。

表4 備選路徑集合Table 4 Collection of alternate paths

根據(jù)改進(jìn)的Dijkstra算法得到最終的尋客路線,且該方法得出的線路相較于常見方案的平均行駛距離減少21.33%,相較于常見方案的平均行駛時(shí)間減少22.16%。通過實(shí)例對比分析證明筆者所提出的方法具有一定的合理性,能有效減少出租車司機(jī)的空載行駛時(shí)間和形式距離,為出租車司機(jī)的尋客線路選擇提供正確的指導(dǎo),以提高出租車出行的服務(wù)水平,減少環(huán)境和能源的消耗成本。

5 結(jié) 論

筆者在綜合考慮空載行駛時(shí)間、載客概率、供需比等相關(guān)指標(biāo)的基礎(chǔ)上,提出一種出租車尋客路徑優(yōu)化方法,基于改進(jìn)的DBSCAN聚類算法及灰色綜合評價(jià)法,得出尋客目標(biāo)區(qū)域,并利用改進(jìn)的Dijkstra算法,提高最短路徑搜索速度,構(gòu)建出租車司機(jī)尋客路徑選擇優(yōu)化方案。本研究的主要結(jié)論如下:

1)根據(jù)訂單數(shù)據(jù)繪制的熱力圖與聚類獲取的載客熱點(diǎn)的比對結(jié)果,表明引進(jìn)K-距離的DBSCAN聚類算法聚類質(zhì)量較優(yōu)。聚類結(jié)果可為出租車司機(jī)尋客巡游區(qū)域提供參考。

2)引入標(biāo)號永久化新規(guī)則和雙向搜索的Dijkstra算法相較于Best-first、Foyld和經(jīng)典Dijkstra算法時(shí)間復(fù)雜度顯著降低,由20次計(jì)算過程減少至8次;最終,筆者提出的出租車司機(jī)尋客路徑選取方案獲取的尋客線路,較其他備選方案行駛距離減少約21.33%,通行時(shí)間較其他備選方案減少約22.16%,能有效減少出租車空載率,進(jìn)而提高出租車出行的舒適度,對出租車尋客線路的指導(dǎo)具有一定的通用性。

3)除筆者所述的對于出租車司機(jī)尋客目標(biāo)區(qū)域與尋客路線選取的影響因素以外還存在許多不容忽視的影響因素。在進(jìn)一步的研究中,可對如天氣狀況,出租車司機(jī)的收入等個(gè)人因素和心理因素以及道路擁擠狀況等進(jìn)行量化,以提高出租車司機(jī)尋客線路選取的合理性。