县市级义务教育学校区位配置优化设计与实验

Optimal Location-allocation for County-level Compulsory School Site Selection Using GIS and Integer Linear Programming

合理规划学校布局是实现义务教育均衡发展和落实就近入学政策的一个重要途径。为满足县市级中小学校空间布局规划需求,本文以区位配置优化方法解决学校区位选址问题。以平均入学距离为目标,以学校总数、学校学额为约束条件,分别构建P中值指派规划和整型规划数学模型。根据学校与居民地之间的空间分布特征进行模型简化,使模型计算效率大幅度提升。因指派规划模型约束矩阵每列非零元素不超过2个,分枝切割算法能获得近似最优解(与最优目标之差小于0.01%);整型规划模型约束矩阵近似于完全单位模矩阵,分枝切割算法通常能获得最优解。在ArcGIS 10Geoprocessing框架中,整合ArcGIS网络分析、Coin-or Python线性规划建模工具PuLP1.4.7和线性规划软件Cplex 12,实现模型建模、模型解算和优化结果可视化。在配置Intel酷睿2双核2.44GHzCPU和2GB内存的计算机环境中,对于有1276个居民点和50所学校的县域进行网络分析、模型建模、模型结算和结果输出。优化结果表明:学校布局调整后学生平均入学距离明显降低,本文构建的优化模型在县市级较大规模的学校选址规划中具有实用价值。

This paper aims to develop an optimal location-allocation methodology for school site selection using GIS and integer programming.According to the nearby enrollment policy,the authors propose two linear programming models（boolean and integer） with constrains of total school number and school capacity.The models are simplified by eliminating the unreasonable school-residence links for reducing the number of decision variables and therefore solving the problems efficiently.Since the constraint matrix of the boolean model is a sparse matrix with two non-zero elements per row,it can be solved optimally with very small tolerance using branch and cut algorithm.The constraint matrix of the integer model is similar to the totally unimodualr matrix and can be solved optimally.In ArcGIS 10 geoprocessing framework,the school site-selection tool is designed by integrating ArcGIS network analysis,Coin-or linear programming modeler（PuLP） and linear programming solver Cplex 12.School site selection of a county region with 1276 resident points and 50 schools is tested successfully.The related network analysis,model building,model solving and result visualization can be implemented speedily in normal personal computer with Intel Dual-Core 2.44GHz CPU and 2GB memory.Case study shows that the mathematical models and solution method introduced in this paper are efficient,easy-to-use and practical for large-scale school location-allocation problems.The authors also argue that instead of using heuristic algorithms,many large-size location-allocation problems can be solved using branch and cut algorithm optimally or optimally with very small tolerance.