文摘
科学的位置选择的学校是一个重要的方式来优化教育资源的配置,提高操作的效率的学校,,实现教育的均衡发展,尤其是在农村地区。许多研究认为学校的位置,但大多数人都忽略了交通网络的影响条件和时间成本差异引起的不同的速度在不同路况下旅行。本研究的目的是为学生总运输成本降到最低,为新的学校建设成本,道路的建设和升级成本与旅游交通网络时间的不确定性表示不同的旅行时间场景。这个问题提出了一个混合整数规划模型。此外,混合模拟退火算法用于解决这个问题。最后,使用一个实际的案例研究说明了数学模型的应用。结果表明,交通网络具有重要影响的优化位置农村学校,和改善交通网络条件可以大大减少所需的时间为学生前往学校。
1。介绍
19全国代表大会的报告的中国共产党提出“农村振兴的战略。农村振兴“的重要任务是振兴教育。学校位置,包括规划和布局学校空间的区域,是振兴的关键部分地区和分配教育资源的一个重要方面(1]。基于交通网络优化学校的位置考虑有两个方面:一是减少学生的旅行费用,另一个是减少基础设施成本通过最小化需要新建或升级道路和设施。特别是,因为“国务院决定基础教育改革和发展”是在2001年出版2),合理规划和布局在农村地区中小学从地方政府已经收到越来越多的关注。1987年,前中国国家教育委员会明确表示,学生的上学时间不超过45分钟。此外,考虑到山地环境建设的高成本,政府部门应该减少学校和道路建设的成本。考虑预算限制道路和学校建设、研究方法来减少学生上学的时间,同时优化学校的位置变得越来越紧迫。在这种情况下,典型的中国农村地区,本研究的目标是最小化总旅行费用对于学生,学校设施建设成本,道路的建设和升级成本。提高农村学校系统的有效运行,必须使用当前的基础设施,必须做出重要决定在哪里建一所新学校,升级现有的道路或构造一个新的道路。
1.1。学校地理位置相关的模型
学校的位置是一个设施选址问题。最早的科学研究设施选址是韦伯(3)确定最优工厂仓库的位置。因为学校提供了一个非常重要的公共服务,学校定位问题已经吸引了许多学者的关注。之后很多学者的系统研究,设施选址的理论已经成熟了。Tewary et al。4)使用最大覆盖模型来研究如何最大化人口覆盖在一个最大距离与固定数量的学校旅行。Pizzolato et al。5)检查基本公立学校的位置在一个大的城市设置使用运筹学技术的un-capacitated p-median模型被用来减少整体residence-to-school距离之和。随后,研究认为学校明确和位于学校大小不同的能力。通过构建一个动态(multiperiod)最优模型,安图内斯(6)制定规划建议在葡萄牙几个学校网络的进化。这个模型允许uncapacity减少设备关闭或大小以及设施开放和规模扩张,规模有限的一组预定义的标准。Pizzolato et al。7)应用地理信息系统(GIS)技术学校定位问题评估巴西学校的布局两种情况与能力,没有能力(p-median模型)。特谢拉和安图内斯8)提出了一个离散的层次位置模型为公共设施规划,使用p-median模型与能力,分配到最近的学校可用容量。哈斯et al。9)开发了一个模型的位置规划学校网络的标准化的期望效用最大化所有学生考虑能力约束和给定的预算为学校网络。Delmelle et al。10)提出了一个multiperiod生产中等学校的网络设施选址规划模型最小化运输成本同时功能成本受到预算约束。一些学者研究了学校专门为中国位置的问题。小张和小王11]重心模型,应用GIS技术和使用最大的福利模式,p-center模型来研究老年人大学的位置。彭和王12)相比的优缺点p-center模型和p-gravity中心模型和改进p-gravity中心模型为最优开发决策支持系统基于GIS技术的农村小学的位置。基于彭和王的12)研究,戴et al。1]添加约束学校的规模和提高了p-center重力模型来研究小学的位置。
1.2。设施选址和网络设计
古典设施选址问题包括一些数量的设施位于一个给定的网络来满足一组客户方面的一些限制(13]。网络设计问题地址决定选择一个数量的候选人之间的联系网络节点以减少建设和旅游成本的总和(14,15]。从本质上讲,网络设施位置设计问题(FLNDP)是一个设施选址和网络设计问题;Daskin et al。16]介绍了FLNDP的第一个模型。它不仅注重设施区位的选择也考虑交通道路网的最优布局设计。该设施location-network设计方法可以有效地解决农村公共服务设施的最优位置问题[17]。他们认为建造新设施的成本可能远远高于改变底层的交通和底层网络配置改变的假设。然后,Melkote [17)设施位置设计问题分为三种模式:un-capacitated设施选址网络设计问题(UFLNDP),生产配送设施选址网络设计问题(CFLNDP)和最大覆盖位置网络设计(MCLNDP)。在此基础上,许多学者扩展研究FLNDP [18- - - - - -23]。
1.3。设施位置不确定的环境下
一般来说,随机优化和鲁棒优化(RO)条件下用于解决优化问题的不确定性。随机优化假设不确定参数的概率分布,并最小化的目标是找到一个解决方案的预期成本。相比之下,离散的场景或一个连续范围是假定在罗依。罗的目标是最小化最坏的成本或者后悔24]。基于集合的RO被索伊斯特首次引入的概念(25]。Kouvelis et al。26]的概念首次引入p-robustness解决制造系统布局规划问题;每个场景的相对后悔 。斯奈德和Daskin27]随后提出了p-robustness措施,将两者的优势结合起来的随机优化和RO方法的预期成本最小化,而相对后悔在每个场景中受到限制。RO处理不确定性和随机优化是频繁的在位置模型,综述的欧文和Daskin [28和斯奈德24]。不幸的是,FLNDPs不确定性的条件下,与其他类型的位置问题,得到了有限的研究的关注。Rahmaniani和Shafia29日]分析了最大覆盖FLNDPs,包括不确定性和综合优化模型的提出解决方案。Shishebori和Yousefi Babadi [30.)提出了一个有效的线性规划模型寻找一个健壮和可靠的解决方案到医疗服务中心位置网络设计问题。
许多研究已经检查了学校的最佳位置。据我们所知,大多数以前的研究都忽略了交通可达性的影响,农村学校的位置和时间成本差异引起的不同的速度在不同路况下旅行。此外,以往的研究未能考虑是否在经济上更合适的升级道路(或构造一个新的路)开办新学校。此外,没有哪个学校留学地点问题一起被认为是网络设计和旅游时间不确定。来填补这些知识空白,导致实证文献,本研究的目的是开发和测试的方法研究交通网络的影响在学校的位置。,设施选址网络设计模型与旅行时间不确定。模型旨在最小化总旅行费用的学生,学校设施建设成本,道路的建设和升级成本。
本文的其余部分组织如下。部分2介绍了鲁棒优化和p-robustness方法。部分3介绍了数学公式的提出问题。部分4包含一个简短的描述混合模拟退火算法。部分5说明了模型的位置优化农村小学在贵州省的一个小镇,中国。部分6提供了讨论和节7总结了研究结果和结论和对未来的研究需要。
2。引入随机p-Robust方法
随机优化通常试图最小化预期总成本在所有场景。然而,找到的最优解在某些情况下,这种方法可以满意,但不满意。此外,鲁棒优化方法试图最小化成本最坏的客观价值,它提供了一个解决方案,这个解决方案在所有场景令人满意。然而,因为最坏的概率很低,传统的反渗透提供了一个非常保守的解决方案。随机优化和RO缺点在解决不确定性问题。斯奈德和Daskin27提出了一种新颖的鲁棒性度量称为“随机。 - - - - - -鲁棒性“基于一组场景。这种方法结合了两个目标的随机优化和RO通过最小化预期成本在每个场景边界相对后悔。
阐述这鲁棒性措施,让表示一组场景。让为每个场景是一个确定性的最小化问题 。让目标函数的最优解 。 表明的可行解对所有 ; 代表的客观价值在解决方案 。 代表最优目标函数值 。与此同时,为每个场景> 0。因此,成本极小极大和极小极大后悔目标函数可以被制定为方程(1)和(2),分别。
制定p-robustness,让是一个非负定值表明所需的可靠性水平。因此,一个可行的解决方案是 - - - - - -健壮的如果
左边的方程(3)场景下的相对后悔 ,和表示绝对后悔。方程(3)集相对后悔在每个场景的最大上限 。方程(3)可以写成
接下来, - - - - - -鲁棒性测量和最低预期成本目标函数相结合获得问题的定义以下形式:最小化 受 在哪里代表场景的发生概率和表示一组解决方案可行的目标函数 。
3所示。问题陈述和数学公式
3.1。问题定义和假设
本节描述一个学校位置和网络设计问题,包括旅行时间不确定。我们把一组村庄需求节点存在于一个地理区域,道路的一组传输链接。道路网络中链接包含现有的和(潜在的)新道路连接。一套学校在该地区已经存在,它显然是希望找到一组新的学校,构造新的道路连接,提高现有道路的链接,这样总投资成本(包括旅行费用对于学生,学校设施的建设成本,和道路的建设和升级成本)最小。因为的村庄坐落在一个山区,严重的季节性天气状况有重要影响(造成的不确定性)的时间学生前往学校。固有的一些假设提出了问题的解决方案。首先,网络的每个节点代表一个村庄或一批住宅的中心。第二,每个节点可以供应中心或中心的需求;也就是说,在每个住宅中心,一所小学可以被打开。第三,必须位于节点只在小学(村庄/住宅中心)的网络。 Fourth, only one primary school can be located at each node (village/residential center) of the network. Fifth, the network is a customer-to-server system in which the students travel to the primary school to be served. Sixth, all travel costs are symmetric. Seventh, all network links are directed. Eighth, the schools and transfer roads are un-capacitated. Last, all travel costs are uncertain and have a stochastic behavior.
3.2。符号
集、参数和决策变量用于该模型在表中定义1。
3.3。模型公式
两个模型是制定。模型1决定学校的最优位置条件下,现有的道路可以升级。模型2确定最优位置的学校条件下,现有的道路可以升级和新道路可以构造。关于上面的假设和符号,p-robust学校位置的两个混合整数规划模型(p-RSLNDP)可以定义网络设计问题。模型1是描述如下: 受
学生的单位旅行成本在不同天气条件下被认为是不确定的。因此,公式(5)的目标函数是最小化所有学生的预期的旅行费用,升级成本的公路,和学校设施建设成本在所有场景。这种情况的概率是多少发生并在决策过程中显示它的重要性。配方(6)- (17约束条件。约束(6)执行p无尺寸标准,表明每个场景的相对后悔不得大于健壮性系数 。此外,一个小的价值可能会产生不可行解。应该注意,如果它 ,p-robust标准变得毫无意义,制定设计问题等价于一个确定的学校位置。约束(7)意味着学生在村庄要么是由一个学校吗或从其他地方获得服务。约束(8)确保学生 ,流入到等于流出节点节点。约束(9)要求所有学生必须提供。约束(10)和(11)确保潜在的转让链接和学校不习惯如果不建造。约束(12)保证只有两个节点之间的单向链接。约束(13)确保构建学校的成本小于固定预算 。约束(14)执行二进制限制决策变量的位置。这意味着,如果有一个新的学校需求节点 ,的价值是1;否则,该值为0。约束(15)和(16)执行流的nonnegativity变量。约束(17)执行二进制限制决策变量的联系。这意味着如果现有的链接节点来是升级,的价值是1;否则,该值为0。
相应的模型1,最优方案成本可以根据以下计算模型: 主题(7)- (17)
模型2描述如下: 受
相比与模型1、模型2的目标函数增加了新的道路的成本。表示一组现有的和新的候选人传输网络中的链接。约束(31)执行二进制限制决策变量的联系。这意味着如果转移链接节点来是升级或构造,的价值是1;否则,该值为0。此外,约束(27)意味着学校建设的总成本和道路建设和升级不到固定预算 。
对应于模型2,最优方案成本可以根据以下计算模型: 主题(20.)- (31日)
4所示。解决方法
当场景的数量等于1,提出的问题是经典的UFLNDP。Melkote [17]证明UFLNDP是一个不确定性多项式时间(NP)困难的问题。模拟退火(SA)是一个本地搜索可以避免局部最优解的启发式迭代接受差的解决方案在解决方案。这个方法是有效解决高度复杂的组合问题31日]。近似全局最优解,利用混合metaheuristic算法相结合SA和Teitz-Bart算法。SA算法提出了大都市et al。32)和独立描述了柯克帕特里克et al。33]。SA算法是基于关于金属的逐渐冷却过程的一般概念。SA算法从一个初始解在一个较高的温度。根据某一温度降低温度调节的过程。在每个步骤中,邻居是随机生成的,其对应的目标函数计算。运动改善目标函数总是接受,接受了一些概率和其他运动。Teitz-Bart算法提出了Teitz和巴特34]。该算法是一种局部搜索方法,改进启发式算法。通过初步交换一个节点一个节点在当前的解决方案,不是在当前的解决方案,它提高了迭代解发现使用建设性的算法(35]。
4.1。解决方案表示
减少解决问题的难度和复杂性,我们把单一情形的解决方案为每个过程分为三个阶段 。首先,我们应该找出现有的道路需要升级和潜在的道路,需要构建道路网络根据成本预算和修复网络投资决策。第二,Teitz-Bart算法用于确定新学校的位置根据剩余的成本预算。第三,每个需求点必须找到相应的学校寻求服务。此外,学生上学的行走路径确定每个需求点。在解决过程的第一阶段,我们需要找出劣质,中质和潜在的道路路网,组合成一个数组按照一定的顺序。解决方案获得的模拟退火算法也是由一个数组表示。位置的数组元素包含一些新的设施和0或1的代码。代码1表示低质量的升级和中质道路或潜在的道路的建设。代码0表示没有道路升级或道路建设。低品位、中间级,和潜在的道路被安排在前面,中间,和后面的数组。 For a road network consisting of five low-quality roads, five medium-quality roads, and five potential roads, the solution can be expressed as an array containing 15 elements (as shown in Figure1)。这个数组意味着升级或构建第二个和第三个低级的道路,第二和第四中高档道路,首先,其次,分别和第四潜在的道路。
4.2。初始解代
每个场景的初步解决方案在这个研究是随机生成的。通过SA算法的解决方案是一个数组(数组中元素的值是0或1),也是会议的范围内随机生成预算约束条件。
4.3。社区生成过程
社区生成的主要因素之一,影响SA算法的性能。社区是通过交换两个传输链接的价值有不同的价值观。为了这个目的,我们寻找一对节点 与的关系 ,然后,其他对将选择交换他们的价值观。变量后是固定的,我们使用Teitz-Bart算法优化设施位置。最后,在变量和是固定的,问题已经解决了,和一个社区生成的目标函数。
4.4。混合SA的框架
的主要操作混合SA算法如图所示2。在流程图中,代表了迄今为止最优解;表示初始温度;显示最终的温度;显示冷却系数和用于控制冷却速率;代表一个随机数;表明马尔可夫链的长度;代表当前的马尔可夫链的长度;表示当前解的目标函数值的区别及其附近。不难解决这个问题如果场景只局限于一个场景。该算法首先初始化一个可行的道路网络和温度和使用Teitz-Bart算法获取设施位置。这句话的值和 ,和当前的客观价值可以通过计算获得。然后,生成一个新的可行的道路网络的过程中逐渐冷却下来。设施的位置在新道路网络使用Teitz-Bart算法得到。因此,我们可以得到一个新的目标函数值。道路网络和设施的位置根据大都市不断更新指南,重复这个过程,直到当前的温度达到最小值。最后,合成道路网络和相应的设施位置设置固定场景下的最优解的问题。此外,Teitz-Bart算法的主要业务在图所示3。Teitz-Bart算法的主要步骤包括以下:(i)确定一个初始子集的设施的位置;(2)用其他节点来取代的子集中的每个节点初始设备位置;和(3)替换节点贡献最大的总加权距离减少设施选址的子集。
5。实际的案例研究
5.1。基本数据
模型1和2的可行性和混合SA算法测试通过应用他们在贵州一个小镇,中国。贵州地处山区环境,是典型的区域指定为“农村振兴。“改善贵州易访问性学校对学生是非常重要的。如图4镇,由26个村庄(节点,编号1 - 26),总人口24730。每个人口中心的人口通过现场调查获得的。公路网络,以及现有的学校,由方块图表示4。最初,有32个现有和六个潜在的道路。六个潜在的道路设计根据研究区域的实际地形(如在谷歌地球)。道路分类根据其质量(“高”,“媒体”和“低”)。公路建设成本的升级或不同根据不同类型的道路。因此,升级成本低收入和中质公路高质量的公路的成本低于建设新的道路。此外,旅行费用(的时间)的学生随不同品质的道路。
5.2。参数设置
中描述的部分3.1和3.3,旅行成本的不确定性是由于天气的影响。因此,单位成本转移随机在某些场景中,被归类为“好”,“坏”,和“媒介,太糟糕了。“天气条件对学生的影响旅行速度是这项研究的主要考虑因素。因此,据《每日天气2017年,四个不确定情况下的概率是0.48(好),0.38(媒介)、0.09(坏的管理者)和0.05(太糟糕了)。每个学生的转移成本(单位:米)被定义为距离的比例提到的四个场景和0.5(好),1(媒介)、1.5(坏的),2(太糟糕了)。每个人口中心的需求等于居住的学生人数。打开学校的固定成本取决于人口中心的需求和均匀变化之间的18000和26000亩(货币单位)。一条新路的建设成本和升级的成本低收入和中质公路高质量的公路被计算成四、三,和两次,分别连接两个村庄之间的距离。运输成本(米)高,中期和低质量的道路为每个学生被随机计算受到离散均匀分布在(0.3,0.32),(0.2,0.22),(0.1,0.12),分别。
必须强调,在中国,投资责任在学校建筑和道路建设或升级都掌握在当地教育部门和交通主管部门,分别。这些部门必须提出一个全面的计划来提高学生学校的可访问性。此外,为了节省成本的学校建筑和道路建设或更新,部门有一个有限的投资决定的预算限制。我们假设学校建筑和道路建设的成本预算或更新的模型1和模型2是80000亩。
5.3。计算结果
模型1和模型2的最优解了使用MATLAB软件和预定值不同的参数。模型1和模型2的最优解给出的数字5和6,分别。对模型1,新学校的最佳位置是Zhaiyun和Yanke ( )。道路节点2和3之间的质量,3和4、8和12、9和14日13和15日14和15日20和21、21日和19日,23和24应该从低到高更新( )。模型2的最优定位的新学校也Zhaiyun和Yanke ( )。两个新的道路节点之间应该建立在7号和8号,和节点19日和26日( ; )。此外,道路节点1到8的质量,3和4,9日和14日,12日和16日,13和15,14、15、20和21、23和24应该更新从低到高。( )。作为数据6和7演示,学生学校的移动方向显示在道路。一些村庄的学生应该直接转移到学校发现村庄。然而,其他城镇的学生需要通过一些中间村庄上学。例如,村9中的学生应该由一个位于村庄的学校通过路线(9-14-15)15。模型的最优解价值1 297805(在细节,第一,第二,第三,第四不可靠的情况是207147年,350611年,473845年和617570年,分别)。此外,模型的最优解值2是329690年(在细节,第一,第二,第三,第四不可靠的情况是221987年,379940年,527179年,663330年,分别)。
5.4。参数化分析
5.4.1之前。理想的鲁棒性水平变化对总成本的影响
为了确定p-robust参数变化的影响在模型1和模型2的目标函数值,进行敏感性分析实验。数据显示7和8,我们可以看到预期的可靠性级别( )和预算约束( )有一个对总成本的影响。起初,被设置为一个更大的值,然后开始下降,直到没有可行的解决方案。此外,所需的总成本有降低趋势健壮性级别( )生长。基于该模型与增加所需的鲁棒性级别( ),可行域不减少。显然,所需的鲁棒性级别( )对总成本变化有重要影响。可以证明p-RSLNDP是不可行的 。
5.4.2。投资预算变化对旅行费用的影响
投资预算约束( )p-RSLNDP模型的一个重要参数,会影响最优解。数据9和10现在旅游的投资预算成本的影响不同p值。正如所料,减少旅行费用和增加的投资预算。此外,我们可以看到数据9和10的增加价值,同样的预算约束下的旅行成本也降低。
6。讨论
本研究构造了一个混合整数规划模型的位置优化农村小学和提出了一种混合模拟退火算法解决模式,它有效地解决了农村小学的位置优化问题。然而,由于约束的能量,能力,和时间,这项研究有一些局限性。首先,在建立模型的过程中,小学的大小限制是省略。在现实生活中,学校的规模可能限制他们接受的学生人数。因此,未来的研究还应该考虑能力约束的学校设施和/或交通网络。其次,我们没有考虑其他因素的影响(地形、坡度、土地利用类型等)在农村小学的位置。这些因素也有重要影响的选择小学的位置。因此,有兴趣的读者可以进一步探索农村小学的位置,考虑这些因素。第三,本文仅探讨了静态小学位置问题,没有考虑到参数等需求,学校,或道路建设成本会随着时间改变。有必要考虑需求变化的影响和工程造价变化对小学的位置在未来的研究。 Lastly, further research is needed to develop algorithms to solve large problems. In a word, we hope that in the future research and work, we will have the opportunity to continue the discussion, and we also hope that more scholars who work on the location optimization of rural primary schools can continue excavating such research.
7所示。结论
科学规划学校的位置是一个重要的方法来优化教育资源配置,提高办学效率,实现教育的均衡发展,尤其是在农村地区。因此,本研究的目标是最小化总运输成本为学生,为学校建设成本,道路的建设和升级成本与旅游交通网络时间的不确定性表示不同的旅行时间场景。在这项研究中,一个优化的混合整数线性规划模型和混合SA算法被开发和使用基于交通网络优化农村学校的位置特征。此外,随机p-robust方法被用来旅行时间不确定性模型。新开发的模型有效地确定最优位置的新学校在农村地区,转移优化构建/升级链接,和最优分配学生的学校。一个实际案例研究证实的适用性的数学模型来解决问题在规划农村学校。交通网络优化有重要影响的农村学校的位置。的影响来确定p-robust参数变化对目标函数值和投资预算的旅行费用模型,进行敏感性分析实验。敏感性分析显示的变化p价值观和投资预算有显著影响目标函数值和旅游成本。
然而,这还需要进一步的研究来开发算法来解决大问题。未来的研究还应该考虑能力约束的学校设施和/或交通网络。
数据可用性
的数据支持本研究的发现可以要求作者。
的利益冲突
作者宣称没有利益冲突的这方面的工作。
确认
这项工作是支持的人文社会科学研究项目的河南省教育部(批准号2022 - zzjh - 281),学院和大学的重点科研项目(批准号河南省a170006 21日),中国国家自然科学基金(批准号41671396)。