基于交通流时间序列相似性的NCut城市路网分区算法

针对大规模城市道路交通路网分区的实际需求，基于可反映时间序列变化趋势的皮尔逊相关系数和度量空间关系的欧式距离，构建了一种衡量交通流时间序列相似性的综合指标; 结合交通流时间序列的时空相似性特点，引入子区内的空间连通约束，利用归一化割(NCut)算法设计了一种改进的路网静态分区算法; 为体现交通路网分区的时变特征，选取了合适的评价指标来确定每一时间段内合理的分区数量，提出了一种基于时间序列的NCut路网动态分区算法; 利用北京市东北二环区域内采集的路段交通流速度数据，应用所设计的算法对7.23 km2的路网进行分区，对比了晚高峰时期的分区效果。研究结果表明:所提出的分区算法能实现对路网内不同区域交通状况的有效识别，以30 min为间隔的动态分区算法能划分出数量和范围随时间变化的多个可变子区域; 与子区数固定为2、3、4、5的静态分区算法相比，动态分区算法的评价指标分别提升了63.77%、50.06%、6.43%和7.13%，提高了路网分区效果。可见，本文提出的动态分区算法在保证子区内部连通性的基础上可将异质路网划分成多个内部同质子区域，并充分体现交通流动态演化的时空特性，有利于制定动态的多区域边界控制方案。 

NCut partitioning algorithm for urban road networks based on similarity of traffic flow time series

Under practical demand of partitioning for large-scale urban road traffic networks, a comprehensive index that measures the similarity of traffic flow time series was constructed based on the Pearson correlation coefficient and Euclidean distance which reflects the trend and describes the spatial relationships for time series. By incorporating the spatial-temporal similarity of the traffic flow time series, an improved static partitioning algorithm for road networks was designed using the normalized cut (NCut) algorithm under the spatial connectivity constraint for each subregion. To reflect the time-varying characteristics of road networks, reasonable cluster numbers during each time period was determined by selecting an appropriate evaluation criterion, and a dynamic partitioning algorithm of the road network based on NCut for the time series was proposed. By using the link traffic flow speed data collected within a region in the Northeast Second Ring of Beijing, the designed partitioning algorithms were applied to the road network covering 7.23 km2, and the partitioning performances during evening peak hours was compared. Analysis results indicate that the proposed partitioning algorithms can effectively distinguish the traffic conditions in different areas within the road network. Using the dynamic partitioning algorithm with a time interval of 30 min, the road network can be divided into several alterable subregions with time-varying cluster numbers and time-varying scopes. Compared to the static partitioning algorithm using fixed subregion numbers of 2, 3, 4, and 5, the evaluation criterion of the proposed dynamic partitioning algorithm increase by 63.77%, 50.06%, 6.43%, and 7.13%, respectively, and the partitioning performance for the road network improves. Therefore, the proposed dynamic partitioning algorithm can divide the heterogeneous road networks into a number of internally homogeneous subregions while the internal connectivity within each subregion is guaranteed, and can fully embody the spatial-temporal evolution characteristics of the traffic flow, and can benefit to formulating dynamical perimeter control scheme for multiple regions. 2 tabs, 8 figs, 30 refs.