基于時(shí)段客流特征聚類的地鐵運(yùn)營(yíng)時(shí)段劃分①

陳東洋,陳德旺,江世雄,徐 寧

1(福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,福州 350108)

2(福州大學(xué) 智慧地鐵福建省高校重點(diǎn)實(shí)驗(yàn)室,福州 350108)

城市軌道交通的列車開(kāi)行方案是運(yùn)營(yíng)公司日常組織運(yùn)營(yíng)調(diào)度的前提與基礎(chǔ)[1],而合適的運(yùn)營(yíng)時(shí)段劃分方案也是列車開(kāi)行方案調(diào)整的基礎(chǔ).對(duì)于運(yùn)營(yíng)公司而言,分時(shí)段等間隔的發(fā)車方式同時(shí)具有靈活、易操作等特點(diǎn),因此是運(yùn)營(yíng)公司廣泛采用的一種發(fā)車模式[2].該模式通常根據(jù)客流規(guī)律將一天劃分為高峰時(shí)期、正常時(shí)期、低谷時(shí)期等若干個(gè)運(yùn)營(yíng)時(shí)段,并在各運(yùn)營(yíng)時(shí)段內(nèi)采用合適的發(fā)車間隔.但在實(shí)際的工作中,地鐵運(yùn)營(yíng)時(shí)段的劃分通常是技術(shù)人員根據(jù)經(jīng)驗(yàn)等因素,主觀地進(jìn)行劃分,難以符合實(shí)際的客流需求.因此國(guó)內(nèi)外有許多學(xué)者針對(duì)此問(wèn)題進(jìn)行了研究.

對(duì)于時(shí)段劃分問(wèn)題的研究主要是針對(duì)公交、路口等問(wèn)題,對(duì)于地鐵的研究較少.在公交運(yùn)營(yíng)時(shí)段劃分方面,Bulut 等[3]通過(guò)站間流量得到公交車使用率,并以此為特征變量采用聚類算法劃分運(yùn)營(yíng)時(shí)段;文獻(xiàn)[4-8]從車輛行程時(shí)間角度出發(fā),以車輛單程時(shí)間、站間運(yùn)行停留時(shí)間等作為特征變量,并采用有序樣本聚類、K-means 等聚類算法劃分運(yùn)營(yíng)時(shí)段;靳文舟等[9]以車隊(duì)運(yùn)營(yíng)時(shí)間最小為優(yōu)化目標(biāo)構(gòu)建模型,并借助遺傳算法對(duì)模型進(jìn)行求解,以尋找最優(yōu)的運(yùn)營(yíng)時(shí)段劃分方案.在交通路口時(shí)段劃分方面,文獻(xiàn)[10-13]以道路路口不同方向的流量等作為時(shí)段內(nèi)道路的特征向量,并采用聚類等算法劃分交通時(shí)段;杜長(zhǎng)海等[14]建立了一種結(jié)合混合蛙跳算法優(yōu)點(diǎn)與模糊C 均值算法優(yōu)點(diǎn)的模型以解決交通運(yùn)營(yíng)時(shí)段的劃分問(wèn)題;楊立才等[15]借鑒生物免疫網(wǎng)絡(luò)理論,建立了以人工免疫算法為基礎(chǔ)的數(shù)據(jù)聚類分析算法模型,以解決城市交通運(yùn)營(yíng)時(shí)段的自動(dòng)劃分問(wèn)題.在地鐵時(shí)段劃分方面,王文憲等[16]建立采用近鄰傳播聚類算法的地鐵運(yùn)營(yíng)時(shí)段劃分模型,模型中以目標(biāo)線路各車站單位時(shí)間內(nèi)的進(jìn)站客流為描述變量;曾小旭等[17]根據(jù)實(shí)際客流數(shù)據(jù)建立了地鐵單向OD 概率矩陣的時(shí)序模型,并以此為基礎(chǔ)采用最優(yōu)分割法求解模型,給出時(shí)段劃分方案.

以上研究為地鐵運(yùn)營(yíng)時(shí)段劃分提供了參考.但是可以發(fā)現(xiàn),上述研究主要是將研究對(duì)象一定時(shí)間內(nèi)各組成部分的客流量或行程時(shí)間作為特征變量來(lái)描述該時(shí)段的特點(diǎn),如站點(diǎn)間的客流量、行程時(shí)間等.但是該方法容易受到一些特殊站點(diǎn)等因素的影響,且其直接采用客流量等作為描述變量,因此難以體現(xiàn)線路總體客流的變化特性.而且在求解劃分方案時(shí)忽略了不同時(shí)段之間的相似性,降低了時(shí)段劃分方案的靈活性.基于以上分析,本文以地鐵線路總體客流的變化特點(diǎn)為基礎(chǔ),首先構(gòu)建運(yùn)營(yíng)日的時(shí)段客流樣本數(shù)據(jù)集.再根據(jù)各時(shí)段客流片段的客流變化特點(diǎn),構(gòu)建每個(gè)時(shí)段客流片段的特征向量,并以此為基礎(chǔ)采用K-means 算法進(jìn)行聚類,最后借助聚類評(píng)價(jià)指標(biāo)確定最佳聚類數(shù).本研究能根據(jù)實(shí)際客流需求,實(shí)現(xiàn)地鐵運(yùn)營(yíng)時(shí)段的準(zhǔn)確、高效劃分,為地鐵列車時(shí)刻表的優(yōu)化設(shè)計(jì)提供了良好的基礎(chǔ).

1 時(shí)段客流特征向量構(gòu)建

城市軌道交通自動(dòng)售檢票系統(tǒng)(AFC)中存儲(chǔ)著大量的乘客出行交易信息,其中包括乘客的進(jìn)出站點(diǎn)編號(hào)、進(jìn)出站日期時(shí)間、交易卡號(hào)等.對(duì)這些信息進(jìn)行挖掘和分析,可以進(jìn)一步提取出地鐵線路的客流變化特征等信息.本文以福州地鐵一號(hào)線2019年5月13日-5月17日以及5月20日-5月24日共10 個(gè)工作日的AFC 客流數(shù)據(jù)為基礎(chǔ),研究福州地鐵一號(hào)線工作日的各運(yùn)營(yíng)時(shí)段的劃分方案.

1.1 單日客流序列構(gòu)建

將目標(biāo)線路在運(yùn)營(yíng)日k中統(tǒng)計(jì)間隔i內(nèi)到達(dá)目標(biāo)線路站點(diǎn)候車的乘客人數(shù)記作則運(yùn)營(yíng)日k的客流序列可記作且滿足其中Qk為目標(biāo)線路在運(yùn)營(yíng)日k的客流總量,n為運(yùn)營(yíng)日k的統(tǒng)計(jì)間隔個(gè)數(shù).本文中統(tǒng)計(jì)間隔選取1 min為單位,同時(shí)考慮福州地鐵的實(shí)際運(yùn)營(yíng)情況,本文的運(yùn)營(yíng)日統(tǒng)計(jì)時(shí)段為06:00-23:59.因此本文中n的取值為1080.

為后續(xù)運(yùn)營(yíng)時(shí)段劃分方便,同時(shí)考慮到目標(biāo)線路多個(gè)工作日的客流序列的相似性,因此采用均值處理方式,構(gòu)建工作日單日客流序列S={s1,s2,···,si,···,sn},其中:

式(1)中,K為運(yùn)營(yíng)日的天數(shù).

1.2 時(shí)段客流樣本構(gòu)建

運(yùn)營(yíng)日的客流序列反映了目標(biāo)線路一天中乘客乘坐地鐵的客流變化規(guī)律.選取合適的時(shí)間間隔d,將運(yùn)營(yíng)日的客流序列劃分為若干個(gè)長(zhǎng)度相同的序列片段,則運(yùn)營(yíng)日的所有序列片段即構(gòu)成了運(yùn)營(yíng)日的時(shí)段客流樣本集D={D1,D2,···,Dm},其中m為樣本集大小,且m=n/d.則有:

本文選取10 min為時(shí)間間隔單位,即d=10 min.因此樣本集的大小m=108.

1.3 時(shí)段客流特征向量

樣本集D的每一個(gè)樣本都是工作日單日客流序列的某一個(gè)時(shí)段的客流變化序列,每一個(gè)樣本的客流序列都有其變化特點(diǎn).不同的時(shí)段客流樣本可能具有相似的變化特點(diǎn),也可能具有不同的變化特點(diǎn).但是從客流數(shù)值上難以看出不同時(shí)段客流樣本的異同,因此本文構(gòu)建時(shí)段客流特征向量來(lái)描述一定時(shí)間段內(nèi)的客流變化特征.

本文采用時(shí)段客流的最大值、最小值、平均值、標(biāo)準(zhǔn)差、客流上升時(shí)間比、客流下降時(shí)間比共6 個(gè)特征值來(lái)描述一定時(shí)間段內(nèi)的客流變化特征.

對(duì)一段長(zhǎng)度為N的時(shí)段客流序列c={c1,c2,···,cN},則上述特征值的計(jì)算公式如下:

時(shí)段客流序列c的最大值cmax計(jì)算公式如式(3):

時(shí)段客流序列c的最小值cmin計(jì)算公式如式(4):

時(shí)段客流序列c的平均值cavg計(jì)算公式如式(5):

時(shí)段客流序列c的標(biāo)準(zhǔn)差cstd計(jì)算公式如式(6):

時(shí)段客流序列c的客流上升時(shí)間比cup計(jì)算公式如式(7):

時(shí)段客流序列c的客流下降時(shí)間比cdown計(jì)算公式如式(8):

這6 個(gè)特征值中cmax反映時(shí)段內(nèi)每分鐘進(jìn)站客流的上限;cmin反 映時(shí)段內(nèi)每分鐘進(jìn)站客流的下限;cavg反映時(shí)段內(nèi)每分鐘進(jìn)站客流的平均水平;cstd反映時(shí)段內(nèi)按分鐘統(tǒng)計(jì)的進(jìn)站客流變化的波動(dòng)幅度;cup體現(xiàn)時(shí)段內(nèi)客流的上升趨勢(shì);cdown體現(xiàn)時(shí)段內(nèi)客流的下降趨勢(shì).這6 個(gè)特征值共同組成該客流片段的特征向量,用以描述該客流片段的客流變化特征.

根據(jù)1.1 節(jié)和1.2 節(jié)生成的時(shí)段客流樣本集,本文采用上述方法構(gòu)建時(shí)段客流樣本集D對(duì)應(yīng)的時(shí)段客流特征向量樣本集C.設(shè)樣本Di對(duì)應(yīng)的特征向量為Ci,且分 別對(duì)應(yīng)樣本Di的最大值、最小值、平均值、標(biāo)準(zhǔn)差、客流上升時(shí)間比、客流下降時(shí)間比,則樣本Di的特征向量Ci表示如式(9):

2 聚類算法模型

數(shù)據(jù)挖掘是一項(xiàng)通過(guò)分析大量歷史數(shù)據(jù)進(jìn)而挖掘提取隱藏的、存在潛在應(yīng)用價(jià)值的信息的技術(shù)手段.而聚類分析作為數(shù)據(jù)挖掘的一種核心技術(shù),具有巨大的潛在應(yīng)用價(jià)值,是當(dāng)下社會(huì)最具有應(yīng)用前景的數(shù)據(jù)分析方式之一.而K-means 聚類算法是一種經(jīng)典的解決數(shù)據(jù)聚類問(wèn)題的算法,其快速、簡(jiǎn)單、高效,并且適合應(yīng)用于大數(shù)據(jù)集上.本文基于K-means 算法進(jìn)行地鐵運(yùn)營(yíng)時(shí)段的劃分.

2.1 K-means 聚類算法原理

K-means是一種常用的聚類算法,算法的核心思想是根據(jù)各樣本之間的距離將最靠近的樣本進(jìn)行聚類,并在多次迭代中不斷更新各聚類中心的值,直至達(dá)到算法設(shè)定的收斂條件,得到最好的聚類結(jié)果.

算法首先從樣本集中隨機(jī)選取k個(gè)對(duì)象作為聚類的初始中心點(diǎn),然后計(jì)算樣本集中所有剩余樣本到各聚類中心點(diǎn)的距離,并以此將剩余的各個(gè)樣本劃分到與其相距最近的類別中,形成新的類別簇,再重新計(jì)算各類別的新的中心值,重復(fù)上述過(guò)程,直至達(dá)到算法提前設(shè)定的停止條件.K-means 算法終止迭代的條件有迭代次數(shù)、各類簇的中心變化率、最小平方誤差等.本文采用最小平方誤差作為K-means 算法的迭代終止條件.則算法的目標(biāo)函數(shù)定義如下:

式(10)中,E表示樣本集中所有樣本到各自類別中心的距離平方之和,當(dāng)某一次迭代之后E的值與上一次迭代后的值相比不發(fā)生顯著變化時(shí),算法即收斂.式中k為劃分的類別數(shù),Nj為類別j中包含的樣本個(gè)數(shù),xi為類別j中的樣本i,μj為類別j的中心.

本文采用歐式距離作為樣本間距離的計(jì)算公式,設(shè)兩個(gè)樣本向量分別為u=(u1,u2,···,un),v=(v1,v2,···,vn),則u,v的歐式距離定義如下:

同時(shí)采用計(jì)算均值替代的方式更新每個(gè)樣本類別的中心點(diǎn) μj的值,公式如式(12).

基于上述選擇,本文的K-means 聚類算法的基本步驟如下:

步驟1.在樣本集C中任意選取k個(gè)樣本對(duì)象 μ1,μ2,…,μk作為每個(gè)類別的初始中心;

步驟2.采用式(11)計(jì)算樣本集中剩余的所有對(duì)象Ci和μ1,μ2,…,μk的距離,并以此將其劃分到與其距離最近的類別中心所屬的類別中,即:

步驟3.根據(jù)式(12)更新每個(gè)類別的中心 μ1,μ2,…,μk;

步驟4.根據(jù)式(10)計(jì)算該次迭代后的目標(biāo)函數(shù)E,如果該次迭代后的目標(biāo)函數(shù)值與上次迭代后的目標(biāo)函數(shù)值相差小于提前設(shè)定的閾值,則K-means 算法終止,否則,重復(fù)步驟2～步驟4.

由算法流程可知,K-means 算法有一個(gè)十分重要的參數(shù),即聚類數(shù)目k值的選取.不同的k值所產(chǎn)生的聚類結(jié)果有很大差別,因此對(duì)于K-means 算法,確定一個(gè)合適的k值就十分重要.本文采用肘部法則以及輪廓系數(shù)兩個(gè)評(píng)估指標(biāo)確定最佳聚類數(shù)k.

2.2 肘部法則

肘部法則(elbow method)根據(jù)聚類的誤差平方和(Sum of the Squared Errors,SSE)的變化程度來(lái)確定最佳的聚類數(shù),SSE的計(jì)算公式如下:

式(14)中,Gi是第i個(gè)簇,p是Gi中的樣本點(diǎn),mi是簇Gi的中心,SSE是所有樣本的聚類誤差結(jié)果,代表了聚類結(jié)果的好壞程度.由SSE定義可知,SSE即為k值確定情況下該k值對(duì)應(yīng)最終聚類結(jié)果的目標(biāo)函數(shù)E.

采用肘部法則確定最佳聚類數(shù)的核心思想為:對(duì)于有一定的區(qū)分度的數(shù)據(jù)來(lái)說(shuō),伴隨著K-means 算法的聚類數(shù)k值的增大,所有樣本的劃分會(huì)越來(lái)越精細(xì),那么每一個(gè)類別的內(nèi)部聚合程度會(huì)越來(lái)越高,則聚類的誤差平方和SSE的值也就會(huì)變得越來(lái)越小.同時(shí),當(dāng)聚類數(shù)k的值還沒(méi)達(dá)到樣本集最優(yōu)的聚類數(shù)時(shí),伴隨k值的增大,會(huì)極大增加樣本中各類別的聚合程度,此階段誤差平方和SSE的值隨k值的增大有較大下降幅度.而當(dāng)聚類數(shù)k的值超過(guò)最優(yōu)的聚類數(shù)時(shí),伴隨k值的增大,所能夠得到的各類別聚合程度的回報(bào)會(huì)快速的降低,此階段的誤差平方和SSE的降幅會(huì)相應(yīng)的變小,并隨著聚類數(shù)k的值的增加而平緩增長(zhǎng).因此誤差平方和SSE的值與聚類數(shù)k的關(guān)系圖變化曲線會(huì)形如手肘,而圖中的這個(gè)肘部位置也即是曲線拐點(diǎn)的位置對(duì)應(yīng)的聚類數(shù)k就是所要找的最佳聚類數(shù).

2.3 輪廓系數(shù)

對(duì)于一個(gè)聚類任務(wù)的結(jié)果,最希望的聚類情況是簇內(nèi)樣本盡量緊密,簇間的樣本盡量遠(yuǎn)離.而輪廓系數(shù)(silhouette coefficient)同時(shí)考慮了類別內(nèi)部的聚集度以及類別間的分離度,用以評(píng)價(jià)聚類結(jié)果的好壞.

輪廓系數(shù)的計(jì)算方法如下:

步驟1.計(jì)算樣本i到同類別下其他樣本的平均距離a(i).a(i)越小,表明樣本i與該類簇的相似度越高,越應(yīng)該被聚類到該類簇.

步驟2.計(jì)算樣本i到與他相鄰的最近的一個(gè)類別簇的所有樣本的平均距離b(i).b(i)越大,表明樣本i越不屬于其他的類簇.

步驟3.根據(jù)以上計(jì)算,定義樣本i的輪廓系數(shù)如下:

步驟4.對(duì)所有的樣本計(jì)算輪廓系數(shù),再采用所有樣本的輪廓系數(shù)的均值作為該聚類結(jié)果的輪廓系數(shù).

由輪廓系數(shù)的定義公式可知,其取值范圍為[?1,1].其中取值越大,就說(shuō)明聚類得到的結(jié)果越加合理.當(dāng)s(i)越 接近1 時(shí),表明對(duì)樣本i的聚類越合理;s(i)的值越接近?1,則表明樣本i更應(yīng)該被分類到其他的類別簇中去.當(dāng)s(i)接近0 時(shí),表明樣本i在兩個(gè)類別簇的邊界上.使用輪廓系數(shù)來(lái)確定最佳聚類數(shù)時(shí),應(yīng)盡量選擇使輪廓系數(shù)較大的聚類數(shù)k值.

3 實(shí)驗(yàn)結(jié)果

基于本文第1 節(jié)提取的樣本特征向量集,采用第2 節(jié)的K-means 聚類算法模型進(jìn)行聚類分析,其中聚類數(shù)k的范圍設(shè)定為[2,9].則各聚類數(shù)k聚類結(jié)果如圖1以及圖2所示,圖1為聚類數(shù)k與誤差平方和的關(guān)系圖,也即肘部法則圖,圖2為聚類數(shù)k與輪廓系數(shù)的關(guān)系圖.

圖1 肘部法則關(guān)系圖

圖2 輪廓系數(shù)與聚類數(shù)k 關(guān)系圖

由圖1可知,聚類數(shù)k與誤差平方和的關(guān)系圖的拐點(diǎn)出現(xiàn)在k=3 處,根據(jù)肘部法則的思想,初步確定k=3為較好的聚類數(shù).由圖2可知,當(dāng)k=2 時(shí),聚類結(jié)果的輪廓系數(shù)最大,但結(jié)合圖1可知,此時(shí)的聚類結(jié)果的誤差平方和還較大,而k=3 時(shí)的輪廓系數(shù)僅略低于k=2 時(shí)的輪廓系數(shù),同時(shí),k=3 時(shí)的誤差平方和也相較更低,而且k=3 也是肘部法則評(píng)判標(biāo)準(zhǔn)中的最佳聚類數(shù).

因此,結(jié)合肘部法則以及輪廓系數(shù)兩個(gè)評(píng)價(jià)標(biāo)準(zhǔn),最終確定k=3為最佳聚類數(shù),即將樣本聚為3 類,此時(shí)聚類結(jié)果的誤差平方和的取值為9.4758,對(duì)應(yīng)的輪廓系數(shù)取值為0.4897.最終的聚類劃分結(jié)果如表1所示.

由表1可知各樣本所屬類別.根據(jù)各樣本所對(duì)應(yīng)的時(shí)段,將各相鄰的樣本對(duì)應(yīng)的時(shí)段進(jìn)行合并,可以得到目標(biāo)線路運(yùn)營(yíng)日中工作日一天的時(shí)段劃分的初步結(jié)果如表2所示.初步的劃分結(jié)果將一天劃分為9 個(gè)時(shí)段.

表1 樣本聚類結(jié)果

表2 初步的時(shí)段劃分方案

由表2可以得到初步的運(yùn)營(yíng)時(shí)段劃分方案.但是在初步的劃分方案中,時(shí)段4 以及時(shí)段5 分別只有10 分鐘的長(zhǎng)度,這樣的劃分方式對(duì)于運(yùn)營(yíng)公司來(lái)說(shuō)并不易于操作,因此需要對(duì)該劃分結(jié)果進(jìn)行修正.考慮到時(shí)段5 與時(shí)段3 在聚類時(shí)屬于同一類別,因此將時(shí)段3、4、5 合并為同一個(gè)運(yùn)營(yíng)時(shí)段.同時(shí)由于福州地鐵一號(hào)線的首末班車發(fā)車時(shí)間分別為6:30、23:00,因此經(jīng)過(guò)修正后的運(yùn)營(yíng)時(shí)段的劃分方案如表3所示.

表3 修正后的時(shí)段劃分方案

最終的運(yùn)營(yíng)時(shí)段劃分方案將工作日一天劃分為6 個(gè)時(shí)段,分別為6:30-7:10、7:10-9:10、9:10-17:20、17:20-18:50、18:50-22:20、22:20-23:00.其劃分結(jié)果示意圖如圖3所示.圖中虛線即為各時(shí)段的起止時(shí)間點(diǎn)分割線.

在該運(yùn)營(yíng)時(shí)段的劃分方案中,每個(gè)時(shí)段內(nèi)的客流都有著相似的變化特點(diǎn),運(yùn)營(yíng)公司可以據(jù)此時(shí)段劃分方案,根據(jù)各時(shí)段內(nèi)的實(shí)際客流需求,采取合適的發(fā)車間隔,制定全天的列車運(yùn)行方案.值得指出的是,時(shí)段6:30-7:10、9:10-17:20 以及18:50-22:20 由于屬于相同類別,因此其客流變化特性具有相似性,在制定發(fā)車間隔時(shí)可以考慮采用相同或者相近的發(fā)車間隔.同理,時(shí)段7:10-9:10 與17:20-18:50 也是如此.這也為運(yùn)營(yíng)公司制定行車方案提供了更加豐富的思路.

圖3 工作日全天時(shí)段劃分

4 結(jié)論與展望

本文著眼于地鐵運(yùn)營(yíng)時(shí)段劃分問(wèn)題進(jìn)行了相應(yīng)的研究.針對(duì)傳統(tǒng)研究中采用客流量作為樣本進(jìn)行研究的局限等問(wèn)題,提出一種構(gòu)建時(shí)段客流特征向量的方法進(jìn)行地鐵運(yùn)營(yíng)時(shí)段的劃分.首先構(gòu)建線路目標(biāo)運(yùn)營(yíng)日的單日客流序列,并采用合適的時(shí)間間隔將客流序列進(jìn)行切片,再通過(guò)構(gòu)建各時(shí)段客流樣本特征向量的方式描述各時(shí)段的客流特征,最后借助于K-means 聚類算法模型確定最佳聚類結(jié)果,進(jìn)而得到最優(yōu)的運(yùn)營(yíng)時(shí)段劃分方案.

地鐵運(yùn)營(yíng)時(shí)段的合理劃分,能夠幫助運(yùn)營(yíng)部門制定更加符合實(shí)際需求的發(fā)車方案.本文提出的基于時(shí)段客流特征聚類的運(yùn)營(yíng)時(shí)段劃分方法,以大量實(shí)際客流為基礎(chǔ),考慮了地鐵客流的實(shí)際變化特性,能夠更加客觀的給出劃分方案,避免了人工劃分的主觀性等缺點(diǎn).當(dāng)然,為了得到更加合理的地鐵列車運(yùn)行時(shí)刻表方案,需要在本研究的基礎(chǔ)上進(jìn)行進(jìn)一步的各時(shí)段發(fā)車間隔研究,這同時(shí)也是作者下一步的研究重點(diǎn).