摘要：本系统在遵守中小学招生政策的前提下，基于就近原则，结合贪心算法和蛮干算法，设计中小学招生划片模型和算法，实现了学校宏微观规划、微观规划和片区拆迁规划功能，使学生能够“就近入学”，最优化利用教育资源，为中小学招生划片提供参考依据。
论文关键词：就近原则,招生划片,片区拆迁,贪心算法
本文研究的系统属于厦门市教育地理信息管理系统的子系统。本系统严格遵守厦门市中小学生招生政策，并根据目前中小学校分布情况，实现了动态分区划片功能。在学校规模、均用地、配套设施、安全方面等满足一定指标的情况下，使学生能够“就近入学”，最优化利用教育资源。
1. 招生划片模型
本系统分区划片的主要原则是就近原则，最优化利用教育资源。要求某一地区全体学生在整体上能够就近入学，并不是仅保证个别学生在最近的学校入学。换句话说，确实按照越靠近哪所学校，就在那所学校学习，但前提是能够满足学校承载力，这样才有实际意义。此有三种情况特此说明如下：
图1 图2 图3
（1）如图1所示，小区一附近只有一所学校A，因而小区一的学生只能被分配到学校A就读，而小区五附近有两所学校，虽然小区五离学校A的距离甚至比小区一更近，但学校A的招生名额已满，因此只能安排到邻近的学校B。这个不违反就近原则。这样综合考虑后，既充分利用了教育资源，又使得的总路程最短。
（2）如图2所示，由于招收名额有限，同一个小区的学生不能到同一所学校就读，如小区五只有20名能上学校A，而另外的230只能上学校B，这时只能采取随机抽号的方法来决定哪20名去学校A，另外的230名去学校B。现在采取的方案就是要拆分小区五。
（3）如图3所示，与（2）类似，由于学校A招收名额有限，同在小区五的学生不能均到距其最近的学校A就读，但是小区四、五与学习A的距离相差不大。可以采取2种方案，第一种方案如（2）情形，即采取拆分小区五；第二种情况是，由于距离差别不大的情况下，采取不拆分小区五，而直接把小区五的学生分到学校A，而把小区四的学生分到学校B，这样使得整个小区的学生可以一起上学。这两种方案孰优孰劣，需要听取民意，不过笔者认为第一种方案更可取。
基于上述原则，设计模型如下：
参数说明：D为综合加权距离；
为第j个社区和第i所学校间的距离；
为第j个社区分配给第i所学校的学生数；
是第j个社区的总学生数；
和
为第i所学校招生规模的上下限。
目标函数为综合加权距离的最小值，此为就近原则的体现。约束条件即每个学生对应一所学校，且划分到某校的人数尽可能的接近招生名额数，以避免过饱和同时达到最优化利用教育资源。
2. 算法设计
蛮干算法以及贪心算法均可求解上述模型。蛮干算法即穷举法，按照一定的次序，找出所有可行解，从而得到最优解。 此算好的优点是一定能够找到最优解，但是算法效率低，运行速度慢；贪心算法就是按照某种次序做出一系列的决定（总是选取当前情况下最优的决定，属于局部最优），使得某个决定仅作一次，且不再重复。这种算法要比蛮干算法在运行速度上快很多，但是，遗憾的是贪心算法并不总能导致最优的结果。在求解过程中我们将蛮干与贪心这两种算法有效的结合，效率大大提高，且大多情况下可以得到最优解。
算法流程如下：
图4 分区划片算法流程图 图5 特别分配算法流程图
3. 实例验证
我们选用厦门市进行实验，为确保数据真实可靠，系统中均采用来自福建省统计软件的数据和统计局人口普查数据，结合系统可依据实际情况做出适当调整，每个小区或街道到学校的距离的采样过程中，我们采取把小区或街道看成一个几何形状，取其几何中心，并取其上学人数，抽象成一个点数据。同时也把学校看成一个点数据，通过两点间沿街道的最短路径当作小区或街道到学校的路程；在学校实际已稳定就读的，在招生规模中排除，模型中主要考虑新生入学人数以及转入转出人数，以保持已就读学生的划片区稳定性。
为保持现有招生结构的稳定一致，系统中按照目前给定划片区域及其情况作为初始状态。利用当前数据对小学进行重新分区划片，为了使结果具有一定的抗干扰能力，系统并非一步到位，将小区（或约特定生源）划分到具体指定的某个学校，而是利用聚类思想，先进行宏观的处理，将整个湖里区划分成如图5中蓝色所示的大的片区，每个片区中容纳适当的小学数量，即一个片区对应多所小学，多个小区。片区划分之后，再利用分区划片模型对每个小区的生源进行微观的处理，如图6。图5中红色部分为原有电脑派位系统得到的一对一划分结果，即一个片区中只有一个学校，蓝色为我们系统实验结果，一个片区对应多所学校。
旧城改造更新以及新区开发建设速度的加快，大部分学校周边已规划建设或更新改造，学校扩建增容难度加大，为解决这个问题，本系统设计了拆迁划片微调功能，如图7所示。以前埔社区为例，依实际情况调整拆迁学生人数，从“可选片区”中选择迁往目的片区，分析结果如表1所示：即把前埔社区的一部分拆除，一部份迁往蔡塘社区，而另一部分迁往长青社区。
图5 厦门市湖里区宏观规划示意图 图6 厦门市瑞景社区微观招生划片示意图
图7 拆迁划片微调功能 表1 前埔社区拆迁划片微调结果
4.总结
本系统根据现有学校的招生划片范围、近年招生数以及我市人口普查数据以及区各年龄段人口的统计数据，采用GIS的空间分析功能，进行学校合理招生片区划分，解决旧城改造中学生就学问题。本系统对学校布局采用宏观的聚类，这样的规划更便于以后的调整，更易于应急操作的调整，抗干扰能力大大增强，为教育部门提供辅助决策支持，具有一定的参考意义。本系统也存在不足之处，数据采集困难，将社区看作点处理，难免存在空间分析上的误差，需要进一步完善。由于篇幅限制，本文算法只给出了初始解，将另文讨论其优化问题。
