Road network partitioning method based on Canopy-Kmeans clustering algorithm

Xiaohui Lin; Jianmin Xu

doi:10.5604/01.3001.0014.2970

Authors

Xiaohui Lin Institute of Rail Traffic, Guangdong Communication Polytechnic, Guangzhou Author https://orcid.org/0000-0002-8922-8815
Jianmin Xu 2School of Civil Engineering and Transportation, South China University of Technology, Guangzhou Author https://orcid.org/0000-0002-4126-5430

DOI:

https://doi.org/10.5604/01.3001.0014.2970

Keywords:

traffic engineering, road network, road network partition, Canopy-Kmeans algorithm, macroscopic fundamental diagram

Abstract

With the increasing scope of traffic signal control, in order to improve the stability and flexibility of the traffic control system, it is necessary to rationally divide the road network according to the structure of the road network and the characteristics of traffic flow. However, road network partition can be regarded as a clustering process of the division of road segments with similar attributes, and thus, the clustering algorithm can be used to divide the sub-areas of road network, but when Kmeans clustering algorithm is used in road network partitioning, it is easy to fall into the local optimal solution. Therefore, we proposed a road network partitioning method based on the Canopy-Kmeans clustering algorithm based on the real-time data collected from the central longitude and latitude of a road segment, average speed of a road segment, and average density of a road segment. Moreover, a vehicle network simulation platform based on Vissim simulation software is constructed by taking the real-time collected data of central longitude and latitude, average speed and average density of road segments as sample data. Kmeans and Canopy-Kmeans algorithms are used to partition the platform road network. Finally, the quantitative evaluation method of road network partition based on macroscopic fundamental diagram is used to evaluate the results of road network partition, so as to determine the optimal road network partition algorithm. Results show that these two algorithms have divided the road network into four sub-areas, but the sections contained in each sub-area are slightly different. Determining the optimal algorithm on the surface is impossible. However, Canopy-Kmeans clustering algorithm is superior to Kmeans clustering algorithm based on the quantitative evaluation index (e.g. the sum of squares for error and the R-Square) of the results of the subareas. Canopy-Kmeans clustering algorithm can effectively partition the road network, thereby laying a foundation for the subsequent road network boundary control.

References

AN, K., CHIU, Y. C., HU, X., Chen, X., 2017. A network partitioning algorithmic approach for macroscopic fundamental diagram-based hierarchical traffic network management. IEEE Transactions on Intelligent Transportation Systems, 99:1-10.

DAGANZO, C.F., 2007. Urban gridlock: macroscopic modeling and mitigation approaches. Transportation Research Part B, 41(1): 49-62.

DAGANZO, C.F., GAYAH, V.V., GONZALES, E.J., 2011. Macroscopic relations of urban traffic variables: Bifurcations, multi valuedness and instability. Transportation Research Part B, 45 (1): 278-288.

DAI, B. K., HU, J., 2010. Research on double-Layer division method of regional traffic district. Railway Transport and Economy, 32(11), 86-89.

DU, C. J. , CHEN, J. H. , LU, A. Q., 2014. Transportation zone classification based on cluster analysis with traffic flow contact. High-way, 59(6), 175-178.

EDIE, L. C., 1963. Discussion of traffic stream measurements and definitions. In J. Almond (Ed.), Proceedings of the 2nd International Symposium on International Symposium on Transportation and Traffic Theory, 139-154.

FENG, S. M. , MA, D. C., 2015. Two-dimensional graphic theory on clustering method of small traffic zones. Journal of Harbin Institute of Technology, 47(9), 57-62.

GAYAH, V. V., DAGANZO, C.F., 2011. Clockwise Hysteresis loops in the Macroscopic Fundamental Diagram: An effect of network in-stability. Transportation Research Part B, 45 (4): 643-655.

GEROLIMINIS, N. , SUN, J., 2011. Properties of a well-defined macroscopic fundamental diagram for urban traffic. Transportation research part b methodological, 45(3), 605-617.

GEROLIMINIS, N., DAGANZO, C.F., 2008. Existence of urban-scale macroscopic fundamental diagrams: Some experimental findings. Transportation Research Part B, 42(9): 759-770.

GODFREY, J. W., 1969. The mechanism of a traffic network. Traffic Engineering Control, 11(7), 323-327.

GONZALES, E., CHAVIS, C., LI, Y., DAGANZO, C. F., 2009. Multimodal Transport Modeling for Nairobi, Kenya: Insights and Recommendations with an Evidence based Model. UC Berkeley, Volvo Working Paper UCB-ITS-VWP-2009-5.

HADDAD, J., SHRAIBER, A., 2014. Robust perimeter control design for an urban region. Transportation Research Part B, 68:315-332.

JI, Y., GEROLIMINIS, N., 2012. On the spatial partitioning of urban transportation networks. Transportation Research Part B Methodological, 46(10), 1639-1656.

KLOS, M. J., SOBOTA, A., 2019. Performance evaluation of roundabouts using a microscopic simulation model. Scientific Journal of Silesian University of Technology. Series Transport,104: 57-67.

LI, X. D., YANG, X. G. , CHEN, H. J., 2009. Study on traffic zone division based on spatial clustering analysis. Computer Engineering and Applications, 45(5), 19-22.

LIN, X. H., XU, J. M., CAO, C. T., 2019. Simulation and comparison of two fusion methods for macroscopic fundamental diagram estimation. Archives of Transport, 51(3) ,35-48

LIU, B. L., SU, J., 2016. Improved Canopy-Kmeans algorithm based on double-mapre-duce. Journal of Xi’an Technological University, 36(9), 730-737.

LOPEZ, C., KRISHNAKUMARI, P., LECLERCQ, L., CHIABAUT, N., LINT, J. W. C. H. V., 2017. Spatiotemporal partitioning of transportation network using travel time data. Transportation Research Record: Journal of the Transportation Research Board, 2017, 2623:98-107.

MAO, D. H., 2012. Improved Canopy-Kmeans algorithm based on mapreduce. Computer Engineering and Applications, 48(27), 22-26+68.

NAGLE A. S., GAYAH V. V., 2014. Accuracy of networkwide traffic states estimated from mobile probe data. Transportation Research Record Journal of the Transportation Research Board, 2421(2421):1-11.

PASCALE A., MAVROEIDIS D., LAM H. T., 2015. Spatiotemporal clustering of urban net-works: real case scenario in London. Transportation Research Record Journal of the Transportation Research Board, 2491(2491), 81-89.

SAEEDMANESH, M., GEROLIMINIS, N., 2015. Optimization-based clustering of traffic networks using distinct local components. IEEE, International Conference on Intelligent Transportation Systems. IEEE Computer Society, 2135-2140.

SAEEDMANESH, M., GEROLIMINIS, N., 2016. Clustering of heterogeneous networks with directional flows based on “Snake” similarities. Transportation Research Part B Methodological, 91:250-269.

WALINCHUS, R. J., 1971. Real-time network decomposition and subnetwork interfacing. Highway Research Record.

WANG, X. X., 2017. The partition of urban traffic network and classification of traffic status based on clustering. Beijing Jiaotong University.

XU, J. M., YAN, X. W., JING, B. B., WANG Y. J., 2017. Dynamic network partitioning method based on intersections with different degree of saturation. Journal of Transportation Systems Engineering and Information Technology, 17(4), 145-152.

YIN, H. Y. , XU, L. Q. , CAO,Y. R., 2010. City transportation road network dynamic zoning based on spectral clustering algorithm. Journal of Transport Information and Safety, 28(1), 16-19+25.

YUN, M. P., YANG, X. G., 2004. Improvement of road network zoning optimization model for incident management in advanced traffic management systems. Journal of Highway and Transportation Research and Development, 04:73-76.

ZHAO, H., HE, R., SU, J., 2018. Multi-objec-tive optimization of traffic signal timing using non-dominated sorting artificial bee colony algorithm for unsaturated intersections. Archives of Transport, 46(2), 85-96.

ZHOU, Z., LIN S., YUGENG X. I., 2013. A fast network partition method for large-scale urban traffic networks. Journal of Control Theory and Applications, 03:37-44.