基于均衡k划分的动态子区划分方法  

Dynamic sub-region partitioning for traffic network control

作　　者：修伟杰[1] 王力[1] 张立立 李敏 张玲玉[1] XIU Wei-jie;WANG Li;ZHANG Li-li;LI Min;ZHANG Ling-yu(Beijing Key Laboratory of Urban Intelligent Traffic Control Technology,North China University of Technology,Beijing 100144,China;College of Information Engineering,Beijing Institute of Petrochemical Technology,Beijing 102617,China;Beijing Zhonghe Yuntong Technology Development Co.,Ltd.,Beijing 100041,China)

机构地区：[1]北方工业大学城市道路交通智能控制技术北京市重点实验室,北京100144 [2]北京石油化工学院信息工程学院,北京102617 [3]北京中合云通科技发展有限公司,北京100041

出　　处：《桂林理工大学学报》2022年第1期229-235,共7页Journal of Guilin University of Technology

基　　金：国家重点研发计划项目(2017YFC0821102,2017YFC0821104);北京市长城学者培养计划项目(CIT&TCD20190304);北京市自然科学基金青年项目(4194078);北京市科学技术协会2021—2023年度青年人才托举工程项目;北京石油化工学院交叉科研探索项目(BIPTCSF-006)。

摘　　要：针对交通路网控制子区的划分问题,提出了基于均衡k划分的动态子区划分方法。首先建立交叉口和路段权重模型,将路网抽象成为带权拓扑图;再针对拓扑图划分的NP问题,采用改进的禁忌搜索算法进行优化求解,同时为降低算法的复杂度设计了一种启发式算法为禁忌搜索算法获取初始近似解;最后利用路网实际数据与已有方法进行对比分析。结果显示:以任意子区内节点权重之和最小与连接不同子区的边权之和最小为目标,可以实现子区划分在宏观意义上的路网类均衡性和微观意义上的区间弱关联性,进而验证了本文所提算法的可行性和有效性。采用的启发式方法为禁忌搜索算法提供初始近似解,能够有效降低其复杂度,提高计算的实时性,并且利用所提方法划分的子区能够降低路网协调控制的难度,避免多个高负荷交叉口聚集而影响路网运行效率。In this study, dynamic subarea division method based on equilibrium k partition is proposed for subarea division of traffic network control. The intersection and section weight models are built, and the road network is abstracted into a weighted topology. An improved tabu search algorithm is used for the NP of graph partition. In order to reduce the complexity of the algorithm, a heuristic algorithm is designed to obtain the initial approximate solution for tabu search algorithm. Finally, the actual data of road network is used for the comparison and analysis with the existing methods. The results show that the goal of this study can minimize the sum of weights of nodes in any subregion and the sum of weights edges can connect different sub-regions, so as to realize the quasi-equilibrium of road network in the macroscopic sense and the weak correlation in the microscopic sense, showing the feasibility and effectiveness of the model degradation concept proposed in this paper. Heuristic method is used to provide initial approximate solution for tabu search algorithm, which can effectively reduce complexity and improve real-time performance. Moreover, the proposed method can reduce the difficulty of road network coordination. The agglomeration of multiple high-load intersections is avoided by road network operation efficiency.

关 键 词：城市交通 交通控制 路网拓扑 子区划分 均衡k划分 禁忌搜索算法 图划分 

分 类 号：U491.3[交通运输工程—交通运输规划与管理]