薛浩楠，王 佳

(1. 長沙理工大學 交通運輸工程學院，湖南 長沙 410114；2. 新疆交通規(guī)劃勘察設計研究院，新疆 烏魯木齊 830000)

0 引言

為了迎合乘客差異化、高品質的出行需求，客運市場出現(xiàn)了諸如定制公交、預約出租車、定制商務巴士等新型城市客運模式。定制公交是這種新型模式的典型代表，它根據(jù)乘客的個性化出行需求，為目的地和時間相同或相近的人群提供量身定制的出行服務，是介于常規(guī)公交與出租車之間的準公共產(chǎn)品[1]。

目前定制公交的研究是熱點問題，胡列格、安桐等針對定制公交合乘站點的合理布局問題設計了基于密度的孤立點檢測算法[2]。馬繼輝、王飛等提出利用k-means聚類算法規(guī)劃定制公交站點，并建立了定制公交線路規(guī)劃模型[3]。阮冠軒、靳文舟等研究了如何確認需求響應式公交乘客出行的中心點，并構建了接駁公交的調度模型用于檢驗站點和孤立點的確認方法[4]。何民、李沐軒等考慮定制公交的可靠性和舒適性，提出了一種基于乘客出行需求的定制公交線路設計模型[5]。Rahul Nair等基于乘客的出行需求數(shù)據(jù)構建了平衡網(wǎng)絡設計模型，該模型能夠實現(xiàn)站點位置、車輛及站點容量的最佳配置，從而使得效益最大化[6]。Li Z和Song R構建了基于乘客的出行時間窗的定制公交線路優(yōu)化模型，并以小規(guī)模網(wǎng)絡為例進行分析，結果表明該模型對定制公交的運營有一定的指導意義[7]。

綜上，現(xiàn)在的研究側重于定制公交的站點布局和線路規(guī)劃，對需求響應機制的研究相對匱乏，而合理的需求響應機制是整個定制公交系統(tǒng)成功運營的重要保證。從各城市的具體實施情況來看，對于乘客需求的響應往往是依靠經(jīng)驗確定，存在著主觀性，缺少相關的定量研究[8-10]。

現(xiàn)有關于需求響應機制的研究是對乘客出行需求數(shù)據(jù)進行線下的調查分析，缺乏乘客與運營者的信息交互[11-12]。隨著互聯(lián)網(wǎng)技術的高速發(fā)展，定制公交服務可以根據(jù)乘客在平臺上發(fā)布信息獲得乘車需求[13-14]。其他一些相關研究是利用k-means等基于劃分的聚類算法從乘客出行的空間維度進行分析，未考慮乘客出行的時間維度，也沒有考慮基于劃分的聚類算法易受孤立點的影響，需要提前確定類簇個數(shù)，較難處理非球形簇數(shù)據(jù)等缺陷[15-16]。

目前為止，定制公交需求響應機制主要分為響應全部需求和有選擇地響應部分需求兩種類型。若響應全部需求，由于采集的預約需求點在時空上分散，往往造成運輸?shù)牟唤?jīng)濟；而在響應部分需求的機制中，主要是根據(jù)經(jīng)驗來判斷是否響應某個需求，會出現(xiàn)因滿足部分孤立的特殊的出行需求而引發(fā)上座率低的問題，降低了定制公交的吸引力[17-18]。較為理想的響應機制是充分考慮乘客的實際出行需求，為大眾化的定制需求提供服務，適當剔除孤立的出行需求。因此，有必要研究一種定量的基于時空聚類的定制公交需求響應機制，通過分析乘客出行數(shù)據(jù)的時空特性，選用合適的聚類算法得到時空趨同的定制需求。

1 響應機制的構建思路

運輸企業(yè)利用互聯(lián)網(wǎng)平臺發(fā)布和采集定制公交需求，將采集到的信息稱為預約需求點。若預約需求點在時空上集中，運輸企業(yè)會為之提供量身定制的出行服務，這稱之為需求響應。確定是否為預約需求點提供出行服務的響應機制至關重要。

該機制一般遵循以下原則：充分權衡運輸企業(yè)與乘客之間的利益，盡量響應出行時間、地點集中，乘客人數(shù)較多的“大眾化需求”，適當剔除出行時間、地點分散，乘客人數(shù)較少的“特殊需求”。

根據(jù)上述原則，針對預約需求點的時空分布特性，對預約需求點進行分步響應，采取“先時間維度，后空間維度”兩步來實現(xiàn)，每個步驟均通過預響應、再響應來剔除時空分散的預約需求點，如圖1所示。時間指預約需求點的出行時間，包括出發(fā)時間段和到達時間段；空間指預約需求點的空間位置，包括出發(fā)地位置和到達地位置。具體步驟如下：

(1)預約需求點的采集

預約需求點通過網(wǎng)絡平臺獲取，采集的預約需求點主要包含時間、空間和人數(shù)等基本屬性，它們作為判斷是否響應的依據(jù)。

(2)預約需求點時間維度的響應

預約需求點時間維度的響應包括預響應和再響應，其中時間維度的預響應是將出發(fā)時間段接近的預約需求點保留。常用的層次聚類算法通常用于空間聚類[19]，本研究提出基于時間度量的層次聚類算法，用時間來度量兩個類簇之間的距離，將距離較小的兩個類簇進行合并。時間維度的再響應是將出發(fā)時間段和到達時間段同時存在交集且人數(shù)較多的預約需求點保留，經(jīng)時間維度的響應后得到空間維度響應的備選集合。

(3)預約需求點空間維度的響應

預約需求點空間維度的響應包括預響應和再響應，其中空間維度的預響應是將到達地位置接近的預約需求點保留，空間維度的再響應是將出發(fā)地位置接近的預約需求點保留，剔除出發(fā)地位置相距較遠的預約需求點。由于乘客出行需求數(shù)據(jù)的空間分布較為冗雜，常用的k-means等基于劃分的聚類算法較難處理非球形簇的數(shù)據(jù)，而DBSCAN(density-based spatial clustering of application with noise)算法能夠較好地識別孤立點，不需要提前確定類簇個數(shù)，能夠處理任意形狀類簇的數(shù)據(jù)，規(guī)避了k-means等傳統(tǒng)聚類算法的缺陷[20]。因此本研究采用DBSCAN聚類算法實現(xiàn)空間維度的再響應。

圖1 響應機制的構建流程Fig.1 Flowchart of constructing response mechanism

2 預約需求點的采集與時間維度的響應

2.1 預約需求點的采集

運輸企業(yè)利用互聯(lián)網(wǎng)平臺采集到的預約需求點主要包含5個基本屬性：出發(fā)地位置、出發(fā)時間段、到達地位置、到達時間段和乘客人數(shù)，如表1所示。

表1 預約需求點的基本屬性Tab.1 Basic attributes of reserved demand

表1中，ph為第h個預約需求點；(xph,yph)為第h個預約需求點的出發(fā)地位置；(eph,lph)為第h個預約需求點的出發(fā)時間段；(x′ph,y′ph)為第h個預約需求點的到達地位置；(e′ph,l′ph)為第h個預約需求點的到達時間段；dph為第h個預約需求點的乘客人數(shù)。

2.2 時間維度的預響應

時間維度預響應的主要思路是首先求解預約需求點的出發(fā)時間段中值，并按中值進行升序排列，形成新的出發(fā)時間序列，然后采用基于時間度量的層次聚類算法形成若干個時間跨度，最后統(tǒng)計每個時間跨度內的預約需求點人數(shù)，剔除人數(shù)較少的孤立點。具體如下：

(1)

式中，eph為升序排列后第h個預約需求點的最早出發(fā)時間；lph為升序排列后第h個預約需求點的最晚出發(fā)時間。

(2)針對預約需求點的出發(fā)時間段屬性，本研究對傳統(tǒng)層次聚類算法進行改進，提出基于時間度量的層次聚類算法，將距離較小的兩個類簇進行合并，直到滿足設定的終止條件時算法結束，具體步驟如下：

步驟1：對升序排列后的出發(fā)時間段中值進行搜索，篩選得到中值相同的預約需求點。

步驟2：采用基于時間度量的層次聚類算法進行分析，當各個時間跨度的方差之和最小，見式(2)，并且每個類簇的時間跨度不超過τ時，可歸為一個類簇，第h個時間跨度不超過τ見式(3)。

(2)

(3)

步驟3：統(tǒng)計各個時間跨度內的預約需求點人數(shù)，當時間跨度內的人數(shù)不小于φ時，對該時間跨度內的預約需求點進行響應，見式(4)。

∑dTh≥φ,

(4)

式中，∑dTh為第h個時間跨度內的乘客人數(shù)；φ為保留預約需求點的最少乘客人數(shù)。

通過對預約需求點時間維度的預響應，得到若干個出發(fā)時間段接近的預約需求點，作為時間維度再響應的備選集合。

2.3 時間維度的再響應

時間維度再響應的主要思路是從預約需求點的出發(fā)時間段和到達時間段屬性入手，若預約需求點的出發(fā)和到達時間段同時存在交集，即當同時滿足式(5)和式(6)時，將其歸為同一個可能響應的類A，當ph∈A時計算類A中的人數(shù)，如果滿足式(7)則將其保留。

[eph,lph]∩[ep′h,lp′h]≠?，

(5)

[e′ph,l′ph]∩[e′ph′,l′ph′]≠?,

(6)

∑Adph≥φ,

(7)

式中，[eph,lph]、[eph′,lph′]為任意兩個預約需求點的出發(fā)時間段；[e′ph,l′ph]、[e′ph′,l′ph′]為任意兩個預約需求點的到達時間段；∑Adph為同一個可能響應的類A中的乘客人數(shù)；φ為保留預約需求點的最少乘客人數(shù)。

通過對預約需求點時間維度的再響應，得到若干個出行時間集中的預約需求點，作為空間維度響應的備選集合。

3 空間維度的響應

3.1 空間維度的預響應

空間維度預響應的主要思路是從預約需求點的到達地位置屬性入手，若兩個預約需求點到達地位置之間的距離滿足設定的條件值，即當式(8)成立時將其保留。

sph,h′≤ω,

(8)

式中，sph,h′為任意兩個預約需求點到達地位置之間的距離；ω為滿足到達地位置接近的條件值。

通過對預約需求點空間維度的預響應，得到若干個出行時間集中、到達地位置趨同的預約需求點，作為空間維度再響應的備選集合。

3.2 空間維度的再響應

通過時間維度的響應和空間維度的預響應實現(xiàn)了出行時間接近、目的地趨同，但不能保證出發(fā)地位置的接近。本研究采用DBSCAN聚類算法進行空間維度的再響應，主要思路是從預約需求點的出發(fā)地位置屬性入手，篩選得到出發(fā)地位置相對集中的預約需求點，同時剔除出發(fā)地位置相對分散且人數(shù)少的預約需求點，通過空間維度的再響應得到若干個時空趨同的預約需求點，如圖2所示。

圖2 空間維度的再響應示意圖Fig.2 Schematic diagrams of re-response in spatial dimension

DBSCAN聚類算法的主要思想是從任意一個未被訪問的預約需求點開始，計算每個預約需求點的ε鄰域，通過密度可達的概念將預約需求點聚類同時標記孤立點，直到所有預約需求點都被訪問時算法終止。其中算法的兩個輸入?yún)?shù)，ε鄰域具體指乘客從居住地或工作地步行至上車地點的距離;mindph具體指定制公交上車地點覆蓋范圍內包含的最少乘客數(shù)量。

(1)基本定義

結合DBSCAN聚類算法的基本思想和定制公交的特征，給出以下5個基本定義：

定義1：預約需求點ph的ε鄰域。預約需求點?ph∈p的ε鄰域ε(ph)定義為以ph為圓心，ε鄰域形成的空間范圍內包含的預約需求點的集合，即ε(ph)={qh∈p|s(ph,qh)≤ε}，其中s(ph,qh)表示p中預約需求點ph和qh之間的距離。

定義2：核心預約需求點。給定參數(shù)鄰域ε和聚類最少包含的乘客數(shù)量mindph，對于預約需求點ph，若ph的ε鄰域形成的空間范圍內包含的預約需求點的乘客人數(shù)滿足∑εdph≥mindph，則稱ph為核心預約需求點。

定義3：預約需求點的密度直達。給定參數(shù)ε和mindph，對于預約需求點ph,qh∈p，如果滿足ph∈ε(qh)且∑εdph≥mindph，則稱ph與qh密度直達。

定義4：預約需求點的密度可達。給定參數(shù)ε和mindph，對于預約需求點ph,qh∈p，如果存在預約需求點序列p1,p2,…,pn,q1,q2,…,qn∈p，其中ph=p1，qh=ph，若ph與ph-1密度直達，則稱ph與qh密度可達。

圖3 DBSCAN聚類算法流程Fig.3 Flowchart of DBSCAN clustering algorithm

定義5：預約需求點的密度相連。給定參數(shù)ε和mindph，對于預約需求點ph,qh∈p，若存在一個預約需求點oh與ph，qh，都是密度可達，則稱ph與qh密度相連。

(2)算法步驟

預約需求點空間維度再響應的方法采用DBSCAN聚類算法，具體步驟如下：

輸入：預約需求點集合p，鄰域ε，能夠聚為一類的乘客人數(shù)下限值mindph。

輸出：基于密度的類集合。

步驟1：初始化未被訪問的預約需求點集合Pw=p，類序號k=0，類集合Pcl=?。

步驟2：根據(jù)類序號設置并更新其對應的聚類參數(shù)鄰域ε和能夠聚為一類的乘客人數(shù)下限值mindph。

步驟3：任意選擇Pw中的一個預約需求點ph，若ph不是核心預約需求點，則執(zhí)行步驟4；若ph是核心預約需求點，則執(zhí)行步驟5。

步驟4：將ph標記為孤立點，并從集合Pw中刪除。

步驟5：令k=k+1，確定p中所有與ph密度可達的預約需求點，并把ph及其密度可達的預約需求點劃分到類Pcl中，并將Pcl中的預約需求點從集合Pw中刪除。

步驟6：若Pw=?，則輸出類的集合Pcl={P1,P2,…,Pk}，否則轉到步驟3。

步驟7：若該類內預約需求點的人數(shù)∑εdph

4 算例分析

4.1 數(shù)據(jù)準備

模擬采集了54個預約需求點，共包含乘客143人，設研究時段為7:00—9:00，隨機分布在方形區(qū)域內。各聚類參數(shù)值先根據(jù)經(jīng)驗設定，τ為6 min，φ為4人，ω為700 m，ε為200 m，mindph為8人，再依據(jù)聚類結果進行調整，模擬的預約需求點信息如表2所示。

表2 預約需求點信息Tab.2 Information of reserved demand stations

4.2 根據(jù)參數(shù)經(jīng)驗值的需求響應

對于模擬的54個預約需求點，首先按照設定的參數(shù)經(jīng)驗值進行響應，如下：

(1)時間維度的預響應。根據(jù)式(1)，求解54個預約需求點的出發(fā)時間段中值，并進行升序排序，篩選得到出發(fā)時間段中值相同的20個預約需求點；對剩余34個預約需求點采用基于時間度量的層次聚類算法，剔除不滿足式(2)和式(3)的p2和p33；統(tǒng)計各個時間跨度內的人數(shù)，剔除不滿足式(4)的p1和p9。通過時間維度的預響應共剔除4個出發(fā)時間段相對孤立的預約需求點，得到50個出發(fā)時間段相同或相近的預約需求點。

(2)時間維度的再響應。根據(jù)式(5)和式(6)，判斷各個預約需求點的出發(fā)和到達時間段是否同時存在交集，若存在則將其歸為同一類，剔除不存在交集的p17，p27和p47；根據(jù)式(7)計算同一類內的乘客人數(shù)，剔除不滿足式(7)的p36和p42。通過時間維度的再響應共剔除5個出行時間相差較大預約需求點，得到45個出行時間接近預約需求點。

(3)空間維度的預響應。根據(jù)式(8)，計算45個預約需求點到達地位置之間的距離，剔除不滿足式(8)的p10，p14，p22和p49。通過空間維度的預響應共剔除4個到達地位置相對分散的預約需求點，得到41個到達地位置接近的預約需求點。

(4)空間維度的再響應。采用DBSCAN聚類算法判斷41個預約需求點是否為核心預約需求點，若是則將其保留，其中p7，p11，p13和p51不是核心預約需求點，將其剔除。通過空間維度的再響應共剔除4個出發(fā)地位置相對分散的預約需求點，得到37個時空趨同的預約需求點。

根據(jù)設定的聚類參數(shù)經(jīng)驗值共響應37個預約需求點，包含107人，滿足了69%預約需求點和75%乘客的出行請求，剔除的預約需求較多，未能較好地實現(xiàn)盡量響應大眾化需求、適當剔除特殊需求的響應原則。根據(jù)聚類參數(shù)經(jīng)驗值的響應結果如表3所示。

表3 根據(jù)聚類參數(shù)經(jīng)驗值的響應結果Tab.3 Response result based on empirical clustering parameters

4.3 響應結果的優(yōu)化

通過調整各聚類參數(shù)對響應結果進行優(yōu)化，設定保留時間跨度的最短時間τ從2 min增加至9 min，保留預約需求點的最少乘客人數(shù)φ從1人增加至8人，滿足到達地位置接近的條件值ω從400 m增大至1 100 m，DBSCAN聚類算法的輸入?yún)?shù)鄰域ε從50 m增大到500 m，能夠聚為一類的乘客人數(shù)下限值mindph從2人增加至11人。分別計算在其他聚類參數(shù)按照經(jīng)驗值設定的前提下，各個參數(shù)變化后的響應結果，如表4～表8所示。

表4 τ變化時的響應結果 Tab.4 Response result varying with τ

表5 φ變化時的響應結果Tab.5 Response result varying with φ

表6 ω變化時的響應結果Tab.6 Response result varying with ω

表7 ε變化時的響應結果Tab.7 Response result varying with ε

表8 mindph變化時的響應結果Tab.8 Response result varying with mindph

由表4可知：在其他聚類參數(shù)按經(jīng)驗值設定的前提下，τ從2 min增加至9 min時，得到響應的預約需求點個數(shù)和乘客人數(shù)逐漸減少。當τ小于3 min時，不再剔除預約需求點，此時，τ的減小將不會再對響應結果造成影響，預約需求點和乘客的最大響應比例分別為76%和80%。隨著τ的增大，研究時段內的類個數(shù)減少，但每個類中的乘客人數(shù)增加，運輸企業(yè)可考慮在降低發(fā)車頻率的同時選用較大的車型。

由表5可知：在其他聚類參數(shù)按經(jīng)驗值設定的前提下，φ從1人增加至8人時，得到響應的預約需求點個數(shù)和乘客人數(shù)逐漸減少。當φ小于2人時，不再剔除預約需求點，此時，φ的減小將不會再對響應結果造成影響，預約需求點和乘客的最大響應比例分別為78%和80%。隨著φ的增大存在部分人數(shù)較多卻因出行時間段較為孤立而被剔除的出行需求，運輸企業(yè)可針對這些需求單獨規(guī)劃線路，從而響應更多的預約需求點。

由表6可知：在其他聚類參數(shù)按經(jīng)驗值設定的前提下，ω從400 m增大至1 100 m時，得到響應的預約需求點個數(shù)和乘客人數(shù)逐漸增加。當ω大于1 000 m 時，不再剔除預約需求點，此時，ω的增大將不會再對響應結果造成影響，預約需求點和乘客的最大響應比例分別為76%和82%。隨著ω的減小，預約需求點的響應比例降低，部分出行需求因空間位置較為孤立而被剔除，使得這部分乘客前往站點乘車的步行時間會相應增加。

由表7可知：在其他聚類參數(shù)按經(jīng)驗值設定的前提下，ε從50 m增大到500 m時，得到響應的預約需求點個數(shù)和乘客人數(shù)逐漸增加。當ε大于400 m時不再剔除預約需求點，此時，ε的增大將不會再對響應結果造成影響，預約需求點和乘客的最大響應比例分別為76%和83%。隨著ε的減小，預約需求點被劃分的類個數(shù)增加、空間范圍縮小，使得乘客在站點的等車時間增加。

由表8可知：在其他聚類參數(shù)按經(jīng)驗值設定的前提下，mindph從2人增加至11人時，得到響應的預約需求點個數(shù)和乘客人數(shù)逐漸減少。當mindph小于4人時不再剔除預約需求點，此時，mindph的減小將不會再對響應結果造成影響，預約需求點和乘客的最大響應比例分別為76%和83%。隨著mindph的增大，預約需求點被劃分的類個數(shù)減少、類中的乘客人數(shù)增加，運輸企業(yè)可考慮選用較大的服務車輛。

綜合表4～表8可知：預約需求點的最大響應比例為78%，乘客的最大響應比例為83%。為滿足響應機制的構建原則，設定預約需求點和乘客的響應比例不小于75%和80%，得到其他聚類參數(shù)按照經(jīng)驗值設定的前提下各參數(shù)的設置條件，如表9所示。

表9 參數(shù)設置條件Tab.9 Parameter setting conditions

由表9可知：在其他聚類參數(shù)按經(jīng)驗值設定的前提下，τ不大于3 min，φ不大于2人，ω不小于1 000 m，ε不小于400 m以及mindph不大于4人時，預約需求點和乘客的響應比例不小于75%和80%，滿足盡量響應大眾化定制需求、適當剔除特殊需求的響應原則。

5 結論

(1)定制公交的預約需求在時空范圍上分散，若對其全部響應，往往會造成運輸?shù)牟唤?jīng)濟，若對其響應過少，則會降低定制公交的吸引力，因此本文通過對預約需求進行時空范圍的聚類來實現(xiàn)定制公交需求響應機制。

(2)按照盡量響應“大眾化需求”和適當剔除“特殊需求”的原則，采取“先時間維度，后空間維度”的方式，分別采用基于時間度量的層次聚類算法和DBSCAN聚類算法篩選預約需求點，算例分析結果表明該機制能夠通過參數(shù)的適當調整滿足響應機制的構建原則，對定制公交預約需求的響應具有良好的適用性，可為運輸企業(yè)開通定制公交線路提供決策依據(jù)，對推動定制公交的實際應用有一定的現(xiàn)實意義。

(3)在對定制公交需求響應機制的研究是在理想路網(wǎng)條件下進行的，未考慮實際道路條件能否滿足定制公交的需求響應，該因素將在未來的研究中進一步討論。在算例分析中給出的聚類參數(shù)經(jīng)驗值存在一定的主觀性，在后續(xù)的研究中可以針對參數(shù)設置進行進一步優(yōu)化，從而得到最優(yōu)的結果。