英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

物流配送中心的二级编程模型和解决算法

Sun Huijun* , Gao Ziyou, Wu Jianjun

北京交通大学轨道交通安全国家重点实验室，北京100044

北京交通大学交通运输学院，北京100044

2006年6月1日收到 2006年11月1日修订;

2007年2月6日接受可在线2007年2月21日

摘要：在本文中，通过考虑客户和物流规划部门的利益，双层次的编程模型是提出寻求物流配送中心的最佳位置。 上层模型是确定最优的位置通过最小化计划者的成本，而较低者通过最大限度的减少客观需求分布，昂贵的成本。 基于约束的特殊形式，提出了一种简单的启发式算法。 最后，用于说明该方法的应用，这表明该算法是可行和有利的。

关键词：双层编程模型; 启发式算法; 位置; 物流配送中心

介绍

配送中心的选址是最重要的管理决策之一。两个分销系统的成本和系统提供的客户服务水平受到重大影响通过配送中心的数量，规模和位置，以及决定哪些客户从每个中心服务（即客户分配到配送中心）。因此，一个重要的研究的数量一直用于配送中心的数学模型的开发，

[1-9]。Aikens提供了九个基本的位置模型，其中包括简单的不起作用的设施位置模型，能力设施位置模型，动态和随机能力设施位置模型这些模型的所有目标功能都是尽量减少运输成本和固定投资费用[2]。 Holmberg [3]研究了不可预测的设施位置问题的确切解决方案运输成本是非线性的。工厂位置的整数规划模型为由Barahona和Jensen提出[5]。它不仅考虑到固定成本和运输成本，而且考虑到库存成本由Dantzig-Wolfe（D-W）分解方法解决。欧文和

Daskin [4]考虑了设施位置问题的动态性质和定制问题的随机性质，需求，并开发简单的动态和随机定位模型。最近，Klose和Drexl [6]回顾了目前设施位置状况的一些贡献配电系统型号。 Zhou等[7]调查了客户的平衡分配，贡献中心采用遗传算法方法。 Syam [8]调查了一个模型和方法物流组件的位置问题。 Lu和Bostel [9]给出了物流系统的设施定位模型，包括逆流。尽管Miller等人[10]研究了均衡关系的位置问题紧张的模型和算法详细，他们只是单级模型，不能考虑有利于规划者和客户。

总而言之，大多数公式都集中于混合整数规划表示，其中两个通常包括各种变量：给定的定位设施（配送中心）的整数变量区域和连续变量，用于确定通过系统的产品流量。在这样一个级别模型，这两个变量需要同时解决。而在实践中，位置和需求分配决策由两个不同的决策者决定。客户需求分布配送中心由规划者决定是不明智的。其实客户总是根据自己的习惯和行为选择配送中心，这种行为是非常的随机。另外，规划人员只能根据定制设备估算配送中心的位置，需求的同时，不同的位置模式也会影响客户需求的分配。

显然，物流配送中心的位置问题可以表现为领导者或者stackelberg游戏，决策管理者是领导者，客户是追随者自由选择配送中心。因此，它适合代表位置问题双层编程模型。然而，虽然设施位置问题已经被广泛研究了已经非常少的关注使用双层编程模型来模拟位置问题。 Tanig-uchi [11]开发了一个双层模型，以确定公共物流终端的最佳大小和位置。该模型的上层描述了计划者的行为，以最小化总成本，运输成本（线路运输和提货/运输成本）和设施投资成本。较低的水平是确定卡车和乘用车的用户平衡分配公路物流终端候选地的任何地点模式下的道路网络。该模型直接采用遗传算法作为解决方案。但是，位置位置的影响客户需求分配（响应函数形式）未得到准确分析。无论是accu-双层次的速率响应函数（上位变量与低级变量的变异关系）获得的模型是否对有效的算法至关重要。在本文中，我们打算给出一个启发式算法 - 通过使用简单的方法估计响应函数，这是基于con的特殊形式双层位置模型的压力。

本文的组织结构如下。下一节将介绍双层程序的基本思想，明法在第3节中，提出了双层编程位置问题的上层模型。第4节给出了较低级别的模型。提出了一种新的启发式算法来解决这一双层模型。最后，给出了一个数值示例来说明该模型及其算法的应用。

2. 二级编程模型的基本思想

假设，通过改变位置模式和广义成本与政策和管理 - 决策管理者可以影响，但不能控制用户的选择行为。 客户群根据习惯性和需求特征选择现有的配送中心。这种互动游戏可以表示为以下双层编程问题[12]：

显然，双层编程模型由两个子模型（U0）组成，（L0）是较低的水平。 Feth;x;yTHORN;是上级决策者的目标函数或系统经理，x是上级决策者的决策向量; G(x;y)是约束一套上层决策向量。 F(x;y)是下级决策者的目标函数; y是下级决策者决策向量;而g(x;y)是下级决策的约束集向量; yfrac14;=y(x)通常称为反应或反应函数。解决双层次编程的关键模型是通过解决较低层次的问题来获得响应函数，并替换变量y上层问题与x和y之间的关系是响应函数。我们可以看到，响应函数连接上下级决策变量，这使得两个编程模型依赖于彼此。只有一个变量的优化不能优化整个系统的性能，反映功能的本质。

与传统的单级编程模型相比，双层编程模型具有更多的优势。主要优点是（1）可以用双层次编程来分析两个不同甚至冲突的目标同时在决策过程中; （2）teria决策方法可以更好地反映实际问题，（3）层次编程方法可以明确地表示系统管理者之间的相互作用顾客。

由于涉及两类决策者的物流配送中心的位置问题是系统管理者和具有不同目标功能的客户。显然，这是适当的采用双层编程模型来描述位置问题。

3. 层次编程定位问题模型

在本文中，双层次编程模型的上层次是确定最优地点，对接中心使总成本（固定成本和可变成本）最小化并满足客户的需求在各方面，在决策者制定的固定投资范围内。 较低级别代表 - 对客户需求在不同配送中心之间进行分配，其反对意见是尽量减少每个客户的成本。 同时，假设以前没有任何旧的配送中心新建的。 也就是说，新旧配送中心之间的竞争不是

sidered。 随着非线性凸变量成本（运输成本和库存成本等）级别编程如下：

其中C ij（AElig;）是从分配中心j满足客户i的需求的单位广义成本，它通常是一个非线性函数; X ij是由配送中心j提供的客户的需求; f j是与建筑物配送中心j有关的固定投资; z j是0-1变量，如果分配中心j是那么z j的值为1，否则为0。从决策者的角度来说，上级目标功能右侧的第一项，代表满足客户需求的总可变成本，右边是第二项代表与建筑配送中心相关的固定成本。 固定投资包括征地费用和设施建设成本。 约束（2）确保至少一个分配中心 - ter被构建，约束（3）表示决策变量的二进制限制。模型（U）是0-1非线性整数规划问题，可以通过分支绑定方法来解决。 X ij在模型中（U）可以通过解决以下较低级别的编程来获得。

4. 二级编程定位问题的下层模型

在配送中心系统中，特定客户需求的分配受到作业的影响的其他客户需求。如果所有的客户都要采取相同的配送中心（这可能是最初的）在旅行费用中最短的一个），因为成本对总需求的依赖，拥塞会发展起来。因此，这个位置的成本可能会增加到不再是这个地步最低成本一。其中一些客户然后将使用替代的分销中心。然而，位置也可能拥挤，等等。此过程称为需求分配迭代直到达到平衡状态。在用户均衡状态下，所有使用配送中心的成本为相等于（以及）小于或等于单个车辆在任何未使用的车辆上经历的成本中心。这种平衡称为用户平衡（UE）条件。为了反映这种现象，我们使用需求函数来描述这种最小成本的关系，i和j：

其中u ij是从配送中心j满足客户i的需求的最小成本; D ij（AElig;）最小成本u ij的递减函数，其中反映分布的其他具体参数尺寸，服务水平和成本信息等。因此，下层模型如下：

其中D？1（AElig;）是需求函数的倒数，功率和对数函数是常见的形式需求函数的倒数;我是客户i的总需求; s j是配送中心j的容量;中号是一个任意大的正常数。较低层次的问题代表了客户的选择行为，分配中心，也就是说，每个客户将配送中心的需求分配给最小化他的总成本。约束（6）确保每个客户的总需求必须通过某些供应来满足配送中心约束（7）是容量约束，确保所有需求分布配送中心不会超过其容量。约束（8）禁止对任何拟议分配的要求，对接中心，实际上没有建造。由于M是任意大的正常数，所以如果z j = 0，那么X ij不能为正;但是如果z j = 1，则X ij可以根据需要而大。最后的约束表示非决策变量的否定性限制。同时，很容易显示出Hession矩阵问题（5） - （9）对于给定的z是正定的，因此模型具有独特的解决方案。可以证明在较低级别模型被最小化的时候满足UE条件[13]。

5. 解决算法

一般来说，很难解决双层编程问题。其中一个原因是双年级克重问题是NP难题。 Ben-Ayed和Blaint [14]深入研究了这个问题指出即使是一个非常简单的双层级问题仍然是一个NP难题。非凸性是另一个H. Sun等/应用数学建模导致解决算法的复杂性。即使上下层的问题都是凸，整个双层问题可能是非凸的，这表明即使我们可以找到

解决双层问题，通常局部最优不是全局最优。

本文提出的解决双层编程问题的难点在于如何描述提出的双层模型中的响应函数的形式。虽然很多解决算法为已经开发了仅具有连续变量的双层模型，如基于敏感性分析的algo-

算术（SAB）[12,15,16]。然而，SAB方法不能应用于解决所提出的双级程序 - 因为有混合的连续和离散变量。混合整数双层编程问题分析工作有着丰富的历史[17-20]。怎么样-这些结果大多数处理线性目标函数。虽然埃德蒙兹和巴德提供了一种用于混合整数非线性双层编程模型的有效算法，该模型需要一个vex二次目标函数在较低层次的问题。上下目标功能我们的模型中的水平问题都是非线性的，显然，目前的所有结果都不适合他们。那里-鉴于本文制定的特殊形式，采用了一种新的启发式算法来解决双层次问题提出了具有混合变量（连续和离散变量）的模型。解决双重问题的关键问题是，级别模型是找到反应函数，即上下变量之间的关系。我们的algo-算法是通过获得变量X ij和z j之间的简单关系来求解模型。

为了给出二级编程模型的求解算法，我们可以考虑模型（L）知道约束（8）可以用来简单地表示客户需求之间的关系X ij和均衡条件下分布中心z j的位置模式。对于给定的z j的值较低级的问题，如果z j = 0，那么X ij = 0，这个约束可以被丢弃;如果z j = 1，则X ij 6 M（M是a较大的正常数。），这个约束自然而然，也可以被丢弃。总之，对于固定的z j，约束（8）可以省略。但是为了得到具体形式的反应函数，约束（8）可以转换成以下形式（它不被添加到下级模型的约束中）：

其中y ij是松弛变量。 对于较低级别的模型，变量z j是已知的。 当z j = 0时，值可以直接获得X ij和y ij：X ij = y ij = 0; 当z j = 1时，我们可以解决较低层次的问题现有的算法，如惩罚函数方法，并得到分配之间的需求中心Xij。 那么方程 （10）可用于计算松弛变量y的值ij。 因此所有的形式的反应功能可以描述如下：

哪里y ij是最佳的松弛变量。线性方程（11）用于描述上下两个变量之间的关系，级别模型。在我们的算法中， （11）代入上层模型，用这个信息 - 上限目标函数和约束，这些是隐含的，可以表示为函数的z。这将导致上层的整数规划问题，只能用变量z，这可以是通过非线性整数规划问题的众所周知的方法解决，如分支和绑定方法和外部近似算法，并获得最优值z *。对于固定的z，解决较低层次的编程，得到分配中心之间分配的新的均衡需求和响应

功能。重复上述过程，结果预计会收敛原始的最优解双层编程模型。该解算法实际上是基于等式的启发式算法。 （11）。该双层编程模型的算法总结如下：

步骤1：确定初始位置模式集合z 0，并设置k = 0;

步骤2：对于固定的z j k，求解较低级的问题并得到X kj

步骤3：基于公式（10），计算y kij。替代XķIJ在上级模型中用Mz j？ y kij，并解决

上层问题，并获得zkthorn;1的新值Ĵ;

步骤4：如果jFkthorn;1？ Fk j 6 e，然后停止;否则，设置kfrac14;kthorn;1，转到步骤2，其中e是收敛公差。

考虑较低层次的问题，它包括容量限制，是非线性规划问题，这可以通过一些众所周知的方法来解决。但有时为了简单地解决它，一个内部惩罚函数法可用于降低能力限制，则较低级别的模型可以通过凸组合法求解[21]。为了加速算法的收敛，M值应尽可能小。一般而言，假定与所有人的总需求相等顾客。

另外，由于算法是一种启发式算法，因此难以测试其收敛特性。因此，我们可以用不同的初始点计算足够的时间，如果所有结果都相同，那么可以是相信算法是收敛的。另外，我们可以用Frank-Wolf的方法来解决较低层次的问题模型，通过获得响应函数，上层可以通过公知的方法来解决。该已经证明了这些已知方法的收敛。

6. 数值示例

在本节中，提出了一个简单的数值示例来说明模型和算法的应用，提出了最优位置问题的算法。 数字实例确实非常弱，只能给出好处，从观察客户的实际行为中可以看出样本。 但是，该示例只显示了算法过程及其可行性。假设有一个客户，四个候补站点的配送中心（B1，B2，B3，B4）系统和广义成本函数是C ij (X ij ) = a ij (X ij ) ^bij - E ij . 客户的需求w 1为400，需求函数的倒数如下: D ^-1 (X ij ) =a ij (X ij ) ^{b ij} -V ij。其中ij，b ij，E ij和V ij是对数。 组

一个

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[28432]，资料为PDF文档或Word文档，PDF文档可免费转换为Word