县市级义务教育学校区位配置优化设计与实验
收稿日期: 2012-02-25
修回日期: 2012-05-04
网络出版日期: 2012-06-25
基金资助
省部共建河南大学科研基金项目(SBGJ090605);河南省教育科学"十二五"规划课题(2011-KGHAD-0399)资助。
Optimal Location-allocation for County-level Compulsory School Site Selection Using GIS and Integer Linear Programming
Received date: 2012-02-25
Revised date: 2012-05-04
Online 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所学校的县域进行网络分析、模型建模、模型结算和结果输出。优化结果表明:学校布局调整后学生平均入学距离明显降低,本文构建的优化模型在县市级较大规模的学校选址规划中具有实用价值。
孔云峰, 王震 . 县市级义务教育学校区位配置优化设计与实验[J]. 地球信息科学学报, 2012 , 14(3) : 299 -304 . DOI: 10.3724/SP.J.1047.2012.00299
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.
[1] 卢乃桂,董辉. 审视择校现象:全球脉络与本土境遇下的思索[J]. 教育发展研究, 2009 (20):1-6.
[2] 尹杰. GIS在教育资源布局规划中的应用[J]. 测绘通报, 2006(2):56-58.
[3] 王伟,吴志强. 基于Voronoi模型的城市公共设施空间布局优化研究——以济南市区小学为例 . 和谐城市规划——2007中国城市规划年会论文集, 2007,2529-2533.
[4] 张霄兵. 基于GIS的中小学布局选址规划研究 . 同济大学论文, 2008,50-61.
[5] 孔云峰. 基于GIS与线性规划的学校最优学区划分[J]. 武汉大学学报(信息科学版), 2012, 37(5): 513-515.
[6] Schrijver A. Theory of linear and integer programming[M]. Hoboken, New Jersey, USA: John Wiley & Sons, 1998,1-3.
[7] Teitz M B and Bart P. Heuristic methods for estimating the generalized vertex median of a weighted graph[J]. Operations Research, 1968,16(5):955-961.
[8] Densham P J and Rushton G. A more efficient heuristic for solving large p-median problems [J]. Regional Science,1992(71):307-329.
[9] Kirkpatrick S, Gelatt C D and Vecchi M P. Optimization by simulated annealing[J]. Science, 1983(220):671-680.
[10] Correa E S, Steiner M T A, Freitas A A,et al. A genetic algorithm for the p-median problem . Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001).San Francisco, CA, USA.2001,1268-1275.
[11] Jorge H J, Bhadury J and Batta R. On the use of genetic algorithms to solve location problems[J]. Computers & Operations Research, 2002(29):761-779.
[12] Elon S C and Maria T S. A genetic algorithm for solving a capacitated p-median problem[J]. Numerical Algorithms, 2004,35(2-4):373-388.
[13] Rolland E, Schilling D A and Current J R. An efficient tabu search procedure for p-median problem[J]. European Journal of Operational Research, 1996,329-342.
[14] Paulo M F and Nelida M S. An adaptive Tabu search algorithm for the capacitated clustering problem[J]. International Transactions in Operational Research, 1999, 6(6): 665-678.
[15] Dorigo M and Stützle T. Ant colony optimization[M]. 北京:清华大学出版社, 2004,1-8.
[16] Taylor R G, Vasu M L and Causby J F. Integrated planning for school and community: The case of Johnston County, North Carolina[J]. Interfaces, 1999, 29(1): 67-89.
[17] Malczewski J and Jackson M. Multicriteria spatial allocation of educational resources: An overview[J]. Socio-Economic Planning Sciences, 2000(34):219-235.
[18] Cropper M. GIS in school facility planning[J]. School Planning & Management, 2001, 42(2):56-60.
[19] Caro F, Shirabe T, Guignard M,et al. School redistricting: embedding GIS tools with integer programming[J]. Journal of the Operational Research Society, 2004(55):836-849.
/
| 〈 |
|
〉 |