ViCTS: A novel network partition algorithm for scalable agent-based modeling of mass evacuation

Emergency evacuation is a critical response to deadly disasters such as hurricanes, floods, and earthquakes, etc. However, mass emergency evacuation itself is a complex process that sometimes could lead to chaotic situations and unintended consequences. In many emergency scenarios, mass evacuation is necessary to cope with severe public threats within tight spatiotemporal ranges. To better understand complex phenomena like mass evacuation, and study possible consequences, agent-based models (ABMs) have been widely developed in previous work. Existing models simulate individual behaviors, posing computational challenges when applied to large geographic areas and sophisticated behaviors. A key strategy for resolving such computational challenges is to partition transportation networks into smaller regions and resolve corresponding computational costs by taking advantage of advanced cyberinfrastructure and cyberGIS. In this study, a novel network partition algorithm is developed to improve the scalability of agent-based modeling of mass evacuation based on a cutting-edge cyberGIS-enabled computational framework that exploits the spatial movement patterns of emergency evacuation. Specifically, the algorithm is termed as Voronoi Clustering based on Target-Shift, or ViCTS. It is enlightened by network Voronoi diagrams and designed to resolve computational scalability challenges caused by the unique characteristics of evacuation traffic. We conducted a set of computational experiments with real street network data in various evacuation scenarios to test the effectiveness and efficiency of the algorithm. Computational experiments show that ViCTS outperforms a widely used network partition algorithm for microscopic traffic simulation in terms of achieving optimal computational performance by balancing computational loads and reducing communications across high-performance parallel computing resources.