能力受限的应急抢修点选址模型的两阶段启发式算法

能力受限的应急抢修点选址模型的两阶段启发式算法

应急救援点的规划系统直接影响应急救援系统的服务质量，特别是在为城市公共服务机构提供紧急救援服务的应急救援站的地区。余鹏等本文所研究的有能力约束应急抢修点选址模型,与集覆盖问题(SetCoveringProblem,SCP)具有相同的覆盖系数限制,与有能力约束的设施选址问题(CapacitatedFacilityLocationProblem,CFLP)具有相同的能力约束,可以根据SCP和CFLP的求解算法思想来设计本文模型的求解算法。SCP和CFLP都是NP难问题,对于SCP问题一般采用启发式算法和进化算法求得满意解在这些算法中,核心问题启发式算法(CoreHeuristicAlgorithm,CHA)是求解大规模整数规划问题的一种非常有效的方法。CHA算法思想最早由Balas等本文所研究的有能力约束的应急抢修点选址模型不仅具有覆盖系数限制和能力约束,而且具有抢修服务水平约束,其约束条件比SCP和CFLP问题更为复杂。本文根据该应急抢修点选址问题的拉格朗日松弛对偶问题最优解对应的检验数确定原问题的核心问题,设计了两阶段启发式算法求解该应急抢修点选址问题。1能力有限的应急评估地点和建模1.1需求点系统故障事件n个设施分布在不同的地点(以下简称需求点),N={1,2,…,n}是这n个需求点集合,需求点i的年均故障率为λ从备选点j到需求点i的通行时间为t(1)各需求点在一个运营年度内的故障发生次数服从参数为λ(2)需求点出现故障和负责对其抢修的应急小组迟到2个事件相互独立。(3)从各备选点到各需求点的通行时间之间相互独立。1.2抢修点负责抢修根据以上描述,可以建立以下数学模型:式(1)是目标函数,表示抢修点总开设成本最小;式(2)表示每个需求点有且仅有1个抢修点负责对其进行抢修;式(3)表示只有已开设的抢修点才能对其所覆盖的需求点进行抢修;式(4)是能力约束,每个抢修点负责抢修的需求点数量不超过其能力限度;式(5)是整个应急抢修系统的服务标准约束,根据模型假设,式(5)是在不考虑约束式(4)和(5)时,上述模型属于集覆盖问题,集覆盖问题是典型的NP难问题,因此,该问题也属于NP难问题。2拉格朗日放松两个阶段的启动算法2.1基于原问题的lr对偶模型求解基于拉格朗日松弛的两阶段启发式算法的基本原理是,对于为混合整数规划问题的选址问题,其对应的线性松弛问题(LinearRelaxationProblem,LP)的检验数和选址问题的最优解之间存在紧密的联系(1)求解原问题对应的LR对偶问题,根据LR对偶问题的最优解对应的最优选址方案及选址变量的检验数确定原问题的核心问题。与原问题相比,核心问题具有和原问题相同的结构,但其中备选点个数少于原问题中备选点个数。核心问题的可行选址方案集以较大的概率包含原问题的最优选址方案,但核心问题的求解难度要小于原问题。(2)求解核心问题,从而得到原问题的解。核心问题中的备选点个数虽然较少,但仍属于NP难问题,因此,仍然用拉格朗日松弛启发式算法求解核心问题。2.2拉格朗日乘子更新2.2.1求解原问题的拉格朗日松弛对偶问题(1)对于给定的拉格朗日乘子,求解原问题的拉格朗日松弛问题。式中,μ对于每个子问题,假定x对于给定的μ为利用次梯度法求得较优的拉格朗日乘子值,需求得原问题最优目标函数值的上界UB。2.2.1节的主要目的是为了得到原问题LR对偶问题的最优解,而不是为了求得原问题的最优解,因此,在求解原问题对应的LR对偶问题时仅在第1次迭代中求得原问题的可行解,以此作为原问题最优目标函数值的上界。为了尽可能地提高求得的原问题可行解的质量,本算法中同时采用两种方法求原问题的可行解,取其中最好的一个作为原问题最优目标函数值的上界。方法1是对拉格朗日松弛问题的最优解进行修补,使之成为原问题的可行解;方法2是用贪婪法直接构造原问题的一个可行解。(2)修补拉格朗日松弛问题的最优解得到原问题的可行解。(a)求出已开设抢修点的备选点集合J(b)计算Z2覆盖修补。以步骤1得到的抢修点开设方案为基础,按以下方法增设抢修点使得所有的需求点都能被已开设的抢修点覆盖,即满足(a)求出已开设抢修点的备选点集合J(b)计算未开设抢修点的备选点对未被分配的需求点覆盖次数之和(d)计算J(e)更新J(f)重复(b)~(d),直至所有的需求点都能被已开设的抢修点覆盖。3根据经过步骤2覆盖修补后的选址方案,求解广义指派问题(GeneralizedAssignmentProblem,GAP),确定分配变量{y对于上述GAP问题中的约束式(14),可以将GAP问题中a(a)求出已开设抢修点的备选点集合J(b)对于已求得的分配关系,计算(c)求出增设1个抢修点后最可能满足约束式(5)的备选点集合J(d)对调整后的抢修点分配方案,按步骤3的方法求解GAP问题求得抢修分配关系y5删除选址方案中的冗余抢修点。对于已开设的抢修点,按开设成本从大到小的顺序,依次检查关闭该抢修点后,按步骤3的方法求解GAP问题得到的抢修分配关系{y经过1~5,由拉格朗日松弛问题最优解的选址方案{x6构造原问题的一个可行解。以未在任何备选点开设抢修点的选址方案(即x(3)更新拉格朗日启发式算法的相关系数。2更新步长系数。步长系数β(4)更新拉格朗日乘子。1计算次梯度值S2计算加权次梯度WS3计算步长(5)终止条件及拉格朗日乘子初始化。当迭代次数大于2000次时,终止算法。拉格朗日松弛启发式算法的计算效率对拉格朗日乘子的初始值比较敏感,通过计算试验,拉格朗日乘子按以下方法取初始值时对原问题拉格朗日松弛对偶问题的计算效果较好,即2.2.2确定原问题的核心问题根据2.2.1中求得的原问题拉格朗日松弛对偶问题的近似最优解,确定原问题的核心问题。(2)确定核心问题中备选点。在2.2.1中求得的拉格朗日松弛对偶问题近似最优解对应的最优选址方案中选址变量的检验数,将各备选点选址变量所对应的检验数按从小到大的顺序排列,取前m(3)确定核心问题的其他参数。核心问题的需求点为原问题的需求点,核心问题中的其他参数为原问题中的对应参数。即在核心问题中备选点是原问题备选点的子集,需求点与原问题的需求点相同,且核心问题的模型具有和原问题模型相同的结构。2.2.3求解原问题的核心问题求解核心问题的基本步骤与求解原问题拉格朗日对偶问题的步骤类似。(1)求解核心问题的拉格朗日松弛问题。采用与2.2.1中步骤1相同的步骤进行求解,计算得到核心问题最优目标函数值的下界LB本文采用与Caprara等(3)对拉格朗日松弛问题近似最优解对应的选址方案进行随机扰动,产生5个的选址方案。2根据每个已开设抢修点的相对检验数大小rrc,以轮盘赌的方式在拉格朗日松弛问题近似最优解对应选址方案中随机关闭m3重复2,产生5个经过扰动的选址方案。(4)修复经过扰动的选址方案得到核心问题的可行解。1采用与2.2.1(2)中步骤1~4相同的方法依次修复5个经过扰动过的选址方案,使之满足原问题的所有约束,得到5个可行解;2在5个可行解中选出目标函数值较小的一个,采用2.2.1(2)中步骤5的方法删除该可行解中的冗余抢修点,并将此可行解作为本次迭代中核心问题的可行解,将其对应的核心问题目标函数值作为核心问题最优目标函数值的上界UB(5)更新拉格朗日启发式算法的相关系数和拉格朗日乘子。采用与2.2.1中(4)、(5)类似的方法更新求解核心问题的拉格朗日松弛启发式算法中的相关系数和拉格朗日乘子。(6)终止条件和拉格朗日算子初始化。当满足以下条件时,终止求解核心问题的拉格朗日启发式算法的求解过程。1迭代次数超过1000次。2核心问题最优目标函数值的最佳上界与最佳下界相对差小于0.01%。3算例结果对比为测试算法的有效性,将本文提出的算法分别对来自实际背景和随机生成的算例进行求解,并对算法的求解质量和求解效率进行验证。在所有算例中,均假设需求点同时也是备选点。来自实际情况的算例中,将上海市各地铁站内的设备作为一个需求点和备选点,通过百度地图提供的接口函数可以获得各地铁站位置以及各站点之间最短通行距离。另外,在随机生成的算例中,需求点(备选点)数量分别为200、300、400和500,分别分布在边长为60、70、80、90(km)的正方形区域内。为了模拟城市中公共服务设施不均匀分布的情况,将每个算例中的正方形区域分为3层方形区域,中心区域、中层和外层环形区域,边长比分别为0.14∶0.43∶1,在中心、中层和外层中的需求点数量比为0.3∶0.5∶1,需求点在各层之内均匀分布。在实际算例和随机生成的算例中,需求点的年失效率λ在各算例中,假设从备选点到需求点的平均通行速度为25km/h,通行时间服从对数正态分布,通行时间均方差与均值的比例为常数0.1。给定按时到达的时间标准t将本文提出的算法用MATLAB2009b编程,在intelCPUT6570,内存2GB的电脑上运行。为检验本文所提出算法的求解效果,将商业优化软件MOSEK由表1可以看出,与原问题比较,核心问题的问题规模减小,而且本文提出的算法对绝大多数算例的求解结果均优于MOSEK的求解结果。在所有40个参数组合的算例求解结果中,核心问题中的备选点个数约为原问题的1/3。本文提出的算法对其中31个参数组合的算例求得的最差求解结果(最大目标函数值)仍优于MOSEK的求解结果;对其中7个参数组合的算例求得的最差求解结果(最大目标函数值)等于或略大于MOSEK的求解结果,但所求的最好求解结果(最小目标函数值)优于MOSEK的求解结果;仅在2个参数组合的算例中(t由表1还可以看出,在所有40个参数组合的算例求解结果中,本文提出算法的求解时间(包含确定核心问题的时间和求解核心问题的时间)均远小于MOSEK的求解时间。其中在37个参数组合的算例中MOSEK的求解时间超过了设定的最长求解时限3600s,而本文提出算法能在相对较短的时间内得到相对较好的求解结果。4基于核心问题的可行解更新能力受限的应急点抢修选址问题是具有抢修系统服务水平约束和抢修点服务能力约束的NP难问题,本文根据原问题的拉格朗日松弛对偶问题近似最优解对应的最优选址方案中各选址变量的检验数确定了原问题的核心问题,核心问题和原问题具有类似的结构但求解难度较小。针对该核心问题设计了拉格朗日松弛启发式算法,在核心问题的拉格朗日松弛问题最优解附近进行随机搜索,并对随机搜索得到的解进行修补使之成为核心问题的可行解,迭代得到核心问题改进的可行解,最后,根据核心问题的最佳可行解得到原问题的满意解。算例计算的结果表明,与商业优化软件MOSEK相比较,该算法能在相对较短的时间内得到较好的可行解。显然约束式(2)等价于1如果(c)计算J4如(e)更新J(f)重复(b)~(e),直至TFV≤λ1更新原问题最优目标函数值最佳下界LB*和最佳上界UB*。如果LB>