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

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

2(福州大學(xué) 智慧地鐵福建省高校重點實驗室,福州 350108)

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

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

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

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

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

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

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

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

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

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

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

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

1.3 時段客流特征向量

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

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

對一段長度為N的時段客流序列c={c1,c2,···,cN},則上述特征值的計算公式如下:

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

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

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

時段客流序列c的標準差cstd計算公式如式(6):

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

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

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

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

2 聚類算法模型

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

2.1 K-means 聚類算法原理

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

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

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

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

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

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

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

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

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

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

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

2.2 肘部法則

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

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

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

2.3 輪廓系數(shù)

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

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

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

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

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

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

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

3 實驗結(jié)果

基于本文第1 節(jié)提取的樣本特征向量集,采用第2 節(jié)的K-means 聚類算法模型進行聚類分析,其中聚類數(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)系圖的拐點出現(xiàn)在k=3 處,根據(jù)肘部法則的思想,初步確定k=3為較好的聚類數(shù).由圖2可知,當k=2 時,聚類結(jié)果的輪廓系數(shù)最大,但結(jié)合圖1可知,此時的聚類結(jié)果的誤差平方和還較大,而k=3 時的輪廓系數(shù)僅略低于k=2 時的輪廓系數(shù),同時,k=3 時的誤差平方和也相較更低,而且k=3 也是肘部法則評判標準中的最佳聚類數(shù).

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

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

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

表2 初步的時段劃分方案

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

表3 修正后的時段劃分方案

最終的運營時段劃分方案將工作日一天劃分為6 個時段,分別為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所示.圖中虛線即為各時段的起止時間點分割線.

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

圖3 工作日全天時段劃分

4 結(jié)論與展望

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

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