【面向公共交通的路徑匹配與軌跡重建分析案例13000字】

面向公共交通的路徑匹配與軌跡重建分析案例目錄TOC\o"1-3"\h\u30366面向公共交通的路徑匹配與軌跡重建分析案例 1125911.1路徑匹配 169271.1.1公交、地鐵路線匹配 1331.1.2出租車地圖匹配 6231781.2行程劃分 1065001.2.1軌跡時(shí)間-里程表達(dá) 10291261.2.2核密度計(jì)算 12277181.2.3駐留點(diǎn)檢測(cè) 13272651.2.4軌跡段語(yǔ)義化 14318811.3軌跡重建 15241811.3.1啟發(fā)式優(yōu)化問(wèn)題 15302331.3.2搜索策略選擇 1698921.3.3軌跡點(diǎn)位置優(yōu)化模型 17244601.3.4數(shù)據(jù)模擬與模型精度評(píng)定 186151.3.5軌跡重建結(jié)果分析 20路徑匹配公交、地鐵路線匹配基站扇區(qū)映射方法對(duì)軌跡和公共交通路線進(jìn)行匹配，首先要對(duì)軌跡點(diǎn)和路線點(diǎn)的相似性進(jìn)行度量。在本研究中，為了準(zhǔn)確反映蜂窩網(wǎng)絡(luò)中的移動(dòng)臺(tái)（即持有手機(jī)設(shè)備）在對(duì)應(yīng)基站領(lǐng)域內(nèi)可能位置以及位于這一位置的概率，首先根據(jù)天線朝向確定各基站對(duì)應(yīng)的信號(hào)覆蓋范圍，再根據(jù)二維正態(tài)分布假設(shè)計(jì)算覆蓋范圍內(nèi)不同位置的概率，作為軌跡點(diǎn)相似性的度量。手機(jī)信令軌跡中每個(gè)記錄點(diǎn)以基站位置來(lái)近似代替終端設(shè)備的實(shí)際位置，這意味著手機(jī)設(shè)備只是位于相應(yīng)手機(jī)基站的地理覆蓋范圍內(nèi)。在實(shí)際情況中，一個(gè)基站可能服務(wù)多個(gè)區(qū)域，一個(gè)區(qū)域也可能被多個(gè)基站服務(wù)，不同的基站的覆蓋范圍有所重疊，根據(jù)不同物理?xiàng)l件和環(huán)境有所變化。目前的研究通常假設(shè)基站的服務(wù)范圍為固定的區(qū)域，如六邊形假設(shè)、泰森多邊形假設(shè)、圓形假設(shè)和扇形假設(shè)ADDINCNKISM.Ref.{CB26D4A659CF4f32BAD52C382CEE9267}(宋璐，2015)，如圖4.1。考慮到手機(jī)基站數(shù)據(jù)中包含天線的航向角，在本文中采用扇形假設(shè)。通常情況下，每個(gè)基站包含3根朝向不同的發(fā)射天線，覆蓋以基站為中心的不同方向范圍，基站天線的朝向字段可以從基站工參表中直接獲取。將基站朝向?yàn)橹行妮S線，向兩側(cè)各延伸60度，以給定半徑r確定天線對(duì)應(yīng)的基站扇形區(qū)域，其中r取一般城區(qū)內(nèi)的基站覆蓋半徑500m。1）六邊形假設(shè)2）泰森多邊形假設(shè)3）圓形假設(shè)4）扇形假設(shè)圖4.1不同基站覆蓋范圍假設(shè)Figure4.1DifferentCoverageofbasestationshypnosis扇區(qū)內(nèi)匹配度計(jì)算基站覆蓋范圍能夠確定手機(jī)用戶可能出現(xiàn)的位置，但考慮到信號(hào)傳輸和負(fù)載平衡，手機(jī)有更大的概率連接與之空間上更接近的基站；同樣，對(duì)于每一個(gè)基站來(lái)說(shuō)，距離其所在位置越近越有可能是與之交互手機(jī)的實(shí)際位置。對(duì)手機(jī)信令軌跡中的每一個(gè)軌跡點(diǎn)，其基站位置可視為含有系統(tǒng)誤差的設(shè)備實(shí)際位置觀測(cè)值，這一觀測(cè)值在真實(shí)位置附近的散布滿足二維空間的正態(tài)分布。基站對(duì)應(yīng)的平面位置(X,Y)是一個(gè)二維隨機(jī)變量，可以認(rèn)為它服從一個(gè)二元正態(tài)分布，其中Xp其中，x0,y0為基站位置，p(圖4.2基站鄰域內(nèi)的點(diǎn)匹配度變化Figure4.2VariationofmatchingdegreeintheneighborhoodofBTS按照定義，(X,Y)落在以sim其中，σ為點(diǎn)分布的標(biāo)準(zhǔn)差。類似地，我們給出點(diǎn)匹配度的定義：sim其中p0,p1分別屬于道路位置點(diǎn)集合軌跡時(shí)空點(diǎn)集，d(p0,p1)表示兩點(diǎn)的歐幾里得距離。sim圖4.3扇區(qū)內(nèi)匹配度隨距離的衰減Figure4.3TheattenuationofmatchingdegreewithdistanceinBTSsector周期最長(zhǎng)公共子序列傳統(tǒng)的最長(zhǎng)公共子序列（longestcommonsubsequence，LCSS）是針對(duì)字符串序列匹配的方法，是一個(gè)在一個(gè)序列集合中（通常為兩個(gè)序列）用來(lái)查找所有序列中最長(zhǎng)子序列的問(wèn)題。一個(gè)數(shù)列，如果分別是兩個(gè)或多個(gè)已知數(shù)列的子序列，且是所有符合此條件序列中最長(zhǎng)的，則稱為已知序列的最長(zhǎng)公共子序列。給定一條手機(jī)信令軌跡序列T和公交路線序列RT=R=其中,tni,ptni為T(mén)在時(shí)刻tni的第i個(gè)軌跡點(diǎn)ptni,prsimPntSectorptni在確定軌跡點(diǎn)匹配規(guī)則后，定義一個(gè)遞歸函數(shù)LCSSTn,Rm來(lái)求解兩條軌跡LCSS從起始時(shí)刻i=1,j=1到終止時(shí)刻i=n,j=m逐個(gè)計(jì)算LCSST動(dòng)態(tài)規(guī)劃求解方法求解LCSS方式包括窮舉法和動(dòng)態(tài)規(guī)劃。對(duì)于長(zhǎng)度分別為n和m和手機(jī)信令軌跡序列T和公交路線序列R來(lái)說(shuō)窮舉法就是針對(duì)T的每一個(gè)子序列T'，檢測(cè)它是否能和R的某條子序列R'相匹配從而判斷T',R'是否是T和R的公共子序列。當(dāng)窮舉完T和R動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。在這類問(wèn)題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，希望找到具有最優(yōu)值的解。動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。表4.1周期最長(zhǎng)公共子序列匹配算法流程Table4.1Crossvalidationresultsofclassificationmodel算法周期最長(zhǎng)公共子序列匹配輸入:手機(jī)信令手機(jī)信令軌跡T和公交路線序列R輸出:最長(zhǎng)公共子序列OPA1:row=LenT2:foreachentryD[i,j]inDdo3:D4:foriin1torowdo5:ifj+ext>colthen6:col+=Len7:forjin1tocoldo8:AccSim=D9:D10:OPA=?,i=Len11:whilei>0andj>0do12:ifDi,j=D13:Insert(T.Pnti,R.Pntj%LenR14:elseifDi,j=D15:Insert(T.Pnti?1,"?")to16:elseifDi,j=D17:Insert("?",R.Pnt(j?1)%LenR)18:whilej>0do19:Insert("?",R.Pnt(j?1)%LenR)20:whilei>0do21:Insert(T.Pnti?1,"?")to出租車地圖匹配與公交、地鐵等沿固定路線運(yùn)動(dòng)的公共交通模式不同，出租車輛的活動(dòng)范圍在整個(gè)城市路網(wǎng)區(qū)域，而非局限于特定路線上。因此，用于公交、地鐵模式匹配的序列方法并不直接適用于出租車軌跡匹配。因此，本節(jié)針對(duì)手機(jī)數(shù)據(jù)的低時(shí)空精度特點(diǎn)，以及城市復(fù)雜路網(wǎng)匹配準(zhǔn)確率較低的問(wèn)題，采用隱馬爾科夫模型（HiddenMarkovModel,HMM）對(duì)出租車模式的個(gè)體軌跡進(jìn)行地圖匹配。HMM模型描述了在已知模型參數(shù)的情況下，尋找產(chǎn)生某個(gè)觀測(cè)序列的最優(yōu)隱藏狀態(tài)序列的過(guò)程。結(jié)合軌跡數(shù)據(jù)而言，觀測(cè)序列即為個(gè)體對(duì)象的移動(dòng)軌跡，最優(yōu)隱藏狀態(tài)序列即為個(gè)體對(duì)象真實(shí)的移動(dòng)路徑。地圖匹配的主要過(guò)程包括以下步驟：確定HMM模型隱藏狀態(tài)空間，得到候選路段集；利用軌跡點(diǎn)和路段的信息及空間關(guān)系，計(jì)算發(fā)射概率和轉(zhuǎn)移概率等HMM模型參數(shù)；利用動(dòng)態(tài)規(guī)劃算法解算HMM模型，將移動(dòng)軌跡匹配到路網(wǎng)，得到用戶在城市路網(wǎng)中的移動(dòng)路徑。搜索空間選擇路徑匹配實(shí)質(zhì)是從研究區(qū)域內(nèi)路網(wǎng)道路線的隱藏狀態(tài)空間查找具有拓?fù)渎?lián)通性的最優(yōu)道路序列。但考慮到城市路網(wǎng)復(fù)雜的復(fù)雜性給模型時(shí)間復(fù)雜度的影響，需要先對(duì)參與匹配的道路集進(jìn)行初篩選。一般采用設(shè)置搜索區(qū)域的方式確定初選路段，搜索區(qū)域主要用于解決在智能交通領(lǐng)域任意兩個(gè)節(jié)點(diǎn)間最短路徑算法過(guò)程中算法復(fù)雜度較高而設(shè)計(jì)，選擇正確的搜索區(qū)域有助于減少算法計(jì)算量，同時(shí)提高算法的匹配效率。本文中選擇橢圓限制搜索區(qū)域作為搜索區(qū)域。橢圓限制搜索區(qū)域能夠?qū)⑺阉鞴?jié)點(diǎn)限制在一定范圍內(nèi)，大幅度減少地圖匹配的搜索規(guī)模，將相鄰的手機(jī)信令軌跡點(diǎn)pntsx[其中，a和b分別為橢圓中心位置的x和y坐標(biāo)，a=xs+xd2，b=ys+y圖4.4中為相鄰兩手機(jī)信令軌跡點(diǎn)構(gòu)造的橢圓限制搜索區(qū)域。兩軌跡點(diǎn)分別視為地圖匹配的源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，可以看出橢圓限制搜索區(qū)域范圍覆蓋了從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)潛在的最優(yōu)路徑；同時(shí)，橢圓搜索區(qū)域內(nèi)網(wǎng)絡(luò)節(jié)點(diǎn)與邊的數(shù)量相較于整個(gè)道路網(wǎng)絡(luò)僅占很小的部分，能夠有效壓縮地圖匹配最優(yōu)路徑的搜索時(shí)間。圖4.4基于橢圓搜索空間的備選路徑選擇Figure4.4Candidaterouteselectionbasedonellipsesearchspace路段發(fā)射概率發(fā)射概率Ppnti?因此，我們采用中的相似度算子simpnt0,pnt1來(lái)度量基站位置位于pnt0的軌跡點(diǎn)，其實(shí)際位置落在候選路徑上pnt1P其中，bts為手機(jī)基站的位置，并有sim式中，Ppnti?i的值越高，則軌跡點(diǎn)圖4.5基站扇區(qū)與路段發(fā)射概率Figure4.5BTSsectorandroutetransmissionprobability如圖4.5中所示，當(dāng)基站的覆蓋扇區(qū)與路網(wǎng)中的候選路段存在交集時(shí)，該候選路段的發(fā)射概率為simpnt0,pnt1沿候選路段路段轉(zhuǎn)移概率狀態(tài)轉(zhuǎn)移概率表示前一個(gè)手機(jī)信令軌跡點(diǎn)的候選點(diǎn)轉(zhuǎn)移至下一個(gè)手機(jī)信令軌跡點(diǎn)候選點(diǎn)的可能性，記為pcp其中，對(duì)參數(shù)α和Dα=DXii+1表示兩個(gè)手機(jī)信令軌跡點(diǎn)pnti動(dòng)態(tài)規(guī)劃路徑匹配如果最優(yōu)路徑在t時(shí)刻經(jīng)過(guò)結(jié)點(diǎn)?????，則從結(jié)點(diǎn)?????到終點(diǎn)?????的后半部分路徑必須相對(duì)從其它結(jié)點(diǎn)到?????的所有路徑為最優(yōu)路徑。本文使用動(dòng)態(tài)規(guī)劃方法對(duì)馬爾科夫模型進(jìn)行解碼(Bloitetal.2008)，在每一步的所有選擇都保存了前續(xù)所有步驟到當(dāng)前步驟當(dāng)前選擇的最小總代價(jià)（或者最大價(jià)值）以及當(dāng)前代價(jià)的情況下前繼步驟的選擇。依次計(jì)算完所有步驟后，通過(guò)回溯的方法找到最優(yōu)選擇路徑。給定落入橢圓搜索空間的備選路段集?j={rt1,…引入矩陣CM×N，其元素為Cin表示第n個(gè)軌跡點(diǎn)在待選路段?i對(duì)于首個(gè)軌跡點(diǎn)pnt1C當(dāng)2≤n≤N時(shí)：CD遞推結(jié)束后，確定最后一個(gè)軌跡點(diǎn)的最優(yōu)匹配路段：x從該最優(yōu)匹配開(kāi)始，依次從DM×N中回溯出前一個(gè)軌跡點(diǎn)的最優(yōu)匹配路段xN?1直至首個(gè)最優(yōu)匹配路段x1行程劃分軌跡行程段劃分（TrajectorySegmentation）是個(gè)體移動(dòng)行為研究的關(guān)鍵問(wèn)題，其主要目的是把原始軌跡分割成多條子軌跡，使得子軌跡在其內(nèi)部保持軌跡特征和語(yǔ)義上的一致性。針對(duì)使用Cell-ID定位的手機(jī)信令數(shù)據(jù)，大多數(shù)已有研究通過(guò)對(duì)數(shù)據(jù)中高頻重復(fù)的基站和持續(xù)長(zhǎng)時(shí)間的停留進(jìn)行檢測(cè)并設(shè)定閾值來(lái)劃分軌跡的行程段，此外部分研究采用空間聚類的方式來(lái)探測(cè)行程的劃分點(diǎn)。以上方法關(guān)注與軌跡點(diǎn)的聚集模式，但沒(méi)有對(duì)劃分行程段的“停留點(diǎn)”賦予特定的語(yǔ)義信息。面向上一章從海量手機(jī)信令軌跡數(shù)據(jù)集中提取的司乘人員手機(jī)信令軌跡，本章提出了一種基于時(shí)空核密度估計(jì)的軌跡行程分段方法。首先將二維平面坐標(biāo)表達(dá)的手機(jī)信令軌跡映射到時(shí)間-里程系中，再進(jìn)行非參數(shù)核密度估計(jì)檢測(cè)密度曲線波峰波谷位置的停留點(diǎn)，最后結(jié)合公共交通站點(diǎn)數(shù)據(jù)和基于規(guī)則對(duì)停留點(diǎn)進(jìn)行語(yǔ)義判別，并進(jìn)行手機(jī)信令軌跡的行程段劃分。軌跡時(shí)間-里程表達(dá)時(shí)空軌跡數(shù)據(jù)一般以“時(shí)間-坐標(biāo)”的形式進(jìn)行存儲(chǔ)與表達(dá)，常以時(shí)空棱柱體的形式來(lái)體現(xiàn)個(gè)體位置隨時(shí)間的變化，并反映起點(diǎn)、終點(diǎn)、出發(fā)時(shí)刻、結(jié)束時(shí)刻、運(yùn)動(dòng)速度和活動(dòng)范圍等個(gè)體運(yùn)動(dòng)特征。但是移動(dòng)軌跡的高維組織結(jié)構(gòu)不利于提取移動(dòng)對(duì)象的移動(dòng)行為統(tǒng)計(jì)特征，尤其是在軌跡大數(shù)據(jù)的范疇下，更是會(huì)降低數(shù)據(jù)分析和處理的效率；同時(shí)手機(jī)信令軌跡本身的空間不確定性也會(huì)將誤差傳遞到后續(xù)的時(shí)空分析中。因此，本研究針對(duì)司乘人員軌跡數(shù)據(jù)，采用高效的移動(dòng)對(duì)象軌跡表示方式，即時(shí)間-里程表達(dá)。移動(dòng)軌跡的時(shí)間-里程表達(dá)，是對(duì)個(gè)體對(duì)象相對(duì)于給定參考點(diǎn)沿公交路線的向前運(yùn)動(dòng)的表示。首先設(shè)定軌跡的起始時(shí)刻（首條記錄時(shí)間戳）作為時(shí)間參考點(diǎn)t0，設(shè)定公交路線的始發(fā)站坐標(biāo)作為空間參考點(diǎn)x0,d式中，di是軌跡點(diǎn)與參考點(diǎn)之間的距離，θi是軌跡點(diǎn)距正北方向的旋轉(zhuǎn)角度（按順時(shí)針?lè)较颍?Trj基于移動(dòng)軌跡的極坐標(biāo)表示方式，可以探索用戶和參考點(diǎn)之間的距離/時(shí)間關(guān)聯(lián)性。提取軌跡序列中的距離和時(shí)間值并繪制散點(diǎn)圖（圖4.6），圖中，靜態(tài)點(diǎn)分布會(huì)呈現(xiàn)出與時(shí)間軸近似平行的趨勢(shì)，表示用戶長(zhǎng)時(shí)間內(nèi)位置未發(fā)生明顯改變；動(dòng)態(tài)點(diǎn)分布則呈現(xiàn)與距離軸近似平行的趨勢(shì)，表示軌跡點(diǎn)攜帶有較大的速度矢量。單日內(nèi)的軌跡點(diǎn)表現(xiàn)出重復(fù)出現(xiàn)的固定模式，體現(xiàn)了公交車輛沿固定線路運(yùn)動(dòng)的周期性。圖中呈現(xiàn)出兩處顯著密集分布的靜態(tài)軌跡點(diǎn)，對(duì)應(yīng)著車輛在始發(fā)站和終點(diǎn)站位置發(fā)生的停留。因此，基于時(shí)間-里程變化信息，有助于更為清晰的提取公交車輛的不同的運(yùn)動(dòng)狀態(tài)（靜態(tài)模式、動(dòng)態(tài)模式）、停留時(shí)長(zhǎng)和狀態(tài)變化時(shí)間點(diǎn)等時(shí)空運(yùn)動(dòng)特征。圖4.6移動(dòng)軌跡的時(shí)間-里程表達(dá)Figure4.6Individualtrajectoryrepresentedintime-distanceapproach核密度計(jì)算在空間分析中，核密度方法可以將樣本點(diǎn)數(shù)據(jù)轉(zhuǎn)換成連續(xù)平滑的面，已經(jīng)被廣泛地應(yīng)用在交通研究和人類移動(dòng)行為分析(Huetal.2018,Lietal.2020)中。傳統(tǒng)核密度的計(jì)算公式為：f式中h為搜索帶寬；n為與當(dāng)前估算手機(jī)信令軌跡點(diǎn)的距離小于或等于帶寬h的軌跡點(diǎn)數(shù)目；k·為采用的核函數(shù)；xi傳統(tǒng)核密度方法側(cè)重于描述要素或事件在空間上的分布，針對(duì)司乘人員軌跡的駐留點(diǎn)探測(cè)問(wèn)題，應(yīng)考慮手機(jī)信令與基站交互事件在時(shí)間維度上的異質(zhì)性。因此，在空間核密度估計(jì)的基礎(chǔ)上，考慮時(shí)空要素在時(shí)間維度上的集聚特性，衍生出時(shí)空核密度估計(jì)方法。借鑒空間核密度估計(jì)思想，將空間距離廣義擴(kuò)展成為“時(shí)空距離”，“時(shí)空距離”越近的事件對(duì)密度值的貢獻(xiàn)越大，“時(shí)空距離”越遠(yuǎn)的事件對(duì)密度值的貢獻(xiàn)越小。根據(jù)定義，累積出現(xiàn)概率表示為移動(dòng)對(duì)象在某個(gè)位置上產(chǎn)生的所有軌跡點(diǎn)的停留時(shí)間的累積概率。參考(Qietal.2006)使用的核函數(shù)選擇，加入時(shí)間變量，將每個(gè)時(shí)空單元中重點(diǎn)交通違法事件的密度估計(jì)值ff核函數(shù)定義為：KK其中，Ks·和Kt·分別是空間維和時(shí)間維的二維和一維高斯核核函數(shù)，n為手機(jī)信令軌跡中軌跡點(diǎn)數(shù)量，h1駐留點(diǎn)檢測(cè)通過(guò)對(duì)軌跡點(diǎn)進(jìn)行非參數(shù)核密度估計(jì)獲取到的核密度曲線，反映了在路線的不同位置軌跡點(diǎn)的聚集程度。圖4.7中展示了對(duì)公交路線307路的某條手機(jī)信令軌跡的核密度曲線，曲線中表現(xiàn)出兩個(gè)主要的波峰和一些局部的變化。根據(jù)軌跡點(diǎn)的核密度定義，波峰位置對(duì)應(yīng)著軌跡中發(fā)生停留的位置，需要給出定量化的標(biāo)準(zhǔn)對(duì)駐留點(diǎn)進(jìn)行識(shí)別。圖4.7公交司乘人員軌跡核密度曲線Figure4.7Trajectorykerneldensitycurveofbus-modestaff以往研究常采用固定的經(jīng)驗(yàn)閾值來(lái)對(duì)軌跡的停留點(diǎn)進(jìn)行判別，但由于公交路線往往跨越不同的城市區(qū)域，沿線的基站分布并不完全均勻的，單一的閾值無(wú)法準(zhǔn)確地識(shí)別停留點(diǎn)。參考圖4.8中的核密度曲線采用過(guò)大的閾值可能漏掉部分停留點(diǎn)，而過(guò)小的閾值會(huì)將軌跡中低速位置誤識(shí)別為停留。因此，本文采用滑動(dòng)窗口搜索范圍內(nèi)的局部極值點(diǎn)避免單一閾值對(duì)停留點(diǎn)的誤分。給定窗口半徑r，在[di圖4.8核密度曲線窗口極值點(diǎn)查找Figure4.8Searchingforextremuminkerneldensitycurvewindow軌跡段語(yǔ)義化通過(guò)查找核密度曲線的極值點(diǎn)檢測(cè)軌跡的停留點(diǎn)，這些停留點(diǎn)將整條手機(jī)信令軌跡分割多個(gè)行程段和停留段。此處行程段指的是公交車輛從始發(fā)站出發(fā)沿路線行，依次途徑各公交站點(diǎn)，直至駛至終點(diǎn)站完成一次單程班次的過(guò)程；而停留段則是包括首班未發(fā)車、末班已結(jié)束、行駛過(guò)程中的臨時(shí)停車和班次之間輪換休息等各類停留，表4.2給出了軌跡段的不同語(yǔ)義類型及其判別條件。表4.2軌跡段語(yǔ)義類型及判別條件Thesemantictypesoftrajectorysegmentsanddistinguishingrules運(yùn)動(dòng)狀態(tài)語(yǔ)義類別判別條件行程段正常行駛在LCSS的首末匹配之間，且未中途發(fā)生停留停留段首班未發(fā)車在LCSS的首次匹配之前的時(shí)間段末班已結(jié)束在LCSS的末次匹配之后的時(shí)間段班次間短暫休息在LCSS的首末匹配之間，位置在始發(fā)站或終點(diǎn)站附近，且時(shí)間小于等于30min班次間長(zhǎng)時(shí)休息在LCSS的首末匹配之間，位置在始發(fā)站或終點(diǎn)站附近，且時(shí)間大于30min途徑站點(diǎn)停車在LCSS的首末匹配之間，位置在途徑站點(diǎn)附近途中臨時(shí)停車在LCSS的首末匹配之間，位于路線上其它位置如圖4.9所示的司乘人員手機(jī)信令軌跡表現(xiàn)出典型的行程段-停留段分布模式。核密度函數(shù)存在兩個(gè)波峰Peak1圖4.9典型司乘人員行程段劃分Figure4.9Tripsegmentdivisionoftypicalbus-modestaff而圖4.10則展示了情況更加復(fù)雜的行程段-停留段分布模式。通過(guò)滑動(dòng)窗口的極大值檢測(cè)到核密度曲線的4個(gè)波峰，對(duì)應(yīng)個(gè)體手機(jī)信令軌跡的4處主要停留位置，共劃分出17條自軌跡段，其中包括9條停留段。結(jié)合LCSS匹配結(jié)果和停留點(diǎn)的空間位置，根據(jù)表4.2的規(guī)則確定，停留段①屬于首班未發(fā)車，停留段⑨屬于末班車已結(jié)束，停留段③⑤屬于途徑站點(diǎn)停車，而停留段②④⑥⑦⑧均屬于短時(shí)間的班次間小憩。圖4.10出現(xiàn)多個(gè)核密度峰時(shí)司乘人員行程段劃分Figure4.10TripsegmentdivisionwithmultipleKDEpeak軌跡重建啟發(fā)式優(yōu)化問(wèn)題啟發(fā)式算法是指在可接受的計(jì)算時(shí)間、占用空間等開(kāi)銷的前提下給出待解決的組合優(yōu)化問(wèn)題的一個(gè)可行解。由于解決復(fù)雜的非線性問(wèn)題的能力以及其在解的質(zhì)量和計(jì)算效率之間取得了較好的平衡，啟發(fā)式算法自提出以來(lái)就成為解決各類組合優(yōu)化問(wèn)題的有效方法之一。啟發(fā)式算法的基本思想是：給定一個(gè)或多個(gè)目標(biāo)函數(shù)，從初始解出發(fā)，通過(guò)某種“搜索策略”在搜索空間中尋找一組滿足約束的解使得目標(biāo)函數(shù)取得最值。這里的“搜索策略”包括局部搜索過(guò)程和學(xué)習(xí)過(guò)程，以及引入避免搜索陷入局部搜索區(qū)域的機(jī)制等。在以往研究中，啟發(fā)式算法在交通領(lǐng)域內(nèi)的路徑選取、資源配置以及軌跡匹配聚類等優(yōu)化問(wèn)題都有著廣泛的應(yīng)用(Levinetal.2017,Oztopetal.2017,Perez-Rodriguezetal.2019)，這些帶有約束的優(yōu)化問(wèn)題可表示如下：minimize

f(x)subjectg

式中fx:Rn→R是目標(biāo)函數(shù)，gix為不等式約束，hix為等式約束，優(yōu)化的目標(biāo)是尋找使得fx最小的搜索策略選擇面向不同類型的優(yōu)化問(wèn)題，啟發(fā)式算法有著不同的求解思路以及最優(yōu)解搜索策略。不同的決策變量、約束條件和目標(biāo)函數(shù)，將優(yōu)化問(wèn)題分為不同類別，各類具體算法只能適應(yīng)于對(duì)應(yīng)類別的優(yōu)化問(wèn)題。根據(jù)決策變量來(lái)劃分，可分為連續(xù)、整數(shù)或混合整數(shù)類型的優(yōu)化問(wèn)題；根據(jù)約束條件，可分為帶約束的優(yōu)化問(wèn)題和無(wú)約束優(yōu)化問(wèn)題；而根據(jù)目標(biāo)函數(shù)可分為單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化。本研究中對(duì)軌跡點(diǎn)位置的優(yōu)化應(yīng)屬于帶約束的連續(xù)型單目標(biāo)優(yōu)化問(wèn)題，因此，在實(shí)驗(yàn)中選取四類滿足對(duì)本優(yōu)化問(wèn)題適用性的啟發(fā)式搜索算法策略（在表4.3中列出）對(duì)軌跡點(diǎn)位置進(jìn)行優(yōu)化重建，并在4.3.5中的重建結(jié)果分析中對(duì)比了這幾類優(yōu)化策略的效果。表4.3適用于軌跡點(diǎn)位置優(yōu)化的啟發(fā)式搜索策略啟發(fā)式搜索策略實(shí)現(xiàn)模塊適用問(wèn)題類型指南針?biāo)阉?CS)PyGMO.algorithm.cs連續(xù)-帶約束-單目標(biāo)粒子群算法(PSO)PyGMO.algorithm.pso_gen連續(xù)-帶約束-單目標(biāo)模擬蜂群算法(ABC)\o"PyGMO.algorithm.bee_colony"PyGMO.algorithm.bee_colony連續(xù)-帶約束-單目標(biāo)增廣拉格朗日算法(AL)PyGMO.algorithm.nlopt_auglag連續(xù)-帶約束-單目標(biāo)軌跡點(diǎn)位置優(yōu)化模型在本研究中對(duì)于不同時(shí)刻公交-地鐵模式軌跡點(diǎn)位置的估算問(wèn)題，本身是一類高維非線性的問(wèn)題，考慮采用啟發(fā)式優(yōu)化來(lái)進(jìn)行求解。如圖4.11中所示，經(jīng)過(guò)行程劃分的某Cell-ID子軌跡段包含多個(gè)與路線匹配上的“錨點(diǎn)”基站，可以知道手機(jī)在與基站發(fā)生交互產(chǎn)生記錄的時(shí)刻（即數(shù)據(jù)中時(shí)間戳記錄的時(shí)刻），車輛位于對(duì)應(yīng)的基站扇區(qū)內(nèi)，扇區(qū)和公交路線的交集為公交車輛可能出現(xiàn)的位置，確定了優(yōu)化模型的搜索空間。圖4.11 路徑沿線基站覆蓋范圍與優(yōu)化模型調(diào)整Figure4.11DiagramofBTScoverageandLCSSoffset對(duì)優(yōu)化模型目標(biāo)函數(shù)的確定，需要對(duì)公交車輛本身的運(yùn)動(dòng)特性展開(kāi)分析。考慮到在沒(méi)有遇到路口、車站等無(wú)阻礙通行的路段時(shí)，公交車輛出于滿足固定車輛排班時(shí)刻表的需求，在路線上是以接近勻速的狀態(tài)行駛的，換言之車輛在公交路線各路段上的平均速度波動(dòng)很小；而在遭遇路口和需要停靠的公交站點(diǎn)時(shí)，則會(huì)需要減速或者停留，其在路段上的平均速度也會(huì)相應(yīng)降低。此外，公交車輛在沿路線行駛時(shí)，有著固定的前進(jìn)方向，其累計(jì)里程值應(yīng)為單調(diào)遞增。因此，我們以車輛行駛速度的方差作為目標(biāo)函數(shù)，基站覆蓋范圍作為搜索空間，并考慮累計(jì)里程的遞增性作為決策變量的不等式約束，建立優(yōu)化模型：minimize

subjectm

如圖4.12中所示，為了簡(jiǎn)化模型的求解，將空間二維的位置轉(zhuǎn)換為車輛從始發(fā)站為參考點(diǎn)的一維累計(jì)里程，mi為軌跡中第i個(gè)點(diǎn)的累積里程，ti為軌跡中第i個(gè)點(diǎn)的時(shí)間戳，圖4.12 啟發(fā)式優(yōu)化算法示意圖Figure4.12Heuristicoptimizationofthelocalizationofanchorpoints數(shù)據(jù)模擬與模型精度評(píng)定在原始手機(jī)信令數(shù)據(jù)集中，個(gè)體真實(shí)途徑的時(shí)空軌跡是難以從其他數(shù)據(jù)源中獲取的，無(wú)法直接驗(yàn)證重建軌跡是否更加接近真實(shí)的個(gè)體時(shí)空軌跡。本節(jié)提出一種基于模擬仿真的驗(yàn)證框架，通過(guò)對(duì)高頻手機(jī)APP采集數(shù)據(jù)進(jìn)行子采樣，能夠構(gòu)建模擬Cell-ID手機(jī)信令軌跡，通過(guò)對(duì)模擬數(shù)據(jù)處理效果驗(yàn)證軌跡重建方法的有效性。圖4.13 基站掃頻安卓應(yīng)用界面Figure4.13ApplicationInterfaceofAndroidApplication我們采用一套安卓端的手機(jī)應(yīng)用程序Geopaparazzi（圖4.13為軟件界面），該款應(yīng)用能夠以1Hz的頻次檢測(cè)手機(jī)天線所連接到的附近基站，同時(shí)通過(guò)內(nèi)嵌GPS模塊記錄設(shè)備持有者的準(zhǔn)確位置。我們對(duì)研究區(qū)域內(nèi)的公交線上采集了多組數(shù)據(jù)，每一組數(shù)據(jù)包含了同一公交車輛的多次行程記錄。表4.4中給出了APP記錄的數(shù)據(jù)樣例。表4.4 安卓應(yīng)用記錄的基站掃頻數(shù)據(jù)示例Table4.4DataRecordedbytheAndroidApplicationNo.TimestampCidLacNetTypeLatLon120171204092707180165174566439.9730116.2900220171204092709181578274566439.9730116.2900320171204092712180165144566439.9732116.2917420171204092714180165144566439.9731116.2917520171204092716180165144566439.9731116.2917620171204092718180165144566439.9731116.2918720171204092720181578274566439.9730116.2918820171204092722181578274566439.9730116.2918920171204092724181578274566439.9730116.29181020171204092726181578274566439.9730116.2919在同樣位置和外界環(huán)境下，Geopaparazzi所采集到的基站與手機(jī)在同一時(shí)刻發(fā)生交互的基站相同，換言之Geopaparazzi記錄數(shù)據(jù)與Cell-ID手機(jī)信令數(shù)據(jù)在空間分布上一致。為模擬Cell-ID手機(jī)信令的時(shí)間分布特征，我們對(duì)APP采集的軌跡數(shù)據(jù)進(jìn)行同樣間隔時(shí)間的子采樣。圖4.14給出了子采樣之后軌跡相鄰點(diǎn)的間隔時(shí)間分布與原始數(shù)據(jù)集對(duì)比，模擬數(shù)據(jù)與真實(shí)數(shù)據(jù)的分布比較一致。圖4.14 相鄰軌跡點(diǎn)時(shí)間差概率分布曲線Figure4.14Distributionofconsecutivetrackingpoint軌跡重建結(jié)果分析精度評(píng)價(jià)指標(biāo)我們采用平均絕對(duì)誤差(MAE)來(lái)評(píng)估重建模型的效果，使用誤差標(biāo)準(zhǔn)差(StDev)度量來(lái)評(píng)估重建模型的穩(wěn)定性。給定一條手機(jī)信令軌跡Trj=pt1,…,ptnErrorMAE=其中，pti?pti'是手機(jī)信令軌跡點(diǎn)ptiStDev=重建結(jié)果首先對(duì)模擬手機(jī)信令軌跡和對(duì)應(yīng)公交路線進(jìn)行LCSS匹配，獲取作為啟發(fā)式算法初始輸入的匹配錨點(diǎn)位置。對(duì)公交路線307路上采集的軌跡數(shù)據(jù)匹配中，沿線共有136個(gè)手機(jī)信令基站，其中有81個(gè)基站屬于錨點(diǎn)基站。圖4.15匹配錨點(diǎn)及對(duì)應(yīng)的基站扇區(qū)Figure4.15Anchorpoint’ssearchspaceinamatchedBTSsectorLCSS匹配算法得到的錨點(diǎn)位置作為決策變量mi表4.5 迭代優(yōu)化得到重建位置Table4.5Estimatedlocationofanchorpoints.PIDTimestampMileageCoordinatexCoordinatey010:02:2636118.53129509044864737110:03:2336407.21129511924864749210:07:2737221.02129520054864780310:10:3037779.06129525634864799410:12:1338164.97129529494864815510:17:0038918.11129529974865498……………表4.5中給出了迭代優(yōu)化得到的重建位置的示例，包含了每個(gè)手機(jī)與基站發(fā)生交互時(shí)刻（即信令數(shù)據(jù)記錄時(shí)刻）的坐標(biāo)位置xi,圖4.16 軌跡重建前后累計(jì)里程與GPS真實(shí)值比較Figure4.16Accumulateddistanceofreconstructedtrackingpoint利用Geopaparazzi應(yīng)用采集到包含4次往返行程的驗(yàn)證數(shù)據(jù)，包含每次往返由GPS模塊記錄的個(gè)體真實(shí)軌跡以及由移動(dòng)通訊模塊記錄的4組手機(jī)信令軌跡，對(duì)重建效果進(jìn)行檢驗(yàn)。圖4.17中以“時(shí)間-里程”形式展示了行程劃分與軌跡重建的結(jié)果，可以看出軌跡被正確地劃分成4段，對(duì)于每一段行程調(diào)整后的錨點(diǎn)位置比調(diào)整前錨點(diǎn)更接近真實(shí)位置。圖4.17 不同往返行程中累計(jì)里程與GPS真實(shí)值比較Figure4.17Accumulateddistanceofreconstructedtrackingpoint不同啟發(fā)式算法比較我們選取了符合模型屬性（連續(xù)-約束-單目標(biāo)）的各類啟發(fā)式算法，并對(duì)不同算法的軌跡重建效果進(jìn)行了比較。優(yōu)化模型采用python智能算法模塊Pygmo進(jìn)行求解，求解的詳細(xì)步驟表示如下：Step1：確定迭代終止條件，設(shè)置最大迭代次數(shù)為200k次Step2：將匹配錨點(diǎn)作為初始輸入，并通過(guò)基站扇區(qū)范圍確定搜素空間Step3：在搜索空間內(nèi)調(diào)整決策向量，并計(jì)算目標(biāo)函數(shù)，如函數(shù)值小于當(dāng)前取得的最小目標(biāo)函數(shù)值，則更新最佳決策向量Step4：若滿足終止條件，終止算法并輸出最優(yōu)值及最優(yōu)解；否則返回step3圖4.18中分別給出了采用粒子群算法（PSO）、增廣拉格朗日算法（AL）、指南針?biāo)阉魉惴ǎ–S）和人工蜂群算法（ABC）4種啟發(fā)式算法來(lái)對(duì)優(yōu)化模型進(jìn)行求解的MAE和STDEV結(jié)果，并采用未經(jīng)過(guò)優(yōu)化的原始位置作為對(duì)照。結(jié)果表明，每一類算法在優(yōu)化后都在MAE和STDEV兩項(xiàng)指標(biāo)上有所提升；與其它算法相比，指南針?biāo)阉魉惴ǎ–S）對(duì)軌跡的重建效果最好，估計(jì)位置與實(shí)際位置的誤差最小。圖4.18 各類啟發(fā)式算法誤差比較Figure4.18Comparisonofdifferentheuristicoptimizations與已有方法的比較我們選取了在以往的軌跡重建研究中最常使用到的插值方法來(lái)和本文提出的啟發(fā)式算法模型進(jìn)行對(duì)比，對(duì)照的插值方法包括最近鄰采樣點(diǎn)插值、線性插值以及Hermit插值方法(Hoteitetal.2014)，線性插值以及Hermit插值方法分有無(wú)公交路線數(shù)據(jù)作為輔助約束條件分別進(jìn)行插值，有公交路線