PDF格式
研究文章|开放获取
利用拉格朗日分解和体积算法求解设备容量定位问题
艾曼·J·阿莱内齐
1个
1个基础教育公共权力的数学系，学院应用教育和培训科威特，科威特城，科威特
摘要
在这项研究中，我们将集中研究这个问题的一个变种：电容设施选址问题（CFLP）。在CFLP的许多公式中，假设每个需求点只能由一个开放设施提供，这是问题的最简单情况。我们考虑每个需求点可以由多个开放设施提供的情况。我们首先研究拉格朗日松弛方法。然后，在问题分解中说明了如何引入更严格的约束条件，从而更快地求解CFLP，同时获得更好的质量解。同时，对于较大的问题规模，应用体积算法对原问题的最优解的上下界进行改进。
一。介绍
我们在文献中所知道的CFLP的测试用例问题数量有限，可以用来评估我们本研究的主要目标拉格朗日分解算法的结果。文献中开发的大多数算法都已在模拟数据上进行了测试。
拉格朗日松弛或拉格朗日分解是70年代初通过hold和Karp的工作引入的[1个,2个]霍尔德等人。[三]. 他们认识到系统旅行商问题和最小生成树问题之间的关系给出了最优解的一个明显的下界。此后，他们使用了一种称为次梯度优化的方法[三]结果表明，该方法能有效地逼近某些分段线性凹函数的最大值。拉格朗日松弛的概念是我们先放松一些约束，然后惩罚它们的违反，而放松这些约束的动机是许多组合优化问题由一个简单的问题和一些额外的复杂约束组成。将拉格朗日松弛法应用到这些问题中，可以将这些复杂的约束条件松弛并吸收到目标函数中。由此产生的放松问题变得更容易解决。
巴拉霍纳和安比尔[4个]提出了次梯度算法的扩展，将产生近似成本每次迭代;他们称之为体积算法。一般来说，它产生一个原始向量和一个对偶向量，可以作为一个更精确的方法的起点。他们成功地进行了线性规划问题的实验。
近年来，针对CFLP的各种应用，人们提出了大量不同技术的近似算法，如[5个–11].
阿莱内齐和哈拉夫[12]详细讨论了拉格朗日分解和体积算法的步骤。在本文中，我们使用它的变体来解决大型问题的CFLP。将所得结果与最优贪婪和贪婪弱解的结果进行了比较。
为了评估我们的拉格朗日分解算法的性能，我们开发了一些贪婪的启发式（过滤器），为文献中已知的问题提供了很好的解决方案[9个]. 这是为了在评估大型问题实例的拉格朗日分解方法时，比较这些启发式方法的有效性。
在非常大问题的极端情况下，不可能有任何强约束。然而，我们对模型表示采用动态方法，即在模型表示中动态添加有效的收紧约束。
特别是，在本文中，我们阐述所有的结果和我们的贪婪启发式算法和拉格朗日分解算法两个实验的分析。我们也有我们的算法相比，一些标杆车型的性能测试。
2.设备定位问题
设施选址问题(FLP)旨在确定若干设施的位置，为若干客户提供服务;因此，有一组潜在的设施地点F型；在指定地点开设设施具有关联的非负固定成本具有有限或无限的容量可用的供应。有一组客户（客户端）或需求点丁需要服务;顾客有需求这必须由开放的设施来满足。如果一个设施在位置用于满足客户的需求的一部分 ,然后是产生的服务或运输成本，通常与距离成正比我到j型，表示通过 .
让F型 = 一组潜在的设施位置，丁 = 一组客户或需求点，米=设施的可能选址数目; ,n个=客户数量; , 顾客的需求（其中 ） =满足客户需求的单位成本来自设施（其中 ） = the capacity of facility我（即，可从设施供应的总需求的上限我，其中 ）第页 = the desired number of open facilities, = 与开业设施相关的固定成本我（其中 ） = the fraction of the demand of customerj型提供的设施我（其中 ）和 = .
然后，将CFLP的表达式表示为一个混合整数规划问题，简称为发现在12]，如下所示。
目标方程：
这个方程保证了每个客户的需求得到满足:
确保关闭的设施不向任何客户供应，设施供应的需求不超过设施的容量，
这是完整性约束：
这种约束收紧CFLP的下界表示。的价值第页如下确定;我们的所有排序从大到小容量秩序的设施。然后，第页是这样的，按照设施的顺序，
虽然约束的右边(5个)由于我们的实验使用大大加快了计算速度，而且不影响解的质量，
最后一个不等式提供了分配变量的界限 .
为了发展一个拉格朗日启发式的CFLP，首先我们需要考虑线性规划松弛的问题，同样的公式( ）除了我们替换不等式(4个）通过
我们将指出放松的第页.
三。拉格朗日分解和体积算法（LD和VA）
在这一部分中，我们首先考虑上述问题的拉格朗日松弛(第页). 然后，我们描述了如何使用volume算法[7个]，这是次梯度优化的一个扩展。
为了研究大型问题的解决方法，我们遵循Alenezy和Khalaf的方法[12]也就是说，通过将CFLP分解成独立的问题，这些问题更容易解决。在这种方法的激励下，让为方程的对偶乘子j型在（1个)然后让 .然后，下限通过解决以下问题给出：
3.1条。拉格朗日分解
据广泛报道，求解以上提供了关于整数最优解的下界的好。这是通过使用所述音量算法改善。这个和事实，即它是难以解决的启发对于大型问题，我们分解问题进入米每个问题的独立子问题为了计算一个下界，我们也在这一点上放松约束(13)，我们稍后将在本节中返回这些内容。每个子问题的一般形式是
解决这个问题以得到一个下限（LB）很容易，对于上限（UB）也很容易。首先，我们将任意变量设置为0同 .然后，我们假设变量的其余排序，使得
现在，让千是最大的指数 ,然后让
如果 ,然后我们设置和为所有人j型. 否则，我们就对于和 .
在解决这些米独立子问题，我们接下来考虑满足所有需求所需的最少设施数量。这样，我们通过比较小时，在已经解决了米子问题，以最小的需要第页. 如果 ,然后我们按固定成本对未开张的设施进行分类，并开张最便宜的设施，直到我们有了第页开的。英镑适当增加，以应付这些额外的固定费用。
3.2。音量算法（VA）
为了提高通过解决上述问题的分解得到的下限，我们使用在[7个]同样的算法在[12]，它停止了一些通行证 = 200，接下来，我们将其扩展到2000。该算法可以通过以下步骤来表示：步骤1。从矢量开始并解决(八)–(13)获得 和并设置 .步骤2。计算 ,哪里和 ,对于步长s公司给出者(20.）以下。解决（八)–(13), .让 求出解。然后， 被更新为 哪里α是0和1之间的数。在为了设定的值α，我们解决了以下一维问题： 价值乙最初设置为0.1，然后每100次迭代我们检查至少没有增加1%，在这种情况下，我们将乙否则，我们就按原样保存。什么时候？乙变得小于 ,我们保持这个值不变。第3步. 如果 ,然后更新作为 .注意，在步骤3中，我们更新了只有 .第四步。停止标准。（一） （二） （三）通过的次数等于2000
当满足上述条件之一时，算法终止。如果不满足停止规则，则设置 ,然后转到第2步。
步长公式s公司就像在次梯度法中一样[13]: 哪里λ是介于0和2之间的一个数。为了设置它的值，我们定义了三种类型的迭代:（一）迭代E类，这是在下界上没有改进的迭代。一系列E类迭代需要更小的步长。因此，经过一系列的20E类迭代，我们相乘λ0.66。(2)如果 ,我们计算 ,为所有人j型和 .如果 ,这意味着较大的步长将为 ,我们称之为迭代是的.（三）如果 ,我们称之为迭代T型;一个T型迭代表明需要更大的步长，因此我们进行乘法运算λ按1.1。
3.3。计算LB
在[12]，我们发现，有两种解决办法以上以获得LB的问题的制剂为了保持本文自成体系，我们列出了以下方法：
第一种方法是分解进入之内米独立子问题。按照上面的说明解决它们。然后，使用前面提到的VA更新这个LB，但在步骤1中有两种方法。一种方法是设置向量的值0并继续使用VA来提高LB。另一种方法是设置向量到由“热启动二元论”表示的值。热启动二元论是放松约束二元论的值(1个），从解决CFLP作为溶液的贪婪弱表示获得。
第二种方法是首先移除约束(11)从公式化以缩小问题的规模，使其得以解决。然后，在不使用上述分解技术的情况下求解它，得到一个LB。为了再次改进这个LB，我们使用与前面讨论的两种方法相同的VA。
注意约束条件(13)包括在公式，但只是部分如前所述，适用于获取LB。这里的另一部分是多余的，因为它只会影响在下一个方法中获得UB。这种方法的下界并不总是有整数值是的，但在分解方法中并非如此；因此，此方法中的LB通常比分解方法中的LB更差。
3.4条。计算UB
要计算UB，一种方法是首先删除约束(三）。解决第页LP溶液配方。然后，使用一种称为随机四舍五入(RR)的技术和一种称为单位成本技术的新技术，来处理是的作为一种概率分布，不断地随机打开它们以获得足够的容量。我们一直在更新这个UB使用VA每50次通过，直到我们满足其中一个停止标准。我们选择50次通过是因为UB变化缓慢，从我们的实验来看，50次通过通常显示UB有一些改进。这是获得UB的一种方法。
另一种方式是与上述类似，除了我们解决后第页问题：我们称贪婪弱表示的上界。我们称这种策略为“温启动UB”。这种UB导致VA的步长变小。因此，在我们的实验中，LB和UB都收敛得更快。然后，在50次传球后，我们像以前一样调用下面的RR技术。我们一直使用VA和RR技术，直到我们满足其中一个停止标准。
第三种技术称为“单位成本技术”（UC），它选择由于按成本来打开。它选择具有最小单位成本的人。我们调用RR之前调用这项技术一旦开头。再经过50次传球，我们切换到调用RR，并保持调用RR每50遍，直到我们停止条件之一满足时更新UB。接下来，我们将详细讨论这些技术。
3.5条。讨论
结合上面讨论的获取LB和UB的方法，我们得到了解决CFLP的8种不同的方法。数字1个下面是一个树形图，用于简化由方法LR1–LR8表示的这八种方法。
这些方法在解决CFLP的大小不同使用。为了确定这是使用的方法来解决这些问题，我们的问题分为三类：小，中等和大。
四。计算结果
选定的模型集合来自Beasley[14], and we selected two instances where they fail to find feasible solutions when they use the factor = 1.5. The factor value is defined as ,这是用来重新调节容量值。他们使用产生一个可行的整数解启发式和使用的拉格朗日松弛和体积算法，以获得下限最佳值。对于CFLP，他们能够解决实例最多 .
我们使用Beasley工作中生成的实例[7个拉维和辛哈的作品[9个]，具体如下：（一）我们产生的需求点j型和设施点我均匀随机地在a中(2)需求值由平均值35和标准差5的均匀分布产生， （三）能力从产生然后重新缩放，以便设置为等于参数因子；设置为10，在某些情况下为1.5（四）的固定成本每个位点都是用公式设置的（五）单位运输成本对应于欧几里德距离标度10
接下来，我们报告两种算法的实验结果，使用方法LR1–LR8表示的许多方法。第一种是无分解的拉格朗日松弛算法（LR1-LR4），我们用LR和VA表示该算法；第二种是分解的拉格朗日松弛算法（LR5-LR8），我们用LD和VA表示该算法。
回想一下，我们根据问题的大小将其分为三类。班级有小、中、大。在接下来的小节中，我们将报告结果和对每类问题的分析。
4.1条。小问题
在桌子上1个下面，我们报告解决大小为100-300的小问题的解决方案。通过比较上述两种算法的解，我们注意到拉格朗日分解的LB和UB与体积算法LR5-LR8在质量和运行时间上都要好得多。两种算法在LB上有很大的差异，原因是LD算法的优点之一是强制成为1。另外，我们还得到了一个闭LB作为贪婪问题的强表示，但是UB和运行时间都比较好。此外，在我们的一些方法LR5–LR8中，错误值小于贪心值。
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
在下一个表中，“passes”列显示了我们寻找更好的LB和UB的算法的次数。最后一行对应于我们能够获得的最佳贪婪解；为了进行比较，我们将其包含在这些表中。最后一列对应于错误百分比值，可以通过 .此值显示问题的上下限之间的百分比差距。如果这个值小于 .另外，在大多数结果中，停止条件是通过的次数，而在其他结果中，它们是错误值。
4.2条。中等规模的问题
桌子2个下面列出了解决400-900个中等问题的所有结果。我们使用拉格朗日分解算法仅仅是因为问题的规模太大，不分解就无法求解。问题大小的结果表明我们能够获得一个更好的LB和UB相比，那些贪婪的解决方案。而且，他们之间的差距小于贪婪的解决方案的差距。在问题尺寸500-900，我们能够得到的一个间隙内的可行的整数解（UB）小于下界LB在我们大部分的解决方案，并在别人小于 .停止标准是在大多数结果的误差值。
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4.3。大尺寸的问题
在桌子上三我们用体积算法和拉格朗日分解来解决大型问题的所有结果，这是本研究的目标。我们能够解决CFLP的大型实例。解决的最大问题是规模 .在一些问题中，我们能够比较贪婪者的解决方案和贪婪者的解决方案。桌子三表明我们取得了较好的LB和UB比贪婪的。而且，他们之间的差距比UB和贪婪的的LB之间的差距小得多。在所有的问题的解决方案的，所述间隙小于 .
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
五，结论
在这篇文章中，我们已经调查解决CFLP非常大的情况下。我们首先提出了一个CFLP一般代数模型。此外，所创建的拉格朗日分解表示解决CFLP的大对象。我们改进了低了都利用分解方法以及引入紧缩约束，这是一个新的正面除了解决CFLP拉格朗日分解方法结合这一技术。
对于非常大的问题，我们将随机舍入技术与单位成本技术一起应用，在合理的计算时间内提供了良好的UB。
本文研究的重点是要能解决CFLP非常大的情况下。我们已经说明，我们的算法扩展了。我们的研究结果表明，增加问题的规模导致的LB和UB之间的相对误差较小而对计算时间过多的负担。为了处理这种大型号的情况下，我们已经利用在实现我们的算法稀疏技术的技术。因此，我们已经开发出一种稀疏的数据结构，我们利用我们的算法实现。
数据可用性
用于支持本研究结果的数据可根据要求从相应的作者处获得。
利益冲突
作者宣称没有利益冲突。
参考
- M、 Hold和R.M.Karp，“旅行商问题和最小生成树”运筹学，第18卷，第6期，第1138-1162970页。视图:发布者网站|谷歌学者
- M、 Hold和R.M.Karp，“旅行商问题和最小生成树：第二部分”数学规划，第1卷，第1期，第6-25页，1971年。视图:发布者网站|谷歌学者
- M、 Hold，P.Wolfe和H.P.Crowder，“次梯度优化的验证”数学规划，第6卷第1期。1，第62-88页，1974。视图:发布者网站|谷歌学者
- F.巴拉奥纳和R. Anbil，“体积算法：产生具有梯度方法原始的解决方案，”数学规划，第87卷，第3期，第385-3992000页。视图:发布者网站|谷歌学者
- K、 Aardal，“有能力的设施位置：分离算法和计算经验，”数学规划，第81卷，第149-175页，1998年。视图:发布者网站|谷歌学者
- K、 Aardal，“容量化设施选址问题的重新制定：冗余信息如何帮助，”运筹学纪事，第82卷，第289-308页，1998年。视图:发布者网站|谷歌学者
- J. E.比斯利，“为解决大容量限制仓库选址问题的一种，”欧洲运筹学杂志，第33卷，no。3，第314-325页，1988。视图:发布者网站|谷歌学者
- J、 E.Beasley，“定位问题的拉格朗日启发式方法”欧洲运筹学杂志卷。65，没有。3，第383-399，1993。视图:发布者网站|谷歌学者
- R、 拉维和辛哈，“设施选址和网络设计问题的近似算法”运筹学卷。54，没有。1，第73-81页，2006年。视图:发布者网站|谷歌学者
- Hajiaghavi, M. M. Mahdian，和V. S. kni，“具有一般成本函数的设施选址问题，”网络卷。42，没有。1，第42-47，2002。视图:发布者网站|谷歌学者
- M、 Mahdian，E.Markakis，A.Saberi和V.Vazirani，“一个贪婪的设施定位算法，使用双重拟合进行分析，”近似、随机化和组合优化:算法和技术，第2129卷，施普林格- Verlag LNCS，柏林，德国，2001。视图:发布者网站|谷歌学者
- E、 J.Alenezy和R.F.Khalaf，“实现拉格朗日分解技术以获得设施位置问题解的充分下界”应用数学，第4卷，第8期，第1168-1172页，2013年。视图:发布者网站|谷歌学者
- D.塞拉，S. Ratick，和C.雷维尔，“最大捕捉问题的不确定性，”环境与规划B：规划与设计卷。23，没有。1，第49-59，1996。视图:发布者网站|谷歌学者
- 《图书馆:通过电子邮件分发测试问题》，运筹学学会杂志，第41卷，第11期，第1069-107219990页。视图:发布者网站|谷歌学者
版权
版权所有©2020 Eiman J.Alenezy。这是一篇在知识共享署名许可协议，其允许在任何介质无限制地使用，分发和再现时，所提供的原始工作正确的引用。
