求解无容量设施选址问题的拉格朗日蝙蝠算法

王婷婷 张惠珍 赵玉苹

摘要无容量设施选址问题（Uncapacitated Facility Location Problem， UFLP）是一类经典的组合优化问题，被证明是一种NP-hard问题，易于描述却难于求解.首先根据UFLP的数学模型及其具体特征，重新设计了蝙蝠算法的操作算子，给出了求解UFLP的蝙蝠算法.其次构建出三种可行化方法，并将其与求解UFLP的蝙蝠算法和拉格朗日松弛算法相结合，设计了求解该问题的拉格朗日蝙蝠算法.最后通过仿真实例和与其他算法进行比较的方式，验证了该混合算法用来求解UFLP的可行性，是解决离散型问题的一种有效方式.

关键词管理科学与工程；无容量设施选址问题；拉格朗日蝙蝠算法；拉格朗日松弛算法；蝙蝠算法

中图分类号TP301.6文献标识码A

Lagrangian Bat Algorithm for Solving

The Uncapacitated Facility Location Problem

Tingting Wang1， Huizhen Zhang1， Yuping Zhao2

（1.School of Management， University of Shanghai for Science & Technology， Shanghai200093， China；

2. State Grid Shanghai Procurement Company， Shanghai200093， China）

AbstractThe uncapacitated facility location problem is a classical combinatorial optimization problem and has been proved an NPhard problem， easy to describe but difficult to solve. Based on the mathematical model and specific features of UFLP， the operators of bat algorithm and proposed a bat algorithm for solving it has been redesigned. Secondly， three feasible methods were designed and lagrangian bat algorithm was presented by combining these three methods， the bat algorithm for UFLP and lagrangian relaxation algorithm. Lastly， the experimental results showed that the hybrid algorithm can feasibly solve UFLP through simulation examples and comparisons with other algorithms and it is an effective algorithm in solving the discrete problem.

Key wordsmanagement science and engineering； uncapacitated facility location problem； lagrangian bat algorithm； lagrangian relaxation algorithm； bat algorithm

1引言

設施选址问题是在各需求点已给定的条件下，选择设施的最佳位置，使设施的总成本降到最低[1].无容量设施选址问题是从给定没有容量限制的设施集中选择要开放的设施，使其以最小的总费用来服务所有客户.到目前为止，求解该问题的方法主要有近似算法、精确算法和智能优化算法.近似算法可以在多项式时间内求得问题的一个解，并且其目标函数值与最优解的目标函数值之比不超过一个常数[2]；精确算法是一种可以求得最优解的算法，但仅适用于小规模问题，且计算速度较慢.智能优化算法更期望在可接受时间内获得问题的最优解或近似最优解.近年来，许多学者运用各种智能优化算法来解决UFLP：Kole（2014）[3]等首次将蚁群算法用于UFLP的求解，并与粒子群算法进行对比，拓宽了蚁群算法的应用范围；Damgacioglu（2015）[4]等为求解该问题提出了一种遗传算法，并验证该算法的可行性，同时将未来的研究工作致力于多设施选址和有容量选址问题；李倩（2016）[5]等针对无容量设施选址问题的特点，设计了两种局部搜索方法，并与基本蚁群算法相结合，提出了求解该问题的混合蚁群算法，结果表明该混合算法具有明显的有效性.

蝙蝠算法（Bat Algorithm， BA）是Yang（2010）[6]提出的一种新型启发式算法.BA的提出是用来求解连续域的函数优化问题，不能直接用来求解组合优化问.通过人们的不断改进，先后对BA进行了改进.Adarsh（2016）[7]等在蝙蝠算法的基础上加入了混沌序列，提出了求解经济调度问题的混沌蝙蝠算法，提高了算法的求解性能.刘春苗（2016）[8]等将蝙蝠算法的操作算子重新进行了定义，设计了求解车辆路径问题的离散蝙蝠算法，这是首次将蝙蝠算法用于车辆路径问题的研究.

拉格朗日松弛的思想起源于20世纪60年代.20世纪70年代初才对拉格朗日松弛算法（Lagrangian Relaxation Algorithm， LR）提出定义.后来，Fisher[9]使用该算法来解决调度问题，同时提出了更新拉格朗日乘子的方法.

深入分析UFLP模型的具体特点，结合BA和LR各自的优点，提出了一种拉格朗日蝙蝠算法，并通过求解系列经典UFLP算例验证了该算法的寻优性能.

2无容量设施选址问题

假设给定m个设施、n个客户，且所有的候选设施都没有容量限制，cij表示设施i与客户j之间的服务费用，hi表示设施i的开放费用，要求每个客户都应由一个且只能一个设施提供服务，同时使总费用最小.UFLP的数学模型可被描述如下：

min z=∑mi=1∑nj=1cijxij+∑mi=1hiyi，（1）

∑mi=1xij=1，j∈N，（2）

xij

SymbolcB@ yi，i∈M，j∈N，（3）

xij∈0，1，i∈M，j∈N，（4）

yi∈0，1，i∈M.（5）

模型中，z是目标函数，即总费用；xij表示客户j是否由设施i服务，如果客户j由设施i服务，则xij=1，否则xij=0；yi表示设施i是否开放，如果设施i开放，则yi=1，否则yi=0.

3 蝙蝠算法

3.1基本蝙蝠算法

蝙蝠算法是一种基于蝙蝠的回声定位系统而产生的智能启发式算法，将蝙蝠类比为当前可行域内分布的搜索点，用目标函数值的大小来判断当前蝙蝠所处位置的优劣，通过蝙蝠的飞行移动来搜索目标函数最优解[10].蝙蝠飞行移动过程中的关键操作包括：速度、位置、音量和脉冲发生率的更新.

3.1.1蝙蝠速度和位置的更新

在d维空间中，蝙蝠i在t+1时刻下的速度和位置更新公式定义如下：

fi=fmin +（fmax -fmin ）β，（6）

vt+1i=vti+（xti-x*）fi，（7）

xt+1i=xti+vt+1i，（8）

其中，β∈[0，1]是服從均匀分布的随机数；fmin和fmax是频率的最小值和最大值；vit和vit+1是t和t+1时刻蝙蝠i的速度；x*表示当前全局最优解；xit和xit+1分别是t和t+1时刻蝙蝠i的位置.

在当前最优解集中选中一个解xold，那么每只蝙蝠在最优解附近按照随机游走法则可产生局部新解xnew.

xnew=xold+εAt， （9）

其中，ε是属于[-1，1]的随机数；At表示t时刻当前代蝙蝠种群音量的平均值.

3.1.2蝙蝠音量和脉冲发生率的更新

当蝙蝠接近猎物时，音量降低，脉冲发生率逐渐提高.音量和脉冲发生率按照以下公式更新：

At+1i=αAti，（10）

rt+1i=r0i1-exp -γt.（11）

其中，α和γ是常量；Ait和Ait+1分别是t和t+1时刻蝙蝠i的音量；ri0是初始脉冲发生率；rit+1是t+1时刻蝙蝠i的脉冲发生率.

3.2求解UFLP的蝙蝠算法

3.2.1编码方式

对m个设施、n个客户的UFLP，每只蝙蝠对应一个n维向量，每个维度上的值为[1，m]内的一个随机整数.例如：给定m=3、n=5的UFLP，若某只蝙蝠的位置向量为[2， 1， 2， 1， 1]，则表示设施1和2开放，3关闭；设施1服务客户2、4、5；设施2服务客户1和3.用这种方式构建UFLP的解，会使每个客户均被考虑到并限制每个客户仅能由一个设施提供服务，大大降低了计算复杂度.

3.2.2种群初始化

考虑到UFLP的特点，当设施开放费用远高于服务费用时，可以开放较少的设施，否则可以通过减少服务费用来降低总费用.在初始化种群时就不是完全随机的，可以带有一定的方向性.将设施的平均开放费用与平均服务费用的比值记为分类指标t，设定t1为t的一个参考值，p1、p2∈[0，1]且p1t1时，如果r

3.2.3速度和位置更新规则

为简化算法复杂度，没有考虑BA的频率，而用当前蝙蝠和最优蝙蝠位置间的汉明距离s来代替速度，再用精英保留策略更新蝙蝠位置.为了保持种群多样性，用最优蝙蝠位置向量中长度为floor（s/2）的基因段来替代当前蝙蝠位置中的同一个基因段.其中，第一个基因段是从第1维至第floor（s/2）维，第二个基因段从第2维至第floor（s/2）+1维，按这种长度直至能替换到位置中的第n维，即分别替换n+1-floor（s/2）次，找出多种替换后适应度值最小的一种方式，则用该基因片段替换得到的位置即为更新后的蝙蝠位置.

例如：给定m=n=5的UFLP，其服务费用矩阵C=[1696 1309 1488 1235 1621； 1666 1980 1227 1783 1135； 1354 1249 1240 1831 108； 1224 1320 121 1340 1004； 192 1439 1375 112 1009]、开放费用矩阵H=[130 199 139 127 103]，蝙蝠i的位置为[3， 2， 2， 5， 3]，适应度值为5222，x*为[5， 3， 3， 4， 4]，s为5，则每次替换的基因片段长度为floor（s/2）=2，用精英保留策略分别替换4次得到的位置为[5， 3， 2， 5， 3]、[3， 3， 3， 5， 3]、[3， 2， 3， 4， 3]、[3， 2， 2， 4， 4]，对应的适应度值分别为3329、4305、6487、7370，其中最小的适应度值为3329，小于5222，则该蝙蝠的新位置为[5， 3， 2， 5， 3].

3.2.4局部搜索

为进一步提高算法的搜索精度，根据UFLP的最优解所具有的特点，在最优蝙蝠附近进行局部搜索，在当前开放的所有设施中随机挑出一个设施p∈[1，m]，将其服务的所有客户由其它m-1个设施分别来服务，其中设施q∈[1，m]且q≠p所需的服务总费用最小，则最优蝙蝠中由设施p服务的客户都改为由设施q来服务.

4拉格朗日蝙蝠算法

拉格朗日蝙蝠算法（Lagrangian Bat Algorithm， LR_BA）是由LR和求解UFLP的蝙蝠算法（Discrete Bat Algorithm， DBA）结合而成，尝试将这两种算法相结合，通过计算上下界值来同时逼近问题的最优解.在求解UFLP时，DBA得到原问题的一个上界值，而LR通过松弛其中的等式约束得到原问题的下界值，再利用可行化方法将该下界值可行化为原问题的另一个上界值.通过比较两个上界值，从而得到UFLP的满意值.

4.1UFLP的拉格朗日松弛

对约束式（2）进行松弛，松弛后的目标函数变为式（12）.

min z=∑mi=1∑nj=1（cij-λj）xij+∑mi=1hiyi+∑nj=1λj.（12）

通过标准次梯度优化方法，按式（13）计算步长T，再根据式（14）更新拉格朗日乘子λ.

Tt=πZUB-ZLB∑nj=1∑mi=1xij-12，（13）

λt+1j=max 0，λtj+Tt1-∑mi=1xij.（14）

其中，ZUB为原问题的上界值，ZLB为松弛问题的下界值；xij为松弛问题的解；π是常数.

根据UFLP的具体特点，对于任意客户，其应当由所需服务费用最少的设施服务.对于任意设施，将其服务的所有客户分别由其他设施来服务，而该设施所需的总费用应当最小，提出了松弛问题的3种可行化方法.

下面通过一个UFLP算例对此进行简要介绍.

给定m=n=5，C和H的值与3.2.3中的值相同.假设松弛问题的解为：xm×n=[0 0 1 0 1； 1 1 1 1 0； 1 1 0 1 0； 1 0 0 0 0； 0 0 0 0 1].

可行化方法一：每个客户应选择所需服务费用最小的设施为其服务.以客户1为例，其分别由设施2、3、4服务，比较三种服务费用，设施4所需费用最少，则客户1由设施4服务，即x41=1，x21=x31=0.可行化后为x23=x24=x32=x41=x55=1，目标函数值为7060.

可行化方法二：对于已开放的设施，将其服务的客户分别由所有设施来服务，最后确认由所需总费用最小的设施来服务.以服务客户3和4的设施2为例，计算客户3和4由所有设施服务的总费用，min[1488+1235+130，1227+1783+199，1240+1831+139，121+1340+127，1375+112+103]=1588，設施4所需费用最少，则客户3和4由设施4服务.最后x32=x51=x53=x54=x55=1，目标函数值为4179.

可行化方法三：每个客户应从已开放的设施集合中选择所需服务费用最小的设施为其服务.以客户1为例，当前开放设施3和5，比较客户1分别由设施3和5服务的费用，设施5所需费用较少，则客户1由设施5服务.最后的结果为x32=x33=x35=x51=x54=1，目标函数值为3143.

4.2拉格朗日蝙蝠算法设计

Step1：各参数初始化.蝙蝠种群大小K；最大迭代次数Nmax（N_iter=1）；音量A；脉冲发生率r；服务费用C；开放费用H，适应度函数f（x）.初始化种群找出最优蝙蝠x*.

Step2：根据汉明距离和精英保留策略更新蝙蝠位置.

Step3：产生随机数rand1，判定rand1>ri是否成立，如果成立，则执行局部搜索.

Step4： 产生随机数rand2，判定rand2>Ai且f（xi）

Step5：求解松弛问题，得到原问题的下界值.

Step6：根据式（14-15）更新拉格朗日乘子.

Step7：下界可行化，得到原问题的可行解UB2，并按以下两个标准更新π：如果连续5次没有提高解，则π将减半；如果连续循环50次后，该值被重置为初始值.

Step8：将UB2与所有蝙蝠的适应度值进行比较，替换其中最大的适应度值.

Step9：比较UB1和UB2，将两者较小值保存为UB=min（UB1，UB2）.

Step10：判断是否达到预设的最大迭代次数Nmax或时间限制3600s，若达到，则输出最优解UB，否则N_iter++，转至Step2.

其中，去除Step5Step9为求解UFLP的蝙蝠算法.

5实验与分析

为验证拉格朗日蝙蝠算法的可行性及其求解性能，在操作系统为64位Windows7的实验环境下，通过MATLAB编程对两组标准算例求解测试，结果见图1.第一组算例来自OR-Library，从中选取12个算例，m=16/25/50，n=50；第二组算例来自UFL基准问题库，同样选取12个算例，m=n=250/500/750.同时，将其与改进蚁群算法、基本蚁群算法、混合蚁群算法、DBA进行比较.DBA和LR_BA的所有目标函数值都是运行测试10次中的最好值.DBA和LR_BA的具体参数设置如下：K=20，Nmax=200，A=0.9，r=0.25，α=0.95，γ=0.05，t1=0.9，π=2，λj1=max cij，同时借鉴文献[11]中p1和p2的参数设置，当求解OR-Library的12个算例时，p1=0.3，p2=0.5；当m=n=250时，p1和p2仍设定相同值；当m=n=500时，p1=0.15，p2=0.3；当m=n=750时，p1=0.1，p2=0.2.表1和2分别给出了OR-Library和UFL基准问题库中算例的计算结果.

在表1中，Na和Nb分别表示DBA和LR_BA的十次运行结果中优于改进蚁群算法的次数.表中包括每个算例的已知最优值、各算法的所得值、Gap值（Gap是各算法所得值与已知最优值的相对偏移百分比）和平均运行时间.DBA和LR_BA的计算结果都远优于改进蚁群算法，其中DBA的计算结果非常接近最优值，而LR_BA更可以得到全部算例的最优值.但在运行时间方面，DBA和LR_BA都耗时较长，这是文章的不足之处.总的来说，DBA和LR_BA都可以用来解决UFLP，但LR_BA在处理时具有更明显的可行性和有效性.

在表2中，Na和Nb分别表示DBA和LR_BA的十次运行结果中优于混合蚁群算法的次数.同时，为进一步分析DBA和LR_BA在求解UFLP时的有效性和计算复杂度，选择算例gs00250a给出求解的迭代过程图，如图1所示，虽然LR_BA中加入了拉格朗日松弛算法和三种可行化方法，致使其运行总时间远高于DBA，但是LR_BA的计算结果明显优于DBA，而且LR_BA的收敛性能明显得到改善.就UFL基准问题库的12个算例而言，DBA和LR_BA在超过一半的算例中得到的计算结果都优于混合蚁群算法.对比Na和Nb的值，发现LR_BA比DBA求解更为有效.LR_BA的最小Gap值和最大Gap值分别为0.790%和6.066%，其明显小于由DBA计算得到的最小Gap值1.256%和最大Gap值11.573%，然而混合蚁群算法的最大Gap值为35.976%，基本蚁群算法的最大Gap值竟达123.572%.四种算法的平均Gap值分别为83.532%、16.707%、4.909% 和3.092%，从中可以看出DBA和LR_BA的计算结果非常接近已知最优值，并且LR_BA的计算结果更优.但就运行时间而言，无论是求解小规模算例，还是大规模算例，DBA和LR_BA总会消耗较长时间.

6结论

为解决无容量设施选址问题，给出了一种结合BA和LR的混合优化算法.针对BA求解离散问题的局限性，重新定义了BA的操作算子，引入了汉明距离和精英保留策略，提出了DBA.在此基础上，通过对UFLP的具体特点进行深入分析，得到其最优解所具有的基本特征，结合LR，设计三种可行化方法，使两种算法取长补短，进一步引导LR_BA在有希望的解区域中强化搜索，明显改进了DBA的计算性能和求解结果.

通过求解24个UFLP算例，可以发现LR_BA无论对小规模算例还是大规模算例都具有较好的全局优化性能，能够有效求解UFLP，验证了该算法在求解质量上的优势，但也存在一定的缺陷，所需消耗的运行时间相对于其他算法来说较长，很难在合理的计算时间内求得问题的满意解，需要对此作进一步的改进，这是作者今后的研究方向.

参考文献

[1]吳烨. 物流配送网络选址的模糊数学模型及其算法[J]. 经济数学， 2008， 25（3）：277-282.

[2]堵丁柱. 近似算法的设计与分析[M]. 高等教育出版社， 2011.

[3]KOLE A， CHAKRABARTI P， BHATTACHARYYA S. An Ant Colony Optimization Algorithm for Uncapacitated Facility Location Problem[J]. Artificial Intelligence & Applications， 2014， 1（1）：55-61.

[4]DAMGACIOGLU H， DINLER D， EVIN O， et al. A genetic algorithm for the uncapacitated single allocation planar hub location problem [J]. Computers & Operations Research， 2015， 62（C）：224-236.

[5]李倩， 张惠珍， Cesar Beltran-Royo. 求解无容量设施选址问题的混合蚁群算法[J]. 上海理工大学学报， 2016， 38（4）：367-372.

[6]YANG X S. A new metaheuristic bat-inspired algorithm[C]//Nature Inspired Cooperative Strategies for Optimization （NISCO 2010）（Eds.J R Gonzalez et al.）， SCI 284， 2010： 65-74.

[7]ADARSH B R， RAGHUNATHAN T， JAYABARATHI T， et al. Economic dispatch using chaotic bat algorithm [J]. Energy， 2016（96）：666-675.

[8]刘春苗， 张惠珍， 马祥丽. 求解车辆路径问题的离散蝙蝠算法[J]. 经济数学， 2016， 33（4）：91-95.

[9]FISHER M L. Optimal Solution of Scheduling Problems Using Lagrange Multipliers： Part II[M]// Symposium on the Theory of Scheduling and Its Applications. Springer Berlin Heidelberg， 1973：1114-1127.

[10]高珊， 马良， 张惠珍. 函数优化的小生境蝙蝠算法[J]. 数学的实践与认识， 2014， 44（15）：253-260.

[11]李岳佳. 基于遗传算法的设施选址问题算法研究[D]. 济南：山东科技大学信息科学与工程学院， 2012.