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

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

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

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

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

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

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

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

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

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

1.1 目標線路單向OD矩陣

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

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

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

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

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

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

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

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

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

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

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

2 有序樣本聚類法

2.1 概述

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

2.2 原理

2.2.1 類直徑定義

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

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

定義該類直徑為

2.2.2 分類損失函數定義

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

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

該分類法下的損失函數定義為:

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

2.2.3 最小分類損失矩陣及分類標記矩陣構建

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

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

基于上式可得最小分類損失矩陣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 最優分割方案求解

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

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

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

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

3 實例分析

3.1 歷史數據統計

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

3.2 有序樣本聚類分析

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

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

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

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

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

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

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

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

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

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

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

3.3 運營時段劃分

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

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

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

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

4 結語

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

［1］?；菝?，陳明明，張明輝.城市軌道交通列車開行方案的優化理論及方法［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］毛保華.城市軌道交通系統運營管理［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］王紅，劉磊.概率論與數理統計［M］.上海:同濟大學出版社，2014.

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

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

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

［8］方開泰.有序樣品的一些聚類方法［J］.應用數學學報，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］周東華.數據挖掘中聚類分析的研究與應用［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

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

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