hMETIS-based offline road network partitioning

Abstract

Distributed transportation simulation is an important technology for evaluating large-scale traffic applications and control policies, before they are implemented in real-world traffic systems. Offline road network partitioning is the first step towards distributed transportation simulation. Currently, road network portioning algorithms, like METIS, are designed to reduce the execution time. However, a slower execution time is acceptable for offline road network partitioning, if it leads to more efficient road network partitions. This paper introduces hMETIS-based offline road network partitioning. One experiment based on Singapore expressways shows that compared with the famous METIS-based offline road network partitioning, hMETIS-based offline road network partitioning reduces the number of vehicles crossing partitions by 9.8% on average, with a similar load imbalance and an acceptable execution time. For distributed traffic simulations, where there are large amount of data exchanged between partitions, hMETIS-based offline road network partitioning is one candidate solution to reduce the simulation time and increase the scalability. © 2012 Springer-Verlag.