基于乘客需求數(shù)據(jù)的定制商務(wù)班車站點(diǎn)選址方法

孫悅, 宋瑞，邱果

(北京交通大學(xué)綜合交通運(yùn)輸大數(shù)據(jù)應(yīng)用技術(shù)交通運(yùn)輸行業(yè)重點(diǎn)實(shí)驗(yàn)室，北京 100044)

定制商務(wù)班車(customized business bus, CBB)的概念源于定制公交(subscription bus)，定制公交是根據(jù)乘客個(gè)性化需求，以多人共用車輛的形式設(shè)定線路，為出行起終點(diǎn)、出行時(shí)間、服務(wù)水平需求相似的人群提供量身定制的客運(yùn)服務(wù)方式[1]。定制商務(wù)班車是依托互聯(lián)網(wǎng)平臺(tái)，由乘客在平臺(tái)上提交通勤出行需求，運(yùn)營(yíng)方根據(jù)這些需求設(shè)計(jì)乘客上下班線路，并利用平臺(tái)招募乘客、預(yù)訂座位、在線支付的一種公交服務(wù)方式[2]。定制商務(wù)班車既繼承了定制公交對(duì)乘客需求進(jìn)行聚合的基本特征，同時(shí)又依托互聯(lián)網(wǎng)平臺(tái)，服務(wù)對(duì)象更集中于通勤乘客。

在常規(guī)公交站點(diǎn)選址問(wèn)題的研究上，國(guó)內(nèi)外學(xué)者已取得了較多的成果。葉英杰[3]把空間co-location模式挖掘技術(shù)應(yīng)用在城市公交站點(diǎn)選址分布的研究當(dāng)中。Saka[4]得出公交站點(diǎn)站間距的最優(yōu)設(shè)置可以通過(guò)最小化公交車服務(wù)數(shù)量降低運(yùn)營(yíng)成本。Chien等[5]以總費(fèi)用效益函數(shù)最小為目標(biāo)優(yōu)化了公交站點(diǎn)的數(shù)量和布局。Ziari等[6]提出了一種優(yōu)化公交站點(diǎn)選址問(wèn)題的新方法，并對(duì)總出行時(shí)間、選取速度等參數(shù)進(jìn)行了靈敏度分析。Alonso等[7]研究了在不同擁擠程度網(wǎng)絡(luò)的條件下，用雙層優(yōu)化模型求解公交站點(diǎn)的最佳位置。上層目標(biāo)效益函數(shù)為社會(huì)費(fèi)用最小，下層包括方式劃分分配模型。Moura等[8]用兩階段模型分析了公交車站的最優(yōu)位置，第一階段以網(wǎng)絡(luò)的社會(huì)費(fèi)用最低為目標(biāo)，從戰(zhàn)略層面確定公交站點(diǎn)宏觀的位置；第二階段以公交服務(wù)的運(yùn)營(yíng)速度最大為目標(biāo)，從戰(zhàn)術(shù)層面獲取特定線路站點(diǎn)的微觀位置。

定制商務(wù)班車的站點(diǎn)選址問(wèn)題是根據(jù)出行需求中乘客的居住點(diǎn)、工作點(diǎn)的地理位置，結(jié)合基礎(chǔ)道路網(wǎng)等情況，對(duì)?？空军c(diǎn)進(jìn)行選址的過(guò)程[1]。郭戎格[9]依據(jù)公交IC卡數(shù)據(jù)，運(yùn)用OD站點(diǎn)識(shí)別算法等手段進(jìn)行乘客出行空間特征分析研究。鄒彥雯[1]通過(guò)改進(jìn)K-means聚類算法，提出了IKCBB聚類算法用于對(duì)定制商務(wù)班車的站點(diǎn)選址問(wèn)題進(jìn)行求解。Kim等[10]在對(duì)站點(diǎn)選址的研究中建立了以乘客總出行距離最短和均衡每位乘客出行距離的班車站點(diǎn)設(shè)置模型。Shaffiei等[11]在一般的車輛路徑問(wèn)題中引入時(shí)間成本的概念，對(duì)原有站點(diǎn)進(jìn)行合并或者加入新的站點(diǎn)。Cipriani等[12]分析了羅馬市為代表的大型城市公交站點(diǎn)布設(shè)問(wèn)題，開(kāi)發(fā)了一種解決多對(duì)多的乘客出行需求的新算法。Nikolic等[13]將基于群體智慧的蜂群算法用于解決定制公交站點(diǎn)規(guī)劃的組合優(yōu)化問(wèn)題。

不同于常規(guī)公交，定制商務(wù)班車更加重視對(duì)乘客需求數(shù)據(jù)的搜集、處理與分析。但現(xiàn)有研究使用的聚類算法較單一，主要以改進(jìn)的K-means算法為主，而K-means算法需要提前指定聚類組號(hào)且無(wú)法規(guī)避噪聲點(diǎn)的影響，聚類質(zhì)量較差。同時(shí)，現(xiàn)有的研究對(duì)于如何在完成初步聚類后結(jié)合周圍區(qū)位和出行條件因地制宜地進(jìn)行選址探討不多，研究的實(shí)踐性不強(qiáng)。

為更好地解決定制商務(wù)班車選址問(wèn)題，本文采用了基于密度的帶有噪聲的空間聚類(density-based spatial clustering of applications with noise, DBSCAN)算法來(lái)規(guī)避噪聲點(diǎn)的影響和進(jìn)行聚類組別的指定，同時(shí)為了體現(xiàn)定制商務(wù)班車精細(xì)化服務(wù)的特征，引入精細(xì)化指標(biāo)指導(dǎo)聚類迭代，并結(jié)合區(qū)位和節(jié)點(diǎn)重要度思想對(duì)站點(diǎn)選址做出改進(jìn)，增加了研究的實(shí)踐性。

1 DBSCAN算法

1.1 相關(guān)定義

在DBSCAN算法中[14]，任意樣本點(diǎn)N的ε鄰域指以該點(diǎn)為中心，半徑為Eps的區(qū)域，即圖中以任意點(diǎn)為圓心，以長(zhǎng)度為Eps的實(shí)線箭頭為半徑繪制得到的各種圓圈，如圖1所示。

圖1 DBSCAN算法概念Fig. 1 DBSCAN algorithm concept diagram

若樣本點(diǎn)M的ε鄰域內(nèi)包含的樣本點(diǎn)數(shù)大于等于最小包含點(diǎn)個(gè)數(shù)minPts, 則M為核心點(diǎn)。圖1是以minPts=3來(lái)繪制的，圖中以圓點(diǎn)為圓心的圓圈所包含的樣本點(diǎn)數(shù)均達(dá)到這一閾值，所以圖中圓點(diǎn)均為核心點(diǎn)。

圖中五邊形點(diǎn)和三角形點(diǎn)均為非核心點(diǎn)，其ε鄰域包含的樣本點(diǎn)數(shù)均未達(dá)到minPts的個(gè)數(shù)要求。其中五邊形點(diǎn)為邊界點(diǎn)，三角形點(diǎn)為噪聲點(diǎn)，二者的區(qū)別方式取決于該點(diǎn)是否能從核心點(diǎn)密度可達(dá)。密度可達(dá)是DBSCAN算法用于說(shuō)明樣本間緊密聯(lián)系程度的概念，由密度直達(dá)的概念引出。

密度直達(dá)如圖中點(diǎn)Q與點(diǎn)M的關(guān)系所示，點(diǎn)Q位于點(diǎn)M的ε鄰域內(nèi)，而點(diǎn)M是核心點(diǎn)，所以點(diǎn)Q從點(diǎn)M密度直達(dá)，在圖中用虛線箭頭表示。而點(diǎn)M位于點(diǎn)P的ε鄰域內(nèi)，所以，點(diǎn)M從點(diǎn)P密度直達(dá)。因此點(diǎn)Q和點(diǎn)P以點(diǎn)M為橋梁建立了聯(lián)系，這種聯(lián)系在DBSCAN算法中被稱為密度可達(dá)。

密度可達(dá)的關(guān)系如圖中O、U、V、R所示，由于U、V之間密度直達(dá)，因而點(diǎn)R可從點(diǎn)O密度可達(dá)，而此時(shí)U、V都為核心點(diǎn)，故密度可達(dá)可以進(jìn)行傳遞，點(diǎn)S從點(diǎn)O密度可達(dá)，故點(diǎn)R和點(diǎn)S密度相連。

在站點(diǎn)選址問(wèn)題的實(shí)際應(yīng)用中，掃描半徑可代表行人距離定制商務(wù)班車的步行路徑，最小包含點(diǎn)個(gè)數(shù)可代表滿足定制商務(wù)班車的上車人數(shù)，密度直達(dá)點(diǎn)代表滿足定制商務(wù)班車設(shè)站要求的一群乘客，而密度可達(dá)點(diǎn)表示這一類乘客的步行距離較近，可以視為集群分布。

1.2 DBSCAN聚類算法的流程

已知Dw為D中未被聚類點(diǎn)的集合，k為聚類別數(shù)，初始狀態(tài)下令Dw=D，k=0, DBSCAN算法的主要執(zhí)行步驟[15]可描述為：

步驟1：任意選擇Dw中的一個(gè)點(diǎn)xj。若xj為非核心點(diǎn)，則執(zhí)行步驟2；若xj為核心點(diǎn)，則執(zhí)行步驟3。

步驟2: 將xj標(biāo)記為噪聲點(diǎn)，并從集合Dw中刪除xj，注意此處僅在集合Dw中刪除xj，xj仍在集合D中，仍可被其他核心點(diǎn)掃描到并劃分到相應(yīng)類簇。

步驟3：令k=k+1，確定D中所有與xj密度可達(dá)的點(diǎn)，并把xj及其密度可達(dá)點(diǎn)劃分到類Ck中，并將Ck中的點(diǎn)從集合Dw中刪除。

步驟4：若Dw中仍存在點(diǎn)未進(jìn)行考察，則重復(fù)執(zhí)行步驟1～3，直到Dw中的點(diǎn)被考察完畢為止。

由此可見(jiàn)，DBSCAN算法通過(guò)計(jì)算樣本點(diǎn)間的緊密聯(lián)系程度，找到密度相連點(diǎn)的最大集合并將其劃分為一類，不同的密度相連集合構(gòu)成了最終的聚類結(jié)果[16]。因此，DBSCAN算法能夠識(shí)別噪聲點(diǎn)，有效地防止了離散程度較大的樣本點(diǎn)對(duì)聚類結(jié)果的影響。同時(shí)DBSCAN算法根據(jù)密度相連關(guān)系自動(dòng)生成類別，可以根據(jù)數(shù)據(jù)特征生成類別而不需要指定聚類數(shù)，對(duì)數(shù)據(jù)的適應(yīng)性強(qiáng)。但如果數(shù)據(jù)的密度分布較不均勻，聚類間距較大時(shí)，DBSCAN算法的聚類質(zhì)量會(huì)顯著降低。DBSCAN算法的聚類參數(shù)Eps及minPts往往根據(jù)經(jīng)驗(yàn)選取，如果選擇不合理對(duì)整體的聚類效果影響很大。由于定制商務(wù)班車的選址需要輸出建議選址地點(diǎn)，這就要求DBSCAN算法不僅要輸出類簇劃分，還要生成聚類中心，這是基本的DBSCAN聚類算法不具備的。

2 改進(jìn)的DBSCAN算法

2.1 改進(jìn)的DBSCAN算法設(shè)計(jì)

2.1.1 精細(xì)化程度的衡量

基本的DBSCAN聚類算法可根據(jù)樣本集合中各樣本點(diǎn)的距離來(lái)進(jìn)行劃分，距離的度量采用歐氏距離的方式，因而該算法可以根據(jù)給定的聚類參數(shù)Eps和minPts確定聚類個(gè)數(shù)而不需要提前指定所需的聚類數(shù)。但在定制商務(wù)班車選址問(wèn)題的實(shí)際應(yīng)用中，聚類所得的各類簇包含的樣本點(diǎn)個(gè)數(shù)不同，所處的城市區(qū)位不盡相同，有的類簇包含的樣本點(diǎn)數(shù)量多且分布較廣，出行客流量較大，需要進(jìn)一步甄別出行需求，增設(shè)站點(diǎn)貫徹定制商務(wù)班車精細(xì)化服務(wù)的理念[17]。而有的類簇包含的樣本點(diǎn)數(shù)量少且分布集中，出行客流量較少，本著節(jié)約成本的原則不需要再進(jìn)一步設(shè)站。鑒于此，本文在基本DBSCAN聚類算法的基礎(chǔ)上提出了類簇精細(xì)化判別步驟，根據(jù)類簇內(nèi)樣本點(diǎn)離散程度、類簇間客流的出行量和出行距離計(jì)算精細(xì)服務(wù)指數(shù)，對(duì)各類簇的精細(xì)化程度進(jìn)行判斷并分而治之。

2.1.1.1 類簇內(nèi)離散程度分析

在對(duì)劃分的類簇進(jìn)行相應(yīng)的公交站設(shè)置時(shí)，如果類簇內(nèi)的樣本點(diǎn)間距較遠(yuǎn)，證明其對(duì)應(yīng)的乘客對(duì)上車站點(diǎn)的要求彼此距離較大，站點(diǎn)設(shè)置較少會(huì)增大乘客的步行距離，無(wú)法體現(xiàn)定制商務(wù)班車門(mén)對(duì)門(mén)服務(wù)的優(yōu)勢(shì)，因而有對(duì)類簇進(jìn)行精細(xì)化劃分的需要。為了衡量類簇的離散程度，采用誤差平方和作為標(biāo)準(zhǔn)測(cè)度函數(shù)，使所獲得的聚類本身盡可能地緊湊，而各聚類盡可能地分開(kāi)。采用的誤差平方和具體定義如下：

(1)

式中：αSSECp為類簇Cp中任意需求點(diǎn)到其他需求點(diǎn)的誤差平方和的最大值；xj為類簇Cp中的任意需求點(diǎn)；cpcen為類簇Cp的質(zhì)心；‖·‖為歐氏距離。

2.1.1.2 類簇間重要度分析

在城市區(qū)位理論中，若一個(gè)小區(qū)到其他小區(qū)的客流出行量較大，出行距離較短，證明該小區(qū)的區(qū)位重要度高，往往對(duì)應(yīng)著大型商業(yè)圈，居民區(qū)等，而這些區(qū)域正是定制商務(wù)班車服務(wù)的起始點(diǎn)，因此能夠正確地識(shí)別區(qū)位重要度對(duì)設(shè)置定制商務(wù)班車站點(diǎn)有十分重要的意義[18]。本文引入?yún)^(qū)位重要度的理念，將類簇視為區(qū)位重要度中的單元小區(qū)，根據(jù)各類簇間的客流量和出行距離分別計(jì)算類簇的重要度并進(jìn)行比較，優(yōu)先對(duì)區(qū)位重要度較高的類簇進(jìn)行精細(xì)化服務(wù)。

在計(jì)算類簇重要度時(shí)，對(duì)于DBSCAN算法得到的類簇集，計(jì)算各類簇間客流量矩陣A：

(2)

其中，apq為類簇Cp至類簇Cq的乘客出行量。

將各類簇的質(zhì)心設(shè)置為類簇內(nèi)樣本點(diǎn)的坐標(biāo)平均值，并建立各類簇間的出行距離矩陣B：

(3)

其中，bpq為類簇Cp至類簇Cq質(zhì)心之間的距離?？紤]類簇間客流強(qiáng)度和出行距離對(duì)類簇重要度的影響，類簇間客流量越大，出行距離越短，則該類簇重要度越高，得出類簇重要度的計(jì)算公式如下：

(4)

對(duì)上述兩個(gè)指標(biāo)進(jìn)行量綱的統(tǒng)一，得出精細(xì)化服務(wù)指標(biāo)為：

χ=αSSECp+ωβCIMPCp，

(5)

其中，ω為量綱統(tǒng)一系數(shù)，因類簇重要度為整數(shù)，而類簇內(nèi)離散程度為小數(shù)，該系數(shù)設(shè)置不影響結(jié)果，得出的量綱統(tǒng)一系數(shù)是為了方便計(jì)算。

2.1.2 聚類參數(shù)Eps和minPts的選擇

根據(jù)2.1.1可知，對(duì)于精細(xì)化服務(wù)指數(shù)較高的類簇，需要利用DBSCAN算法對(duì)其進(jìn)行進(jìn)一步聚類，而初始聚類的參數(shù)Eps和minPts已經(jīng)不適用精細(xì)化聚類的要求[19]。在定制商務(wù)班車發(fā)展尚不成熟的條件下，根據(jù)經(jīng)驗(yàn)改變聚類參數(shù)可能會(huì)出現(xiàn)較大誤差。同時(shí)統(tǒng)一改變聚類參數(shù)，將其作為精細(xì)化聚類的全局變量無(wú)法體現(xiàn)定制商務(wù)班車因地制宜的特點(diǎn)。因此，本文提出利用最大最小值距離法(maximum and minimum distance, MMD)[20]，根據(jù)數(shù)據(jù)特征自適應(yīng)更新聚類參數(shù)，得到最適用于該類簇更新的聚類參數(shù)。

聚類參數(shù)Eps和minPts的更新方式為：針對(duì)待精細(xì)化的類簇Cu,分別計(jì)算其任意兩個(gè)樣本間的距離，得到樣本距離集合ECu：

ECu=(e1,e2,…,em,…)

。

(6)

統(tǒng)計(jì)集合中ECu中最小最大距離值min(ECu),max(ECu)，將其差值max(ECu)-min(ECu)劃分為z個(gè)不同的取值區(qū)間，考察每一區(qū)間包含的樣本對(duì)數(shù)，并構(gòu)建統(tǒng)計(jì)量HCu:

(7)

其中，lz為第z個(gè)區(qū)間內(nèi)包含的樣本對(duì)數(shù)。找到包含最多樣本對(duì)數(shù)的區(qū)間號(hào)h，則類簇Cu對(duì)應(yīng)的更新后的Eps的參數(shù)值為第h個(gè)區(qū)間對(duì)應(yīng)樣本距離的中心值，該中心值的計(jì)算方法為：

(8)

其中，Δeu=[max(ECu)-min(ECu)]/z。更新后的minPts的值則為類簇Cu中所有樣本在更新后的ε鄰域內(nèi)包含的樣本量的最大值。

2.1.2 聚類中心計(jì)算與站點(diǎn)選址

聚類得到的各類簇經(jīng)過(guò)精細(xì)化衡量之后，通過(guò)自適應(yīng)調(diào)整聚類參數(shù)進(jìn)行進(jìn)一步聚類，最終使得全部類簇不需要再進(jìn)行精細(xì)化，此時(shí)得到的類簇即為可進(jìn)行選址依據(jù)的類簇。而基本的DBSCAN算法不能生成聚類中心，傳統(tǒng)的聚類算法對(duì)于聚類中心的計(jì)算主要以歐氏距離最小為依據(jù)[21]。

傳統(tǒng)的公交站點(diǎn)選址方法主要是根據(jù)交通部門(mén)劃分的線路，在城市道路實(shí)地考察，偏重問(wèn)卷調(diào)查和實(shí)地訪問(wèn)，最后匯總市民意見(jiàn)，根據(jù)需求呼聲最大的確定線路建設(shè)方案[22]。定制商務(wù)班車根據(jù)乘客個(gè)性化需求，通過(guò)集合這些需求的共同點(diǎn)，以多人共用交通工具的形式設(shè)定線路，是為出行起訖點(diǎn)、出行時(shí)間、服務(wù)水平需求相似的人群提供量身定制的客運(yùn)服務(wù)方式，具有定點(diǎn)、定時(shí)、定車、定人等特點(diǎn)和“一人一座、一站直達(dá)、線路靈活”等優(yōu)勢(shì)。在國(guó)內(nèi)，定制商務(wù)班車具有服務(wù)范圍大、乘客規(guī)模相對(duì)較小、線路設(shè)計(jì)靈活、需求響應(yīng)迅速、按需而設(shè)、乘客黏度較高等特點(diǎn)。因此，在定制商務(wù)班車的站點(diǎn)選址過(guò)程中，要盡可能地選擇有利于大站開(kāi)行，道路條件優(yōu)良，有利于發(fā)揮定制商務(wù)班車速度快、質(zhì)量高的地點(diǎn)，因而在選址過(guò)程中應(yīng)該考慮公交專用道、公交快線的遠(yuǎn)近。同時(shí)由于軌道交通站點(diǎn)附近客流疏散能力較強(qiáng)，可以作為定制公交站點(diǎn)選址的參考。

所以，本文引入節(jié)點(diǎn)重要度的思想，將不需精確化的類簇中的樣本點(diǎn)作為備選節(jié)點(diǎn)，建立網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)指標(biāo)，對(duì)各節(jié)點(diǎn)的重要度進(jìn)行評(píng)價(jià)作為選址的依據(jù)。

類簇Cv內(nèi)樣本點(diǎn)j的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)指標(biāo)值為：

δWTj=ρ×fjr+ρ×fjb+γ×fjz,

(9)

式中，fjr為樣本點(diǎn)j連接軌道線路的邊數(shù)；fjb為樣本點(diǎn)j連接BRT公交快線的邊數(shù)；fjz為樣本點(diǎn)j連接的城市道路可用于公交專用道的車道數(shù)；ρ、φ、γ分別為fjr,fjb,fjz的權(quán)重系數(shù)，可通過(guò)專家咨詢法和層次分析法來(lái)確定，本文建議ρ=1,φ=0.8,γ=0.5。

類簇Cv內(nèi)樣本點(diǎn)j的節(jié)點(diǎn)重要度為：

(10)

式中，ηPIMPvmax為類簇Cv內(nèi)所有樣本點(diǎn)重要度的最大值。類簇內(nèi)各節(jié)點(diǎn)的重要度為接下來(lái)的選址提供了依據(jù)，對(duì)各樣本點(diǎn)的重要度進(jìn)行評(píng)級(jí)，重要度越低的樣本點(diǎn)賦予較大的懲罰系數(shù)，使其在聚類過(guò)程中有較大的距離，不易被選中，懲罰系數(shù)指標(biāo)如表1所示。

表1 距離懲罰系數(shù)指標(biāo)

計(jì)算類簇內(nèi)各樣本點(diǎn)間的距離集合，得到任一樣本點(diǎn)到其他樣本點(diǎn)的距離中位數(shù)并通過(guò)距離懲罰系數(shù)換算成選址距離，比較各樣本點(diǎn)的選址距離，選址距離最短的即為選址點(diǎn)。

2.2 改進(jìn)的DBSCAN算法流程

改進(jìn)的DBSCAN算法流程如圖2所示。

圖2 改進(jìn)的DBSCAN算法流程Fig. 2 Improved DBSCAN algorithm flow

輸入：乘客出行需求調(diào)查樣本點(diǎn)集合D，公交站、地鐵站等交通樞紐分布集合S。

輸出：基于乘客需求數(shù)據(jù)的定制商務(wù)班車站點(diǎn)建議選址坐標(biāo)。

步驟1：初始化未訪問(wèn)樣本點(diǎn)集合Dw=D,類簇序號(hào)k=0，待精細(xì)化簇集合Djx=?，類簇劃分集合Crc=?。

步驟2：根據(jù)類簇序號(hào)k設(shè)置并更新其對(duì)應(yīng)的聚類參數(shù)Eps和minPts，k=0時(shí)，依據(jù)站點(diǎn)布設(shè)經(jīng)驗(yàn)設(shè)置初始參數(shù)Eps=10, minPts=1000。

步驟3：任意選擇Dw中的一個(gè)點(diǎn)xj。若xj為非核心點(diǎn)，則執(zhí)行步驟4；若xj為核心點(diǎn)，則執(zhí)行步驟5。

步驟4：將xj標(biāo)記為噪聲點(diǎn)，并從集合Dw中刪除。

步驟5：令k=k+1，確定D中所有與xj密度可達(dá)的點(diǎn)，并把xj及其密度可達(dá)點(diǎn)劃分到類Ck中，并將Ck中的點(diǎn)從集合Dw中刪除。

步驟6：若Dw=?，則輸出類簇劃分的結(jié)果Crc={C1,C2,…,Ck}, 否則轉(zhuǎn)到步驟3。

步驟7：對(duì)于劃分得到的任意類簇Cq∈Crc，依據(jù)2.1.1節(jié)計(jì)算其精細(xì)化服務(wù)指標(biāo)。

步驟8：若該類簇的精細(xì)化服務(wù)指標(biāo)達(dá)標(biāo)，則將其歸入Cjx，更新簇Crc=Crc-Cjx。

步驟9：若Cjx=?，則轉(zhuǎn)入步驟11,否則對(duì)Cjx內(nèi)任意類簇Cu根據(jù)2.1.2的方法計(jì)算并更新其對(duì)應(yīng)的Eps和minPts，轉(zhuǎn)入步驟2。

步驟11：對(duì)Crc內(nèi)的各類簇Cv，根據(jù)2.1.3的理論計(jì)算并輸出其建議選址位置。

3 案例分析

3.1 出行需求數(shù)據(jù)分析與處理

本文通過(guò)北京市定制商務(wù)班車電子商務(wù)平臺(tái)，采集到了從2016年1月到2016年7月共計(jì)1 701條定制商務(wù)班車乘客出行需求數(shù)據(jù)。鑒于站點(diǎn)選址要在乘客出行點(diǎn)位置分布的基礎(chǔ)上進(jìn)行自適應(yīng)聚類，因此，從基礎(chǔ)數(shù)據(jù)中提取乘客出行需求中的出發(fā)地和到達(dá)地兩項(xiàng)數(shù)據(jù)，通過(guò)篩選整理得到如表2所示的定制商務(wù)班車乘客出行地址統(tǒng)計(jì)表。

表2 定制商務(wù)班車乘客需求點(diǎn)統(tǒng)計(jì)表

由表2可見(jiàn)，采集到的乘客信息主要是地址的描述，在進(jìn)行分析時(shí)需要將其轉(zhuǎn)變?yōu)榈乩碜鴺?biāo)數(shù)據(jù)。因此，需要利用大批量地址經(jīng)緯度解析轉(zhuǎn)換工具XGeocoding進(jìn)行解析，得到每個(gè)出行需求的經(jīng)緯度坐標(biāo)?；诘玫降淖鴺?biāo)，將乘客的出行需求點(diǎn)繪制成分布圖如圖3所示。

圖3中底圖為北京市路網(wǎng)分布圖，從圖中可以直觀地看到乘客出行需求在市區(qū)的分布情況：大部分的乘客需求位于六環(huán)以內(nèi)，且越靠近城區(qū)需求點(diǎn)越密集。由于北京市的路網(wǎng)呈環(huán)形放射狀，一些從市中心延伸出來(lái)的主干路的沿線也有較多的需求分布，這些需求隨著路網(wǎng)的走向在空間呈條形分布，離散程度較大，不利于聚類的進(jìn)行。還有一小部分需求點(diǎn)位于京郊區(qū)縣，這些需求點(diǎn)與主城區(qū)的節(jié)點(diǎn)群間隔很大，進(jìn)行聚類時(shí)也應(yīng)注意排除這些節(jié)點(diǎn)的影響。

3.2 聚類分析與精細(xì)化衡量

在對(duì)需求數(shù)據(jù)的空間特征進(jìn)行簡(jiǎn)單的分析后，結(jié)合站點(diǎn)規(guī)劃理論[23]和定制商務(wù)班車的服務(wù)經(jīng)驗(yàn)[24]，確定定制商務(wù)班車粗略選址的條件為滿足周邊半徑1 000 m區(qū)域大于10人次的出行需求。故設(shè)置初始聚類參數(shù)Eps=1 000，minPts=10，運(yùn)行DBSCAN算法進(jìn)行初始聚類，得到的類簇分布如圖4所示。

圖3 北京市需求點(diǎn)分布Fig. 3 Distribution ofdemand point in Beijing

圖4 帶噪聲點(diǎn)的分類結(jié)果Fig.4 Classification results with noise points

由圖4可見(jiàn)，DBSCAN算法自動(dòng)識(shí)別并排除了噪聲點(diǎn)的影響，將剩下的需求點(diǎn)依據(jù)數(shù)據(jù)特征自動(dòng)劃分為19個(gè)類簇組。通過(guò)對(duì)比圖3和圖4，我們可以看到大部分分布于京郊區(qū)縣且離散程度很大的節(jié)點(diǎn)都被識(shí)別成為噪聲點(diǎn)，剩下來(lái)的節(jié)點(diǎn)大多位于中心城區(qū)且分布較為稠密，這證明DBSCAN算法能有效規(guī)避數(shù)據(jù)離散程度過(guò)大點(diǎn)的影響，并且能夠較合理地進(jìn)行類簇劃分，是需求點(diǎn)聚類的理想選擇。但同時(shí)也可以看出，以圖中類簇C5為代表的一些類簇組位于三四環(huán)核心區(qū)域，乘客需求多且分布廣，以圖中類簇C1為代表的一些類簇組分布狹長(zhǎng)，乘客步行時(shí)間長(zhǎng)。在這兩類地區(qū)，定制商務(wù)班車有必要進(jìn)一步增設(shè)站點(diǎn)，提供精細(xì)化服務(wù)。

為了識(shí)別出需要增設(shè)站點(diǎn)的類簇，依據(jù)2.1.1論述的方法計(jì)算各類簇的精細(xì)化服務(wù)指數(shù)，結(jié)果如表3所示。

表3 各類簇精細(xì)化程度指標(biāo)

根據(jù)定制商務(wù)班車服務(wù)理論[25]，本文取精細(xì)化服務(wù)判別的閾值為0.5。由表3中可看出，需要進(jìn)一步增設(shè)站點(diǎn)的類簇組號(hào)為C1、C3、C5、C8、C9、C15、C16，這與圖4中分布在城市中心圈或者分布狹長(zhǎng)的類簇相吻合。在這些類簇中，由于類簇C3的需求點(diǎn)過(guò)少，為節(jié)約建設(shè)資源，暫不考慮對(duì)其進(jìn)行精細(xì)化聚類。由此得出，最終待精細(xì)化聚類的類簇組號(hào)為C1、C5、C8、C9、C15、C16。

根據(jù)前述理論可知，待精細(xì)化的類簇需要DBSCAN算法根據(jù)其自身數(shù)據(jù)特點(diǎn)更新聚類參數(shù)Eps和minpts,根據(jù)2.1.2節(jié)的思想，計(jì)算各區(qū)間的Eps和minPts，得到的結(jié)果如表4所示。

表4 更新的各類簇聚類參數(shù)值

利用得到的聚類參數(shù)重新控制DBSCAN算法進(jìn)行聚類，并將得到的結(jié)果進(jìn)行精細(xì)化衡量，直到所有類簇不再需要精細(xì)化為止。

3.3 類簇聚類中心確定與對(duì)比

得到的類簇需要結(jié)合節(jié)點(diǎn)重要度和區(qū)位重要度計(jì)算聚類中心，在第一次聚類得到的類簇組C1，經(jīng)二次聚類后得到了6個(gè)組，經(jīng)過(guò)精確化指標(biāo)檢驗(yàn)，不需再進(jìn)行進(jìn)一步聚類，下面選取C1組精細(xì)化聚類得到的最終類簇中的第4組(即為C1-4組)為例計(jì)算聚類中心，組內(nèi)各需求點(diǎn)分布如圖5所示。

圖5 C1-4組聚類節(jié)點(diǎn)分布情況Fig.5 Distribution of cluster nodes in C1-4 Group

根據(jù)各需求點(diǎn)周圍的交通樞紐分布情況，結(jié)合2.1.3的思想計(jì)算類簇內(nèi)各樣本點(diǎn)的節(jié)點(diǎn)重要度，并據(jù)此得出節(jié)點(diǎn)層級(jí)及其對(duì)應(yīng)的懲罰系數(shù)，對(duì)樣本點(diǎn)間的實(shí)際距離結(jié)合懲罰系數(shù)換算，各樣本點(diǎn)的距離中位數(shù)如表5所示。

表5 組內(nèi)各樣本點(diǎn)距離中位數(shù)

由表5可知，樣本點(diǎn)3與其他樣本點(diǎn)間的距離經(jīng)懲罰系數(shù)換算之后最小，因而可以確定樣本點(diǎn)3為類簇C1-4的聚類中心。根據(jù)以上結(jié)果，得出待精確化組的最終的聚類各點(diǎn)坐標(biāo)如表6所示。

表6 改進(jìn)的DBSCAN最終聚類結(jié)果

聚類中心分布如圖6所示，由圖中可看到，考慮節(jié)點(diǎn)重要度的各類簇的聚類中心點(diǎn)都分布在主要交通干路上。

利用K-means算法聚類，將得到的中心與改進(jìn)的DBSCAN算法得到的聚類中心進(jìn)行對(duì)比，結(jié)果如圖7所示。圖7中較大的點(diǎn)代表利用K-means算法得到的聚類中心，較小的點(diǎn)代表利用改進(jìn)的DBSCAN算法得到的聚類中心。由圖中可見(jiàn)，改進(jìn)的DBSCAN算法能夠有效地規(guī)避噪聲點(diǎn)的影響，所選取的聚類中心更趨向于需求點(diǎn)稠密的中心區(qū)域，該算法能夠依據(jù)類簇的數(shù)據(jù)分布和區(qū)位特征調(diào)整聚類中心的個(gè)數(shù)，需求點(diǎn)多且分散的集群分配了較多的備選站點(diǎn)，同時(shí)這些備選站點(diǎn)自身也分布于交通通達(dá)性較高的地點(diǎn)，能夠充分利用周圍的交通資源，便于縮短乘客的換乘時(shí)間和步行距離，有利于公交網(wǎng)絡(luò)的構(gòu)建。

圖6 改進(jìn)的DBSCAN聚類中心分布情況Fig.6 Improved DBSCAN cluster center distribution

圖7 兩種算法所得的聚類中心對(duì)比Fig.7 Comparison of cluster centersfrom two algorithms

4 結(jié)語(yǔ)

本文對(duì)DBSCAN算法的優(yōu)缺點(diǎn)進(jìn)行了研究，分析了聚類參數(shù)質(zhì)量對(duì)聚類結(jié)果的影響，提出了DBSCAN算法動(dòng)態(tài)選擇方法，同時(shí)結(jié)合區(qū)位重要度分析，考慮各類簇至其他類簇的空間距離和類簇間的客流強(qiáng)度，確定相關(guān)類簇是否需要進(jìn)一步精細(xì)化，其布局結(jié)論可以保證類簇和其他分區(qū)之間具有較好的可達(dá)性以及實(shí)現(xiàn)類簇客流來(lái)源的極大化。在聚類中心的確定中，考慮到城市建成區(qū)難以滿足公交樞紐建設(shè)用地要求，所以在有限滿足類簇內(nèi)需求點(diǎn)的出行，根據(jù)區(qū)域節(jié)點(diǎn)重要度確定樞紐布局方案，提高了站點(diǎn)選址的實(shí)用性。本文提出的算法減輕了對(duì)聚類參數(shù)的依賴，同時(shí)改進(jìn)了聚類中心的選擇。在對(duì)基本的DBSCAN算法進(jìn)行改進(jìn)、增加其功能的同時(shí)，可能使得算法計(jì)算聚類中心的時(shí)間較長(zhǎng)，下一步的研究可以對(duì)算法進(jìn)行進(jìn)一步優(yōu)化，爭(zhēng)取在實(shí)現(xiàn)功能的同時(shí)減少算法運(yùn)算時(shí)間，使其能更快地完成站點(diǎn)選址的目標(biāo)。