基于網格聚類優化的區域熱點路徑識別

翁旭艷 鄭淑妮

摘要：針對軌跡聚類方法難以準確識別高相似熱點路徑的問題，提出能區分起訖點或局部路段的熱點路徑識別方法，將出行軌跡映射并壓縮為移動網格序列，分別從邊界與內部區分序列間的空間相似性度量，整合轉化為距離并進行基于方格序列密度的空間聚類（grid sequencedensity-based spatial clustering of applications with noise，GS-DBSCAN）。以青島市市南區部分出租車的軌跡數據為例，與只考慮內部相似性且分別以對比序列中較短序列和較長序列為基準的聚類方法進行對比驗證。結果表明：同時考慮邊界與內部相似性且以較長序列為基準的GS-DBSCAN算法能正確區分多出行起訖點分布下長度差異較大的分離、匯合與交叉耦合熱點路徑，受路徑長度、網格尺寸等變量差異的影響小于2%，且聚類運算效率較高。

關鍵詞：熱點路徑；邊界；內部；軌跡聚類

中圖分類號：U491文獻標志碼：A文章編號：1672-0032（2024）02-0089-08

引用格式：翁旭艷，鄭淑妮.基于網格聚類優化的區域熱點路徑識別［J］.山東交通學院學報，2024，32（2）：89-96.

WENG Xuyan， ZHENG Shuni. Regional hotspot path identification based on grid clustering optimization［J］.Journal of Shandong Jiaotong University，2024，32（2）：89-96.

0?引言

在交通領域廣泛應用全球定位系統（global positioning system，GPS），可得到大量車輛軌跡數據，為車輛路徑規劃、交通運行等研究提供數據支持。Wang等[1]、Zhang等[2]通過出租車軌跡GPS數據檢測車輛異常軌跡；Liu等[3]、陳振華[4]通過出租車GPS軌跡數據分析城市交通擁堵模式；Lin等[5]通過GPS軌跡數據預測城市交通路網流量。通過GPS軌跡數據分析熱點路徑的研究較多，熱點路徑指在一段時間內車輛頻繁經過的路段，通過識別熱點路徑，可為綠波帶設置、主路優先等交通運行管理提供決策依據。采用聚類方法識別熱點路徑的關鍵是相似性度量[6]。李穎等[7]分別采用離散弗雷歇算法、動態時間規整算法、最長公共序列（longest common subsequence，LCS）算法和實序列編輯距離算法對貨車軌跡數據進行聚類，認為LCS算法的有效性最優。Kim等[8]以LCS算法下車輛行駛距離與較短軌跡距離之比作為軌跡空間相似度進行基于密度的聚類（density-based spatial clustering of application with noise，DBSCAN）算法，分析交通網絡中空間和時間出行模式。馮琦森[9]、趙欣[10]改進DBSCAN算法，前者結合重慶地形特點考慮海拔高度因素，認為比對軌跡中的最大海拔高度差不應超過一定范圍，否則相似度為0；后者在軌跡點空間相似度度量上增加車輛轉角差異性，定義時間維度上的軌跡相似度。Kang等[11]通過直接度量軌跡網格序列間重疊區域表征軌跡相似性。吳俊偉等[12]將網格抽象為圖模型并通過圖搜索進行網格聚類。王超[13]考慮時空事件的密度和類型對出租車軌跡點進行聚類。Lee等[14]提出基于軌跡分段的相似性度量，對速度或方向上快速變化的軌跡點分段。在軌跡映射至網格空間的聚類研究中，可通過直接度量軌跡網格序列間重疊區域表征軌跡相似性[15]，也可將網格抽象為圖，以鄰接網格的共有軌跡定義網格間可達性，通過圖搜索進行網格聚類及熱點路徑識別[16]。通過優化相似度算法、增加相關因素變量等全面、準確地分析軌跡數據，但以較短軌跡為基準的LCS相似度可能造成過于重視不同熱點路徑的重疊部分，導致將重疊度較高的不同路徑歸為同一類熱點路徑。起訖點（origin-destination，OD）矩陣和路徑流量的研究較多，但考慮軌跡數據的邊界起訖點和內部中間點屬性的研究較少。雙層規劃模型[17]在OD矩陣估計中應用較多，Ou等[18]基于機器學習算法，提出估計動態OD流量的雙層框架；Tang等[19]將改進的三維卷積神經網絡模型用于動態OD矩陣估計；Cao等[20-21]提出的OD矩陣，采用極大似然法擬合各路段的速度-密度函數，建立基于動態交通分配的雙層廣義最小二乘法估計器，分析浮動車采樣頻率較低時的OD矩陣估計方法，保證正常估計路段流量；Huang等[22]采用長短期記憶（long short-term memory，LSTM）模型估計OD矩陣。以較短軌跡為基準的LCS相似度識別熱點路徑軌跡，易將不同起訖點的路徑歸為同一類熱點路徑。

本文優化基于軌跡數據的路徑識別方法，以區域網格化為基礎，將車輛軌跡壓縮為僅關注移動特征的網格序列，序列間的相似性度量包含邊界與內部2部分，考慮GPS定位漂移及出行產生與吸引的集聚性，邊界網格的相似性通過基于熱點網格密度的空間聚類（hot grid density based spatial clustering of application with noise， HG-DBSCAN）得到熱點小區度量，內部網格以基于網格的改進LCS相似度表征，二者融合后轉化為距離度量，最后進行基于方格序列密度的空間聚類（grid sequence density-based spatial clustering of applications with noise，GS-DBSCAN），優化識別熱點路徑。

1?熱點路徑識別優化

1.1?區域網格化

假設研究區域的經度范圍為[ψmin，ψmax]，緯度范圍為[γmin，γmax]，正方形網格邊長為k，將研究區域劃分為若干正方形網格。綜合考慮路網密度、車輛GPS軌跡點密度及運算效率等因素確定網格尺寸，網格過大，易覆蓋同方向相互平行的若干道路；網格過小，會導致大部分網格沒有GPS軌跡點落入且運算效率低。

用Gx，y表示網格，x、y分別為Gx，y在網格坐標系下的橫、縱坐標。網約車訂單i的軌跡點列表為Oi=Pi1，Pi2，…，Pin，…，PiN，其中，N為軌跡點數；Pin（n∈［1，N］）為第n個軌跡點，是包含3項基本信息的一維向量，Pin=（tinψinγin），ψin、γin分別為tin時刻車輛的經、緯度坐標。以Pin為例說明車輛GPS軌跡點與網格的映射關系，公式為：

x=ψin－ψmin/k」y=γin－γmin/k」，（1）

式中?」為取整符號。

1.2?序列邊界

GPS定位有隨機漂移特征，挖掘熱點出行區域時不直接基于軌跡點進行聚類，而是先將軌跡抽象為熱點網格，再通過HG-DBSCAN算法聚類，提升搜索效率，且可處理任意形狀和大小的簇。采用HG-DBSCAN對熱點網格進行空間聚類時，作以下3個基本定義。

定義1?熱點網格。Gx，y包含的GPS軌跡起訖點數w應大于預先設定的判斷閾值λ。

定義2?網格經、緯度坐標。考慮到Gx，y中GPS軌跡點分布不均勻，采用網格內軌跡點的平均經、緯度表示網格經、緯度坐標，公式為：

ψ—x，y=∑wq=1ψq/wγ—x，y=∑wq=1γq/w。

定義3?網格球面距離。任意2個網格Gx，y、Gx′，y′在經、緯度坐標下的球面距離[23]

d（Gx，y，Gx′，y′）=ΔηR，

式中：Δη為Gx，y的平均經、緯度坐標（ψ—x，y，γ—x，y）、Gx′，y′的平均經、緯度坐標（ψ—′x′，y′，γ—′x′，y′）連線與地球中心線的夾角，Δη=2arcsin（sin2（Δψ/2）+cos ψ—cos ψ—′sin2（Δγ/2）），其中Δψ為2個網格經度之差，Δγ為2個網格緯度之差；R為地球半徑。

HG-DBSCAN的網格密度是以熱點網格的經緯度坐標為圓心，在指定半徑Eps內的熱點網格數。若網格密度大于給定的最小核心網格判別數Num，則該網格為核心網格。邊界網格指落在某核心網格的鄰域內，但本身不是核心網格；噪聲網格是既非核心也非邊界的網格。HG-DBSCAN算法流程包括輸入、初始化、運行、輸出。

1）輸入。輸入λ、Eps、Num。

2）初始化。將分析時間內所有訂單軌跡的起訖點映射至對應網格；依據定義1確定熱點網格集合H={Gh1，Gh2，…，Ghb，…，GhB}，其中，B為熱點網格數，Ghb為第b個熱點網格，Ghb=（xyψ—γ—l）hb，其中l為網格的類標簽，l=－2，簇編號C=－1。

3）運行。（1）隨機選取1個類標簽l=－2的熱點網格Ghb，若Ghb的Eps鄰域內至少有Num個熱點網格Gh，則C+1，并將第b個熱點網格的類標簽lhb賦值為C，令H′為Ghb鄰域中的熱點網格集合，循環遍歷H′中的每個熱點網格直至結束，若類標簽lhb′＝－2，則將lhb′賦值為C，同時若Ghb′鄰域內至少有Num個Gh，則將Ghb′鄰域中的熱點網格追加至H′；（2）若Ghb的Eps鄰域內沒有大于或等于Num個熱點網格Gh，lhb＝－1；（3）重復步驟（1）（2），直到沒有l=－2的Ghb。

4）輸出。依據簇內軌跡點數確定熱點小區集合Z={Zh1，Zh2，…，Zha，…，ZhA}，其中，A為熱點小區數，Zha為第a個熱點小區，含若干類標簽相同且大于－1的Ghb。

1.3?序列內部

將軌跡點的LCS擴展至網格序列可提升搜索效率，且LCS允許序列部分形變（車輛運動的隨機性）。訂單軌跡Oi通過式（1）映射為網格序列Si，刪除Si中的重復網格，得到壓縮后的Si′。考慮網格化下，同一路徑的不同軌跡-網格序列受駕駛行為、GPS定位漂移及網格大小等因素影響，網格的重疊率可能較低，建立基于網格的LCS，需定義網格間的空間相似度。

給定2個網格序列Si′={Gi′1，Gi′2，…，Gi′N′}與Sj′={Gj′1，Gj′2，…，Gj′M′}，計算Si′中的第n個網格Gi′n=（t x y）i′n和Sj′中的第m個網格Gj′m=（t x y）j′m間的歐式距離

dG（Gi′n，Gj′m）=（xi′n－xj′m）2+（yi′n－yj′m）2，

式中：xi′n、yi′n分別為Gi′n的橫、縱坐標，xj′m、yj′n分別為Gj′m的橫、縱坐標。

對網格相似度sG（Gi′n，Gj′m）進行歸一化處理，公式為：

sG（Gi′n，Gj′m）=0，dG（Gi′n，Gj′m）>δ1－dG（Gi′n，Gj′m）/δ，dG（Gi′n，Gj′m）≤δ，

式中δ為網格間允許的最大臨近距離。

基于網格相似度，通過動態規劃方法確定Si′與Sj′間的最長公共序列，需將待求解的問題劃分為若干階段，定義各階段的狀態及變量，確定階段間的狀態轉移方程。Si（n）′為Si′前n個網格，Sj（m）′為Sj′前m個網格，將sLCS（Si（n）′，Sj（m）′）狀態定義為Si（n）′與Sj（m）′間匹配網格相似度總和的最大值。當n=0或m=0時，sLCS（Si（n）′，Sj（m）′）=0；若n、m均不為0，滿足無后效性前提下，sLCS（Si（n）′，Sj（m）′）與Si′前n-1個網格與Sj′前m-1個網格的相似度sLCS（Si（n-1）′，Sj（m-1）′）、Si′前n-1個網格與Sj′前m個網格的相似度sLCS（Si（n-1）′，Sj（m）′）、Si′前n個網格與Sj′前m-1個網格的相似度sLCS（Si（n）′，Sj（m-1）′）有關，分別對應M1、M2及M3 3種匹配模式，M1=sLCS（Si（n－1）′，Sj（m－1）′）+sG（Gi′n，Gj′m），M2=sLCS（Si（n－1）′，Sj（m）′），M3=sLCS（Si（n）′，Sj（m－1）′），即：

sLCS（Si（n）′，Sj（m）′）=0，m=0或n=0

maxM1，M2，M3，m、n≠0。

對長度分別為N′與M′的序列Si′與Sj′，建立行列數分別為N′+1與M′+1的矩陣D（N′+1，M′+1），通過D（N′+1，M′+1）說明動態規劃求解最長公共序列長度及內容的過程，如圖1所示。矩陣D（n，m）保存當前sLCS（Si（n）′，Sj（m）′）及匹配的網格序列長度lLCS（Si（n）′，Sj（m）′），M1、M2及M3對應D（n，m）由D（n-1，m-1）、D（n-1，m）及D（n，m-1）分別沿對角線、向下及向右方向傳遞得到。以Si（3）′（長度為3的網格序列Si′）與Sj（3）′（長度為3的網格序列Sj′）為例，設置δ=2，分析Si（3）′與Sj（2）′匹配至Si（3）′與Sj（3）′匹配的轉移過程。對Si（3）′與Sj（2）′，只有在M1下Gi′3與Gj′2相匹配，sLCS（Si（2）′，Sj（1）′）+SG′（Gi′3，Gj′2）取得最大值，并沿對角線由D（2，1）傳遞至D（3，2）。對Si（3）′與Sj（3）′，sLCS（Si（3）′，Sj（2）′）并未繼續傳遞，D（3，3）中的sLCS（Si（3）′，Sj（3）′）由D（2，2）傳遞得到，說明該方法從全局確定網格間的最佳匹配。D（m，n）中的lLCS（Si（n）′，Sj（m）′）遵循sLCS（Si（n）′，Sj（m）′）確定的傳遞方向，但當D（n-1，m-1）沿對角線向D（m，n）傳遞時，lLCS（Si（n-1）′，Sj（m-1）′）是否加1還需檢驗sG（Gi′n，Gj′m）是否大于0，若大于0，說明Gi′n與Gj′m真正匹配且最長公共序列長度加1。當n或m從0變化至N′或M′時，D（M′，N′）的sLCS（Si（N′）′，Sj（M′）′）及lLCS（Si（N′）′，Sj（M′）′）分別表示序列間網格相似度總和最長公共序列長度的最大值。若獲取最長公共序列中的匹配網格對，需借助矩陣D（M′+1，N′+1）反向搜索，但耗時長。

1.4?序列整體相似度及GS-DBSCAN

車輛的出行不僅受路網約束，還與起訖點的用地相關，故軌跡-網格序列的相似性度量應充分考慮邊界與內部的特征。對熱點小區間的任意2個網格序列Si′與Sj′，首先結合Gx，y與熱點小區zha的隸屬關系，將邊界網格分別替換成對應的熱點小區Si′（od）={zh（i）a，Gi′2，…，Gi′N′－1，zh（i）a′}、Sj′（od）={zh（j）a，Gj′2，…，Gj′M′－1，zh（j）a′}，根據移動序列Si″={Gi′2，…，Gi′N′－1}與Sj″={Gj′2，…，Gj′M′－1}計算序列相似度sSeq（S′（od）i，

S′（od）j），其包含2部分：1）起訖熱點小區間的比較，若存在不同，則懲罰因子pf=－1，保證相似序列小于等于0；2）Si″與Sj″比較，以序列中較長的1個為基準，計算最大公共子序列與其長度之比，計算公式為：

sSeq（S′（od）i，S′（od）j）=lLCS（Si″，Sj″）max（lSeq（Si″），lSeq（Sj″））+pf，

pf=0，zh（i）a=zh（j）a且zh（i）a′=zh（j）a′－1，zh（i）a≠zh（i）a或zh（i）a′≠zh（i）a′，

式中：lLCS（Si″，Sj″）為Si″與Sj″間匹配的最長網格序列長度，lSeq（Si″）、lSeq（Sj″）分別為Si″與Sj″的網格序列長度。

耦合路徑軌跡因起訖點或局部路段不同分為分離、匯入及交叉3種情況，如圖2所示。對同時與S3相耦合且長度差異較大的S4及S5，以較長序列為基準的度量可正確表征S4與S5分別對S3的相似性，即受長度差異影響較小。對長度相近的路徑，如處于同一對小區的S1與S2，以較短或較長序列為基準均可，前者比后者更接近1；但對不同小區的S3與S6，2種度量方法均存在局限性，此時需增加起訖邊界小區不同的限制條件進行區分。

計算Si′（od）與Sj′（od）間的相似度后，需轉化為距離度量才可進行GS-DBSCAN聚類，公式為：

dSeq（Si′（od），Sj′（od））=1－sSeq（Si′（od），Sj′（od））。

GS-DBSCAN的偽代碼與HG-DBSCAN類似，研究對象變成網格序列，不再贅述，得到熱點路徑集合R={rh1，rh2，…，rhU}，其中U為熱點路徑數。

2?案例分析

以2017-01-13青島市市南區的網約車訂單數據為案例驗證方法的有效性。區域覆蓋的經度區間為（120.375 6°，120.400 0°），緯度區間為（36.063 1°，36.075 9°），面積約為4.79 km2。案例共采集33 538條訂單軌跡數據，每條訂單數據包含脫敏處理后的訂單編號及軌跡點列表2個字段，如訂單編號3e7a3f2d231的軌跡點列表為{（1 484 236 791 s?120.398 56°?36.007 014°），（1 484 236 794 s?120.398 57°?36.070 17°），（1 484 236 977 s?120.398 55°?36.070 18°）}，軌跡點列表中包含Unix時間戳及WGS84坐標系下的經、緯度。

2.1?熱點路徑識別結果

先聚類識別熱點小區，再將熱點小區作為網格邊界，增加約束條件，聚類識別熱點路徑。取網格尺寸為30 m×30 m，小于次干路及以上等級道路間的最小平行距離。假設車輛

在網格內的位置均勻分布且速度為36～55 km/h，軌跡點平均采樣時間為3 s，則車輛每次移動的網格數為1.0～1.5。

首先建立參數不同間隔取值下的交叉組合，通過試算，設置λ=30，Eps=30 m，Num=2。根據所選組合進行HG-DBSCAN聚類，聚類后的簇總數為82，根據簇中包含的出行起訖點數降序排列選取前13個簇作為熱點小區，如圖3所示。

由圖3可知：該區域內的熱點小區多分布在研究范圍內道路的端點處，表示聯系研究范圍外熱點區域的主要途經點。zh12和zh13位于研究范圍內道路中間，結合該點的用地可知，周邊商業綜合體華潤萬象城成為農歷新年前最后1個工作日的出行熱點。從熱點小區間出行期望線可知zh12與zh1間的聯系最強，說明華潤萬象城是研究范圍內有強吸引力的出行熱點，同時對研究范圍外從zh1方向的居民有較強吸引力。

選取早、晚高峰時段（07：00—10：00，18：00—21：00）數據識別熱點路徑。通過試算，設置δ=2，Eps=0.2 m，Num=3。對13個熱點小區間的軌跡-網格序列進行GS-DBSCAN聚類，選取其中序列數較多的前20個簇作為熱點路徑集合，如圖4所示。由圖4結合熱點小區分布可知：熱點路徑主要分布在主干道，受相交道路或道路一側鄰近熱點小區的吸引，又存在若干條轉入、轉出的高相似路徑。

2.2?基于LCS的序列相似性度量算法對比與網格敏感性分析

保持δ=2，Eps=0.2 m，Num=3不變，對比分析不同計算方法下的聚類效果。方法1：只考慮內部相似性且以對比序列中較短序列為基準。方法2：只考慮內部相似性且以對比序列中較長序列為基準。方法3：本文建立同時考慮邊界與內部相似性的GS-DBSCAN聚類且以對比序列中較長序列為基準。

以zh1至zh5、zh7、zh9的網格序列集為例分別進行3種方法下的軌跡聚類，得到的簇如圖5所示。由圖5可知：方法3中的5個軌跡簇C0、C1、C2、C3、C4對應區域中的路徑rh2、rh7、rh14、rh21、rh22；方法1中以較短序列為基準，C1與其他簇軌跡的相似度均較高，在密度可達的傳遞作用下將其歸于1類；方法2中雖以較長序列為基準，但C0與C2序列長度相近且重疊度較高，導致rh2與rh14無法區分；方法3中C0、C1、C2、C3、C4可較好地區分rh2、rh7、rh14、rh21與rh22的軌跡，說明本文考慮邊界與內部相似性，且以對比序列中較長序列為基準的方法合理。

分析GS-DBSCAND方法對網格尺寸的敏感性，在k=30 m的基礎上分別縮小、擴大1倍，相應地調整δ進行聚類，得到不同路徑下的正確軌跡數，如表1所示。

由表1可知：聚類時間隨k的減小而增大，當δ=4，k=15 m時，聚類時間約為440 s，僅比δ=2，k=30 m時的聚類時間增大43.32%，GS-DBSCAN方法的軌跡聚類運算效率較高；不同k和δ下，rh2、rh7、rh14、rh21及rh22的聚類結果整體偏差小于2%，受k和δ的影響較小。

3?結束語

為準確識別熱點路徑，本文提出細分邊界與內部兩部分度量序列間相似性的軌跡數據熱點路徑識別優化方法，以區域網格化為基礎，將車輛軌跡映射為移動網格序列，通過HG-DBSCAN算法識別熱點區域，再將熱點區域作為網格邊界，增加約束條件，通過GS-DBSCAN算法識別熱點路徑。以青島市市南區的網約車訂單數據為案例進行熱點路徑識別，驗證方法的有效性。結果表明：本文提出的移動網格序列研究方法能準確識別熱點小區，正確區分多出行起訖點分布下長度差異較大的分離、匯合與交叉耦合熱點路徑，且聚類運算效率較高，可為城市范圍內交通組織設計、交通擁堵治理、智慧交通出行路徑規劃等城市交通規劃設計與管理提供參考依據。后續將結合實際工作，采集私家車、共享單車等更豐富的軌跡數據，擴大案例范圍，開展更全面的研究。

參考文獻：

[1]?WANG Y L， QIN K， CHEN Y X， et al. Detecting anomalous trajectories and behavior patterns using hierarchical clustering from taxi GPS data[J].ISPRS International Journal of Geo-Information， 2018，7（1）：25-45.

[2]?ZHANG D Q， LI N， ZHOU Z H， et al. Ibat： detectiong anomalous taxi trajectories from GPS traces[C]//Proceedings of 13th International Conference on Ubiquitous Computing. Beijing， China： Ubicomp，2011：17-21.

[3]?LIU C K， QIN K， KANG C G. Exploring time-dependent traffic congestion patterns from taxi trajectory data[C]//2015 2nd IEEE International Conference on Spatial Data Mining and Geographical Knowledge Services （ICSDM）. Fuzhou， China：IEEE，2015：39-45.

[4]?陳振華.基于軌跡數據的城市交通擁塞傳播模式挖掘[D].吉林：吉林大學，2019.

[5]?LIN S， SCHUTTER B D， XI Y G， et al. Efficient network-wide model-based predictive contral for urban traffic networks[J].Transportation Research Part C： Emerging Technologies， 2012，24：122-140.

[6]?MAZIMPAKA J D， TIMPF S. Trajectory data mining： a review of methods and applications[J].Journal of Spatial Information Science，2016，13：61-99.

[7]?李穎，趙莉，趙祥模，等.基于大貨車GPS數據的軌跡相似性度量有效性研究[J].中國公路學報，2020，33（2）：146-157.

[8]?KIM J， MAHMASSANI H S. Spatial and temporal characterization of travel patterns in a traffic network using vehicle trajectories[J].Transportation Research Part C： Emerging Technologies， 2015，7（10）：164-184.

[9]?馮琦森.基于出租車軌跡的居民出行熱點路徑和區域挖掘[D].重慶：重慶大學，2016.

[10]?趙欣.基于時空約束的城市熱點區域與熱點路徑挖掘[D].重慶：重慶大學，2017.

[11]?KANG H Y， KIM J S， LI K J. Similarity measures for trajectory of moving objects in cellular space[C]//Proceedings of the 2009 ACM Symposium on Applied Computing. Honolulu， Hawaii， USA： Spatial Information Society，2009：9-12.

[12]?吳俊偉，朱云龍，庫濤，等.基于網格聚類的熱點路徑探測[J].吉林大學學報（工學版），2015，45（1）：274-282.

[13]?王超.基于軌跡聚類的頻繁模式挖掘方法[D].杭州：浙江大學，2021.

[14]?LEE J G， HAN J W， WHANG K Y. Trajectory clustering： a partition-and-group framework[C]//Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. Beijing， China： SIGMOD，2007：593-604.

[15]?KANG H Y， KIM J S， LI K J. Similarity measures for trajectory of moving objects in cellular space[C]//Proceedings of the 2009 ACM Symposium on Applied Computing. Honolulu， Hawaii， USA：ACM Symposium on Applied Computing， 2009：1325-1330.

[16]?YANG H， SASAKI T， IIDA Y， et al. Estimation of origin-destination matrices from link traffic counts on congested networks[J].Transportation Research Part B： Methodological， 1992，26（6）：417-434.

[17]?ZHOU X S ， MAHMASSANI H S. Dynamic origin-destination demand estimation using automatic vehicle identification data[J].IEEE Transactions on Intelligent Transportation Systems， 2006，7（1）：105-114.

[18]?OU J S， LU J W， XIA J X， et al. Learn， assign， and search： real-time estimation of dynamic origin-destination flows using machine learning algorithms[J].IEEE Access， 2019， 7：26967-26983.

[19]?TANG K S， CAO Y M， CHEN C， et al. Dynamic origin-destination flow estimation using automatic vehicle identification data： a 3D convolutional neural network approach[J].Computer-Aided Civil and Infrastructure Engineering， 2021，36（1）：30-46.

[20]?CAO P， MIWA T， YAMAMOTO T， et al. Bilevel generalized least squares estimation of dynamic origin-destination matrix for urban network with probe vehicle data[J].Transportation Research Record： Journal of the Transportation Research Board， 2013， 2333：66-73.

[21]?CAO P， MIWA T， YAMAMOTO T， et al. Estimation of dynamic link flows and origin-destination matrices from lower polling frequency probe vehicle data[J].Journal of the Eastern Asia Society for Transportation Studies， 2013，10：762-775.

[22]?HUANG T， MA Y T， QIN Z T， et al. Origin-destination flow prediction with vehicle trajectory data and semi-supervised recurrent neural network[C]//2019 IEEE International Conference on Big Data. Los Angeles， CA， USA：IEEE， 2019：1450-1459.

[23]?GODAU M， ALT H. Computing the Fréchet distance between two polygonal curves[J].International Journal of Computational Geometry & Applications， 1995，5（1）：75-91.

Regional hotspot path identification based on grid clustering optimization

WENG Xuyan， ZHENG Shuni

Zhejiang Scientific Research Institute of Transport， Hangzhou 310023，China

Abstract：To solve the problem that the trajectory clustering method is difficult to accurately identify high-similarity hotspot paths， a hotspot path identification method that can distinguish between start and end points or local sections is proposed. The travel trajectory is mapped and compressed into a moving mesh sequence， and the spatial similarity measurement between sequences is distinguished from the boundary and the interior， integrated and transformed into distance， and spatial clustering based on grid sequencedensity-based spatial clustering of applications with noise （GS-DBSCAN） is performed. Taking the trajectory data of some taxis in Shinan District， Qingdao as an example， the clustering method that only considers internal similarity and is based on the shorter and longer sequences in the comparison sequence is verified. The results show that the GS-DBSCAN algorithm， which considers both boundary and internal similarity and is based on longer sequences， can correctly distinguish the separation， convergence， and cross-coupling hotspot paths with large length differences under the distribution of multiple travel start and end points. The influence of variable differences such as path length and grid size is less than 2%， and the clustering operation efficiency is high.

Keywords：hotspot path; boundary; interior; trajectory clustering

（責任編輯：趙玉真）

收稿日期：2023-02-02

基金項目：浙江省交通運輸科技計劃項目（2023001）

第一作者簡介：翁旭艷（1993—），女，上海人，工程師，工學碩士，主要研究方向為城市交通，E-mail：2445951226@qq.com。

DOI：10.3969/j.issn.1672-0032.2024.02.013