張 瑾，向一擘 ZHANG Jin, XIANG Yibo

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

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

0 引 言

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

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

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

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

1 公交運營時段劃分方法

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

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

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

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

1.1 運營時段劃分方法

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

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

1.2 劃分方法改進

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

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

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

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

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

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

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

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

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

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

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

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

2 實例驗證

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

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

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

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

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

2.1 劃分特征

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

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

2.2 計算復(fù)雜度

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

表3 不同簇數(shù)目劃分結(jié)果表

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

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

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

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

3 研究結(jié)論

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

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