基于自适应分布式搜索的供应链协调优化算法

付立坤++乔佩利

摘 要：主要研究生产计划下的多级供应链伙伴之间的协调优化问题.在多阶段多项目约束生产批量问题模型的基础上，考虑关联约束及相关需求约束，对整个供应链的生产计划问题利用拉格朗日松弛算法将其分解为多个子问题，并应用自适应分布式算法更新内部价格来协调各成员之间的决策，实现了多级供应链批量生产问题的协调优化，以及较好的保证各成员隐私，实验分析证明了该策略在协调多级供应链生产计划问题具有优越性，

关键词：供应链协调：树搜索；自适应分布式

DOI：1O.15938/j.jhust.2015.02.015

中图分类号：TP399

文献标志码：A

文章编号：1007-2683（2015）02-0080-05

0 引 言

供应链管理（SCM）是在充分利用资源条件下，通过协调供应链中各成员间相互关系，以实现供应链整体的协调优化，供应链运作计划在SCM主要在满足客户服务约束的前提下，负责协调供应链上资源的调配，物料的供需关系，以及优化供应链总成本.在以往关于供应链协调问题的研究中，较为常用的方法是层次式模式，假定由一个决策者掌握了全部的信息，并集中对协调问题进行决策，供应链中的信息具有私有性、实时性、非对称性等特性，虽然层次式模式通常情况下，可高效获得全局最优策略，但如果供应链有多个决策者，则无法使用层次式模式.文提出一种在不干涉自主决策实体的决策权和私有信息等条件下，又能够有效的协调和优化整个供应链运作的模式，并用拉格朗日松弛技术和遗传算法对多级多成员批量生产供应链问题进行协调优化，但其效率并不是最优的.文根据协调理论分析了供应链在物流、资源共享和时序间的依懒关系，并用拉格朗日松弛算法对模型进行协调优化.文运用拉格朗日松弛技术和启发式算法协调优化的多厂生产计划内部价格问题，有相对较好的优化性能，文基于协调企业和代理商之间供需关系，采用基于自适应分布式搜索算法来缩短整个供应链协调过程巾的所耗费的时间，每次提出的协调策略都是最优的.

在供应链中合作伙伴寻求竞争优势，如在短时问内不断满足成员多样化需求的能力，本研究着重从宏观角度看，是一个典型的规划和调度问题.在本研究中，将拉格朗日松弛算法和自适应分布式算法结合起来，以协调各成员子问题间的决策，

本研究中，先利用拉格朗日松弛算法简化多厂供应链问题，并用自适应分布式搜索算法对其进行协调优化.首先，将多级供应链生产计划问题模型用拉格朗日松弛算法分解为多个相对独立成员的子问题，降低问题本身的复杂度，其次，提出该模型可行解的构造方法，将问题模型用树形结构表示，并用自适应分布式搜索算法子问题进行协调优化，最后，对供应链整体进行协调优化.

1 多级供应链问题

1. 1 优化模型

如多级供应链生产计划问题是指在某一计划时问内，最终产品需求以及对应其产品结构的物料清单，并为最终产品加工或装配部件的成员企业制定生产计划，以达到最小化总成本的目的，其本质是为多级多产品受约束的批量问题（multi-level，multi-i-tem Capacitaled Lot-Sizing Problern，MLCLSP）.在本模型的计算过程中，假定产品所需提前周期为0.MLCLSP的主要约束包括：1）成员企业提供资源的数量约束和物料之问的顺序约束；2）最大库存能力约束；3）企业n的加工能力约束.符号定义如下： Prn为工厂n乍产的产品集合；Ok为生产产品k所需要的原料集合；D（n，k）为企业中所有下游工厂以工厂n的产品k为原料的集合；U（n，1）为企业中所有L游工厂为工厂n提供原料f的集合；为周期为t寸，下游工厂m向上游丁厂，n请求的产品k的产品数量；为周期为t时，上游工厂n向下游工厂m提供的产品k的产品数量；T为整个生命周期；hnk为工厂n对于产品k的单位库存a费用；Snk为工厂n对于产品k的setup费用；Cn，k为工厂，n对于产品k的单位生产费用；dn，k为外部市场生产周期t时，对工厂n的产品k的需求量；trn，k为工厂n生产产品k的setup时问；tbn，k为工厂n生产单位产品k耗时；capn，1为工厂n在生产周期t的加工能力；/i：'ak为工厂n对于产品k的最大库存能力；k.1β为产品k和产品2之间的物料清单关系；M为大的正数；Xn.k.为工厂n中产品k在生产周期t时的生乍产量为工厂n中产品k在生产周期t结束时对应的库存数量；为为0-1变量，如果生产取值为1，则表示工厂n在生产周期f时，是生产产品k，反之亦然.

在模型中，式（1）为最小化供应链总成本；式（2）为库存平衡约束；式（3）为产品的物料消单关系和T厂，z相对于其全部的上游工厂的原料需求；式（4）为工厂n的产品生产加工能力；式（5）为工厂在产品生产时，所需固定值的生产准备费用；式（6）为企业的产品库存最大值；式（7）表示物料在上下游工厂的平衡约束条件，保证上下游工厂的供需平衡.

1.2 模型的拉格朗日分解

拉格朗日松弛算法通过拉格朗日乘子，将模型中复杂约束作为惩罚项整合到目标函数中，以降低问题的复杂度，拉格朗日松弛式（8），将拉朗格朗日乘子整合到目标函数中，可将原问题分解为一组成员独立的子问题，能较好的保证成员信息的隐私.拉格朗日算子A表示对不符合产品上下游供应平衡约束的惩罚.本文称其为产品的内部价格，其中示工厂的原料成本.在确定产品的内部价格后，式（9）中所有变量为工厂的本地变量，无需其它工厂信息.拉格朗日分解后模型MLCLSP为：

2 自适应分布式搜索算法

2.1 建立树形结构

次梯度算法常用于求解拉格朗日松弛算法分解后的子问题.在本模型中，分解后的子问题为线性目标函数，如果采用次梯度对其求解，将产生振荡，难于收敛.拉格朗日松弛技术对于成员企业之间的信息必须保证全部共享，对于本模型来说，并不适用.因此本文建立的协调结构和协调过程内嵌了一个基于自适应分布式可行化方法，该方法不需要集成模型和成员的全部信息，在可行化过程中，自适应算法淘汰可能会失败的拉格朗日乘子，保证能求得问题的可行解.虽然增加了淘汰步骤，但在汁算过程中，子问题是并行计算，所耗费时间很短.为此，本文在拉格朗日松弛算法的基础上，运用自适应分布式搜索算法，进行可行化求解.

图l为多级供应链生产计划问题的用树形表示的结构图.树的根节点是协调中心，根节点制定产品的内部价格，以及协调各个工厂.A、B、C为3个工厂，作为根节点的子节点，3个工厂根据自己的本地信息，在获得内部价格后，可得到各自工厂的生产计划，并将确定各自向上游工厂提出的原料需求量，和向下游工厂提供的产品供给量，以及所得优化结果传给根节点.10种产品作为工厂节点的子节点，生产计划结果和其它信息通过枝进行传递，协调中心根据接收到的消息，更新内部价格，然后将其传送给各个工厂.一直执行该步骤，直到得出最优决策，才停止运行.

2.2优化算法

自适应分布式搜索算法是一种全局性的搜索算法.许多研究者采用失败学的方法处理树在遍历过程中违反约束导致失败的情况，并分析树在整个搜索中的其余部分，它具有对函数的形态无要求、搜索效率高、较好的全局搜索能力等优势，并且可以处理混合参数的约束优化问题.自适应方法涉及系统的动态响应和调整特定实例的求解过程，能充分利用问题的约束条件.自适应算法的实现通常为：1）更新数据.每次遍历一个新的节点，可能会引起相关节点的数据变化，及时更新数据，自适应判断是否更新当前节点的数据，即对全局决策无影响，不更新除父节点和本身节点以外的节点.2）选择节点，最优决策通过系统地遍历树的所有节点，根据节点的属性值判断获得最优策略的可能性，可动态搜索概率最高的节点.每次通过比较该次得到的策略与上次最优策略，保存对比后较优策略对应的数据和路径.当搜索到最优决策之后，便停止搜索.本步骤的所有操作在多节点上都是并行进行处理.3）网溯节点.根据约束条件或者搜索到叶子后，采用回溯方法，常用的回溯方法是SyncLDS（ synchronous limited dis-crepancy search）

对应本模型的具体步骤如下：

步骤1：初始化参数.如制定初始的产品内部价格、各个节点值、节点之间的关系变量、初始化掩格朗日乘子、最大迭代次数等，

步骤2：各独立成员接收由协调中心所推送的拉格朗日乘子，在协调中心局部求解过程中，采用模糊次梯度算法进行更新.在协调过程中，协调中心采用自适应方法对优化结果进行判断.为第一种，其他为.其中J为最优解的估计值.这里选择步长α5满足：

步骤3：每个独立成员在拉格朗日乘子的基础上，并行计算f值，并将所得结果传送给协调中心.

步骤4：上游成员把下游成员的X品作为子问题模型中参数xkit的输入值，然后更新值，，并向根节点（即协调中心）发送可行性和值fe，同时迭代次数n减1.

步骤5：如果迭代次数达到最大值，则转向步骤6，否则，根据白适应方法，直到得到最优结果，才停止运行.

步骤6：输出最优解后，停止运行.

3 实例与分析

采用文中标准MLCLSP问题中的ClassB集的非循环产品结构，最终产出4个最终产品，用该实例验证白适应分布式搜索算法的如何求解多级供应链生产计划问题.每级对应有一个成员（成员各有一种资源）的三级供应链中，拥有10种物料，成员之问的物流结构关系如图2所示.利用文[3]中的方法，生产准备成本可分为：1）生产规模均衡、准备成本相对低；2）生产规模均衡、准备成本适中；3），生产规模均衡、生产准备成本高；4）下游准备成本较低和上游准备成本较高时；5）下游准备成本较高和上游准备成本较低时，其中p为变化的资源利用率，取值情况如表l所示.3种需求模式，通过不同的变异系数改变需求，变异系数（coefficients ofvariation）分别为0.1，0.4，0.7.共计75个问题，

平均每个时期的需求为最终产品的组装结构中被设置为100.实例中，大的正数M=1000，物料k的库存保存成本和生产准备成本参数如表2所示，

可利用Visual Studio 2005实现供应链运作汁划协调算法（拉格朗日松弛技术与自适应分布式算法），对成员独立的子问题的求解可用Liogo11软件.拉格朗日乘子取值范围介于-100到100之间，最大代数值为100.首先，将通过Lingol1软件求解所得到最优解作为评价其它算法性能的一个基准，在拉格朗日松弛的基础上，对比白适应分布式算法和文中的LRCASCP算法求解问题的结果，如表3所示.表中的偏差由两种算法的解与基准对比可得，如图3所示.

偏差为通过计算所得的最优结果和基准的之间的差：其中：t，为初始最优解；J*为整个问题计算所得的最优解.

如表2结果显示，自适应分布式搜索算法和LRGASCP算法的优化性能基本不依赖于问题的结构，相对比自适应分布式算法的平均偏差更低些.

由表3和图3可得，在75个问题中，应用LR—CASCP算法所得偏差为1.47%；自适应分布式搜索算法的情况，偏差在l%以内占问题总数的61%，问题偏差在5%以内占问题总数的97%.对比可知，自适应分布式搜索算法具有优越性和鲁棒性.将自适应分布式搜索算法、LRGASCP算法同文中所提到的中心强制、一般协调和最大公平协调，以及文中的内部价格协调与基准比较后的偏差进行对比，结果如表4所示.显而易见，在相同问题集的情况下，白适应分布式搜索算法的优化性能在这几种协调机制中是最高的.

在求解问题的计算过程中，各成员独立子问题的求解占据了大部分的运行时间，自适应分布式搜索算法具有分布式的特性，即成员子问题的决策计算过程都是并行进行计算，可减少子问题串行计算所消耗的时间，因此，该算法具有较高的运算效率.

4 结 论

本文针对多阶段多项目批量供应链协调优化问题，在拉格朗日松弛算法的基础上，运用白适应分布式搜索算法协调产品的内部价格协调策略，应用拉格朗日松弛技术分解简化本文中的数学模型，可得到多个成员独立的子问题，子问题的运算复杂性较低，其中，协调中心主要是对拉格朗日乘子进行更新，来达到对各个成员决策的协调优化目的，利用自适应分布式搜索算法来求解成员的子问题，可降低了求解问题的复杂度，并具有高效性.实验结果表明，与其它多种协调机制对比，自适应分布式搜索算法具有优越性以及鲁棒性.