地球信息科学学报 ›› 2012, Vol. 14 ›› Issue (3): 299-304.doi: 10.3724/SP.J.1047.2012.00299

• 地球信息科学理论与方法 • 上一篇    下一篇

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

孔云峰1,2, 王震1   

  1. 1. 河南大学环境与规划学院,开封 475004;
    2. 河南大学中澳地理信息分析与应用研究所,开封 475004
  • 收稿日期:2012-02-25 修回日期:2012-05-04 出版日期:2012-06-25 发布日期:2012-06-25
  • 作者简介:孔云峰(1967-),男,河南省新安县人,博士,河南大学地理信息系统学科特聘教授、博士生导师。研究兴趣包括GIS分析与设计、空间分析及应用。E-mail: yfkong@henu.edu.cn
  • 基金资助:

    省部共建河南大学科研基金项目(SBGJ090605);河南省教育科学"十二五"规划课题(2011-KGHAD-0399)资助。

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

KONG Yunfeng1,2, WANG Zhen1   

  1. 1. College of Environment and Planning, Henan University, Kaifeng 475004, China;
    2. China-Australia Cooperative Research Center for Geoinformation Analysis and Applications, Henan University, Kaifeng 475004, China
  • Received:2012-02-25 Revised:2012-05-04 Online:2012-06-25 Published:2012-06-25

摘要:

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

关键词: 学校选址, 整型规划, 区位配置模型, GIS

Abstract:

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.

Key words: GIS, integer programming, location-allocation modeling, school site selection