A Hybrid Algorithm for the Equal Districting Problem

The equal districting problem (EDP) arises in applications such as political redistricting, police patrol area delineation, sales territory design and facility service area design. The important criteria for these problems are district equality, contiguity and compactness. A mixed integer linear programming (MILP) model and a hybrid algorithm are proposed for the EDP. The hybrid algorithm is designed by extending iterative local search (ILS) algorithm with three schemes: population-based ILS, variable neighborhood descent (VND) local search, and set partitioning. The performance of the algorithm was tested on five areas. Experimentation showed that the instances could be solved effectively and efficiently.