Journal of Geo-information Science >
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
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.
KONG Yunfeng, WANG Zhen . Optimal Location-allocation for County-level Compulsory School Site Selection Using GIS and Integer Linear Programming[J]. Journal of Geo-information Science, 2012 , 14(3) : 299 -304 . DOI: 10.3724/SP.J.1047.2012.00299
[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.
/
| 〈 |
|
〉 |