高萬(wàn)晨，路世昌，李丹

(遼寧工程技術(shù)大學(xué)，工商管理學(xué)院，遼寧葫蘆島 125000)

0 引言

科技的進(jìn)步與發(fā)展使自動(dòng)數(shù)據(jù)收費(fèi)系統(tǒng)成為可能，并在城市公交系統(tǒng)中得到廣泛運(yùn)用，尤其是自動(dòng)收費(fèi)系統(tǒng)(Automatic Fare Collection,AFC)和自動(dòng)車輛位置系統(tǒng)(Automatic Vehicle Location,AVL)。AFC 系統(tǒng)不僅可以實(shí)現(xiàn)收費(fèi)的目的，還可以實(shí)時(shí)地收集到巨量的乘客刷卡交易數(shù)據(jù)。AVL系統(tǒng)可以實(shí)時(shí)記錄公交車輛的到離站時(shí)間、經(jīng)緯度坐標(biāo)、瞬時(shí)速度及方向角等內(nèi)容。因此，公交企業(yè)試圖將收集到的海量數(shù)據(jù)應(yīng)用于城市公共交通的線網(wǎng)規(guī)劃、運(yùn)營(yíng)、控制與管理等方面，以使公交系統(tǒng)達(dá)到最優(yōu)狀態(tài)[1]。

但是，如何將海量數(shù)據(jù)轉(zhuǎn)化成公交企業(yè)想要獲得的直接可以應(yīng)用的數(shù)據(jù)便成為研究者主要關(guān)注的內(nèi)容。在過(guò)去的幾十年內(nèi)，學(xué)者基于公交企業(yè)提供的數(shù)據(jù)將OD 估計(jì)和調(diào)度優(yōu)化等內(nèi)容開展了一系列研究。就OD估計(jì)而言，BARRY等[2]基于紐約市的智能刷卡數(shù)據(jù)，提出兩個(gè)假設(shè)算法，估計(jì)一票制公交系統(tǒng)的OD。馬曉磊等[3]將車輛分為已安裝GPS和未安裝GPS設(shè)備兩類，針對(duì)前者采用數(shù)據(jù)融合算法估計(jì)乘客上車站點(diǎn)，針對(duì)后者采用貝葉斯決策樹算法估計(jì)上車站點(diǎn)，并利用馬爾科夫鏈降低算法復(fù)雜度。陳君等[4]將自動(dòng)收費(fèi)系統(tǒng)數(shù)據(jù)與智能調(diào)度系統(tǒng)數(shù)據(jù)進(jìn)行關(guān)聯(lián)，估計(jì)乘客的上車站點(diǎn)，并進(jìn)行了準(zhǔn)確度分析和算法實(shí)現(xiàn)。就車輛調(diào)度優(yōu)化而言，TANG 等[5]基于自動(dòng)收費(fèi)系統(tǒng)和車輛位置系統(tǒng)數(shù)據(jù)，獲取與時(shí)間相關(guān)的變量，構(gòu)建公交時(shí)刻表的多目標(biāo)優(yōu)化模型，優(yōu)化現(xiàn)有公交時(shí)刻表。ZHANG等[6]基于智能刷卡數(shù)據(jù)，構(gòu)建單條線路時(shí)刻表優(yōu)化的非線性模型，采用無(wú)導(dǎo)數(shù)約束羅盤搜索算法求解模型。

但是，在上述研究中，公交OD 估計(jì)是最基礎(chǔ)且最重要的研究?jī)?nèi)容之一，因?yàn)?，公交OD 估計(jì)是后續(xù)研究的主要數(shù)據(jù)輸入，所以，公交OD 估計(jì)的準(zhǔn)確率直接關(guān)乎后續(xù)研究，因此，本文選取公交OD矩陣估計(jì)中的O估計(jì)(即上車站點(diǎn)估計(jì))作為主要研究?jī)?nèi)容，D估計(jì)作為將來(lái)的研究工作。

AFC系統(tǒng)主要包含一票制與分段計(jì)費(fèi)兩類，前者，乘客在上車時(shí)需要進(jìn)行刷卡付費(fèi)，下車無(wú)需再次付費(fèi)。后者，乘客在上車和下車均需要完成刷卡付費(fèi)。針對(duì)上車站點(diǎn)估計(jì)，國(guó)內(nèi)外學(xué)者根據(jù)公交企業(yè)提供的原始數(shù)據(jù)類型和屬性字段內(nèi)容的差異開展了一系列研究工作，主要分為上車時(shí)間和上車站點(diǎn)均已知，上車時(shí)間已知而上車位置未知及上車時(shí)間和上車位置均未知[1]。

就第一類而言，乘客的上車時(shí)間和站點(diǎn)均為已知，因此，不需要進(jìn)行上車站點(diǎn)估計(jì)研究，但是，ALSGER 等[7]提出上車站點(diǎn)估計(jì)方法，運(yùn)用真實(shí)的上車站點(diǎn)數(shù)據(jù)，驗(yàn)證了估算方法的有效性。針對(duì)第二類，由于AFC 系統(tǒng)缺乏上車站點(diǎn)屬性字段的記錄，僅有上車時(shí)間字段，因此，柳伍生等[8]使用時(shí)間窗方法進(jìn)行上車站點(diǎn)估計(jì)研究，并未對(duì)估計(jì)準(zhǔn)確性進(jìn)行度量。TANG等[9]采用多階段深度學(xué)習(xí)方法估計(jì)乘客的上車站點(diǎn)，確定總的上車需求，采用真實(shí)的總需求進(jìn)行驗(yàn)證。在此類別中，由于AFC 系統(tǒng)中缺少個(gè)體乘客真實(shí)的上車站點(diǎn)數(shù)據(jù)，因此，無(wú)法采用個(gè)體真實(shí)上車站點(diǎn)驗(yàn)證不同算法估計(jì)每個(gè)乘客上車站點(diǎn)的準(zhǔn)確性。最后一類也是最難估計(jì)的一類，因?yàn)?，AFC 等系統(tǒng)既沒(méi)有提供上車時(shí)間也沒(méi)有提供上車站點(diǎn)數(shù)據(jù)，因此，CHENG等[10]根據(jù)城市公交系統(tǒng)的相關(guān)數(shù)據(jù)，采用概率模型估計(jì)乘客的上車站點(diǎn)。

針對(duì)不同算法估計(jì)乘客上車站點(diǎn)準(zhǔn)確性而言，已有研究中，部分學(xué)者采用實(shí)際調(diào)查法進(jìn)行驗(yàn)證，但是該方法由于僅調(diào)查少部分樣本用于驗(yàn)證，當(dāng)總體數(shù)量達(dá)到一定量級(jí)時(shí)，無(wú)法真實(shí)反映總體的準(zhǔn)確性。另一部分研究?jī)H做了上車站點(diǎn)估計(jì)研究，并未對(duì)估計(jì)結(jié)果進(jìn)行準(zhǔn)確性度量。已有研究中，僅有少數(shù)學(xué)者采用乘客真實(shí)的上車站點(diǎn)進(jìn)行驗(yàn)證。由于大多數(shù)乘客出行具有一定的規(guī)律性，因此，可以把乘客多日出行的所有上車站點(diǎn)數(shù)據(jù)按照時(shí)間順序進(jìn)行排序，形成一個(gè)上車站點(diǎn)序列。如果能夠采用合理的方法度量此上車站點(diǎn)序列的出行規(guī)律性，便可進(jìn)一步確定某種算法估計(jì)乘客上車站點(diǎn)的準(zhǔn)確性。在信息論中，熵率可以度量事件發(fā)生的平均不確定性，熵率越大，則不確定性越高。崔洪軍等[11]采用熵率度量人們出行時(shí)間序列的重復(fù)性，研究表明，出行事件序列的熵率越小，出行規(guī)律性越強(qiáng)，反之亦然。因此，本文采用熵率方法度量不同算法確定乘客上車站點(diǎn)的準(zhǔn)確性，為確定乘客上車站點(diǎn)和后續(xù)研究提供參考。

本文的研究工作屬于第二類，即上車時(shí)間已知，而上車位置未知。已有研究中，少有學(xué)者采用多種算法進(jìn)行對(duì)比分析，且少有采用熵率方法度量乘客上車站點(diǎn)的準(zhǔn)確率。因此，本文首先采用兩階段算法、改進(jìn)K近鄰算法和改進(jìn)模糊C均值聚類算法估計(jì)乘客的上車站點(diǎn)。其次，就乘客上車站點(diǎn)的匹配率而言，將3種算法與傳統(tǒng)時(shí)間窗算法進(jìn)行對(duì)比分析。最后，采用熵率方法度量3種算法估計(jì)乘客上車站點(diǎn)的準(zhǔn)確率。

1 數(shù)據(jù)描述與預(yù)處理

本文所使用的公交原始數(shù)據(jù)來(lái)自于珠海市城市公交系統(tǒng)，數(shù)據(jù)由AFC 和AVL 兩個(gè)系統(tǒng)收集。在系統(tǒng)中截取2021年9月6日～10日的數(shù)據(jù)作為研究使用，獲取了公交線路、站點(diǎn)及車輛編號(hào)等靜態(tài)數(shù)據(jù)。

1.1 AFC數(shù)據(jù)

由于珠海市所有公交線路均為一票制，乘客每完成1 次有效刷卡，AFC 系統(tǒng)便會(huì)記錄1 條刷卡數(shù)據(jù)，如表1 所示，包括：乘客的上車刷卡時(shí)間、線路編號(hào)、車輛編號(hào)、卡號(hào)及交易類型等主要字段，但AFC 系統(tǒng)并未記錄乘客具體的上車站點(diǎn)信息。

表1 AFC數(shù)據(jù)示例Table 1 Example of AFC data

1.2 AVL數(shù)據(jù)

AVL系統(tǒng)通過(guò)將GPS設(shè)備裝于公交車上，用于公交車實(shí)時(shí)監(jiān)控，便于調(diào)度人員了解公交車的實(shí)際運(yùn)行狀況。目前，珠海市所有運(yùn)營(yíng)公交車均已安裝車載GPS設(shè)備，該系統(tǒng)可以實(shí)時(shí)地收集公交車運(yùn)行數(shù)據(jù)，并按照固定的時(shí)間間隔將數(shù)據(jù)上傳至服務(wù)器，包括：公交車到站時(shí)間、公交車離站時(shí)間、經(jīng)緯度坐標(biāo)、速度及方向角等字段數(shù)據(jù)，如表2所示。

表2 AVL數(shù)據(jù)樣例Table 2 Example of AVL data

1.3 數(shù)據(jù)預(yù)處理

設(shè)備失效和人為錯(cuò)誤是導(dǎo)致部分?jǐn)?shù)據(jù)異常的主要原因，在數(shù)據(jù)產(chǎn)生、上傳及存儲(chǔ)等過(guò)程中均可能發(fā)生。設(shè)備失效包括：刷卡設(shè)備、GPS 設(shè)備及系統(tǒng)設(shè)備等問(wèn)題。人為錯(cuò)誤包括：乘客上車忘記刷卡和多次刷卡等。由于上述錯(cuò)誤，可能會(huì)導(dǎo)致數(shù)據(jù)缺失、數(shù)據(jù)重復(fù)、數(shù)據(jù)錯(cuò)誤及相同字段在不同系統(tǒng)之間的數(shù)據(jù)不一致等錯(cuò)誤形式。如果對(duì)其不進(jìn)行科學(xué)的數(shù)據(jù)清洗操作，將會(huì)影響最終的研究結(jié)果。因此，需要對(duì)AVL 和AFC 系統(tǒng)中獲取的原始數(shù)據(jù)進(jìn)行預(yù)處理，具體如下。

(1)針對(duì)數(shù)據(jù)缺失情況，需要判斷缺失數(shù)據(jù)能否通過(guò)其他已有數(shù)據(jù)代替，如果不能，則需要進(jìn)一步判斷能否運(yùn)用插值、均值及經(jīng)驗(yàn)判斷等補(bǔ)全。如果上述方法均無(wú)法補(bǔ)全缺失數(shù)據(jù)，則需要?jiǎng)h除缺失數(shù)據(jù)。

(2)針對(duì)數(shù)據(jù)重復(fù)情況，根據(jù)實(shí)際情況進(jìn)行刪除，數(shù)據(jù)重復(fù)常見(jiàn)于起始站或終點(diǎn)站。

(3)針對(duì)數(shù)據(jù)錯(cuò)誤情況，常見(jiàn)的錯(cuò)誤主要有公交到站時(shí)間大于離站時(shí)間、站點(diǎn)不屬于此線路、時(shí)間錯(cuò)誤、僅有部分GPS 數(shù)據(jù)及僅有GPS 數(shù)據(jù)無(wú)IC卡數(shù)據(jù)，或僅有IC 卡數(shù)據(jù)無(wú)GPS 數(shù)據(jù)等。如果是靜態(tài)數(shù)據(jù)發(fā)生錯(cuò)誤，則需要通過(guò)歷史數(shù)據(jù)進(jìn)行更改；如果是動(dòng)態(tài)數(shù)據(jù)發(fā)生錯(cuò)誤，可以酌情進(jìn)行刪除。

(4)針對(duì)相同字段在不同系統(tǒng)之間的數(shù)據(jù)不一致情況，首先，利用兩個(gè)系統(tǒng)中字段相同且數(shù)據(jù)格式一致的數(shù)據(jù)將兩個(gè)系統(tǒng)的數(shù)據(jù)進(jìn)行關(guān)聯(lián)操作；然后，對(duì)相同字段存在差異的數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，或者選取其中一列數(shù)據(jù)作為基準(zhǔn)。

經(jīng)過(guò)數(shù)據(jù)清洗后，可以采用合理的算法對(duì)AFC和AVL數(shù)據(jù)進(jìn)行匹配操作，以科學(xué)合理地估計(jì)每天每條線路每輛車在運(yùn)營(yíng)時(shí)間內(nèi)的乘客上車站點(diǎn)。

2 方法

傳統(tǒng)的時(shí)間窗算法作為識(shí)別乘客上車站點(diǎn)的一種基本方法，具有簡(jiǎn)單明了和易于理解的特點(diǎn)。正常情況下，乘客上車后，需要進(jìn)行刷卡操作，第j名乘客的刷卡時(shí)間為Tj(j=1,…,μ)，公交車到達(dá)第i站時(shí)間為Ti,A(i=1,…,m)，離站時(shí)間為Ti,L(i=1,…,m)，顯然，乘客的刷卡時(shí)間應(yīng)該介于區(qū)間[Ti,A,Ti,L] 內(nèi)。但是，在公交車的實(shí)際運(yùn)營(yíng)過(guò)程中，往往會(huì)出現(xiàn)因設(shè)備誤差或故障，高峰期間擁堵產(chǎn)生的車輛提前開門或乘客因車內(nèi)擁擠產(chǎn)生的滯后刷卡，相鄰兩個(gè)公交站之間距離較近等問(wèn)題，進(jìn)一步導(dǎo)致了部分乘客的刷卡時(shí)間在公交車到站和離站時(shí)間窗之外，如圖1所示。

圖1 公交站點(diǎn)和乘客刷卡數(shù)據(jù)時(shí)空分布Fig.1 Spatial and temporal distribution of bus stops and passengers'swiping card time

由于部分乘客的刷卡時(shí)間置于車輛到站和離站時(shí)間窗之外，因此，部分學(xué)者引入了閾值[12]，改進(jìn)公交車的到站和離站時(shí)間窗，以提高時(shí)間窗外刷卡數(shù)據(jù)的匹配率，但是該方法在高峰期間可能會(huì)遇到某一站點(diǎn)上車人數(shù)過(guò)多或某一站點(diǎn)上車人數(shù)過(guò)少的情況，進(jìn)而可能因閾值過(guò)大導(dǎo)致調(diào)整后的時(shí)間窗與后續(xù)時(shí)間窗存在交集或因閾值較小導(dǎo)致調(diào)整后的時(shí)間窗與調(diào)整前的時(shí)間窗相差不大，因此，可能會(huì)影響匹配準(zhǔn)確率。

改進(jìn)的公交車到站和離站時(shí)間窗為

式中：θ為時(shí)間窗閾值。

綜上，無(wú)論時(shí)間窗算法是否有閾值，都會(huì)有一定比例的刷卡數(shù)據(jù)無(wú)法匹配，需要人工匹配。當(dāng)樣本數(shù)據(jù)達(dá)到一定數(shù)量時(shí)，該方法的效率會(huì)降低。因此，本文設(shè)計(jì)兩階段算法、改進(jìn)K 近鄰算法和改進(jìn)模糊C均值聚類算法對(duì)城市公交1條線路上所有車輛的刷卡數(shù)據(jù)進(jìn)行上車站點(diǎn)估計(jì)。由于熵率可以度量乘客出行的規(guī)律性，因此，為驗(yàn)證3 種算法的準(zhǔn)確率，采用了熵率方法。

2.1 兩階段算法

第1階段，算法采用可變閾值的時(shí)間窗方法初次匹配乘客刷卡數(shù)據(jù)和車輛到站離站時(shí)間；第2階段，算法對(duì)第1階段未匹配成功的乘客刷卡數(shù)據(jù)進(jìn)行二次匹配，確定所有刷卡數(shù)據(jù)的上車站點(diǎn)。

2.1.1 第1階段算法

基于式(2)和式(3)，繼續(xù)進(jìn)行優(yōu)化研究?；诘趇站的離站時(shí)間Ti,L(i=1,…,m)與第(i+1) 站的到站時(shí)間T(i+1),A(i=1,…,m)，提出帶有可變閾值的時(shí)間窗方法，進(jìn)一步提高乘客上車站點(diǎn)的匹配精度，具體算法如下。

Step 1 獲取所有公交運(yùn)營(yíng)線路集合L={L0,…,Ly,…,Lk}，k為線路總數(shù)，y為線路編號(hào)。

Step 2 選取某線路Ly，獲取線路Ly在運(yùn)營(yíng)時(shí)間內(nèi)的車輛集合B={By0,…,Byz,…,Bys}，s為車輛總數(shù)，z為車輛編號(hào)。刷卡數(shù)據(jù)匹配上車站點(diǎn)集合P={P0,…,Px',…,Pt}，t為匹配上車站點(diǎn)總數(shù)，x'為匹配上車站點(diǎn)編號(hào)。

Step3 選取某車輛Byz，獲取車輛Byz的刷卡時(shí)間集合I={Iyz0,…,Iyzx',…,Iyzt}，車輛到站和離站時(shí)間集合T={Tyz0c,…,Tyzic,…,Tyzmc}，c={A,L}，L 為車輛離站，A 為車輛到站，站點(diǎn)集合S={Syz0,…,Syzi,…,Syzm} 。

Step 4 確定可變閾值ψ。

(1)根據(jù)式(1)，對(duì)某條線路全天的乘客刷卡數(shù)據(jù)進(jìn)行第一次匹配，存在一定比例的刷卡數(shù)據(jù)匹配失敗。

(3)由于刷卡數(shù)據(jù)介于兩站之間，要么屬于前者，要么屬于后者。因此，選擇集合tB中小于30 s的數(shù)據(jù)組成新集合tB_new，tB_new的平均值為σB。它將用于確定車輛B在線路Ly全天的可變閾值ψB=

(4)重復(fù)Step 2和Step 3，直到確定線路Ly所有車輛的可變閾值ψ。

Step 5 對(duì)車輛Byz在運(yùn)營(yíng)時(shí)間內(nèi)的所有刷卡時(shí)間數(shù)據(jù)I和車輛到站離站時(shí)間數(shù)據(jù)T進(jìn)行匹配運(yùn)算。

(1)當(dāng)i=1時(shí)(始發(fā)站)

如果Iyzx'≤(Tyz,1L+Ψ0)，Ψ0為始發(fā)站的可變閾值，Ψ0=ψ(Tyz,2A-Tyz,1L)，則乘客Px'在第1 站(始發(fā)站)上車，即Px'=1。

否則，i=i+2，繼續(xù)進(jìn)行匹配操作。

(2)當(dāng)i ＞1時(shí)

Ψw和Ψq分別為中間站車輛到達(dá)和離開的可變閾值，Ψw=ψ(Tyzi,A-Tyz(i-1),L)，Ψq=ψ(Tyz(i+1),A-Tyzi,L)。

如果Syzi=Syz(i+1)，則需要做出如下判斷：

① 如果Iyzx'≤(Tyzi,L+Ψq)且Iyzx'≥(Tyzi,A-Ψw)，則乘客Px'在i站上車，即Px'=i。

②如果Iyzx'≥(Tyzi,A-Ψw)且Iyzx'＜(Tyzi,A-Ψw)，則乘客Px'上車站點(diǎn)匹配失敗，即Px'=Null。

③如果Iyzx'＞(Tyz(i+1),L+Ψq)，則i=i+2，繼續(xù)匹配。

④除上述3種情況外，i=i+1，繼續(xù)匹配。

否則：

①如果Iyzx'≤Tyzi,A，則Px'=i-1。

②否則，如果Iyzx'≤Tyz(i+1),A，則Px'=i+1；反之，i=i+1，繼續(xù)匹配。

(3)當(dāng)i=m(終點(diǎn)站)時(shí)

如果Iyzx'≤Tyzm,A時(shí)，乘客Px'在第(m-1) 站上車，即Px'=m-1。

Step 6 如果集合B中仍有未匹配成功的刷卡數(shù)據(jù)，轉(zhuǎn)至Step 3；否則，執(zhí)行Step 2，直到所有線路的刷卡數(shù)據(jù)全部完成上車站點(diǎn)匹配。

2.1.2 第2階段算法

經(jīng)過(guò)第1階段算法后，由于存在部分刷卡時(shí)間Iyzx'無(wú)法準(zhǔn)確匹配公交車到離站時(shí)間Tyzic，因此，需要進(jìn)一步設(shè)計(jì)一種算法，處理匹配失敗的刷卡數(shù)據(jù)，實(shí)現(xiàn)每天所有運(yùn)營(yíng)公交線路的所有車輛的全部乘客的刷卡數(shù)據(jù)的完全匹配，具體如下。

Step 1 獲取所有公交運(yùn)營(yíng)線路集合L={L0,…,Ly,…,Lk} 。

Step 2 選取某一線路Ly，獲取線路Ly在運(yùn)營(yíng)時(shí)間內(nèi)的所有刷卡數(shù)據(jù)I={Iyz0,…,Iyzx',…,Iyzt} 匹配上車站點(diǎn)的集合P={P0,…,Px',…,Pt}，并對(duì)其進(jìn)行完全匹配運(yùn)算，將完全匹配后的上車站點(diǎn)集合定義為Pb={Pb0,…,Pbx',…,Pbt} 。

Step 3 進(jìn)行數(shù)據(jù)完全匹配運(yùn)算。

(1) 如果Px'=Null，在集合P'={Px'-1,…,0} 中尋找第1個(gè)不為Null 的元素，并記錄此元素的位置d。同時(shí)，在集合P″={Px'+1,…,Pt} 中尋找第1個(gè)不為Null 的元素，并記錄此元素的位置e。如果(Iyzx'-Iyzd)＜(Iyze-Iyzx')，則Pbx'=Pd；否則，Pbx'=Pe。

(2)如果Px'!=Null，則無(wú)需再次進(jìn)行完全匹配運(yùn)算，即Pbx'=Px'。

Step 4 如果集合L中仍有未完成匹配運(yùn)算的線路，轉(zhuǎn)至Step 2；否則，算法終止。

2.2 改進(jìn)K近鄰算法

AFC系統(tǒng)中實(shí)時(shí)記錄乘客的刷卡數(shù)據(jù)，包括刷卡時(shí)間和IC卡號(hào)等主要字段。由于不同乘客在同一站點(diǎn)上車的刷卡時(shí)間具有一定的連續(xù)性，因此，可以采用最近鄰聚類算法識(shí)別乘客的上車站點(diǎn)。其中，數(shù)據(jù)集樣本為某條公交線路全天的刷卡數(shù)據(jù)，選擇曼哈頓距離作為距離計(jì)算的依據(jù)，聚類中心個(gè)數(shù)(K值)不超過(guò)公交站點(diǎn)總數(shù)S，因?yàn)椋赡艽嬖谀痴军c(diǎn)無(wú)人刷卡的現(xiàn)象，且終點(diǎn)站乘客只下不上，具體運(yùn)算步驟如下。

Step 1 算法初始化

刷卡數(shù)據(jù)I為線路Ly車輛Bz的上行或下行方向運(yùn)行一次所產(chǎn)生的t條刷卡記錄，上車刷卡時(shí)間I={Iyz0,…,Iyzx',…,Iyzt} 。選取Iyz0為聚類中心K0的初始值，即Iyz0∈K0。

Step 2 計(jì)算分類閾值ψ

以相鄰公交站點(diǎn)之間的最小行駛時(shí)間為分類閾值，ψ=min{Tyzi,A-Tyz(i-1),L}，i=2,…,S。

Step 3 計(jì)算距離

采用曼哈頓距離計(jì)算相鄰兩次刷卡數(shù)據(jù)之間的距離。假設(shè)Iyz(i-1)∈Ki，如果Di(i-1)=|Iyzi-Iyz(i-1)|＞ψ，則Iyzi∈K(i+1)；反之，Iyzi∈Ki。

Step 4 迭代操作

執(zhí)行Step 1，Step 2 和Step 3，直至所有線路所有車輛的所有刷卡數(shù)據(jù)全部完成歸類。

Step 5 站點(diǎn)匹配

首先，將第1 個(gè)刷卡數(shù)據(jù)Iyzx'與公交車到站離站時(shí)間數(shù)據(jù)T={Tyz0c,…,Tyzic,…,Tyzrc} 進(jìn)行匹配操作。其次，如果Iyzx'與Iyz(x'+1)均屬于Ki類，則Iyz(x'+1)的匹配結(jié)果與Iyzx'相同；反之，Iyz(x'+1)與公交車到站離站時(shí)間數(shù)據(jù)進(jìn)行匹配。直至所有線路所有車輛的所有刷卡數(shù)據(jù)全部完成站點(diǎn)匹配。

2.3 改進(jìn)模糊C均值聚類算法

模糊C 均值聚類算法是應(yīng)用比較廣泛且較成功的無(wú)監(jiān)督機(jī)器學(xué)習(xí)的算法，通過(guò)優(yōu)化目標(biāo)函數(shù)得到每個(gè)樣本點(diǎn)對(duì)所有類中心的隸屬度，從而決定樣本點(diǎn)的類屬，達(dá)到自動(dòng)對(duì)樣本數(shù)據(jù)進(jìn)行分類的目的。已有研究中，鮮有學(xué)者采用模糊C均值聚類算法估計(jì)研究乘客上車站點(diǎn)。因此，本文采用該方法進(jìn)行上車站點(diǎn)估計(jì)，并將計(jì)算結(jié)果與其他算法進(jìn)行對(duì)比。由于乘客上車刷卡數(shù)據(jù)是一系列的時(shí)間點(diǎn)，因此，對(duì)傳統(tǒng)的模糊C均值聚類算法進(jìn)行改變，針對(duì)兩點(diǎn)距離的計(jì)算，采用曼哈頓距離替代歐式距離。

模糊C均值聚類算法通過(guò)引入隸屬度矩陣，用于衡量當(dāng)前樣本屬于某一類別的可能性大小，并不是完全絕對(duì)屬于哪一類。當(dāng)前樣本可能屬于第1類，也可能屬于第2 類。假如樣本數(shù)據(jù)F=(f1,f2,…,fg,…,fG)被劃分為C=(c1,c2,cε,…,cρ)個(gè)類別，那么每個(gè)類別會(huì)有1 個(gè)類中心，即共C 個(gè)類中心，uεg為樣本fg屬于某一類別cε的隸屬度，U=(u1g,u2g,uεg,…,uρg)，數(shù)學(xué)模型為

利用拉格朗日乘數(shù)法對(duì)uεg和cε分別求偏導(dǎo)，即

具體運(yùn)算步驟如下。

Step 1 算法初始化。根據(jù)式(6)初始化一個(gè)隸屬度矩陣U(a)，根據(jù)U(a)計(jì)算初始聚類中心C(a)，確定模糊因子ξ，最大迭代次數(shù)和迭代停止閾值τ。

Step 2 根據(jù)U(a)和C(a)計(jì)算并更新隸屬度矩陣U(a+1)，然后，根據(jù)U(a+1)計(jì)算并更新聚類中心C(a+1)。

Step 4 站點(diǎn)匹配。首先，將第1個(gè)刷卡數(shù)據(jù)fg與公交 車到站 離站時(shí) 間數(shù)據(jù)T={Tyz0c,…,Tyzic,…,Tyzmc} 進(jìn)行匹配操作。其次，如果fg與f(g+1)均屬于cε類，則f(g+1)的匹配結(jié)果與fg相同；反之，f(g+1)與公交車到站離站時(shí)間數(shù)據(jù)進(jìn)行匹配。直至所有線路所有車輛的所有刷卡數(shù)據(jù)全部完成站點(diǎn)匹配。

2.4 熵率法

上述3 種算法均可以估計(jì)乘客上車站點(diǎn)，但是，不同的算法表現(xiàn)出不同的準(zhǔn)確性。因此，本文采用前文敘述的熵率方法進(jìn)一步確定不同算法估計(jì)乘客上車站點(diǎn)的準(zhǔn)確性。將每個(gè)乘客多天的所有出行的上車站點(diǎn)按照時(shí)間進(jìn)行排序，形成一個(gè)上車站點(diǎn)序列X={X1,X2,X3,…,Xn-2,Xn-1,Xn}，稱之為上車鏈，因此，僅需要計(jì)算上車鏈的熵率。通過(guò)比較熵率大小，便可以確定不同算法估計(jì)乘客上車站點(diǎn)準(zhǔn)確率關(guān)系。熵率方法的具體描述如下。

隨機(jī)向量或隨機(jī)變量X需要在有限集合E中取值，集合E是乘客可以選擇的上車站點(diǎn)，概率分布為P(x)=Pr{X=x},x∈E，X的熵[13]為

X={… ,X-1,X0,X1,X2,…} 是一個(gè)隨機(jī)過(guò)程，{Xn}是隨機(jī)變量的序列，對(duì)于一個(gè)連續(xù)的部分過(guò)程(可能是無(wú)限的)(Xρ,Xρ+1,…,Xη), -∞≤ρ≤η≤+∞，H=H(X)為X的熵率，即的熵隨n變化的漸近率，即

H(X1,X2,…,Xn)為隨機(jī)變量(X1,X2,…,Xn)的熵。對(duì)于平穩(wěn)的隨機(jī)過(guò)程，熵率存在，為式(9)條件熵，即

本文假設(shè)乘客長(zhǎng)期的公交出行是一個(gè)平穩(wěn)的隨機(jī)過(guò)程X。隨機(jī)變量X表示乘客在某站點(diǎn)上車，用離散概率p(x) 表示。在實(shí)際中，上述公式中的聯(lián)合概率分布和往往難以計(jì)算，通常采用估算方法進(jìn)行熵率計(jì)算，常用的熵率估算方法有Plug-in Estimator、Lempel-Ziv Estimators、Context-Tree Weighting 及Burrows-Wheeler Transform(BWT)等。

由于BWT 是目前最好的無(wú)損壓縮方法之一，且BWT能夠把有限的記憶序列轉(zhuǎn)化成分段平穩(wěn)的無(wú)記憶序列，以此過(guò)程為基礎(chǔ)估算原始序列的熵率。因此，本文選用Burrows-Wheeler Transform方法估算熵率[14]，具體計(jì)算步驟如下。

圖2 BWT例子Fig.2 Example of BWT

Step 2 將新的序列分為r段，每段長(zhǎng)度不必相同，但是分段長(zhǎng)度相同是非常有效的。

Step 3 估計(jì)每段內(nèi)的一階分布。本文用Nr(x)表示符號(hào)x在第r段中出現(xiàn)的次數(shù)，用表示符號(hào)x在第r段中的概率估計(jì)，用表示第r段的熵估計(jì)，即

Step 4 通過(guò)各段熵的均值求出隨機(jī)過(guò)程X，即乘客上車站點(diǎn)出行序列的熵率為

乘客N在3 d內(nèi)乘坐線路A的出行序列如圖3所示。圖3(a)為上車鏈，可以看出該序列有2 個(gè)未知參數(shù)X1和X2。假設(shè)以下4 種情況，X1=2，X2=3；X1=2，X2=6；X1=5，X2=3 和X1=5，X2=6。通過(guò)計(jì)算4 條上車鏈的熵率，結(jié)果如圖3(b)～(e)所示?？梢园l(fā)現(xiàn)，乘客上車鏈1 比上車鏈2、上車鏈3和上車鏈4具有更低的熵率，因此，上車鏈1表現(xiàn)出更強(qiáng)的出行規(guī)律性。上述案例可以進(jìn)一步說(shuō)明，熵率可以測(cè)度人們出行的規(guī)律性，熵率越小，出行規(guī)律性越強(qiáng)，能夠反映不同算法估計(jì)乘客上車站點(diǎn)的準(zhǔn)確率。

圖3 不同序列的熵率對(duì)比Fig.3 Comparison of entropy rates of different sequences

3 案例與結(jié)果分析

選取珠海市2021年9月6日～10日AFC和AVL系統(tǒng)中18 路公交車(6:30-21:15)的運(yùn)營(yíng)數(shù)據(jù)，統(tǒng)計(jì)該線路運(yùn)營(yíng)時(shí)間內(nèi)所有乘客的上車站點(diǎn)，線路布局如圖4 所示。經(jīng)過(guò)數(shù)據(jù)清洗后，刷卡數(shù)據(jù)共27028條。刷卡數(shù)據(jù)包括：普通卡、老人卡、學(xué)生卡、二維碼、殘疾人卡、員工卡及其他卡7 種類型。不同類型IC卡占比如圖5(a)所示，18路公交運(yùn)營(yíng)期間刷卡數(shù)據(jù)具有早晚高峰特征，每天客流變化不明顯，具有一定的規(guī)律性，如圖5(b)所示。

圖4 珠海市18路Fig.4 Line 18 in Zhuhai

圖5 18路公交不同類型IC卡占比及不同時(shí)間段的客流分布Fig.5 Proportion of different types of IC cards and passenger flow distribution in different time periods of No.18 bus

3.1 不同算法的匹配結(jié)果

采用傳統(tǒng)時(shí)間窗算法、兩階段算法、改進(jìn)K近鄰算法及改進(jìn)模糊C均值聚類算法對(duì)18路5 d的刷卡數(shù)據(jù)進(jìn)行匹配計(jì)算，匹配結(jié)果如圖6所示，圖中，P0為傳統(tǒng)的時(shí)間窗算法，P1為第1階段算法，P1+2為兩階段算法，P3為改進(jìn)K近鄰算法，P4為改進(jìn)模糊C均值聚類算法；虛線為5 d內(nèi)P0與P1的平均匹配率。

圖6 乘客上車站點(diǎn)的匹配率Fig.6 Matching rate of passengers'boarding stops

由圖6 可知，各種算法的匹配結(jié)果為P0＜P1＜P1+2=P3=P4。18 路刷卡數(shù)據(jù)匹配平均增長(zhǎng)率為P1，比P0增長(zhǎng)31.3%，P1+2、P3、P4較P0高36.3%，P1+2、P3、P4較P1增加了5.0%。發(fā)現(xiàn)P1+2、P3、P4這3種算法均可以實(shí)現(xiàn)所有刷卡數(shù)據(jù)的完全匹配。

3.2 熵率計(jì)算結(jié)果

雖然3 種算法均可以實(shí)現(xiàn)上車站點(diǎn)的完全匹配，但無(wú)法判斷各種算法的匹配準(zhǔn)確率。因此，可以通過(guò)熵率進(jìn)行判斷。本文采用熵率方法，結(jié)合3個(gè)維度的樣本數(shù)據(jù)，深入探討各種算法估計(jì)乘客上車站點(diǎn)的準(zhǔn)確率。

(1)維度I

首先，根據(jù)IC 卡號(hào)，統(tǒng)計(jì)5 d 內(nèi)的所有刷卡數(shù)據(jù)；其次，將統(tǒng)計(jì)后的刷卡總數(shù)按降序排序；然后，選擇累計(jì)刷卡次數(shù)大于5次的前10%的IC卡號(hào)；最后，基于篩選后的IC卡號(hào)，采用3種算法分別計(jì)算，獲取每個(gè)IC 卡號(hào)的上車鏈，并以此為基礎(chǔ)計(jì)算各上車鏈的熵率。3種算法對(duì)維度I數(shù)據(jù)的熵率計(jì)算結(jié)果分布如圖7所示，圖中，虛線表示平均熵率。

圖7 3種算法在維度I的熵率分布Fig.7 Entropy rate distribution of three algorithms in dimension I

由圖7 可知，3 種算法的平均熵率分別為H(1+2)＜H3＜H4。如前文所述，熵率越小，乘客出行的規(guī)律性越強(qiáng)。因此，從平均熵率來(lái)看，3種算法匹配乘客上車站點(diǎn)的準(zhǔn)確率關(guān)系為P1+2＞P3＞P4。而P1+2和P3的平均熵率差異不大，匹配精度比較接近。

(2)維度II

首先，經(jīng)過(guò)傳統(tǒng)算法P0計(jì)算后，在所有匹配失敗的刷卡數(shù)據(jù)中，選擇累計(jì)刷卡次數(shù)大于5次的IC卡號(hào)；然后，根據(jù)篩選后的IC卡號(hào)，采用3種算法獲取每個(gè)IC 卡號(hào)的上車鏈用于熵率計(jì)算。在維度II的數(shù)據(jù)中，3 種算法的熵率計(jì)算結(jié)果分布如圖8 所示，圖中，虛線表示平均熵率。

圖8 3種算法在維度II的熵率分布Fig.8 Entropy rate distribution of three algorithms in dimension II

由圖8 可知，維度II 的平均熵率結(jié)果與維度I相似，即H(1+2)＜H3＜H4，P1+2＞P3＞P4。

(3)維度III

首先，根據(jù)IC卡類型，對(duì)所有刷卡數(shù)據(jù)按照IC卡類型進(jìn)行分類，選擇每種類型中5 d 內(nèi)累計(jì)刷卡次數(shù)大于5次的IC卡號(hào)；然后，根據(jù)篩選后的IC卡號(hào)，采用3種算法獲取每種類型中每個(gè)IC卡號(hào)的上車鏈用于計(jì)算熵率。在維度III數(shù)據(jù)中，3種算法的熵率計(jì)算結(jié)果分布如圖9 所示，圖中，虛線表示平均熵率。

由圖9 可知，除員工卡外，其他類型IC 卡的平均熵率分布結(jié)果與維度I和維度II相同。對(duì)于員工卡而言，熵率結(jié)果為H(1+2)=H3＜H4。因此，從熵率的平均值來(lái)看，3 種算法匹配乘客上車站點(diǎn)的準(zhǔn)確率關(guān)系為P1+2=P3＞P4。由于P1+2和P3的平均熵率相等，因此，匹配精度相同。

為進(jìn)一步驗(yàn)證上述某種算法更加適合于公交企業(yè)的實(shí)際應(yīng)用，進(jìn)行如下操作。首先，在數(shù)據(jù)庫(kù)中，選擇3個(gè)IC卡卡號(hào)，對(duì)應(yīng)3名乘客；其次，采用3種算法統(tǒng)計(jì)3名乘客5 d的上車站點(diǎn)，形成9條上車鏈；最后，分別計(jì)算所有上車鏈的熵率，如圖10所示。

圖10 3名乘客上車鏈的熵率Fig.10 Entropy rate of three passengers'boarding chain

由圖10可知，就乘客1而言，3種算法對(duì)乘客1形成了相同的上車鏈，且熵率相同，因此，選取其中一種算法產(chǎn)生的上車鏈作為乘客1 的最終上車站點(diǎn)估計(jì)結(jié)果。就乘客2而言，P1+2和P3形成的上車鏈相同，與 P4不同，熵率計(jì)算結(jié)果為H(1+2)=H3＜H4，因此，選擇P1+2或P3產(chǎn)生的上車鏈作為乘客2的最終上車站點(diǎn)估計(jì)結(jié)果。就乘客3而言，P1+2形成的上車鏈與P3、P4不同，熵率計(jì)算結(jié)果為H(1+2)＜H3=H4，因此，選擇P1+2產(chǎn)生的上車鏈作為乘客3的最終上車站點(diǎn)估計(jì)結(jié)果。綜上，并非某種算法完全優(yōu)于或劣于其他算法，前文敘述的結(jié)果是基于3 個(gè)維度樣本數(shù)據(jù)的平均熵率而言。因此，公交企業(yè)在實(shí)際應(yīng)用的過(guò)程中，應(yīng)該選擇3 種算法中的最小熵率作為乘客上車站點(diǎn)估計(jì)的最終結(jié)果。

4 結(jié)論

(1) 熵率方法不僅可以反映乘客出行的規(guī)律性，還可以確定不同算法估計(jì)乘客上車站點(diǎn)的準(zhǔn)確率。是一種估計(jì)乘客上車站點(diǎn)準(zhǔn)確率的新方法。熵率越小，乘客上車站點(diǎn)估計(jì)的準(zhǔn)確率越高。

(2)通過(guò)對(duì)比不同算法獲取上車鏈的平均熵率發(fā)現(xiàn)，兩階段算法的準(zhǔn)確率高于改進(jìn)K 近鄰算法，改進(jìn)K 近鄰算法的準(zhǔn)確率高于改進(jìn)模糊C 均值聚類算法。兩階段算法與改進(jìn)K 近鄰算法的準(zhǔn)確率差異不大。

(3)公交企業(yè)在沒(méi)有更好的方法可供選擇時(shí)，可以采用熵率方法確定乘客上車站點(diǎn)估計(jì)的準(zhǔn)確率，在具體應(yīng)用時(shí)，應(yīng)選擇熵率最小的估計(jì)算法確定乘客的上車站點(diǎn)。

(4)在兩階段算法中，基于可變閾值設(shè)計(jì)了時(shí)間窗算法，克服了傳統(tǒng)時(shí)間窗算法的不足。同時(shí)，兩階段、改進(jìn)K近鄰算法和改進(jìn)模糊C 均值聚類這3種算法均可估計(jì)所有乘客的上車站點(diǎn)，與傳統(tǒng)時(shí)間窗算法相比，進(jìn)一步提升了乘客上車站點(diǎn)估計(jì)的匹配率。