A novel distributed parallel simulation method with dynamic partitioning using KLeiden-based community detection

Microscopic traffic simulation constitutes a foundational technology in Intelligent Transportation Systems, and as traffic management paradigms continue to evolve, the requirements for its real-time application have become increasingly stringent. The computational efficiency of microscopic traffic simulation in large-scale road networks remains a critical issue. Distributed parallel simulation is considered one of the viable measures to address the above issue. However, this approach currently encounters challenges in the following three aspects: (a) the integration of network partitioning scheme and computational resources; (b) developing an efficient solver for the network partitioning problem; (c) enabling dynamic partitioning in distributed parallel simulation under time-varying OD (Origin-Destination) patterns. In order to address the aforementioned challenges, this study applies Amdahl’s Law to analyze the relationship between partitioning schemes and simulation time considering parallel and serial computations. Based on this finding, a network partition optimization model is formulated aiming at minimizing simulation time. Consequently, a dedicated solving algorithm is created based on analytical derivation and community detection that simultaneously preserves each subnetwork’s internal connectivity and satisfies the minimum-cut criterion. Meanwhile, the proof for the optimality of the solving algorithm is also provided. Furthermore, a distributed parallel simulation framework with dynamic partitioning is introduced to address load imbalance arising from changes in OD patterns. Extensive experiments conducted on several large-scale urban traffic networks demonstrate that the proposed method achieves up to 17.5 times real acceleration, while maintaining overall macroscopic errors within 1 %. In particular, under varying OD conditions, the proposed dynamic partitioning framework consistently yields superior acceleration performance compared with static partitioning schemes. The code will be released upon acceptance at https://github.com/TJINTO/parallel_sumo.