Distance-Constrained k Spatial Sub-Networks: A Summary of Results

摘要

Given a graph and a set of spatial events, the goal of Distance-Constrained k Spatial Sub-Networks (DCSSN) problem is to find k sub-networks that meet a distance constraint and maximize the number of spatial events covered by the sub-networks. The DCSSN problem is important for many societal applications, such as police patrol assignment and emergency response assignment. The problem is NP-hard; it is computationally challenging because of the large size of the transportation network and the distance constraint. This paper proposes a novel approach for finding k sub-networks that maximize the coverage of spatial events under the distance constraint. Experiments and a case study using Chicago crime datasets demonstrate that the proposed algorithm outperforms baseline approaches and reduces the computational cost to create a DCSSN.