地理学报 ›› 2017, Vol. 72 ›› Issue (2): 256-268.doi: 10.11821/dlxb201702006
收稿日期:
2016-07-04
修回日期:
2016-10-22
出版日期:
2017-02-15
发布日期:
2017-04-28
作者简介:
作者简介:孔云峰(1967-), 男, 博士, 博士生导师, 主要从事空间分析、空间优化等研究。E-mail:
Yunfeng KONG1(), Yanfang ZHU1, Yujing WANG1,2
Received:
2016-07-04
Revised:
2016-10-22
Online:
2017-02-15
Published:
2017-04-28
摘要:
中国城市义务教育学校采用单校划片或多校划片的方式确定招生范围,落实就近入学的法律要求。针对多校划片这一新的学校分区问题,提出“先学校分组,再学生分派”的策略进行划片,并设计了学校分组线性规划模型和学校分区混合元启发算法。分区算法包括初始解构造、邻域搜索算子、破坏重建扰动、集合划分问题(SPP)建模与求解等基本模块,在多启动迭代局部搜索(ILS)算法框架中进行问题求解。通过多启动、随机搜索、破坏重建扰动等机制提升算法的多样性,并引入SPP模型提升算法的全局寻优能力。选择一个县级市和一个市辖区分别进行学校划片实验,结果表明:混合元启发算法优化性能优异且收敛性好,适用于求解单校划片和多校划片问题;SPP模型在单校划片问题中具有明显的优势。
孔云峰, 朱艳芳, 王玉璟. 学校分区问题混合元启发算法研究[J]. 地理学报, 2017, 72(2): 256-268.
Yunfeng KONG, Yanfang ZHU, Yujing WANG. A hybrid metaheuristic algorithm for the school districting problem[J]. Acta Geographica Sinica, 2017, 72(2): 256-268.
表1
学校划片结果统计"
案例区 | 划片 数量 | 数学模型 | 多启动ILS(M-ILS)算法 | 多启动ILS-SPP(M-ILS-SPP)算法 | ||||||
---|---|---|---|---|---|---|---|---|---|---|
入学距离(km) | 分区 连续 | 入学距离 均值(km) | 最好入学 距离(km) | 标准差(%) | 入学距离 均值(km) | 最好入学 距离(km) | 标准差(%) | SPP改进(%) | ||
GY | 4 | 107648.06 | 是 | 107648.06 | 107648.06 | 0.00 | 107648.06 | 107648.06 | 0.00 | 0.00 |
GY | 5 | 99098.15 | 是 | 99098.15 | 99098.15 | 0.00 | 99098.15 | 99098.15 | 0.00 | 0.00 |
GY | 6 | 97819.38 | 否 | 99670.59 | 99570.09 | 0.12 | 99546.57 | 99536.49 | 0.02 | 0.12 |
GY | 7 | 97359.92 | 否 | 99212.62 | 99069.17 | 0.23 | 99034.18 | 99025.61 | 0.02 | 0.18 |
GY | 8 | 91286.51 | 否 | 94368.16 | 94260.15 | 0.10 | 94210.98 | 94192.28 | 0.03 | 0.17 |
GY | 39 | 81321.49 | 否 | 84626.82* | 83713.52* | 1.10 | 84872.52 | 84500.09 | 0.57 | - |
ZY | 3 | 2861.76 | 否 | 2863.86 | 2862.01 | 0.05 | 2863.86 | 2862.01 | 0.05 | 0.00 |
ZY | 4 | 2654.27 | 否 | 2661.99 | 2659.30 | 0.07 | 2661.94 | 2659.30 | 0.07 | 0.00 |
ZY | 5 | 2604.72 | 否 | 2609.60 | 2606.35 | 0.06 | 2609.47 | 2606.35 | 0.06 | 0.00 |
ZY | 15 | 2610.82 | 否 | 2676.91 | 2650.10 | 0.86 | 2666.96 | 2644.65 | 0.67 | 0.37 |
表2
算法及主要模块计算时间(s)统计"
案例区 | 分区数量 | 总时间 | 构造初始解 | 邻域搜索 | 破坏重建扰动 | 空间连续检测 | 分区池更新 | SPP模型求解 |
---|---|---|---|---|---|---|---|---|
GY | 4 | 13.13 | 3.70 | 5.88 | 3.15 | 2.58 | 0.17 | 0.22 |
GY | 5 | 13.77 | 4.03 | 6.55 | 2.79 | 2.79 | 0.17 | 0.30 |
GY | 6 | 22.13 | 4.27 | 13.30 | 3.94 | 5.21 | 0.31 | 0.52 |
GY | 7 | 25.97 | 4.42 | 17.47 | 3.49 | 4.37 | 0.24 | 0.48 |
GY | 8 | 30.89 | 4.52 | 20.21 | 4.93 | 5.63 | 0.41 | 1.11 |
GY | 39 | 278.80 | 6.47 | 227.46 | 37.58 | 5.90 | 1.89 | 6.94 |
ZY | 3 | 35.44 | 2.28 | 22.16 | 9.20 | 15.77 | 0.58 | 1.67 |
ZY | 4 | 36.00 | 2.31 | 24.69 | 6.70 | 13.89 | 0.71 | 2.19 |
ZY | 5 | 37.38 | 2.37 | 26.39 | 5.58 | 10.49 | 0.75 | 2.88 |
ZY | 15 | 195.51 | 3.06 | 148.32 | 33.01 | 29.28 | 1.34 | 10.53 |
[1] |
Koenigsberg E.Mathematical analysis applied to school attendance areas. Socio-Economic Planning Sciences, 1968, 1(4): 465-475.
doi: 10.1016/0038-0121(68)90003-7 |
[2] |
Franklin A D, Koenigsberg E.Computed school assignments in a large district. Operations Research, 1973, 21(2): 413-426.
doi: 10.1287/opre.21.2.413 |
[3] |
Heckman L B, Taylor H M.School rezoning to achieve racial balance: A linear programming approach. Socio-Economic Planning Sciences, 1969, 3(2): 127-133.
doi: 10.1016/0038-0121(69)90004-4 |
[4] |
Mckeown P G, Workman B.A study in using linear programming to assign students to schools. Interfaces, 1976, 6(4): 96-101.
doi: 10.1287/inte.6.4.96 |
[5] |
Jennergren L P, Obel B.A study in the use of linear programming for school planning in Odense. Journal of the Operational Research Society, 1980, 31(9): 791-799.
doi: 10.1057/jors.1980.146 |
[6] |
Schoepfle O B, Church R L.A new network representation of a "classic" school districting problem. Socio-Economic Planning Sciences, 1991, 25(3): 189-197.
doi: 10.1016/0038-0121(91)90017-L |
[7] |
Sutcliffe C, Board J A, Cheshire P C, et al.Goal programming and allocating children to secondary schools in reading. Journal of the Operational Research Society, 1984, 35(8): 719-730.
doi: 10.1057/jors.1984.148 |
[8] |
Caro F, Shirabe T, Guignard M, et al.School redistricting: Embedding GIS tools with integer programming. Journal of the Operational Research Society, 2004, 55(8): 836-849.
doi: 10.1057/palgrave.jors.2601729 |
[9] |
Ferland J A, Guénette G.Decision support system for the school districting problem. Operations Research, 1990, 38(1): 15-21.
doi: 10.1287/opre.38.1.15 |
[10] | Maravalle M, Simeone B.A spanning tree heuristic for regional clustering. Communications in Statistics-Theory and Methods, 1995, 24(3): 625-639. |
[11] |
Assunção R M, Neves M C, Câmara G, et al.Efficient regionalization techniques for socio-economic geographical units using minimum spanning trees. International Journal of Geographical Information Science, 2006, 20(7): 797-811.
doi: 10.1080/13658810600665111 |
[12] |
Guo D.Regionalization with dynamically constrained agglomerative clustering and partitioning (REDCAP). International Journal of Geographical Information Science, 2008, 22(7): 801-823.
doi: 10.1080/13658810701674970 |
[13] |
Openshaw S.A geographical solution to scale and aggregation problems in region-building, partitioning and spatial modelling. Transactions of the Institute of British Geographers, 1977, 2(4): 459-472.
doi: 10.2307/622300 |
[14] |
Openshaw S.An optimal zoning approach to the study of spatially aggregated data//Masser I, Brown P. Spatial Representation and Spatial Interaction. Springer US, 1978: 95-113.
doi: 10.1007/978-1-4613-4067-6_5 |
[15] |
Sammons R.A simplistic approach to the redistricting problem//Masser I, Brown P. Spatial Representation and Spatial Interaction. Springer US, 1978: 71-94.
doi: 10.1007/978-1-4613-4067-6_4 |
[16] |
Kim K, Dean D J, Kim H, et al.Spatial optimization for regionalization problems with spatial interaction: A heuristic approach. International Journal of Geographical Information Science, 2016, 30(3): 451-473.
doi: 10.1080/13658816.2015.1031671 |
[17] | Browdy M H.Simulated annealing: An improved computer model for political redistricting. Yale Law & Policy Review, 1990, 8(1): 163-179. |
[18] | Macmillan W, Pierce T.Optimization modelling in a GIS framework: the problem of political redistricting//Forthering S, Rogerson P. Spatial Analysis and GIS. Taylor and Francis, 1994: 221-246. |
[19] |
Openshaw S, Rao L.Algorithms for reengineering 1991 Census geography. Environment and Planning A, 1995, 27(3): 425-446.
doi: 10.1068/a270425 pmid: 12346252 |
[20] | Duque J C, Church R L.A new heuristic model for designing analytical regions//North American Meeting of the International Regional Science Association, Seattle, 2004. |
[21] |
Guo D, Jin H. iRedistrict: Geovisual analytics for redistricting optimization. Journal of Visual Languages & Computing, 2011, 22(4): 279-289.
doi: 10.1016/j.jvlc.2011.03.001 |
[22] |
Ko J, Nazarian E, Nam Y, et al.Integrated redistricting, location-allocation and service sharing with intra-district service transfer to reduce demand overload and its disparity. Computers, Environment and Urban Systems, 2015, 54: 132-143.
doi: 10.1016/j.compenvurbsys.2015.07.002 |
[23] | Bacao F, Lobo V, Painho M, et al.Applying genetic algorithms to zone design. Soft Computing, 2004, 9(5): 341-348. |
[24] |
Wei B C, Chai W Y.A multiobjective hybrid metaheuristic approach for GIS-based spatial zoning model. Journal of Mathematical Modelling and Algorithms, 2004, 3(3): 245-261.
doi: 10.1023/B:JMMA.0000038615.32559.af |
[25] |
Xiao N.A unified conceptual framework for geographical optimization using evolutionary algorithms. Annals of the Association of American Geographers, 2008, 98(4): 795-817.
doi: 10.1080/00045600802232458 |
[26] | Fraley G, Jankowska M, Jankowski P.Towards memetic algorithms in GIScience: An adaptive multi-objective algorithm for optimized delineation of neighborhood boundaries//GIScience Conference, Zurich, Switzerland, 2010. |
[27] |
Kalcsics J.Districting problems//Laporte G, Nickel S, da Gama F S. Location Science. Springer, 2015: 595-622.
doi: 10.1007/978-3-319-13111-5_23 |
[28] |
Duque J C, Ramos R, Surinach J, et al.Supervised regionalization methods: A survey. International Regional Science Review, 2007, 30(3): 195-220.
doi: 10.1177/0160017607301605 |
[29] |
Keane M.The size of the region-building problem. Environment and Planning A, 1975, 7(5): 575-577.
doi: 10.1068/a070575 |
[30] |
Shirabe T.A model of contiguity for spatial unit allocation. Geographical Analysis, 2005, 37(1): 2-16.
doi: 10.1111/j.1538-4632.2005.00605.x |
[31] |
Shirabe T.Districting modeling with exact contiguity constraints. Environment and Planning B: Planning and Design, 2009, 36(6): 1053-1066.
doi: 10.1068/b34104 |
[32] |
Duque J C, Church R L, Middleton R S, et al.The p-regions problem. Geographical Analysis, 2011, 43(1): 104-126.
doi: 10.1111/j.1538-4632.2010.00810.x |
[33] |
Kong Yunfeng, Wang Zhen.Optimal location-allocation for county-level compulsory school site selection using GIS and integer linear programming. Journal of Geo-Information Science, 2012, 14(3): 299-304.
doi: 10.3724/SP.J.1047.2012.00299 |
[孔云峰, 王震. 县市级义务教育学校区位配置优化设计与实验. 地球信息科学学报, 2012, 14(3): 299-304.]
doi: 10.3724/SP.J.1047.2012.00299 |
|
[34] |
Fotheringham A S, Densham P J, Curtis A, et al.The zone definition problem in location-allocation modeling. Geographical Analysis, 1995, 27(1): 60-77.
doi: 10.1111/j.1538-4632.1995.tb00336.x |
[35] | Kong Yunfeng, Lv Jianping.Spatial modeling and analysis of the nearby school enrollment: A case study of the junior middle schools in Gongyi City, Henan Province. Geography and Geo-Information Science, 2011, 27(5): 87-90. |
[孔云峰, 吕建平. 就近入学空间模型分析: 以河南省巩义市初级中学为例. 地理与地理信息科学, 2011, 27(5): 87-90.] |
No related articles found! |
|