Stochastic Simulation Optimization for Districting Problems with Application to Police Patrol District Design

Districting or territory design is the procedure of partitioning small geographic units into larger areas in order to facilitate the operations performed over the region and optimize planning criteria under certain constraints, such as contiguity and compactness. The size of the possible solution space is large and the corresponding graph-partitioning problem is NP-hard. District design problems arise in a broad range of real-world applications such as political redistricting, sales and services territory alignment, school districts and emergency services. This dissertation develops a simulation-based optimization districting methodology for public services with stochastic demand and dynamic service operations. Stochastic inputs and constraints make the optimization problem difficult to solve. We apply the new approach to police patrol district design, which is one of the most important decisions that affect the effectiveness of patrol operations. The objective is to find the best districting plan so that the long-term average response time and workload variation can be minimized. A heuristic parameterized districting algorithm is developed to generate various district plans. The parameters in the seeds-growing algorithm can control the pattern or layout of the district plans.

In this dissertation, an Agent-Based (AB) simulation model and a Discrete-Event (DE) simulation model are built to evaluate districting plans generated by the parameterized districting algorithm. The AB model is developed using Java Repast in Geographical Information System (GIS) environment. It simulates the patrolling, dispatching and responding activities of police cars in actual road network and building locations of the city. The calls for services (CFS) incidents in the simulation are generated based on spatial and temporal patterns extracted from historical data. The high fidelity simulation provides good visualization for model validation but limits the computational efficiency. Inspired by the Hypercube Queuing Model, a Discrete-Event simulation model is developed using Java SE. It only keeps track of major events of police cars and thus improves the evaluation efficiency. A comparative study is conducted between the AB and DE simulation model.

In the simulation optimization procedure, three methodologies are developed to find the best district plan under simulation evaluations. In the Response Surface Methodology (RSM), the relationship between districting parameters in the districting algorithm and performance measures is studied using an iterative experimental design method for computer simulation. Fractional Factorial Design, Space Filling Design and Kriging Prediction are used to find optimal settings of important districting parameters. Good districting plans can be generated more efficiently and thus support the decision making process of police department. Another Simulated Annealing (SA) approach is developed based on an existing SA algorithm. The new approach defines the solution neighborhood by making relatively big changes on current plan, such as merging and cutting districts. Compared with the existing SA method, the new approach uses less iteration to converge and is more robust to deal with different adjacency patterns of geographical atoms. Genetic Algorithm (GA) is also applied to the optimization of police districting. The three simulation optimization methodologies are tested and compared in the application study of police districting of Charlottesville, VA, USA.