A modified multilevel k-way partitioning algorithm for trip-based road networks

Department of Computer Science and Engineering, University of Moratuwa, Sri Lanka

^* Corresponding author: mailto:chanaka.14@cse.mrt.ac.lk

Abstract

In today’s world, the traffic volume on urban road networks is multiplying rapidly due to the heavy usage of vehicles and mobility on demand services. Migration of people towards urban areas result in increasing size and complexity of urban road networks. When handling such complex traffic systems, partitioning the road network into multiple sub-regions and managing the identified sub regions is a popular approach. In this paper, we propose an algorithm to identify sub-regions of a road network that exhibit homogeneous traffic flow patterns. In a stage wise manner, we model the road network graph by using taxi-trip data obtained on the selected region. Then, we apply the proposed modified multilevel kway partitioning algorithm to obtain optimal number of partitions from the developed road graph. An interesting feature of this algorithm is, resulting partitions are geographically connected and consists minimal interpartition trip flow. Our results show that the proposed algorithm outperforms state-of-the-art multilevel partitioning algorithms for tripbased road networks. By this research, we demonstrate the ability of road network partitioning using trip data while preserving the partition homogeneity and connectivity.