售商从原来服务它的DC服务的零售商集中删除，然后将其分配给另一DC服务。这样重新分配后的变动值等于目标函数（1）中第二项和第三项的变动值之和。对于每一个零售商进行上述步骤，直到对任何零售商重新分配都不会再改进目标函数（1）为止。此时得到的解还是一个不考虑约束（4）时的SMLIM的可行解。
    当按上述步骤计算了每个属于R[,2]的DC被删除后的总成本后，如果其中有解是SMLIM的可行解，就定义其中总成本最小那个解为本次循环中得到的最优解，此时得到的总成本即为目标函数（1）的一个上界值。否则，从R[,2]中删除删除后总成本最小的DC，然后继续使用上述贪婪算法直到得到一个SMLIM的可行解。
    当得到本次循环中的最优解后，如果此时上下界的差值小于某一特定值或者当循环次数超过最大值时，算法结束，本次循环中的最优解则为SMLIM的最优解。否则，回到3.1继续求解新的LDP。
    4　算例
    本文设计三组规模大小不同的算例组，分别包含了10个候选DC和30个零售商、20个候选DC和60个零售商、30个候选DC和90个零售商。对于所有的算例，只考虑如图1所示的6情景3阶段的问题。本文假设所有候选DC和零售商均匀随机分布在［0，1000］×［0，1000］的平面中，唯一供应商的坐落在点［500，500］，两点之间的运输费用与其之间的欧几里得距离成正比。
    除此之外，假设只有零售商需求量的均值与方差，候选DC的固定建设费用与运营成本是与情景结点相关的。因此,定义算例中的各参数为:

 此外，本文令算例中每个情景的发生的概率依次为：0.15，0.15，0.2，0.2，0.15和0.15，则情景树的每个结点的概率依次为：1，0.3，0.3，0.3，0.15，0.15，0.2，0.2，0.15和0.15。对于三种规模不同的算例组，按规模从小到大的顺序，令每组算例中的投资资本上限参数Cb分别为40000，60000和80000。同时，对于每个算例，本文分别考虑了9组不同权重组合的β和θ的情况。
    本文使用MATLAB对提出的拉格朗日松弛算法进行了编码，然后在CPU为Intel Pentium IV 2.4 GH[,z]，内存为512 MB的计算机上进行计算试验。表1给出了本文中的拉格朗日松弛算法的相关运行参数。针对三个不同的算例组，本文按上述步骤随机产生10个算例。表2给出了用拉格朗日松弛方法求解同一规模中的10个算例的平均计算结果。在所有的算例中，最小上下界相对误差为1.09％，而最大上下界相对误差仅为3.63％。而且除了2种情况外，所有算例的求解时间都在1000秒内。所以，表2给出的计算结果表明，本文提出的拉格朗日松弛算法是求解SMLIM的一种有效算法。


 5　结语
    本文介绍了一种随机多阶段的选址一库存模型（SMLIM），该模型的目标是在由基于情景的随机参数所表示的多阶段战略周期中，使整个供应链的选址、分配、库存和市场选择决策最优。因为该模型是无容量约束的设施选址问题（UFLP）的一种扩展模型，所以它也是一个NP-hard问题。因此，为了求解该模型本文提出了一种基于拉格朗日松弛的启发式算法。然后，本文用该算法求解了三组规模大小不同的随机产生的算例组，得到的计算结果中所有算例的最优解的上下界相对误差值都在3.63％以内，而且大多数求解时间都不超过1000秒，所以，笔者认为拉格朗日松弛算法是求解SMLIM的有效算法。
    同时，本文还有许多不足之处还需要进一步的改进：首先，本文提出的算法只适用于中小规模的算例。因为当候选配送中心数目增加时，在有效时间内求解出的算例的最优解的上下界相对误差值也会不断增大。其次，本文的所有算例都是随机产生，有一定的偶然性。所以，在今后的研究中，需要进一步的改进算法，同时通过与其他算法进行比较，找出求解SMLIM的最优算法。

上一页  [1] [2]