有序樣本聚類方法在城市軌道交通運營時段劃分中的應用

曾小旭，汪林，羅賢迪，張寧，趙圣娜

有序樣本聚類方法在城市軌道交通運營時段劃分中的應用

曾小旭1，汪林2，4，羅賢迪3，張寧2，趙圣娜2

(1.天津市地下鐵道運營有限公司，天津300222;2.東南大學ITS研究中心軌道交通研究所，南京210018; 3.東南大學成賢學院，南京210088;4.北京城建設(shè)計發(fā)展集團股份有限公司，北京100045)

為合理劃分軌道交通運營時段并指導其開行方案，提出一種基于有序樣本聚類技術(shù)的運營時段劃分方法。根據(jù)統(tǒng)計時段內(nèi)客流數(shù)據(jù)，引入單向OD(origin-destination)概率矩陣，并給出單向OD概率矩陣的時序模型和提取方法;利用有序樣本聚類方法，以最優(yōu)分割法量化站間客流轉(zhuǎn)移規(guī)律，求解聚類方案。最后以某一軌道交通線路為例，提取時間間隔為20 min的上行OD概率矩陣時間序列，以最優(yōu)分割法進行聚類，將站間客流轉(zhuǎn)移規(guī)律相近的統(tǒng)計時段歸為一類，提出目標線路運營時段劃分方案。

城市軌道交通;單向OD概率矩陣;運營時段劃分;有序樣本聚類

城市軌道交通列車開行方案規(guī)定了列車在沿線各車站的到發(fā)時刻，是日常運營組織的前提與基礎(chǔ)［1］。為最小化站臺乘客的候車時間，提高服務(wù)水平，運營單位廣泛采用分時段等間隔發(fā)車的列車開行方案［2］。這種方案具體表現(xiàn)為:客流高峰期縮短發(fā)車間隔，以提高發(fā)車頻率的方式減少乘客候車時間;客流低谷期延長發(fā)車間隔，通過減少發(fā)車次數(shù)以節(jié)約運營成本。

常見的運營時段劃分方法是根據(jù)一日內(nèi)目標線路特征區(qū)間斷面客流的變化情況，將運營日全天劃分為高峰時段、正常時段、低谷時段、過渡時段等若干運營時段［3］，不同運營時段的客流規(guī)律通常存在較大差異。鑒于斷面客流數(shù)據(jù)無法直接由乘客交易記錄統(tǒng)計［4］，本文基于目標線路特定時間間隔的單向OD矩陣，提取相對應的單向OD概率矩陣，并對提取的矩陣序列進行有序樣本聚類分析，以期實現(xiàn)運營時段的合理劃分，為優(yōu)化列車開行方案提供依據(jù)。

1 目標線路單向OD概率矩陣

1.1 目標線路單向OD矩陣

軌道交通OD矩陣反映了線路上起、訖點之間的乘客出行分布［5］，體現(xiàn)了乘客在矩陣包含的起、訖點之間的出行需求。目標線路OD矩陣包括上行和下行兩個客流統(tǒng)計方向，本文以上行方向單向OD矩陣為例進行分析。

將目標線路共J個站點依次編號為1，2，…，J，在統(tǒng)計時段Tk內(nèi)抵達目標線路站點i候車，且選擇站點j下車的乘客人數(shù)記作以自動售檢票(automatic fare collection，AFC)系統(tǒng)采集的歷史交易記錄作為基礎(chǔ)數(shù)據(jù)，對Tk時段內(nèi)各進行統(tǒng)計。在客流需求給定的前提下，各站首班車離站前抵達候車的乘客，其當前出行不受發(fā)車方案的影響。

因此，本文僅針對首班車離站后的站臺候車人數(shù)進行統(tǒng)計，可得目標線路對應時段的單向OD矩陣Sk，且有(Sk)ij=

1.2 目標線路單向OD概率矩陣

1.2.1 單向OD概率矩陣的時序模型

單向OD概率矩陣反映了目標線路上乘客在各起、訖點之間的出行分布概率。將統(tǒng)計時段Tk內(nèi)抵達站點i候車的乘客在站點j下車的概率記作由于僅考慮上行客流，故有＜J)。因此，在統(tǒng)計時段Tk內(nèi)，目標線路單向OD概率矩陣Ak為J×J上三角陣，且有(Ak)ij=akij，Ak表達式為

選取適當?shù)臅r間間隔，將運營日全天劃分為若干前后相繼的統(tǒng)計時段，并分別對各單向OD概率矩陣進行提取，得到一組時間序列A:{A1，A2，A3，…}，該序列反映了目標線路單向OD概率隨時間推移的演變情況。

1.2.2 單向OD概率矩陣的提取方法

由伯努利大數(shù)定律［6］可知:фε＞0，有依概率收斂于當統(tǒng)計時段內(nèi)抵達站點i候車的乘客數(shù)量足夠多時，“乘客選擇站點j下車”這一隨機事件發(fā)生的頻率與相應概率的偏差大于預先給定精度ε的可能性會小到忽略不計。因此，可構(gòu)建矩陣Bk對Ak進行估計，使得當幾乎不存在較大偏差，Bk表達式為

當在統(tǒng)計時段內(nèi)抵達目標線路站點i候車的上行方向乘客數(shù)給定時，可借助契比雪夫不等式［6］估計上述方法的可靠性，表達式為

由于工作日與周末屬于不同類運營日，其群體出行規(guī)律存在較大差異［7］。因此，在提取單向OD矩陣時，通過增大統(tǒng)計樣本數(shù)量，選取多個同類運營日的交易記錄，以此來滿足預估參數(shù)的精度及可靠性要求。

2 有序樣本聚類法

2.1 概述

在許多實際問題中，對按一定要求排列的樣本進行聚類分析時，必須保證樣本的排列順序不能被隨意打亂［8］。為解決這類樣本聚類問題，費歇［9］于1958年提出了有序樣本聚類方法，又稱最優(yōu)分割法，算法的基本思想在于:以總的分類損失函數(shù)作為評判依據(jù)，尋找使得類內(nèi)相似度最大、類間差異最顯著的最優(yōu)聚類方案。

2.2 原理

2.2.1 類直徑定義

設(shè)S1，S2，…，Sn是n個有序樣本，Si(i=1，2，…n)為m維行向量。設(shè)其中某一類G包含的樣本為

式中，類直徑D( i，j)表示樣本的離差平方和;S=

定義該類直徑為

2.2.2 分類損失函數(shù)定義

用b(n，k)表示將n個有序樣本分為k類的某一種分法，記該分法為

式中，1=j1＜j2＜…＜jk＜n=jk+1－1為分類點。

該分類法下的損失函數(shù)定義為:

當n、k固定時，L b(n，[k])越小，表示各類的離差平方和越小，分類越合理［10］，故要尋找一種分類方法P (n，k)，使分類損失函數(shù)達到最小，P(n，k)即為給定分類數(shù)k下的最優(yōu)分割方法。

2.2.3 最小分類損失矩陣及分類標記矩陣構(gòu)建

費歇最優(yōu)分割算法的核心是以下兩個遞推公式:

式中，3≤l≤n，k≤j≤n。公式(7)(8)表明，將n個樣品分為k類的最優(yōu)分割方案，建立在使前j－1個有序樣本分為k－1類的最優(yōu)分割之上。

基于上式可得最小分類損失矩陣Pn×n，使得2≤k＜l≤n，有(P)lk=L P(l，k[])，矩陣P中其余元素均置為0。

同樣可得與之對應的分類標記矩陣Jn×n，使得2≤k＜l≤n，有(J)lk=jlk，其中jlk表示P l，(k)中第k類的起始樣本序號;且k=l，有(J)lk=k，矩陣Jn×n中其余元素均置為0。

2.2.4 最優(yōu)分割方案求解

基于最小分類損失矩陣Pn×n以及對應的分類標記矩陣Jn×n，求解最優(yōu)分割方案P n，(k)。

1)指定分類數(shù)k(1＜k＜n)。(P)nk為最優(yōu)分類p n，()k對應的最小損失函數(shù)，(J)nk為P n，()k中第k類的起始樣本序列號jk，滿足下式:

可得第k－1類Gk－1={jk－1，jk－1+1，…，jk－1}。以此類推，得到所有分類G1，G2，…，Gk，即為所求的最優(yōu)分割P(n，K)={G1，G2，…，Gk}。

2)未指定分類數(shù)k。若事先不能確定分類數(shù)k，則可以作出(P)nk隨k變化的趨勢圖，結(jié)合實際應用需求，根據(jù)曲線走勢確定合適的分類數(shù)目。

3 實例分析

3.1 歷史數(shù)據(jù)統(tǒng)計

選取某城市軌道交通2013年3月18日—4月14日所有工作日的線網(wǎng)交易記錄作為基礎(chǔ)數(shù)據(jù)，從中提取時間間隔為20min的某線路上行OD概率矩陣序列。該目標線路共有車站26座，運營日按提取時間間隔可劃分為54個時間段，即54個有序樣本，按時間順序?qū)颖窘M織成26×26×54的三維數(shù)組，記作OD_RATE。

3.2 有序樣本聚類分析

由于單向OD概率矩陣序列具有明顯的時序特性，利用最優(yōu)分割法對OD_RATE進行初次聚類，得到分類損失函數(shù)L[ p( 54，k)]隨分類數(shù)k的變化趨勢，如圖1所示。

圖1 基于最優(yōu)分割的初次聚類損失函數(shù)變化趨勢Fig.1 Trend of first clustering loss function based on optimal separation

當分類數(shù)k＜10時，曲線較為陡峭;當k＞15時，曲線漸趨平緩，損失函數(shù)隨分類數(shù)的增加而緩慢衰減。曲線的拐點大致出現(xiàn)在k=12處，因此，初始分類數(shù)設(shè)定為12，相應損失函數(shù)L[ p( 54，12)]=8.6873，初次聚類結(jié)果如表1所示。

表1 初次聚類結(jié)果明細Tab.1 Detailed results of first clusterin g

由表1可知，初次聚類結(jié)果中存在樣本編號為1、2、51、52、53、54的多個孤立點。通過分析相應樣本發(fā)現(xiàn)，除樣本51外的孤立樣本點中均出現(xiàn)全零行，樣本1、2中的全零行均出現(xiàn)在矩陣下方，行數(shù)遞減;樣本52～54中的全零行均位于矩陣上方，行數(shù)單調(diào)遞增。

結(jié)合單向OD概率矩陣的提取方法可推知，樣本1、2中的全零行是由構(gòu)造單向OD矩陣時所采取的客流統(tǒng)計方法造成的。在6:00—6:20時段，由于僅對各站首車離站后的進站客流進行統(tǒng)計，對于首車離站時間在6:20以后的站點，其進站客流均未計入該時段的單向OD矩陣，從而導致樣本1中的對應位置出現(xiàn)全零行。同理，樣本2中出現(xiàn)全零行。

目標線路運營方式是導致樣本52～54孤立的主要成因。在23:00—23:20時段，首站已不再產(chǎn)生有效的進站客流，因此，樣本52中首行出現(xiàn)全零;在23:20—23:40時段，對于末班離站時間在23:20以前的站點，亦不再產(chǎn)生有效的進站客流，導致樣本53中對應位置出現(xiàn)全零行;樣本54中的全零行也是由此導致，且其行數(shù)因時間推移而有所增加。

基于上述分析，判定樣本1、2、52～54為異常樣本，將其從樣本集OD_RATE中剔除。對剩余樣本進行二次聚類，得到二次聚類的損失函數(shù)L[ p( 49，k)]隨分類數(shù)k的變化趨勢，如圖2所示。

經(jīng)分析，曲線的拐點大致出現(xiàn)在k=7處，設(shè)定二次聚類的分類數(shù)為7，相應損失函數(shù)L[ p( 49，7)]= 8.6873，聚類結(jié)果如表2所示。

圖2 基于最優(yōu)分割的二次聚類損失函數(shù)變化趨勢Fig.2 Trend of twice clustering loss funtion based on optimal separation

表2 二次聚類結(jié)果明細Tab.2 Detailed results of tw ice clustering

3.3 運營時段劃分

依據(jù)該城市軌道交通運營管理規(guī)定，目標線路上行方向首班發(fā)車時間為6:00，末班發(fā)車時間為23:00，全程運行時長為58 min?；谏衔木垲惤Y(jié)果，結(jié)合實際運營條件，提出目標線路工作日運營時段劃分方案，如表3所示。

表3 工作日運營時段劃分方案Tab.3 Division of operation periods ofworking day

在此運營時段劃分方案中，全天運營時間被劃分為8個不等間隔的運營時段，每個運營時段內(nèi)的客流分布規(guī)律較為統(tǒng)一，不同時段之間則體現(xiàn)出較大的差異性?；诖?，軌道交通運營管理部門可根據(jù)各運營時段的實際客流情況，選取各自合適的發(fā)車間隔，構(gòu)建目標線路的全日分時段等間隔發(fā)車方案并制定相應的列車開行計劃。

需要指出的是，該線路末班車發(fā)車時間為23:00，末班車到達終點站時間約為23:58，線路全天實際運營時間為6:00—23:58，比有效發(fā)車時間6:00—23:00長1 h左右，因此，本方案劃分的最后一個運營時段與其實際發(fā)車時段并不完全重合。由于末班車于23:00準點發(fā)車，故該運營時段的有效發(fā)車時間僅為22:40—23:00共計20 min。

4 結(jié)語

圍繞軌道交通運營時段劃分展開研究，提出一種基于有序樣本聚類技術(shù)的運營時段劃分方法，以一定時間間隔內(nèi)目標線路單向OD概率矩陣為樣本，構(gòu)造有序樣本序列，并利用有序樣本聚類的最優(yōu)分割法，量化站間客流轉(zhuǎn)移規(guī)律的差異性，在此基礎(chǔ)上合理劃分運營時段。軌道交通運營時段劃分方法的研究，為運營部門制定分時發(fā)車計劃提供決策支持，同時，也為進一步優(yōu)化目標線路的運營調(diào)度方案奠定基礎(chǔ)。考慮到將來軌道交通線網(wǎng)逐漸形成，客流情況更加復雜，需在本研究的基礎(chǔ)上著眼于軌道交通全網(wǎng)，兼顧上下行兩個方向，增加換乘站等影響因素，這也是作者下一步研究的重點。

［1］?；菝?，陳明明，張明輝.城市軌道交通列車開行方案的優(yōu)化理論及方法［J］.中國鐵道科學，2011，32(4):128- 133.

NIU Huim in，CHEN M ingming，ZHANG Minghui.Optim ization theory and method of train operation scheme for urban rail transit［J］.China railway science.2011，32(4): 128- 133.

［2］毛保華.城市軌道交通系統(tǒng)運營管理［M］.北京:人民交通出版社，2006.

MAO Baohua.Operation and management for urban rail transit［M］.Beijing:China Communications Press，2006.

［3］孫焰，施其洲，趙源，等.城市軌道交通列車開行方案的確定［J］.同濟大學學報(自然科學版)，2004，32(8): 1005- 1008.

SUN Yan，SHIQizhou，ZHAO Yuan，et al.Method on making train running-plan for urban railway traffic［J］.Journal of Tongji University(natural science edition)，2004，32(8):1005- 1008.

［4］Newell G F.Dispatching policies for a transportation route［J］.Transportation science，1971，5(1):91 105.

［5］徐瑞華，徐永實.城市軌道交通線路客流分布的實時預測方法［J］.同濟大學學報(自然科學版)，2011，39(6):857 861.

XU Ruihua，XU Yongshi.Real-time forecastof passenger flow distribution on urban rail transit line［J］.Journal of Tongji University(natural science edition)，2011，39(6):857 861.

［6］王紅，劉磊.概率論與數(shù)理統(tǒng)計［M］.上海:同濟大學出版社，2014.

WANG Hong，LIU Lei.Probability and mathematical statistics［M］.Shanghai:Tongji University Press，2014.

［7］邱華瑞.城市軌道交通客流時空演變規(guī)律研究［D］.南京:東南大學，2014.

QIU Huarui.Research of passenger flow space-time evolution regularity on urban rail transit［D］.Nanjing:Southeast University，2014.

［8］方開泰.有序樣品的一些聚類方法［J］.應用數(shù)學學報，1982，5(1):94- 101.

FANG Kaitai.Some clustering methods for the order sample［J］.Actamathematicae applicatae sinica，1982，5(1): 94- 101.

［9］FISHER W D.On grouping for maximum homogeneity［J］.Journal of the American statistical association，2015，53(284):789- 798.

［10］周東華.數(shù)據(jù)挖掘中聚類分析的研究與應用［D］.天津:天津大學，2006.

ZHOU Donghua.Research and application of cluster analysis in datamining［D］.Tianjin:Tianjin University，2006.

(編輯:曹雪明)

Application of Ordinal Clustering in the Division of Operation Periods for Urban Rail Transit

ZENG Xiaoxu1，WANG Lin2，4，LUO Xiandi3，ZHANG Ning2，ZHAO Shengna2
(1.Tianjin Metro Operation Co.，Ltd.，Tianjing 300222;2.ITSRail Transit Research Institute of Southeast University，Nanjing，210018;3.Scool of Chengxian，Southeast University，Nanjing 210088; 4.Beijing Urban Construction Design＆Development Group Co.，Ltd.，Beijing 100045)

To divide rail transit operation period reasonably and conduct the operation plan，amethod of operation period division using ordinal clustering was put forward in this paper.On the basis of one-way OD(Origin-Destination)probability matrix，the timingmodel and extractionmethod for one-way OD probabilitymatrix in a statistical period was given.Then，the optimal partition algorithm was used to quantify interstation-passenger-transfer rules and solve the ordinal clustering scheme.Finally，the time sequences of uplink OD probabilitymatrix(for an interval of 20m inutes)was constructed on the case of a rail transit line.According to the results of the ordinal clustering by the optimal partition algorithm，the statistical periods with similar interstation-passenger-transfer rules were classified together and the operation period division was proposed，providing decisionmaking basis for division of operation periods by the operation department.

urban rail transit;one-way OD probabilitymatrix;division of operation periods;ordinal clustering

F530.7

A

1672- 6073(2017)02- 0108- 05

10.3969/j.issn.1672 6073.2017.02.022

2016- 05 27

2017 01 08

曾小旭，男，高級工程師，從事軌道交通運營管理、調(diào)度指揮等工作，18530606@qq.com

交通運輸部建設(shè)科技項目(2015318J33080);江蘇省重點研發(fā)計劃(社會發(fā)展)項目(BE2016740)