具有凸运输成本的无容量定位问题的精确解决方法
摘要
在本文中，我们研究了非容量设施定位问题的精确求解方法，其中运输成本是非线性和凸性的。成本的精确线性化使得能够将问题公式化为扩展的线性纯零位置模型。开发了基于双上升和调整程序的分支定界方法，并与改进的Benders分解方法的应用进行了比较。研究的具体应用是具有空间相互作用的简单植物定位问题（SPLP），这是一种适合公共设施定位的模型。以前的近似求解方法已用于此问题，而我们在此论文研究精确的解决方法。提供了计算结果。
1.介绍
在文献中已经广泛地处理了不同类型的设施位置模型。在简单的工厂位置问题（SPLP）中，参见例如Cornuejols等人。（1990），以及大多数其他离散位置模型，设施和客户点之间的运输模式是通过最小化线性运输成本获得的。然而，在某些模型中，运输成本是非线性和凸性的。这与凹面生产成本（设施的固定费用）一起通常使问题更加困难。（在Holmberg和Tuy（1993）中，另一个具有这种特殊困难的模型，即凹凸非线性代价函数，都得到了处理。）
在本文中，我们研究了具有一般非线性可分凸运输成本的无容量设施定位问题的求解方法。我们假设运输量的整数要求（在SPLP中自动满足，但可能不在我们的模型中），这使我们能够对非线性成本进行精确线性化。通过这种方式，我们获得了一个线性的纯零点模型变量数量显着增加的价格。然后，我们研究了该模型的精确求解方法。在某些情况下，非线性运输成本是原始模型重新制定的结果。我们在本文中特别研究了下面讨论的一个这样的案例。
在货物运输方面，（线性）运输成本的频繁最小化通常是非常自然的。然而，在公共设施位置问题中，客户通常可以自由选择设施。对这种情况进行建模，目标不仅可以最大限度地减少总运输和设施成本。空间相互作用的影响已被用于改进这种类型的位置模型。在Coelho和Wilson（1976），Leonardi（1978,1983），Erlenkotter和Leonardi（1985），Jacobsen（1986,1988）中对旅行者之间具有空间相互作用的SPLP进行了处理，模拟为非线性，混合整数规划问题。在Holmberg和Jo rnsten（1990）中，导出了一个不同的模型，称为具有空间相互作用的SPLP的精确公式，因为避免了产生熵项的近似。得到的模型是线性整数规划问题，具有可以被几种不同解决方法利用的特殊结构。
在先前的报告中已经提出并研究了该问题的近似解决方法。已经开发出针对该问题的双上升程序，参见Holmberg和Jo rnsten（1996a）。另一种基于相同对偶的方法是拉格朗日松弛和次梯度优化，在Holmberg和Jo rnsten（1996b）中进行了研究。也可以使用基于原始和双重分解技术的解决方法，参见Holmberg和Jo rnsten（1995）。为了获得问题的精确求解方法，我们在本文中将双上升方法嵌入到分支定界框架中。我们将这种解决方法与Benders分解的修改版本进行了比较，发现在Holmberg和Jo rnsten（1995）中效率最高。在第2节中，我们提出了一般模型，在第3节中，我们讨论了具有空间相互作用的SPLP的特殊情况。第4节致力于解决方法。在4.2节中，我们回顾了双上升方法，在4.3节我们描述了双上升方法的分支定界框架，在4.4节我们回顾了修改后的Benders分解方法。在4.5节中，我们确定了要比较的方法，在第5节中我们给出了计算结果。
- 工厂位置问题简单，运输成本高
供应点（工厂）和n个需求点有多个可能的位置。如果建设工厂i，则产生固定成本fi。需求点j的需求为wj。引入以下变量。
xij=工厂i和需求点j之间的物流量， i=1,...,m,j=1,...,n
zi=如果位置i建设，则为1；如果没有，则为0。i=1,...,m.
工厂i和要求点j之间的流量xij的运输成本由gij（xij）给出，其假定为凸非线性函数得到以下模型：
SPLPC是纯整数问题，具有非线性目标函数。
现在我们在区间Ole;xijle;wij中对每个变量xij的成本函数进行线性化，每个整数点都有断点。注意这不会引入错误。然后变量的数量取决于需求的价值。让：
注意cijkge;cijk-1，由于gij的凸性。然后我们做替换xij=sum;kcijk，其中xijk是落在区间（k-1，k）中的xij的量。获得以下模型:
这是具有二元变量的大线性整数规划问题。请注意约束条件（6）中的系数都减少到1，这是有利的，因为它可以减小LP弛豫解和整数解之间的差异。我们现在有一个纯粹的O/l问题，在解决方法方面也很有用。
3.具有空间相互作用的简单定位问题
现在让我们讨论一个特殊的位置模型，即公共设施位置模型，其中有供应点（工厂）和n个需求点（现在是客户区）的m个可能位置。开放工厂i的固定成本是i。在需求点j，需求（现在是区域j中的客户端数量）是wj。将在需求点和开放的工厂之间进行运输，以满足需求。工厂i和需求点j之间的一次旅行的运输成本（即，区域j的客户在工厂i获得服务的成本）是cij。使用与第2节中相同的变量，但是这里xij表示工厂i和需求点j之间的跳闸次数（即，在工厂i中获得服务的区域j中的客户端的数量）。现在获得以下模型：
其中y反映了客户对成本的敏感性（这将在下面进行讨论）。SPLPS是纯整数问题，具有非线性目标函数，实际上仅在整数点中定义。通常，这样的问题很难解决。
目标函数可以通过以下方式激励。如果y非常大，则对数部分可以忽略不计，我们得到一个极端情况，即纯粹的成本最小化。然后该模型与SPLP相同，并且可以通过例如双上升法Erlenkotter（1978）有效地解决。如果gamma;=0，我们得到另=一个极端，忽略成本。然后我们注意到几个微观状态（通过识别每个客户的旅行获得）可能产生相同的宏观状态（x解决方案）。根据Wilson（1967）的观点，最大数量的微观状态给出的宏观状态是最可能的解决方案。最大化产生x的微观状态的数量，获得目标函数的对数部分。当然，最好的模型是通过组合极端来获得的。我们可以将gamma;视为客户将成本考虑在内的重量。必须通过针对现实生活情况校准模型来找到gamma;的最佳值。这里我们假设y是固定的并给出。
在之前的工作中，x中的连续松弛与Stirling的近似，产生了非线性的混合整数规划问题。我们现在可以完全按照第2节中的方式线性化每个变量xij的成本函数。我们再次注意到这一点这没有引入任何错误（与斯特林的近似相比）。在这里我们得到注意不是cijkgt;cijk-1，它表示所得成本函数的凸性。然后我们进行与第2节相同的替换，并获得模型SPLPE，即。
4.解决方法
4.1.使用标准的分支定界代码直接解决方案
解决SPLPE的第一种可能性当然是使用标准的分支定界代码，在我们的例子中是LAMPS，因为它是具有二进制变量的线性整数规划问题。然而，问题的大小是一个严重的缺点，由于存储器的要求，实际上无法解决大问题。
4.2.双重上升和调整方法
在Holmberg和Jo rnsten（1996a）中开发的双上升程序可用于解决问题的LP-松弛。该方法的想法是在小的受控步骤中增加双变量，从而提升双重功能。双重调整程序可用于暂时减少阻碍进一步改进的双重变量。
设cxj表示对应于SPLPE的LP松弛的约束集（5）的双变量，beta;ijk表示对应于约束集（6）的双变量，而bi表示对应的双变量约束zle;1。除此之外，在LP弛豫中只需要非负性约束。（由于约束集（6），不需要强制执行x变量的上限。）LP-dual模型如下：
该方法现在用于搜索双变量aj。对于固定的a，LP-dual很容易解决，趋近于
得到：
我们按如下方式进行。设kij如下：
并且：
我们定义
然后我们可以表明，Holmberg和Jo rnsten（1996a），即：
这意味着wl和wu是约束（13）左侧的下限和上限。所以为了获得可行性（意味着双重的最优性），这些界限应该包含右手双方j。在Holmberg和Jo rnsten（1996a）中证实了以下内容。
定理1.如果，那么我们有一个LP弛豫的最优解。
该方法现在以小步骤增加alpha;j，这使得wl和wu增加j。增加了alpha;j个某个j受最近断点的限制，由任一组（13）的双重约束引起或设置（14）（对应于启用或强制增加另一个zi）。边界wl和wu将从下面接近wj，我们不允许wl超过wj。aj的增加在j的每个步骤中继续增加，其中wu和wj之间的距离最大，直到找到最佳值（然后我们j停止）或者阻止改善（即进一步增加任何aj致wlgt;wj）。在最后一种情况下，我们使用调整程序，减少一些alpha;j，以允许增加其他alpha;j。然后重复上面的上升阶段。更多细节可以在Holmberg和Jo rnsten（1996a）中找到。
4.3.双上升和分支绑定
可以将上述双上升和调整过程插入到分支定界框架中，以产生精确的最佳值。然后使用双上升过程来解决分支定界树的每个节点中的子问题，尤其是在最优目标函数值上产生下界，但也常常是原始解。当下限超过已知的最佳上限时，分支被切断。首先，我们只考虑对z变量进行分支。然后我们必须能够在双上升阶段处理固定的z变量。设I0是zi固定为0的索引集合，I1是zi固定为1的索引集合。对于所有固定的z变量，即所有我0 I1，双变量bi被移除，并且集合（14）的相应双约束被移除。对于所有的相关集合（14）的主要约束是多余的，因此我们可以假设此外，我们当然有没有必要使得siisin;I0cup;I1，但我们必须从Igt;，I=，Ilt;中去除I0 I1的所有元素。
在这些变化之后，上面给出的互补松弛条件仍然有效，并且有界限wl和wu 可以如上计算。一些支持超平面将从双重中移除功能，作为固定的结果，因此在特定的双上升过程中，通常需要采取更少的步骤。（有时aj的增加受到设施打开的断点的限制。如果设施是固定打开或关闭的话，这不会发生。）为了证明这种分支定界方法的收敛，我们需要表明我们的双上升程序可以在所有z变量都得到修复时准确地解决问题。
定理2.如果所有z变量都是固定的，则双上升方法将在有限数量的步骤内准确地解决剩余问题。
证明。在SPLPE中，约束集（6）将被每个x伊杰克上的单独上限替换为0或1.这使得问题在j中可分离，并且对于每个j，以下简单的背包问题仍然存在。它具有完整性属性，因此我们可以删除x上的整数要求而不更改生成的解。
对于每个j，此问题的LP对偶如下：
请注意，此问题仅包含一个alpha;j变量。通过最优选择减少到以下形式：
应用我们的双上升方法来解决这个问题，它将从一个小的alpha;j（子梯度等于wj）开始，并通过找到剩余子集的最小成本系数逐步增加它，系数cijk。对于每个步骤，子梯度将减少一个单位，因此在精确wj迭代之后，将获得等于零的子梯度，这表示找到了双重最大值。
由于每个这样的步骤打开了将一个xijk增加到l的可能性，因此可以将相应约束（5）的左侧设置为等于wj而不违反互补松弛条件。因此，还获得了可行的整数原始解，并且该问题被解决为最优。
这结束了双重上升方法将在迭代中完全解决问题的证据，当所有的z变量是固定的。证据还表明，在这种情况下，x变量会自动获取整数值。因此，永远不需要对x变量进行分支，并且我们选择仅对z变量进行分支。因为在最坏的情况下，分支定界方法将枚举所有z-解，所以通过该方法在有限数量的步骤中找到最优。因此，我们得到以下结果。
推论1.分支定界框架内的双上升方法将在有限的步骤内找到SPLPE的精确最优值。
回到分支定界程序的实际问题，我们必须决定分支策略和树的搜索策略。与基于LP-松弛的分支和绑定相比，当在分支定界树的节点中使用的求解方法是近似时，会发生另外的复杂化。在我们的方法中，当双上升和调整过程停止时进行分支，这不一定意味着找到LP最优。在许多情况下，完成了不必要的分支，并且我们必须期望分支定界树比基于LP的分支定界方法更大。但是，如上所述，将某些变量固定为O或l会使双重功能更简单，并加速双重上升方法。因此，我们认为，有限的不必要的分支在实践中并没有比进一步努力精确地解决LP弛豫效率低得多。
使用的分支策略是分支任何ziiisin;I=，因为O和l之间的任何值都是最佳的。对于这样的zi，即互补松弛条件允许z的非整数值i。我们首先按深度搜索树，然后从l分支开始。在每个节点（第一个除外）中，我们可以选择从前一节点的双解（ex）开始。第4.5节讨论了一些由几个参数控制的选项。通常，这种分支绑定过程非常简单。当然可以开发更复杂的程序，这可能会显着减小树的大小。
4.4.本德斯分解
Benders分解，Benders（l962），是一种主要用于混合整数规划问题的方法。但是，在这种情况下，可以使用该方法精确地解决纯整数编程问题。下面我们简要介绍一下该方法如何应用于SPLPE，就像在Holmberg和Jo rnsten（1995）中对空
资料编号：[5153]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
