随机多阶段分销网络设计模型，本文主要内容关键词为：模型论文,阶段论文,网络论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
中图分类号：F713.50文献标识码：A
文章编号：1003—207（2007）06—0098—07
1 引言
在供应链管理（Supply Chain Management，SCM）中，分销网络设计（Distribution network design，DND）一直是企业一个重要的战略问题[1]。该问题的主要内容为合理规划整个分销网络的库存、选址和分配决策，从而使得整个系统的总成本（包括库存、运输与选址成本）最小。很多企业通过重新设计其分销网络使得在降低千万元的物流成本的同时，提高了整个企业的物流服务水平。Chopra[2] 也指出企业的总物流成本是供应链分销网络中库存、运输和设施选址成本之和。所以，企业供应链DND的好坏直接影响着整个企业物流成本和服务水平。
设施选址是DND的关键问题之一。设施选址问题（Facility location Problem，FLP）有着丰富的研究历史。最初，DND问题主要就是指对供应链中的工厂、配送中心（Distribution Center，DC）和／或仓库进行最优选址。Owen和Daskin[3]、Revelle和Eiselt[4]都对FLP进行了详细的综述。随着研究的深入，研究学者们发现，战略层面上的FLP没有能力处理设施选址和库存决策的相互影响，特别是当存在着风险分摊（Risk Pooling）效益时（当顾客或零售商被少数配送中心聚集并统一服务时，可以降低系统的总安全库存成本[5]）。所以为了确定配送中心的最优数量和位置，库存控制决策应该与企业其他战略层与运作层决策联合考虑。
近几年，有很多国外学者开始将库存控制决策与FLP结合进行研究，比如Baragiba和Jensen[6]，Nozick和Turnquist[7，8]，Daskin等人[9]，Shen等人[10]，Miranda和Garrido[11，12]等。最初，Baragiba和Jensen[6] 在设施选址的整数规划模型中简单地考虑了库存费用，并通过Dantzig-wolfe分解算法对模型进行了求解。Nozick和Turnquist[7，8] 推测出安全库存成本与配送中心的数目近似成线性相关，因此可以在带固定费用的设施选址问题（FCFLP）中直接考虑安全库存成本。Daskin等人[9]、Shen等人[10]和Shu等人[13] 建立了一种联合选址库存模型，即将（Q，r）库存控制策略（每个配送中心都储存一定数量的安全库存）加入到无容量限制的设施选址问题（UFLP）中进行了研究。在该库存控制策略中，假设当每次库存水平低于在订货点r时，则向供应商订购固定数量为Q的货物。为了求解该模型，Daskin等人[9] 使用了拉格朗日松弛算法，而Shen等人[10] 则将该模型转化为一种集分割问题，然后通过列生成算法进行了求解，Shu等人[13] 则对Shen等人的算法进行了进一步的研究与改进。最近，Miranda和Garrido[11，12] 在有容量限制的设施选址问题（CFLP）中考虑了库存控制策略，并且通过拉格朗日松弛算法对其进行了求解。在国内，也有许多学者开始研究相关的内容，比如张长星和党延忠[14]，谭凌等人[15]，秦绪伟等人。[16] 等等，他们大多数都是对相关模型中的库存成本进行了适当的改进。
然而，以上大多数文献都只考虑了单阶段的供应链DND问题。但是，作为战略层决策的供应链DND需要巨额建设资金，而且实施之后很难再修改，并且会在未来的多个时间周期中对企业产生影响。除此之外，在未来的战略周期中，问题的各参数——零售商的需求量、库存成本、单位运输成本等都有可能随着时间而改变。因此，在设计供应链的分销网络时，不能只考虑当前的环境。所以，本文提出了一种更加现实的考虑了经济规模和分摊效益的随机多阶段库存选址模型（Location Inventory Model，LIM），通过情景树来处理市场环境（由模型中各种参数表示）不确定性，同时假设每个周期阶段中可以用于DC建设的投资资金是有限的。该模型的目标是使整个战略周期内的总期望成本（包括库存、运输、选址成本与损失的收益）最小。本文称该模型为随机的多阶段选址—库存模型（Stochastic Multistage Location Inventory Model,SMLIM）。
2 问题阐述
在现实中，有可能因为对未来预测不足，测量误差或需求模式的改变，使得对需求参数与成本的评估不准确。所以，为了描述未来战略周期中各参数的不确定性，本文引用Ahmed和Sahinidis[17] 提出的多级情景树来对SMLIM进行建模。在情景树中每一个点层对应于一个时间周期t，每一个情景s对应于在这棵树中的一条从根结点到某一叶子的路径，从而表述了所有时间周期中与现实相关的不确定性参数。因此，情景树使得建模者可以定义若干个未来可能出现的市场环境，同时使得建模者可以防范对未来参数预测的误差或参数变化。图1给出了一个6情景3时间周期的情景树的例子。p[s]表示一个情景（路径）s的发生概率。q[b]表示与情景结点n相关的概率，它等于经过它的情景（路径）的概率之和。
定义I为地理上均匀随机分布的零售商集合，每个零售商在不同时间周期中不同情景下的需求量服从于不同的正态分布，而且互不相关。定义J表示所有候选DC的位置集合。有可能J
I。假设存在唯一的供应商通过直接运输为每个DC供货，同时假设每个DC使用单源策略和直接运输为分配给它的零售商服务，并且瞬间到货。而且为了防止缺货，本文假设每个DC都使用（Q，r）库存控制策略（每个DC都维持一定数量的安全库存，当库存水平低于再订货点r时，则向供应商定购固定数量为Q的货物）。本文还假设零售商的维持库存成本与固定订货成本可以忽略不计。除此之外，本文还假设在每一个时间阶段中可以用于修建DC的资金是有限的，所以有些零售商在早期可能因为服务它们的成本大于服务它们所获得的收益而被放弃服务。
为了简化模型中的符号，本文假设在所有的情景结点中所有DC的单位年库存维持费用h都是相同的。而且在以上定义的符号和将要进行的分析中，本文假设模型考虑的战略周期中每个时间周期的跨度为一年。除了以上定义的参数外，本文还定义了以下决策变量：
在上述模型中，目标函数（1）表示整个战略周期的总期望成本最小。其中，等式左边第一项为建立DC所需的固定成本与运营成本之和，第二项为整个分销网络的总期望运输成本，第三项与第四项分别表示总期望库存维持成本与总期望安全库存成本（其具体推导过程见阅读参考文献[9]），最后一项表示因为放弃部分零售商而损失的总期望收益。
注意观察上述模型可以发现，如果θ＝0，则目标函数（1）中的非线性项就会消失。此时如果不考虑约束（4），并令｜N｜＝1，就能得到一个传统的属于NP-hard问题的无容量约束的设施选址问题（UFLP）[18]。所以UFLP是SMLIM的一个特例。因此，SMLIM比UFLP更加复杂和难于求解。
3 求解方法
拉格朗日松弛算法和Drop算法都是能求解UFLP的启发式算法，本文对这两种算法进行修改并结合，使其成为了一种求解SMLIM的有效算法。
3.1 寻找一个上界值
subject to：（3），（5），（6），and（7），
Step 3：计算部分和
通过以上步骤求解完LDP后，使用标准的次梯度优化算法[11] 寻找更优的拉格朗日乘子。得到的式（10）的最优值则是目标函数（1）的一个下界值。
3.2 寻找一个上界值
每次循环求解一次LDP后，可以根据得到的拉格朗日松弛解（X，y），使用类似于求解UFLP的DORP算法[18] 的贪婪算法，求得一个原SMLIM的可行解。
因为存在约束（5），所以某情景结点中的决策变量会受到以前时间周期中的结点的选址决策变量的影响。如果不考虑约束（5），SMLIM可以按下标b分解为｜N｜个LIM。所以，为了寻找每个结点中的可行解，必须按广度搜索遍历整个情景树中的情景结点。
3.2.2 使用DROP算法寻求一个可行解
为了得到一个可行解，需要对每一个属于R[,2]的DC使用以下步骤，计算当其不被建立时，系统的总成本：
假设某一个DC被从R[,2]删除，然后将其原来服务的零售商们按增加成本（目标函数（1））最小的原则分配给R[,2]中的其他DC。然后，为了进一步的改进目标函数（1），考虑将单个零售商从原来服务它的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的最优算法。
收稿日期：2007—05—24：修订日期：2007—11—20