基于時(shí)間標(biāo)簽的公交運(yùn)營時(shí)段劃分方法

張 瑾，向一擘 ZHANG Jin, XIANG Yibo

（昆明理工大學(xué) 交通工程學(xué)院，云南 昆明650000）

(School of Transportation and Engineering, Kunming University of Science and Technology, Kunming 650000, China)

0 引 言

隨著城市機(jī)動(dòng)化出行的發(fā)展，各大城市機(jī)動(dòng)車保有量不斷增多，同時(shí)人民日益強(qiáng)烈且多樣化的出行需求也使得交通負(fù)荷越發(fā)加重，給城市交通帶來日益嚴(yán)峻的考驗(yàn)。地面常規(guī)公交作為“高效率、低成本、大運(yùn)能”城市公共交通的代表，是政府用于解決交通需求及交通擁堵問題的強(qiáng)力手段。隨著軌道交通的興起，目前認(rèn)為地面常規(guī)公交的交通出行占比已被地鐵和小轎車所瓜分，但國家統(tǒng)計(jì)局信息表明，地面常規(guī)公交仍是城市交通出行的主力，在公共交通占有較大比例（如表1 所示）。因此，對地面常規(guī)公交的研究仍是解決城市交通問題的可靠途經(jīng)。

表1 各城市交通方式出行量占比表

為了改善地面常規(guī)公交服務(wù)水平，必須對公交運(yùn)營情況進(jìn)行全面了解。而公交線路在不同的運(yùn)營時(shí)段，其運(yùn)營時(shí)間和客流規(guī)律往往存在很大差異。所以必須將公交運(yùn)營時(shí)段進(jìn)行劃分來掌握不同情況下的公交運(yùn)營規(guī)律。針對這方面的研究，楊新苗[1]等依據(jù)利用有序樣品聚類的費(fèi)歇算法完成運(yùn)營時(shí)段劃分；沈吟東[2]等采用改進(jìn)的K-means 聚類算法劃分時(shí)段；尚春琳[3]等研究了基于公交優(yōu)先的交叉口多時(shí)段劃分方法；靳文舟[4]等提出基于最小化車隊(duì)運(yùn)營時(shí)段成本的劃分方法；張雪妍[5]等采用Fisher 有序聚類算法完成了劃分時(shí)段仿真。

在當(dāng)前，公交企業(yè)主要仍是通過經(jīng)驗(yàn)人工完成時(shí)段劃分，而隨著車內(nèi)GPS 定位系統(tǒng)的普及，公交企業(yè)在獲取大量數(shù)據(jù)儲(chǔ)備的同時(shí)，如何利用這些大規(guī)模數(shù)據(jù)完成公交運(yùn)營時(shí)段劃分顯得尤為重要。本文基于GPS 數(shù)據(jù)，參考K-means 算法具有解決大規(guī)模數(shù)據(jù)聚類的能力，設(shè)計(jì)相對應(yīng)的算法以期自動(dòng)化、高效率、高精確度的實(shí)現(xiàn)公交運(yùn)營時(shí)段劃分，為分時(shí)段公交運(yùn)營研究打下基礎(chǔ)。

1 公交運(yùn)營時(shí)段劃分方法

當(dāng)前對公交時(shí)段劃分主要以客流量作為依據(jù)，常用的通過乘客數(shù)量對公交調(diào)度劃分忽略了外部客觀環(huán)境對公交派車數(shù)量的限制，常有如下情況：線路乘客出行需求旺盛，但由于當(dāng)前整個(gè)線路斷面客流量較大，增添派車不能及時(shí)到達(dá)目標(biāo)站點(diǎn)，造成串車等現(xiàn)象，既造成了運(yùn)力浪費(fèi)，也增加了交通負(fù)荷。也有學(xué)者使用線路單程時(shí)間作為劃分依據(jù)，但由于每一個(gè)數(shù)據(jù)代表的時(shí)間段較長，不能反映實(shí)時(shí)的公交乘車需求。

本文使用公交于站間運(yùn)行所花時(shí)間作為分類依據(jù)?？梢哉J(rèn)為該指標(biāo)既反映了乘客出行需求，當(dāng)公交站間運(yùn)行時(shí)間短時(shí)，當(dāng)前線路交通狀況良好，也代表當(dāng)前時(shí)段居民出行欲望不強(qiáng)，公交使用者數(shù)量也相應(yīng)減少；而當(dāng)公交站間運(yùn)行時(shí)間較長時(shí)，則與前種情況相反，可以認(rèn)為公交出行需求旺盛。

對于時(shí)間段的不同，公交所處道路交通狀況也有所不同，進(jìn)而導(dǎo)致運(yùn)行時(shí)間產(chǎn)生較大差異。目前，公交運(yùn)營企業(yè)對于車輛運(yùn)行時(shí)刻表的編制往往不注重道路交通狀況的變化，同時(shí)調(diào)度計(jì)劃也不考慮各個(gè)站點(diǎn)的實(shí)時(shí)狀況，往往采用“一刀切”的手法，也因此導(dǎo)致“串車、車輛同時(shí)滯站”等亂象發(fā)生。

考慮到本文以車輛于站點(diǎn)間運(yùn)行的時(shí)間作為時(shí)間段劃分依據(jù)，產(chǎn)生的數(shù)據(jù)量較多，因此擬采用定量的方法，以在地球科學(xué)、信息技術(shù)、交通運(yùn)輸?shù)确矫娅@得廣泛應(yīng)用的K-means 算法為基礎(chǔ)設(shè)計(jì)算法。

1.1 運(yùn)營時(shí)段劃分方法

傳統(tǒng)的K-means 算法的基本思路是：設(shè)有K個(gè)簇，依據(jù)選定的距離測度方法，將一系列單元逐個(gè)賦予或重新賦予最“接近”的簇，并反復(fù)迭代，直至滿足預(yù)設(shè)的終止條件。

首先要求人為制定的簇的個(gè)數(shù)K，隨機(jī)于元素集合P中選取K個(gè)基本元素作為簇的中心。然后遍歷所有元素，計(jì)算元素與各個(gè)簇中心的距離，并將其劃分至最近的簇中心。初次完成后，記錄整個(gè)集合中各元素與簇中心的距離之和，并按照改進(jìn)中心規(guī)則選取新的簇中心，之后重復(fù)上述過程，反復(fù)迭代至滿足停止條件。

1.2 劃分方法改進(jìn)

使用經(jīng)典K-means 算法雖然可以獲得公交運(yùn)行時(shí)段劃分的結(jié)果，但針對公交運(yùn)營特點(diǎn)可以對部分算法內(nèi)容做出改進(jìn)，以減少運(yùn)算時(shí)間。

改進(jìn)規(guī)則1：初始簇中心的選擇。公交運(yùn)營不同時(shí)段是具有明顯的時(shí)間距離的，因此最終所獲得的各個(gè)簇中心必定彼此有一定距離。而K-means 算法隨機(jī)產(chǎn)生各個(gè)初始簇中心，該過程可能使多個(gè)簇中心點(diǎn)集中于一處，迭代過程會(huì)花費(fèi)較多的時(shí)間來獲得最優(yōu)解。因此本文基于GPS 數(shù)據(jù)自帶的時(shí)間標(biāo)記為依據(jù)，提出改進(jìn)的初始簇中心生成方法。公交GPS 數(shù)據(jù)示意如表2 所示：

表2 公交GPS 數(shù)據(jù)示意表

根據(jù)整體元素集時(shí)間范圍［Ta,Tb］，每個(gè)元素p均有其相應(yīng)的時(shí)間標(biāo)記Tp。首先根據(jù)目標(biāo)簇?cái)?shù)K，計(jì)算平均時(shí)間間隔t= Tb-Ta/K。隨機(jī)生成1 號簇中心m1，對m1的時(shí)間標(biāo)簽Tm1向正、反方向檢驗(yàn)，判斷是否有下式成立：

正方向：Tm2=Tm1+t∈［Ta,Tb］

反方向：Tm3=Tm1-t∈［Ta,Tb］

若正方向的檢驗(yàn)成立，則將TC2作為2 號簇中心的時(shí)間標(biāo)簽，否則中斷該方向上判斷；反方向的判斷于此相同。反復(fù)迭代該過程直至完成K個(gè)初始簇中心時(shí)間標(biāo)簽的選取，再從擁有簇中心標(biāo)簽的元素中隨機(jī)選擇簇中心點(diǎn)。

改進(jìn)規(guī)則2：不必要距離計(jì)算。在將元素劃分進(jìn)各個(gè)簇的過程中，需要計(jì)算元素與每個(gè)簇中心的距離并劃分至最近的簇。而在本文研究問題中，每個(gè)公交時(shí)段均具有明顯的時(shí)間范圍，即具有較強(qiáng)的時(shí)間相關(guān)性。

為減少元素歸類這一過程的計(jì)算量，本文將各個(gè)簇中心按其時(shí)間標(biāo)簽進(jìn)行由小至大排序，依次計(jì)算元素時(shí)間標(biāo)記Tp與各個(gè)簇中心時(shí)間標(biāo)記Tm的距離，若出現(xiàn)Tp-Tmi＞Tp-Tmj，K≥j＞i≥1，則停止元素p的計(jì)算并將其劃分至簇Ci。

改進(jìn)規(guī)則3：邊界元素的劃分。各個(gè)簇的邊界元素由于其處于兩個(gè)公交運(yùn)營時(shí)段的過渡位置，包含兩個(gè)時(shí)間段的信息，若簡單通過距離進(jìn)行劃分難以保證其科學(xué)合理性。本文引入決策變量ε，通過以下算法完成邊界元素的劃分。

對于邊界元素p，判斷其與最近兩簇中心的距離，若則表明該元素與最近、次近簇中心的距離差別明顯，可將其歸類至最近的簇。若2p-mi-mj＜ε，則將該元素歸類至待定集合φ，并尋找與該元素最近的元素pc1。若pc1屬于簇Ci且

基于上述改進(jìn)，本文公交時(shí)段劃分方法如下：假設(shè)一個(gè)已知的公交站間運(yùn)營數(shù)據(jù)集合P，則其中每一個(gè)車輛站間運(yùn)營時(shí)間歸一化后的數(shù)據(jù)為基本單元p，p∈P。簇的個(gè)數(shù)K可以根據(jù)公交運(yùn)營計(jì)劃確定，其中每個(gè)簇為如“低峰—早高峰—平峰—晚高峰—低峰”的交通狀況可以擬定K=5。簇中心mi迭代時(shí)通過簇內(nèi)單元位置，即簇內(nèi)所有車輛站間運(yùn)營時(shí)間的平均來確定新的簇中心單元間距離的度量采用歐幾里得距離進(jìn)行度量。采用作為聚類效果的目標(biāo)函數(shù)。

2 實(shí)例驗(yàn)證

以某日昆明市5 路公交車6：00～18：00 運(yùn)行的GPS 數(shù)據(jù)為例進(jìn)行說明，首先，由于車輛在不同的站點(diǎn)間需要的運(yùn)行時(shí)間不同，將車輛運(yùn)行時(shí)間數(shù)據(jù)同數(shù)據(jù)集中最大值相除，進(jìn)行歸一化處理。其次，以1 分鐘作為時(shí)間基本間隔，確定各個(gè)數(shù)據(jù)的時(shí)間標(biāo)簽。取ε=2,N=7 得到示意圖如圖1 所示：

圖1 目標(biāo)簇N=7 時(shí)數(shù)據(jù)示意圖

由圖1 可以看出，所選案例在運(yùn)行12 個(gè)小時(shí)中，呈現(xiàn)“低峰—平峰—高峰—平峰—低峰—次高峰—低峰”的分布，符合常見的公交運(yùn)營分布規(guī)律。而該線路出現(xiàn)上述分布特征，是由于該線路主要服務(wù)對象為老年乘客，主要的出行活動(dòng)為休閑、購物、接送孩子等，出行高峰較常見的通勤高峰有所延后，因此出行高峰出現(xiàn)的時(shí)間標(biāo)簽為［21 4,318 ］，既9：30～11：20，也與現(xiàn)有的研究相符[6]。而在經(jīng)過第一個(gè)早高峰后，乘客出行欲望消減，直至?xí)r間標(biāo)簽［52 2,622 ］，即15：30～16：30 期間，外出的老年人需要回家，也帶來本組案例公交的次高峰。

依據(jù)本文提出的方法成功將公交運(yùn)營時(shí)段進(jìn)行劃分，這是因?yàn)樵谟?jì)算各個(gè)元素距離的過程中，將運(yùn)行時(shí)間歸一化既可以消除線路站點(diǎn)距離不同對結(jié)果的影響，使其統(tǒng)一為表現(xiàn)交通運(yùn)行狀態(tài)的指標(biāo)，且其上下界為［0,1 ］；同時(shí)基本單位為1min 的

時(shí)間標(biāo)簽的引入，有效地增加了時(shí)間在歐式距離計(jì)算結(jié)果中的占比，在各元素進(jìn)行簇的歸類過程中時(shí)間起到更大地影響作用。

2.1 劃分特征

在公交運(yùn)行中，常根據(jù)不同的指標(biāo)將公交服務(wù)過程劃分為“高峰、平峰、低峰”三類，為驗(yàn)證如何行之有效地完成公交運(yùn)營時(shí)段內(nèi)的劃分，通過對不同目標(biāo)簇?cái)?shù)目的設(shè)置，得到表3 的結(jié)果。

首先，隨著目標(biāo)簇?cái)?shù)目的增加，公交運(yùn)行時(shí)刻將劃分的更為細(xì)致，研究人員可以根據(jù)期望的劃分結(jié)果對簇?cái)?shù)目進(jìn)行設(shè)置。其次，無論目標(biāo)簇?cái)?shù)目為多少，設(shè)P= Ta-Tb/2N，簇中心時(shí)間標(biāo)簽間隔均大致為［P,2P,…,2P,P］，邊界點(diǎn)時(shí)間標(biāo)簽間隔大致為呈現(xiàn)明顯的規(guī)律性分布。這是因?yàn)楦鱾€(gè)元素在時(shí)間上分布較均勻所導(dǎo)致的。而若改變時(shí)間標(biāo)簽基本單元為Xmin，將對時(shí)間標(biāo)簽分布規(guī)律沒有影響。這是由于若使用歐式距離與作為目標(biāo)函數(shù)，雖然在計(jì)算過程中橫坐標(biāo)差值大小發(fā)生變化，但元素與各簇中心的相對距離仍然不變，元素劃分至簇的結(jié)果不造成影響，只要保證數(shù)據(jù)分布形式不變將不會(huì)改變該時(shí)間標(biāo)簽分布規(guī)律。

2.2 計(jì)算復(fù)雜度

經(jīng)典的K-means 算法中，若從大小為m的元素集合中選取K個(gè)簇中心，每個(gè)元素為n維，共迭代I次，則完成一次計(jì)算的時(shí)間復(fù)雜度為

表3 不同簇?cái)?shù)目劃分結(jié)果表

在簇中心隨機(jī)生成且目標(biāo)簇?cái)?shù)為K的條件下，多次進(jìn)行計(jì)算時(shí)初始簇中心將出現(xiàn)K! 種分布情況。若簇中心集中多次出現(xiàn)，則簇中心迭代過程將需要額外進(jìn)行多次計(jì)算復(fù)雜度為）的運(yùn)算。在大規(guī)模樣本數(shù)據(jù)下，若使用本文簇中心等間距平均生成的改進(jìn)規(guī)則1，將節(jié)省上述的計(jì)算時(shí)間。

每次計(jì)算各元素與簇中心距離需要m·n·K次運(yùn)算，根據(jù)本文基于時(shí)間標(biāo)簽的改進(jìn)運(yùn)算規(guī)則2，每個(gè)元素有1/K的概率位于與簇中心Ci最近，其中i的數(shù)學(xué)期望為K/2，則該運(yùn)算過程數(shù)學(xué)期望為：

對于波動(dòng)性較強(qiáng)的公交運(yùn)行而言，難免會(huì)出現(xiàn)極端值的出現(xiàn)。不同于常規(guī)的剔除操作，改進(jìn)運(yùn)算規(guī)則3 雖然每個(gè)元素會(huì)帶來O（m·n·）

n的運(yùn)算復(fù)雜度，但仍在多項(xiàng)式時(shí)間內(nèi)可完成計(jì)算。與此同時(shí)，通過隸屬概率保留該類數(shù)據(jù)，結(jié)合對邊界數(shù)據(jù)的處理將使時(shí)段劃分結(jié)果更具有可靠性。

3 研究結(jié)論

本文針對公交時(shí)段劃分問題，提出了基于K-means 聚類的劃分方法。針對GPS 數(shù)據(jù)規(guī)模大，傳統(tǒng)K-means 計(jì)算過程需較長時(shí)間的問題，從初始簇中心生成、元素歸類計(jì)算及邊界元素的歸屬上提出基于GPS 時(shí)間標(biāo)簽的運(yùn)算優(yōu)化規(guī)則。

以昆明市5 路公交車輛運(yùn)行GPS 數(shù)據(jù)為例驗(yàn)證了方法的可行性，同時(shí)討論了使用該方法進(jìn)行公交運(yùn)行時(shí)段劃分時(shí)簇中心與邊界元素時(shí)間標(biāo)簽的分布特征，并給出了算法上的解釋。最后，討論了提出改進(jìn)規(guī)則前后在計(jì)算復(fù)雜度上的變化，為公交運(yùn)營時(shí)段劃分工作快速準(zhǔn)確地完成提供了新的思路。