基于聚类方法的物流中心选址的双层规划模型.doc

《基于聚类方法的物流中心选址的双层规划模型.doc》由会员分享，可在线阅读，更多相关《基于聚类方法的物流中心选址的双层规划模型.doc（15页珍藏版）》请在三一办公上搜索。

1、基于聚类方法的物流中心选址的双层规划模型以上介绍的这些选址模型都假定从设施点或物流中心到需求点（客户点）的配送是放射线状的，即从设施点出发的运输车辆每次访问一个客户后，就返回到该设施（见图1）。这样配送过程中的运输费用就表示成了这种直接返回的距离的函数。实际上，有些不满载的配送任务从物流中心到客户都是采用巡回线路的，即若干个需求量较小的客户在一条配送线路上（见图2）（Hokey，1998；Klose，1996；Srivastava，1993；Bramel和Simchi-Levi，1995；Hansen et al.，1994）。因此，传统的运输费用表示忽视了对车辆巡回线路的考虑，有可能造成对分

2、销成本估计的不准确。随着物质需求的多样性及贸易呈全球化趋势的发展，企业管理者希望协调好物流系统中的各个环节，即采用集成物流管理系统的概念。此概念认为在设施相对于客户的位置、货物的配送、运输货物车辆路线的安排之间存在相互依赖关系（Hokey，1998）。因此，对于某一物流中心服务于各个客户的费用不再是独立的，而是车辆路线安排的结果。 图 1放射线路 图 2 巡回线路表示客户点； 表示建立的物流中心； 表示运输路线； 表示没建的物流中心在国内，还未见到这方面有影响的研究成果，而国外学者如Hokey（1998）和Klose（1996）等在有关文献中对这类设施选址问题进行了研究，这些研究都是将设施选址

3、和运输路线安排结合起来同时考虑的，模型的目标：找出最优的供应点的位置，同时还要使供应点到各个需求点的运输成本最小。这些模型在得出了最优配送路线的同时，也合理计算了每个客户的运输费用。模型求解方式：求解这类问题一般采用启发式算法，通常的求解模式：先选址后安排线路；先安排线路后选址；基于聚类的算法等。但多数这类问题也是在单层规划的基础上解决，不能同时考虑规划人员和客户的利益。为克服现有此类模型的不足，我们在此也用双层规划来描述这类问题。1 基于聚类方法的物流中心选址的双层规划模型上层规划（U5）的描述：决策部门在允许的固定投资范围内确定最佳的物流中心的地点用最小成本吸引最大的需求量。下层规划（L5

4、）的描述：与前面的模型（L1）相同，描述了在多个物流中心存在的条件下，客户需求量在不同物流中心之间的分配模式，它的目标是使每个客户的费用最低。此模型也假定在新物流中心建立前不存在已有物流中心，也就是不考虑新旧物流中心之间的竞争。具体模型：（U5） （25） 其中为第个客户由地点的物流中心提供服务的广义单位费用（,）； 为修建物流中心的总投资预算；为匹配投资费用与需求量单位的系数。其它符号与前面定义相同。上层目标函数是从决策者的角度出发使其总的广义费用和客户需求量之差最小，表示既要最小化总费用，又要尽可能多的容纳客户需求量。第一个约束保证修建的物流中心费用不超过其总投资额；第二个约束保证至少建一

5、个新的物流中心；第三个约束为变量的0-1约束。模型（U5）为0-1整数规划问题，可用分枝定界法求解。值得指出的是（U5）中由下层规划（L5）求得。模型的分析：由于在现实配送系统中，某个客户需求量的分配会受到所有客户分配需求量的影响，比如当系统中多个客户要求同一配送中心为其提供服务时，在这一配送中心处服务的广义费用就会增加，有些客户可能会选择其它配送中心，相应的在这一配送中心分配的需求量会减少，这是显而易见。为了反映这一现象，可以用一个需求函数来描述这种关系： （26）式中为第个客户要求第个配送中心提供服务的最小费用。一般讲，所有客户的需求函数具有基本一致的形式，只是函数的参数不同（Sheffi

6、, 1985）。（L4.5） = （4.27） ， 其中为需求函数的反函数，其他相关符号的定义与前面相同。目标函数及其约束含义也与前面相同。2 基于聚类的运输费用估计及求解算法传统的运输成本是在假设从物流中心出发访问一个客户即返回的情况下的费用值，事实上，在不满载的情况下，可能有多个客户同时在一条巡回线路上接受服务，这时的费用值与传统费用有很大不同。因此，我们用分级聚类方法对传统运输成本的估计进行修正，将由同一个物流中心提供服务、能在一条线路上的客户聚为一类，然后根据每一类估计其费用值，这样物流中心也能合理计算它的配送成本。首先将由某一物流中心提供服务的所有客户的成本估计看作一个子问题，其具体

7、步骤如下：第一步：初始化，设每个客户单独为一类。第二步：具有最小距离的任意两类、合成为一新类，同时保证合并的新类中需求量不超过车容量及每条线路最大长度的限制。若两距离相同，在满足车容量和线路长度的条件下尽可能将更多客户聚为一类。直到不能合并为止。第三步：用表示从第个物流中心出发的通过客户的第条线路上的单位运量总费用（），最优的可由对每一条线路解旅行商（TSP）问题得到。那么物流中心服务客户（类）的成本为： （28）表示此类中（即这条线路上）所有客户的总需求量不超过车容量及线路最大长度限制。依上述步骤对所有提供客户服务的物流中心的运输成本进行估计，得所有的单位运输成本。由于此模型也不考虑竞争，则

8、其基本算法可采用第一小节的思路。求解双层规划模型的算法步骤可写为：第一步：设定一个初始解，令迭代次数；第二步：对于给定的，求解下层问题，得到；第三步：根据式（28）估计服务各客户的运输成本；第四步：根据式（24），计算，将关系式=代入上层目标函数，结合求解上层问题，得到一组新的值；第五步：如果，停；否则，令，转第二步。其中为迭代精度。3 算例分析在本节中，用一个简单的例子来说明双层规划模型在物流中心选址决策中的应用。为了计算方便，算例中的数值都是假定的。在实际应用中，应通过实际观测用统计方法来校正。假设系统中只有三个客户（B1、B2、B3）、二个新建物流中心的候选点（A1、A2）。客户初始需求

9、量，。需求函数的反函数采用如下幂函数的形式：，其中为参数。可令，。另设，。客户之间的距离为，。同时假设各物流中心的能力都能满足要求，其车辆载重量为70。其计算步骤为：第一步：初始化。设所有候选物流中心全部修建，=（1,1），并置。第二步：求解下层问题，得到均衡条件下客户需求量在各物流中心的分配，则反应函数的关系分别为：，第三步：根据三个客户之间的距离和车辆载重量的限制，可将客户B1，B2分为一类，B3单独为一类，即B1和B2在一条线路上，B3单独在一条线路上。然后根据服务每个客户的单位成本用式（4.28）计算每条线上的单位运量成本，设其为， （成本计算在实际中应根据距离聚类得来）。第四步： 将

10、所得线性关系代入上层规划目标函数中，利用分枝定界技术求得上层问题一组新的选址方案：。第五步：收敛判断，显然，令，转到第二步。最后，经过二次迭代，得到选址方案的合理值为：，即实际的物流中心只在第一个候选物流中心地点建，第二个候选地点不建。考虑竞争的物流中心选址双层规划模型在本节中，上层规划（U6）可以描述为决策部门在允许的固定投资范围内确定最佳的新选物流物流中心的地点以使得总成本最小（包括固定成本和变动成本）。而下层规划（L6）则描述了在多个物流中心存在的条件下，客户需求量在不同物流中心之间的分配模式，它的目标是使每个客户的费用最低。具体模型如下所示。令 为所有物流中心地点的集合，其中为已有物流

11、中心的集合，为新增候选物流中心集合。本模型的上层规划为传统的离散选址模型：（U6） （38） 其中为第个客户由地点的物流中心提供服务的单位运量的广义费用（,）；为第个客户在地点的物流中心得到满足的需求量；为在（）地建物流中心的固定投资；为0-1变量，在（）地建物流中心时，此值为1，否则为0；为总的投资预算。上层目标函数是从决策者的角度出发使总的广义费用最小。第一个约束保证建立的物流中心总投资不超过其总预算支出；第二个约束保证至少建一个新的物流中心；第三个约束为变量的0-1约束。模型（U6）为0-1整数规划问题。值得指出的是（U6）中由下层规划（L6）求得。下层规划为：（L6） = （39） ，

12、 ， 模型中的有关符号定义与前面相同。下层规划表示客户选择最优的物流中心，即各个用户在各物流中心间分配需求量，以使其总费用最小。第一个约束保证物流中心能满足所有客户的需求量；第二个约束保证客户需求量只在要建的物流中心处分配，不建的地点分配需求量为零；最后一个约束为变量的非负约束。同时目标函数的Hessan矩阵是正定的，因此模型（L6）有唯一解。同时假定每个物流中心的能力都能满足需求，也就是不考虑物流中心的能力限制。一般非线性混合整数双层规划求解算法 一般来说，在实际中，非线性混合整数双层规划模型具有如下形式（P4） （40） 其中由下述规划求得 （41） 其中，。 从前面小节的分析我们知道，求

13、解双层规划问题是非常困难的。然而，相对于连续变量型的双层规划问题的求解而言，求解混合整数型的双层规划问题就变得更加困难。主要原因在于难以找到反应函数的具体形式。事实上，由于求解含有大量0-1变量的混合整数型双层规划问题存在困难，所以离散网络设计问题在交通领域仍被认为是最困难和最具有挑战性的问题之一（Magnanti 和Wong, 1984；Yang和Bell, 1998）。虽然具有连续变量的双层规划问题已经有很多有效的求解算法（参见上节），例如基于灵敏度分析的方法（Kim, 1990; Yang et al., 1994, 1998; Wong 和Yang, 1997; Gao和Song, 2

14、002）。然而这些方法难以求解非线性混合整数型的双层规划问题，因为混合整数型的双层规划问题中既含有离散变量也含有连续变量。目前通常使用求解非线性混合整数型双层规划问题的方法是库恩-塔克方法，此方法一般使用分枝定界技术来解决互补性问题（Bard，1983; Edmunds和Bard, 1992）。但此方法考虑的下层规划的目标函数仅是二次凸函数的情形，而本节下层规划为一般非线性规划，不能用此方法进行求解。为此，下面我们介绍求解一种特殊类型的非线性混合整数型双层规划问题的求解方法。求解混合整数型双层规划问题的基本思路是首先在给定的条件下求解下层问题的最优解，然后寻找变量与之间的关系，因此我们就可以用

15、的某种函数关系来代替，并代入上层问题，此时上层问题的目标函数中只有唯一的决策变量。考虑一般形式的非线性混合整数规划问题：（） （42） 其中是非空凸集，对于每个给定的也是凸函数。问题（）可定义为（）： （43） 定义为 （44）是以为变量的函数，对给定的它对应着（）的最优值。令集合为：问题（）可写为（）： （45）定理 1（的对偶表示） （46）其中将式（46）代入（），它等价于（）： 应用上确界为最小上界的定义，引入标量，我们得到： （47）其中上述问题称为主问题（M）。如果我们假定对所有的，有界，我们可以将下界用最小化代替，那么主问题可写为： 在中变量为参数，对应每一个给定的值，对应着问题

16、（）的最优值。当给定后，问题（）有两种情况 （）有可行解和 （）无可行解。而对于离散选址问题中的下层问题，当给定网络时，肯定能得到在其上分配的客户需求量。所以只需要考虑给定时，即（）可行的情况。用表示次迭代给定的值，其中表示迭代的次数。问题（）在第次迭代时可以写为： （48）在 中，我们可以得到 和 为问题中等式与不等式约束中的最优拉格朗日乘子向量。则可以用以下形式表示为第次迭代时（）问题的支撑函数：= （49）其中为当和时变量的函数形式（为在点的支撑函数当且仅当和，）。 很明显，（49）式中仅含有变量。如果可以利用特殊的函数表达关系将（49）式中下层问题的最优解转化到上层问题的目标函数中，则

17、在上层问题中只含有变量，因此就容易求解上层问题了。对于给定的，求解下层规划问题，得到新的平衡流量和乘子。重复上述的过程，最后有望收敛于双层规划问题的最优解。 考虑竞争的物流中心选址双层规划求解算法虽然第7.1节提出了一种启发式算法，但其模型假定在新建物流中心之前市场上没有其他物流中心，也就是不考虑新旧物流中心之间的竞争。其算法也不适合本节存在竞争条件下物流中心选址的双层规划模型。因此，本节以上节的求解算法为基础，根据目标函数的特殊关系设计了求解这类问题的新算法。（1）模型求解思路按一般求解双层规划的思路，对于给定的上层离散变量，解下层问题，同时找到变量和的关系，将表示为的函数，代入上层目标函数

18、中，消去上层规划中所含的变量，将上层简化为只含的形式来求解。但对于本文的离散问题很难找到二者的关系，我们知道上层问题的目标函数为系统最优，而下层目标为用户最优，且其函数形式有一定的关系。这样我们可以对给定的值求解完下层问题后，用下层的目标函数和部分含有变量的约束（如第二个约束）来表示上层目标函数（这时为已知），上层规划就只含变量了，可用一般方法求解。也就是说尽管用表示较困难，我们可以用表示上层问题中含有的目标函数。根据上节所提出的非线性混合整数双层规划问题的求解算法，下层规划可写为=+ （50） ， ，我们定义，根据上节中支撑函数的定义，第次迭代时，下层规划的支撑函数可写为： （51）其中为下

19、层规划第次迭代时的不等式约束乘子。对上层规划给定的， 可以表示为第次迭代时下层规划的最优值。为了简化计算可将（51）式右边写为： （52）根据系统最优和用户最优的关系，可以得出上下层目标函数的关系（如式（53），这样我们可以将下层目标函数的最优值通过转换变成上层目标函数的最优值。 （4.53）由上节中有关双层规划的理论，第次迭代时上层目标函数的支撑函数 可以表示为： （54） 根据前面的理论可以得知（54）中只含变量。令 （55）可将看作上层规划问题的上界。那么主问题可写为： （56）其中 or ，为上层规划问题的下界，为迭代次数。（2）求解算法具体的求解算法步骤如下：第一步：给定初始值，令。

20、对给定的，采用增广的F-W算法求解下层规划问题得,及支撑函数,。令当前上界为，迭代精确度。第二步：求解松弛主问题, 令 为上述松弛问题的最优解。为上层规划问题的下界，即当前下界。如果，终止。第三步：对，求解下层规划问题，我们得到下层规划的最优解、最优乘子和支撑函数分别为，。更新当前的上界。如果，终止；否则，令，。转第二步。 由（54）式及（55）式可知，上层规划的目标函数值一定小于等于上界，而根据（56）式可知，它的目标值又一定大于等于下界，经过反复迭代，当上下界逐渐逼近时，算法终止，最后收敛到双层规划的最优解。注1：第二步中的松弛主问题在第一次迭代中有一个对应着支撑函数的约束，即： 在第二次

21、迭代中，松弛问题将有两个约束： 可以看出，第一次迭代时松弛问题的解将会大于或等于第二次迭代时松弛问题的解，因此，由松弛问题产生的下界序列是不减的。注2：尽管上界是通过固定产生的，但更新的上界是单调非增的（始终保持最小的上界）。注3：算法终止条件是更新的上界和当前下界的差值，当这个差值小于或等于一个预先给定的迭代精度时，则算法停止。注4：在求解过程中，每次迭代时对固定的，我们需要用乘子法找到约束对应的最优乘子（Patriksson，1994）：对下层规划，定义如下增广的拉格朗日函数： 其中为惩罚因子；为不等式约束的拉格朗日乘子，在迭代过程中可通过下式进行修正 可以证明 将会收敛到最优的乘子。因而

22、，下层规划可用传统的方法直接求解，如Frank-Wolfe方法 ( Partriksson，1994 )。在利用F-W算法求解下层规划时，我们可以同时得到最优解及最优的乘子向量。此模型的求解算法只适于上下层目标函数有特殊关系的情况，对于一般的双层规划还需要进一步改进算法设计过程。算例分析假设有一个客户，总需求量为20。对于多个客户的情况，计算方法相同。6个备选物流中心，2个已有物流中心。各物流中心的费用函数均符合下式：其中，是第个物流中心费用参数。两个已有物流中心对应的参数分别为。表4.5 备选物流中心的费用参数序号123456242219192016成本7127151118表4.6分别给出了

23、依次取预算上限为30，40，50，60，70所得的结果以及每步迭代数据（其中0代表不修，1代表修）。通过每一步的迭代数据可以看到上界逐步减少，而下界逐步增加，直到上界和下界趋于一个较接近的值，而这个值正是双层规划问题的最优解。从结果中可以看到随着预算上限的增大，添加的物流中心越多，目标函数值越小，这是合乎实际情况的。通过算例可以看到，本算法是可行且有效的。为了验证算法的收敛性，对预算值为40时的情况选取不同初值进行计算，最后的结果如表4.7所示，表中数据相同说明算法是收敛的。表4.6 不同预算值下的迭代结果预算上限上界 下界 修建结果 303980.019714; 0.000000; 1 0

24、1 1 0 0 731.892884; 518.239290; 1 1 0 0 1 0 731.892884; 518.239290; 1 0 1 0 1 0 731.892884; 698.516956; 1 1 1 0 0 0 731.892884; 698.516956; 0 1 1 0 1 0 723.494237; 723.494237; 0 1 1 0 1 0 * result: 723.494237 迭代次数：6403980.019714; 0.000000; 1 1 0 0 1 0 739.869790; 441.582547; 0 1 1 0 1 0 723.494237;

25、441.582547; 1 0 0 1 1 0 723.494237; 472.760806; 0 1 1 0 0 1 698.516956; 472.760806; 1 0 0 0 1 1 698.516956; 472.760806; 0 0 1 0 1 1 683.795721; 479.705083; 1 0 0 1 0 1 683.795721; 479.705083; 1 0 1 1 1 0 518.239290; 479.705083; 1 1 0 0 0 1 518.239290; 479.705083; 1 1 1 0 0 0 518.239290; 491.629739;

26、1 0 1 0 0 1 518.239290; 491.629739; 1 1 1 0 1 0 518.239290; 502.427112; 0 1 1 1 0 0 518.239290; 502.427112; 0 1 0 1 1 0 518.239290; 502.427112; 0 0 1 1 0 1 518.239290; 518.239290; 1 0 1 1 1 0 *result: 518.239290 迭代次数：16503980.019714; 0.000000; 1 0 1 1 0 0 731.892884; 0.000000; 1 1 1 0 1 0 531.037270

27、; 0.000000; 0 0 1 1 1 0 531.037270; 441.582547; 0 1 1 1 1 0 502.427112; 441.582547; 1 0 1 0 0 1 502.427112; 441.582547; 1 1 1 0 0 1 502.427112; 472.760806; 1 0 1 0 1 1 502.427112; 472.760806; 0 1 0 1 0 1 502.427112; 472.760806; 1 1 1 1 0 0 502.427112; 472.760806; 1 1 0 0 1 1 502.427112; 472.760806;

28、1 1 0 1 1 0 502.427112; 472.760806; 1 0 1 1 1 0 502.427112; 479.705083; 1 0 0 1 0 1 502.427112; 479.705083; 0 1 1 0 1 1 491.629739; 479.705083; 0 0 0 1 1 1 491.629739; 479.705083; 1 0 1 1 0 1 491.629739; 491.629739; 0 1 1 0 1 1 * result: 491.629739 迭代次数：17603980.019714; 0.000000; 0 1 1 0 1 1 491.629

29、739; 0.000000; 1 1 1 0 1 1 479.705083; 0.000000; 0 1 0 1 1 1 479.705083; 0.000000; 1 0 0 1 1 1 479.705083; 0.000000; 1 1 0 1 0 1 479.705083; 0.000000; 0 1 1 1 0 0 479.705083; 0.000000; 1 0 1 1 0 1 479.705083; 0.000000; 0 0 1 1 1 1 472.760806; 441.582547; 1 0 1 1 1 1 472.760806; 441.582547; 1 1 1 1 0

30、 0 472.760806; 441.582547; 1 1 1 1 0 1 472.760806; 441.582547; 1 1 0 1 1 0 472.760806; 441.582547; 1 1 1 1 1 0 472.760806; 472.760806; 1 0 1 1 1 1 *result: 472.760806 迭代次数：14703980.019714; 0.000000; 1 1 1 0 0 0 740.309894; 0.000000; 0 1 1 1 1 0 502.427112; 0.000000; 1 1 1 1 0 0 502.427112; 0.000000;

31、 1 0 1 0 1 0 502.427112; 0.000000; 1 0 1 0 1 1 502.427112; 0.000000; 1 1 0 0 1 1 502.427112; 0.000000; 1 1 1 0 1 0 502.427112; 0.000000; 1 0 1 1 1 0 502.427112; 0.000000; 0 0 1 1 0 1 502.427112; 0.000000; 0 1 1 0 1 1 491.629739; 0.000000; 1 1 0 1 1 0 491.629739; 0.000000; 1 0 0 1 0 1 491.629739; 0.0

32、00000; 0 1 1 1 0 1 487.053042; 0.000000; 1 0 1 1 1 1 472.760806; 0.000000; 1 1 1 1 1 0 472.760806; 0.000000; 1 1 1 1 1 1 441.582547; 441.582547; 1 1 1 1 1 1 * result: 441.582547 迭代次数：17表4.7 预算为40时不同初始点下的迭代结果初始点预算 40结果1 0 0 0 1 11 0 1 1 1 00 1 1 0 0 11 0 1 1 1 01 0 0 0 1 01 0 1 1 1 01 0 0 0 0 01 0 1 1 1 0