Algorithms for the School Districting Problem

Abstract

This paper presents two algorithms for finding solutions to the problem of school districting, which is the dividing of an administrative area into some school districts consisting of several population units. The problem is formulated as a set partitioning problem, after having enumerated the feasible districts satisfying all the given requirements. An algorithm for finding an exact optimal solution is first proposed. Using the population units as indivisible elements, the first phase enumerates all the feasible districts which satisfy the given requirements, such as contiguity, capacity, and so on. The second phase determines the optimal school districting that minimizes the sum of the distances traveled by all students. Since the computation time of the exact algorithm increases very quickly as the number of population units increases, an improved algorithm is derived for finding an optimal or near-optimal solution within a reasonable computation time. This algorithm constructs the core of each school district before enumerating the feasible districts. The core of each school district is composed of the population units which are assigned to the school, with the minimal distances traveled until the given bound on the population is satisfied. Computation results show that the improved algorithm can find an optimal or near-optimal solution for a problem having 122 units within one minute.