|
|
Optimization of time-of-day breakpoints based on improved NJW algorithm |
ZHAO Wei-ming, WANG Dian-hai, ZHU Wen-tao, DAI Mei-wei |
College of Civil Engineering and Architecture, Zhejiang University, Hangzhou 310058, China |
|
|
Abstract In order to overcome the artificial arbitrariness on time-of-day breakpoints determination in traffic control and the defects of K-means method, spectral clustering algorithm was used to obtain the optimal time-of-day (TOD) breakpoints. Each phase’s volume was selected as clustering data to reflect the system status as closely as possible and identify different traffic patterns in the dynamic traffic movements. The classic Ng-Jordan-Weiss (NJW) spectral clustering algorithm was improved to obtain an initial breakpoints, and then the final breakpoints at a given number of clusters were obtained after dealing with the outliers. After the best timing plans were obtained by Synchro software for each period, the best numbers of clusters was selected by simulation evaluation under different numbers of clusters using SimTraffic. And comparing with K-means method on simulation results, the proposed method contributed to a reduction of 6.8% in total delay and 5.4% in stops.
|
Published: 01 December 2014
|
|
基于改进NJW算法的交通控制时段划分
为了克服人为地对交通控制进行时段划分的随意性和K-means方法本身的缺陷,使用谱聚类算法得到最优的时段划分结果.选择道路交叉口各相位的流量作为聚类数据,以尽可能代表交叉口的状态,识别出动态交通中的不同交通模式.对谱聚类中的经典NJW (Ng-Jordan-Weiss)算法进行改进,得到初始时段划分结果,再进行离群点的修正后,得到给定聚类数目下的时段划分结果.通过Synchro软件为每个时段建立最佳信号配时方案,使用SimTraffic对不同聚类数目下的时段划分结果进行仿真评价,以选择最佳的聚类数目.与K-means方法仿真对比结果表明:提出的方法使得总延误减少了6.8%、停车次数降低了5.4%.
|
|
[1] 陈琳,刘翔,孙优贤. 单交叉路口交通流的通用多相位智能控制策略[J]. 浙江大学学报:工学版, 2006, 40(11): 1947-1950.
CHEN Lin, LIU Xiang, SUN You-xian. General multi-phase intelligent control method[J]. Journal of Zhejiang University :Engineering Science, 2006, 40(11): 1947-1950.
[2] 金盛,徐程,王殿海. 城市路网交叉口检测器均衡布设优化方法[J]. 浙江大学学报:工学版, 2013, 47(3): 515-521.
JIN Sheng, XU Cheng, WANG Dian-hai. Optimal traffic detector locations for equal distribution at urban network intersections[J]. Journal of Zhejiang University :Engineering Science, 2013, 47(3): 515-521.
[3] 孔祥杰,沈国江,梁同海. 具有公交优先的路网交通流智能协调控制[J]. 浙江大学学报:工学版, 2009, 43(6): 1026-1031.
KONG Xiang-jie, SHEN Guo-jiang, LINAG Tong-hai. Intelligent coordinated control of traffic flow on road network with bus-priority[J]. Journal of Zhejiang University: Engineering Science, 2009, 43(6): 1026-1031.
[4] RATROUT N T. Subtractive clustering-based k-means technique for determining optimum time-of-day breakpoints[J]. Journal of Computing in Civil Engineering, 2011, 25(5): 380-387.
[5] WONG Y K, WOON W L. An iterative approach to enhanced traffic signal optimization[J]. Expert Systems with Applications, 2008, 34(4): 2885-2890.
[6] SMITH B L, SCHERER W T, HAUSER T A. Data-mining tools for the support of signal-timing plan development[J]. Transportation Research Record, 2001, 1768: 141-147.
[7] WANG Xiao-dong, COTTRELL Wayne, MU Si-chun. Using k-means clustering to identify time-of-day break points for traffic signal timing plans[C]∥ IEEE Conference on Intelligent Transportation Systems. Vienna: IEEE, 2005: 519-524.
[8] 李英,李武,王浣尘. 聚类分析算法在交通控制中的应用[J]. 系统工程,2004,22(2): 6668.
LI Ying, LI Wu, WANG Huan-chen. An application of cluster analysis algorithm in traffic control[J]. Systems Engineering, 2004,22(2): 66-68.
[9] 宫晓燕,陈德望,刘小明. 基于有序样本聚类的交叉口交通信号控制算法研究[J]. 公路交通科技,2003, 20(1): 101-104.
GONG Xiao-yan, CHEN De-wang, LIU Xiao-ming. A newly integrated algorithm for intersection control[J]. Journal of Highway and Transportation Research and development, 2003, 20(1): 101-104.
[10] 杜长海,黄席樾,杨祖元,等. 改进的FCM聚类在交通时段自动划分中的应用[J]. 计算机工程与应用,2009, 45(24): 190-193.
DU Chang-hai, HUANG Xi-yue, YANG Zu-yuan, et al. Application of improved Fuzzy C-Means clustering in automatic programming traffic intervals[J]. Computer Engineering and Applications, 2009, 45(24): 190-193.
[11] PARK B B, SANTRA P, YUN I, et al. Optimization of time-of-day breakpoints for better traffic signal control [J]. Transportation Research Record, 2004, 1867: 217-223.
[12] 杨立才,贾磊,孔庆杰,等. 基于人工免疫算法的交通时段自动划分方法[J]. 控制理论与应用,2006,23(2): 193-198.
YANG Li-cai, JIA Lei, KONG Qing-jie, et al. Method of automatic programming traffic intervals based on artificial immune algorithm[J]. Control Theory &Applications, 2006,23(2): 193-198.
[13] ABBAS M, SHARMA Anuj, JUNG Younsu. Optimization of time of day plan scheduling using a multi-objective evolutionary algorithm[C]∥ Proceedings of the Transportation Research Board Annual Meeting. Washington, DC: Transportation Research Board, 2005.
[14] NASCIMENTO M C V, DE CARVALHO A C P L F. Spectral methods for graph clustering—A survey[J]. European Journal of Operational Research, 2011, 211(2): 221-231.
[15] CHUNG F. Spectral graph theory[M]. New York: American Mathematical Press, 1997.
[16] SHI J B, MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.
[17] NG A Y, JORDAN M I, WEISS Y. On spectral clustering: analysis and an algorithm[C]∥Advances in Neural Information Processing Systems (NIPS). Cambrige, MA: MIT, 2001: 849-856.
[18] ZELNIK-MANOR L, PERONA P. Self-tuning spectral clustering[C]∥Advances in Neural Information Processing Systems. Cambridge: MIT, 2004: 1601-1608. |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|