School District Division Based On Hybrid Heuristic Algorithm

Making students fair and the student enrollment distance as short as possible are important principles for school district division.The division of the school district mainly includes single-school district division and multi-school district division.School district division needs to consider factors such as the number of school-age students,the community,the size of the school,and the traffic conditions.It is a complex zoning problem.At present,most of the literature is for single-school district division,and few about multi-school district division.The commonly used methods are mathematical model method and some classic heuristic algorithms.The mathematical model method has large computational complexity and high computational complexity.The heuristic algorithm is difficult to find the optimal solution within the specified time,and it is easy to fall into the local optimum.Therefore,we study the problems existing in the current algorithm for solving the school district partition problem.Under the idea of hybrid algorithm,three hybrid heuristic algorithms are proposed to solve the school district division problem.The research work of this paper mainly includes:?1?The theoretical knowledge of school district division is studied,and the principles,the factors and goals of school district division are analyzed.According to the principle of“school grouping first and students assigning second”,the school grouping model is constructed based on the principle of k-medoids algorithm.The school grouping is obtained under the constraints of moderate school size and at least one high-quality school in each group.?2?The student enrollment distance is calculated based on the spatial co-location pattern mining,Floyd algorithm and the road network map.From a practical point of view,the network model is constructed based on the spatial co-location model,and the shortest path distance between the pair of points is solved by the edge-based Floyd algorithm.In the single-school district division,the student enrollment distance is the distance from the student to the nearest school.In the multi-school district division,students have the opportunity to select the school.According to the probability assigned to the high-quality school,the distance from the student to the nearest school and the high-quality school can be weighted to calculate the enrollment distance.?3?Three hybrid heuristic algorithms,M-ILS-SA,M-ITS-SA and M-VND-SPP,are proposed to solve the school district division problem.M-ILS-SA algorithm combines the Iterated Local Search?ILS?algorithms and Simulated Annealing?SA?algorithms.M-ITS-SA algorithm combines the Iterated Tabu Search?ITS?algorithms and SA algorithms.M-VND-SPP algorithm combines the Variable Neighborhood Descent?VND?algorithm and the Set Partition Problem?SPP?.Two neighborhood search operators?1-0?₄ and?1-0?₈ are also proposed in the algorithm to expand the search range and improve the search speed.All of the three algorithms solve the problem of school district division under the multi-start and random search mechanism.Under multiple starts,multiple initial solutions are obtained,and the initial solution is optimized and re-optimized to obtain multiple optimization solutions.Finally,the optimal target function is introduced.The function finds an optimal solution from multiple optimization solutions as the final partitioning scheme.Experiments show that the proposed algorithms in this paper are applicable to single-school district division and multi-school district division,which can guarantee spatial continuity,have good optimization ability and convergence,and achieve global optimization and fast convergence.