基于分级选址模型的学校选址问题研究

基于分级选址模型的学校选址问题研究万波1,2，杨超1，黄松1，董鹏1(1.华中科技大学管理学院，湖北武汉430074；2.江汉大学教务处，湖北武汉430056)摘要:学校作为一类非常重要的公共服务设施，其选址问题引起了各国学者们的广泛关注。考虑到我国中小学选址问题的特性，本文引入分段效用函数，综合考虑距离、服务质量等多种选址因素，提出基于效用函数的分级的带容量限制的中位模型。模型约束条件包括需求的全覆盖、设施的最小容量约束、需求点就近分配给设施点、需求点单一分配给设施点及开放与关闭设施数目限制等。本文使用拉格朗日松弛算法，以武汉市经济技术开发区为例，就目前学校选址及分配的合理性问题、需求波动后的重新选址及分配问题和学校最小容量的合理设置问题进行了分析。关键词：学校选址；中位问题；效用函数；拉格朗日松驰算法中图分类号：O22文献标识码：AASchoolLocationProblemBasedonHierarchicalLocationModelWANBo,YANGChao,HUANGSong,DongPeng(1.SchoolofManagement,HuazhongUniversityofScience&Technology,Wuhan430074,China；2.RegistrationCenter，JianghanUniversity，Wuhan430056，China)Abstract:Schoolbeingonekindofveryimportantpublicservicefacilities,itslocationhasarousedwideattentionfromscholarsindifferentcountries.ConsideringthecharacteristicsofelementaryandsecondaryschoollocationinChina,sub-utilityfunctionisadoptedandavarietyoflocationfactorssuchasdistance,servicequality,etchavebeentakenintoaccounttosetuphierarchicalmedianmodelwithcapacityconstraintsandutilityfunction.Theconstraintsofthemodelincludethewholecoverageofdemand,theminimumcapacityconstraintoffacilities,closest-assignment,single-assignment,andthelimitednumberofopenedandclosedfacilities.Asareal-worldcase,thelagrangianrelaxationalgorithmhasbeenusedtosolvetheschoollocation-allocationproblemofWuhanEconomicandTechnologicalDevelopmentZone,inwhichthreescenariosarediscussed:location-allocationrationalityatthepresent,re-locationandallocationafterfluctuationsindemand,andreasonableminimumcapacityconstrains.Keywords:schoollocation;medianproblem;utilityfunction;lagrangianrelaxationalgorithm1引言城市公共服务设施是指为市民提供公共服务产品的各种公共性、服务性设施，按照具体的功能特点可分为教育、医疗卫生、交通、体育等设施。公共服务强调社会效益，同时注重公民享有的权利，是反映城市居民生活质量的重要标志[1]。公共服务设施选址涉及服务的便捷性，服务质量与服务水平以及需求者对服务的需求偏好等众多因素，且与和谐社会建设息息相关，该问题是城市规划和城市发展的重要问题。学校作为一类非常重要的公共服务设施，其选址比其它类型公共设施选址问题更为复杂，因而引起了各国学者们的广泛关注。Moore和ReVelle[2]提出基于分级的带容量限制的覆盖选址模型，求各级服务设施覆盖人口最大化。Pizzolato等[3]利用无容量约束的P-中位模型，以所有居民到学校的总行走距离最小化为目标，对巴西的学校选址问题进行了研究。Antunes等[4]将动态规化模型用于葡萄牙学校网络规划，模型考虑了学校开关情况及学校规模的扩大与缩小情况。Pizzolato等[5]将ArcViewGIS软件运用于选址问题中，利用P-中位模型对巴西学校选址与分配现状进行了研究，并就有容量约束与无容量约束两种情况进行了选址规划。Dohn等[6]将无容量约束设施选址模型(UFL)进行扩展，考虑设施数目及设施的最小容量约束，利用线性规划及混合整数规划方法进行求解与讨论。Şahinç等[7]认为学校选址问题具有单流、非嵌套、需求对于服务水平的一致分配属性。Teixeira和Antunes[8]提出基于嵌套式并带容量限制的分级中位模型，并就三种类型的空间分配模式：单一分配、就近分配与路径分配进行了讨论。高阳等[9]综合运用层次分析法和重心选址法对上海某区学校选址问题进行了研究。收稿日期：2010-07-05基金项目：国家自然科学基金项目(70871044);教育部新世纪优秀人才支持计划项目(NCET-06-0653)作者简介：万波(1972-)，男，湖北汉阳人，博士研究生，主要研究方向：管理定量分析，现代管理理论与方法。本文研究了一类基于分级选址模型的学校选址问题，利用基于引力模型的分段效用函数来刻画学校对居民点的效用，以总效用最大化为目标，建立了基于效用函数的分级的带容量限制的选址模型。本文的创新之处在于在刻画学校对居民点的效用时，不仅考虑了距离因素，还综合考虑了服务质量，外部环境，道路交通状况，所提供的延伸服务等多种因素的影响，对非嵌套式的学校选址问题进行了探讨。2模型的建立2.1模型背景我国属于发展中国家，人口众多，面临着教育资源相对有限与老百姓对优质教育资源需求日益增长的矛盾。同时，随着计划生育国策的深入贯彻落实，我国人口得以有效控制，特别是适龄入学人口呈负增长态势，从全国情况来看，根据《中国人口统计年鉴》数据显示，人口出生率由2002年的12.86‰降低至2009年的12.13‰。从武汉市情况来看，2008年招生人数与毕业人数相比，普通中小学共减少44990人，占当年毕业总人数的17.86%。此外，农村城镇化步伐的加快及城区改造等众多因素，导致新一轮的中小学布局的调整势在必行。根据我国特殊国情，我们考虑的学校类设施选址问题具有以下特点：(1)需求层次的多样性。即不同的年龄段的学生需要进入不同类型的学校学习。(2)需求的波动性。随着人口出生率的变化及人口迁徙等因素，致使人口数量发生变化，导致需求量的波动，从而需要对服务设施进行重新选址与分配。(3)需求偏好。除距离外，设施的服务质量、外部环境、道路交通状况、所提供的延伸服务等因素均为需求者在选择服务时需考虑的因素。(4)教育的公平性。保障教育公平的根本措施是合理配置教育资源，而合理配置教育资源的目标就是保证学生就近入学与保证学生充分享受优质教学资源[10]。(5)成本与效用均衡问题。一方面，学校需要为尽可能多的需求者提供优质服务，尽可能满足需求者的需求偏好，从而社会效益最大化；另一方面，学校设置最小容量约束，保证规模效应，因此需要寻求系统社会效益最大化和运行成本最小化之间的均衡。2.2基于效用函数的分级的带容量限制的中位模型(UHCM)根据我国学校选址问题的特点，本文在传统中位模型的基础上，引入分段效用函数，提出基于效用函数的分级的带容量限制的中位模型(UHCM)，对学校选址问题进行求解。该模型需要考虑需求的全覆盖、设施的最小容量约束、需求点就近分配给设施点、需求点单一分配给设施点及开放与关闭设施数目限制等约束条件，其目标是求取系统总效用最大化。模型的有关参数定义如下：S：需求水平的集合，1,,Sns；I：需求点的集合，1,,In；0sJ：已经存在的s级水平的设施的集合；1sJ：新增的s级水平的设施集合；J：所有设施的集合，01ssJJJ；isw：需求点i关于s级水平的需求数量；jsb：定位于j点的s级水平的设施的最小容量；sp：新增的s级水平的设施数；sq：已存在的s级水平的设施要关闭的最大数目；ijsu：定位于j点的提供s级水平服务设施对于需求点i的效用；ijd：需求点i到设施候选点j的距离；sjA：设施候选点j提供s级水平服务设施的引力因子；s：引力敏感度参数；1sL：需求点i与设施点j的最小临界距离；2sL：需求点i与设施点j的最大临界距离。同时定义如下的决策变量：ijsx：源于需求点i的对于s级水平的需求分配给j点设施的份额；jsy：如果s级水平的设施定位于j点，1jsy；否则为零。首先给出分段效用函数定义[11]：1212212,,0,sssjijssijijssjsijsssijsAdLLduALdLLLdL图1分段效用函数图上述效用函数如图1所示，当1ijsdL时，效用完全由服务设施的引力决定，不受距离的影响；当12sijsLdL时，距离对需求者选择服务设施偏好有比较灵敏的反应；而当2ijsdL时，其效用为0，不管设施如何提高引力水平，需求者都不会考虑选择该服务设施[12]。模型目标函数及约束如下：maxijsisijsiIsSjJuwx(1)Subjectto：1,ijsjJx,,iIsS(2),jsijsyx,,iIjJsS,(3),isijsjsjsiIwxby,,jJsS(4)|,ikijiksjskJddxy,,,iIjJsS(5)1,sjssjJyp,sS(6)00||,sjsssjJyJq,sS(7){0,1},{0,1},ijsjsxy,,iIjJsS(8)其中，(1)式表示求所有学校的服务效用总和最大；(2)式确保源于所有需求点的所有水平的需求都能得到满足；(3)式表示一个特定水平的需求仅仅能被相应水平的设施提供的服务所满足；(4)式表示每个服务设施点的最小容量限制；(5)式表示每一种水平的需求必须分配给最近的提供相同服务水平的设施；(6)式和(7)式限定了新设施开放的数目与可关闭的已存在的设施的数目；(8)式表示决策变量的取值范围。3求解算法分析(6)-(7)式可知，当关闭已有的设施数目达到上限sq且不新增开任何新的设施时，选址方案的设施数目达到最小值0||ssJq，如果不关闭任何已有的设施而增开新的设施数目达到最大值sp时，选址方案的设施数目达到最大值0||ssJp，所以约束条件(6)-(7)式等价于如下约束条件：0100||||ssssjsssjJJJqyJp，sS(9)因为中位问题已经被证明是NP-Hard问题[13]，而上述问题UHCM是考虑容量约束与设施数目约束的中位问题，因此也是NP-Hard问题，没有有效的算法。拉格朗日松弛算法的基本原理是将造成问题复杂的约束吸收到目标函数中，并使得目标函数仍保持线性，从而使得问题的求解过程变得简单。其思路是将复杂的量和各自的对偶变量的乘积加载到目标函数上作为惩罚项，形成拉格朗日问题。该算法已经广泛运用于大型的优化调度问题的求解。因此，本文采用拉格朗日松弛算法求解。松弛约束条件(2)式和(4)式，得到原UHCM问题的拉格朗日对偶问题(D)：ijd01sL2sL1sL2sLijsussjA,,minmax(1)()ijsisijsisijsjsisijsjs