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 some 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. Experimenta-tion showed that the instances could be solved effectively and efficiently.