Modeling and Solving the Dynamic R-Neighbor P-Center Problem in the First-Aid System Based on Attack-Defense Game

We study a dynamic r-neighbor p-center problem (DRNPC problem for short). It can be used to solve the layout and migration problem of temporary first-aid stations (stations for short) under malicious attacks in a certain district, which is also very important for critical infrastructures protection and network security. A dynamic demand distribution is added to the problem to extend the traditional layout problem. We divide the whole process into several periods, and assume that the demand sites for first aid are fixed within each single period. But the number and locations of demand sites will change in different periods. We present a multi-period location model (MPL model for short) based on linear programming and Attack-Defense game (A-D game for short). The first part of MPL model determines the locations of stations, the correspondence between demand sites and stations in different periods. The second part determines the migration schemes with lowest migrating cost. The whole MPL model ensures that the first-aid system would not be interrupted by any malicious attacks; meanwhile it would be maintained with the best timeliness under the strongest attack. We give some theoretical analysis and computational test on the optimal solution of dynamic problem. A general solution approach is also proposed in this study.