Partitioning of Transportation Networks by Efficient Evolutionary Clustering and Density Peaks

Algorithms

Clelia Lopez¹  Pamela Al Alam²  Ibtissam Constantin³  Joseph Constantin³ 

[1] ERIC, Université de Lyon, Université de Lyon 2, ERIC UR 3083 5Avenue Pierre Mendès France, CEDEX, F69676 Bron, France;LISIC, University of Littoral Côte d’Opale (ULCO), Calais, BP 719, CEDEX, 62228 Calais, France;LaRRIS, Faculty of Sciences, Lebanese University, Fanar, Jdeidet BP 90656, Lebanon;

关键词: algorithms;    density peak;    efficient evolutionary spectral clustering;    transportation network;    snake similarities;    traffic congestion;   

DOI  :  10.3390/a15030076

来源: DOAJ

【 摘 要 】

Road traffic congestion has became a major problem in most countries because it affects sustainable mobility. Partitioning a transport network into homogeneous areas can be very useful for monitoring traffic as congestion is spatially correlated in adjacent roads, and it propagates at different speeds as a function of time. Spectral clustering has been successfully applied for the partitioning of transportation networks based on the spatial characteristics of congestion at a specific time. However, this type of classification is not suitable for data that change over time. Evolutionary spectral clustering represents a state-of-the-art algorithm for grouping objects evolving over time. However, the disadvantages of this algorithm are the cubic time complexity and the high memory demand, which make it insufficient to handle a large number of data sets. In this paper, we propose an efficient evolutionary spectral clustering algorithm that solves the drawbacks of evolutionary spectral clustering by reducing the size of the eigenvalue problem. This algorithm is applied in a dynamic environment to partition a transportation network into connected homogeneous regions that evolve with time. The number of clusters is selected automatically by using a density peak algorithm adopted for the classification of traffic congestion based on the sparse snake similarity matrix. Experiments on the real network of Amsterdam city demonstrate the superiority of the proposed algorithm in robustness and effectiveness.

【 授权许可】

Unknown