基于NSGA-Ⅱ算法的复杂供应链网络库存协同控制

刘洪娟，高寒冰，姜大立，甘 明

（1.后勤工程学院 现代物流研究所，重庆 401311；2.后勤工程学院 军事工程管理系，重庆 401311）

1 引言

供应链是一个复杂网络系统,需要协调各参与方的活动,才能实现最优的运作效果。库存是供应链中重要的一环，库存成本的高低直接影响着供应链管理的效益。供应链中的企业在库存管理上存在冲突,表现为供应链成员间库存相互挤压，主要是存货价格挤压、成本挤压及存货水平挤压，最终形成利润和生存空间的挤压。这种挤压会对供应链造成负面影响，通常造成供应链整体成本的增加，影响供应链的竞争力，所以说供应链成员间的库存协同是供应链各节点企业实现合作以及提高供应链竞争力的关键[1]。

国内外的专家针对供应链库存协同控制问题进行了大量的研究。Shin[2]将供应链库存协同定义为一种集成管理思想，协调从供应商到最终用户的全部物流和资源的流动，试图发现一种优化整个供应链库存而不是实现供应链的每一层库存次优化的方法，其中所有的努力和方法都称之为供应链库存协同。Munson 和Rosenblatt[3]给出了一个由一个供应商、一个制造商和一个经销商组成的直线形三阶段供应链库存协同模型。Zhou等[4]建立了一种Stackelberg博弈模型，其中制造商主导制定产品价格,并提供各种优惠政策，零售商接受零售价格及最佳订货量。Arcelus 等[5]研究了单一利润最大化的制造商提供采取回购政策,分担零售商的销售风险，并因此增大订购量，使双方都能达到利润最大化。Viswanathan[6]假定供应链是由供应商和多个购买商构成的，供应商规定一个共同补货期，要求所有的购买商以共同补货期的整数倍为补货期来订货，通过共同补货期来调节库存。郭敏和王红卫[7]研究了由一个供应商和一个分销商组成的两级供应链系统的库存协同问题，提出激励供应链成员诚实申报信息的新的协同机制，实现了供应链系统的联合最优化。蔡建湖等[8]讨论了一个两级供应链库存决策模型，在分析传统回收契约模型的基础上，引入了一个特殊的回收契约，讨论不同契约参数下供应链成员的最优决策。苏菊宁等[9]讨论分析了在可调数量策略下，供应商分担部分库存风险时供需双方的利润模型，在此基础上得出供应链Pareto优化模型。李琳，周永务[10]研究了弹性需求条件下，由单一零售商和单一供应商组成的两级供应链的协同订货问题，运用了共同补给期和分担运输费用的双重策略，分别从订货周期及年需求量的角度协调供应链订货。余国锋，周永务[11]在随机需求以及考虑缺货成本的前提下，针对由供货商和零售商组成的两级供应链，考虑转移支付的协同策略，使得双方成本最小化，同时使得供应链达到最优。

以上这些研究主要考虑的是简单、直线式的供应链库存协同问题，然而随着经济全球化、生产国际化、信息技术的发展，供应链规模越来越庞大，结构也越来越复杂，供应链已经成为了一个复杂的网络系统。本文基于NSGA-II 算法，提出一种基于库存协同条件下的供应链节点淘汰机制，对复杂供应链网络进行优化，从而实现对复杂供应链网络库存协同的控制。

2 复杂供应链网络库存协同模型

在实现供应链复杂网络的库存协同时，由于单个节点掌握的信息并不完备，如果各节点的库存量全部由自己决定，容易导致牛鞭效应的产生，因此，供应链上各节点的库存决策需要上下游节点共同来确定。本文的供应链网络库存协同模型正是在这种思路的指导下建立的，模型中供应链某节点根据自己掌握的信息对自身库存有个预测值，相邻的上下游企业根据自己掌握的信息对该节点库存也有个预测值，在供应链这个复杂网络运作时，各节点总是期望与能够持续为自己提供较为准确的预测信息的上下游节点合作，基于此，通过比较相邻节点及节点自身的预测值和节点实际库存需求的关系，对长期提供较为准确的预测信息的节点给予更多的信任，而对于经常性给出不准确的预测信息的节点逐步进行淘汰，从而保持供应链网络上较优的库存协同状态。

2.1 建立模型

若eij和kj越接近，则说明节点i对节点j的库存估计偏差越小，表示节点i与节点j库存协同程度越好。eii和ki越接近，则说明节点i对自身库存估计偏差越小，表示节点i对自身的库存预测越好。如果节点i既对自身的库存预测较好，又对节点j的库存协同程度较好，认为节点i是节点j的协同节点，认为节点的协同节点数为其相连节点数的一半，则网络中的每个节点都存在它的协同节点。若某节点是网络中许多节点的协同节点，则该节点和网络的协同程度较高，反之，若某节点几乎不是其他节点的协同节点，则该节点和网络的协同程度较低。通过保留与网络协同程度高的节点，逐步淘汰与网络协同程度低的节点，提高整个供应链网络的库存协同程度。

假设任意节点i1有j1个相连的节点，则它的协同节点数j2=[j12] 。问题转化为从j1个节点中选择j2个，使得最小。xj=1 表示节点j被选择，表示选择的j2个节点对自身库存估计的累积偏差。表示选择的j2个节点对节点i1库存估计的累积偏差，用来衡量j2个节点对节点i1的库存协同程度，偏差越大，协同程度越小。据此建立模型：

此模型为一个0-1二次目标规划模型，本文采用非劣排序遗传算法（NSGA-Ⅱ）来求解该问题，分别令i1=1,2,…,N，可以得到对应于任意节点的协同节点。统计某节点为协同节点的频数，频数越大，说明该节点与网络的库存协同程度越高。

2.2 NSGA-II算法

NSGA-Ⅱ算法是一种基于非劣快速排序及拥挤度计算的多目标遗传算法，能够使种群快速收敛到Pareto 前沿，并且能保持解的多样性分布。

2.2.1 基本思想

（1）随机产生种群规模为pop的初始父代种群P1，对种群进行非劣排序，每个个体被赋予秩；并通过遗传算子（交叉、变异）产生子代种群Q1，其种群大小也为pop；

（2）将父代种群和子代种群合并组成规模为2pop的合成种群；进行快速非劣排序，将合成种群中的2pop个个体按非劣序号（等级）重新分类，得到等级F1,F2,…；

（3）对所有的Fi(i=1,2,…) ，计算其个体局部拥挤距离并排序，根据排序结果选取pop个个体作为新的父代种群P2；

为了项目实施效果最大化，教师在项目实施时要设计评价方式，坚持多方评价和全程评价的原则。多方评价，包括学生自评、组内互评、组间互评、教师点评；全程评价，包括过程性评价、阶段性评价、总结性评价。务求评价全方位，多角度，重诊改，以有效鼓励学生持续性学习。

（4）重复步骤（1）至（3），直到达到算法设置的迭代次数gen（P1到P2为一次迭代）。

2.2.2 非劣排序。对集合P进行非劣排序的具体过程如下：

（1）令x∈P对应的支配数nx=0，对应的集合Sx=φ。对于任意q∈P且q≠x，如果q支配x（表示q优于x），则nx=nx+1，否则Sx=Sx∪{q} 。最终得到每个解x∈P对应的支配数nx和集合数Sx，若nx=0，则将解x放到F1中；

（2）令i=1 且Q为空集，对每个解x∈Fi执行如下操作：对于任意q∈Sx，若nq=i，则Q=Q∪{q} ；

（3）如果Q不为空集，则i=i+1，Fi=Q，转步骤（2）；否则，停止迭代。

2.2.3 遗传算子

（1）选择算子。选择算子采用的是锦标赛选择，该选择方式是随机选择k（一般取k=2）个个体进行比较，如果非支配排序序号不同，则选取序号小（等级高）的个体；若序号相同，则选取周围较不拥挤的个体。这样，只有适应值较好的个体才有较大的生存机会。

（2）交叉算子。采用双节点交叉，首先对两个父代个体随机产生两个交叉点，然后交换父代两节点之间的部分，从而产生子代。但交叉操作后可能不能保证解的可行性，考虑对解进行修复。假设需要选出q个协同节点，子代中实际选择了i个，若i＞q，在子代值中随机选择i-q个1，用0替代；若i＜q，在子代中值随机选择i-q个0，用1替代。

（3）变异算子。本文采用对个体进行逆转变异的方法，逆转变异是在父代的个体中随机选取两点，将这两点间的子串进行逆转。显然，这种操作只是改变了个体基因的顺序，不会产生不可行解。

3 算例分析

设置初始网络节点数N=100，网络中任意两节点连接的概率为0.2，得到随机供应链复杂网络。若节点i与节点j相连，eij和eji随机在( 0,1) 间取值，表示节点i和节点j相互的库存预测。eii和ki也随机在( 0,1) 间取值，分别表示节点i对自身库存预测和节点i实际库存需求。

在此初始条件下，基于Matlab 编程平台，令种群规模pop=100，迭代次数gen=50，运行NSGA-II 算法程序。对于节点i=1，得到8个Pareto最优解，见表1。

表1 Pareto最优解

依据Pareto最优解，决策者可根据不同的趋向（比如更趋向于个体信息还是更趋向于协同信息）取不同组解。本文主要考虑供应链网络库存协同问题，因此对于节点i=1,选择第1组解（1,0,1,1,1,0,1,0,1,0,1,0,1,0,0,0,0,1,1）T，作为节点i=1 的最终解，节点i=1 的协同节点为5、11、14、20、33、44、72、94、98，这组解中节点间的库存估计累积偏差最小，库存协同效果最好。

据此可以求出任意节点i的协同节点，从而得到各节点作为协同节点的频数，如图1 所示。可以看出节点5、14、100 作为协同节点的频数为21，是整个供应链网络所有节点中最大的，所以应该保留。而节点64作为协同节点的频数只有2，节点85和94作为协同节点的频数只有4，应该逐步淘汰。

图1 某节点作为协同节点频数

4 结束语

本文通过研究供应链复杂网络的库存协同问题，建立了供应链复杂网络的库存协同模型，提出了一种供应链节点淘汰机制，旨在对供应链复杂网络库存协同进行控制。基于NSGA-II算法，在Matlab8.0环境下，对随机供应链网络进行了算例分析，得到每个节点的协同节点，从而得到各节点作为协同节点的频数。通过保留频数大的节点，逐步淘汰频数小的节点，实现了对随机供应链网络库存协同的控制与优化。

[1]蒋林,张怀胜.供应链库存协调问题研究综述[J].工业工程,2010,13(4):129-133.

[2]Shin H J.Inventory coordination in the industrial supply chain[D].Columbus:The Ohio State University,2001.

[3]Munson C L,Rosenblatt M J.Coordinating a three-level supply chain with quantity discounts[J].IIE Transactions,2001,33(5):371-384.

[4]Zhou Yongwu.A comparison of different quantity discount pricing policies in a two-echelon channel with stochastic and asymmetric demand in formation[J].European Journal of Operational Research,2007,181:686-703.

[5]Arcelus F J,Satyendra Kumar G.Srinivasan.Evaluating manufacturers buy back policies in a single-period two-echelon frame work under price-dependent stochastic demand[J].Omega,2008,36(5):808-824.

[6]Viswanathan S,Piplani R.Coordinating supply chain inventories through common replenishment epochs[J].European Journal of Operational Research,2001,129(3):277- 286.

[7]郭敏,王红卫.“批对批”供应链在信息不对称下的协调机制[J].计算机集成制造系统,2004,10(2):152-156.

[8]蔡建湖,黄卫来,张子刚.一个考虑回收契约的两级供应链库存决策模型研究[J].管理工程学报,2008,22(1):122-124.

[9]苏菊宁,刘书庆,赵小惠.随机需求下供应链库存协调策略研究[J].系统工程,2004,22(7):26-30.

[10]李琳,周永务.弹性需求下带有分摊运费的供应链协调策略[J].计算机集成制造系统,2007,13(1):171-177.

[11]余国锋,周永务.不对称信息下两阶段供应链的库存博弈[J].合肥工业大学学报(自然科学版),2008,31(3):364-369.

[12]Aravind Seshadri.NSGA-II:A multi-objective optimization algorithm[EB/OL].http://www.mathworks.com/matlabcentral/fileexchange/10429-nsga-ii-amulti-objective- optimization-algorithm,2006-03-19.