基于改进NSGA-Ⅱ的港机制造企业供应链网络优化

李怀栋 胡坚堃 黄有方

摘要：针对港机制造企业供应链网络面临的经济性、稳定性优化需求，本文以供应商、制造基地、港口和客户在内的四级供应链网络为研究对象，对网络各级节点之间的稳定性和港口的物流能力进行评估，选取网络的利润、稳定性为优化目标建立多目标混合整数规划模型。结合算例选择矩阵实数编码、行列交叉操作、差分变异算子对第二代非支配排序遗传算法（non-dominated sorting genetic algorithm Ⅱ，NSGA-Ⅱ）进行改进。计算结果表明，该模型能够对网络的经济性和稳定性进行有效优化，且算法能获得Pareto最优解集，可为决策者提供较强的决策支持。

关键词： 港机制造企业; 供应链网络; 多目标优化; 第二代非支配排序遗传算法（NSGA-Ⅱ）

中图分类号： F552.6;F274    文献标志码： A

Abstract： In view of the economy and stability optimization needs of port machinery manufacturing enterprises’ supply chain networks， this paper takes the four-level supply chain network including suppliers， manufacturing bases， ports and customers as the research object， and estimates the stability between the nodes at all levels of the network and the port logistics capability. This paper selects the profit and stability of the network as the optimization objectives to establish a multi-objective mixed integer programming model. Combined with examples， the non-dominated sorting genetic algorithm Ⅱ （NSGA-Ⅱ） is improved by selecting the matrix real-number coding， the row and column crossing operation and the difference mutation operator. The calculation results show that， the economy and stability of the network can be optimized effectively by the model， and the Pareto optimal solution set can be obtained by the algorithm， which can provide decision-makers with strong decision support.

Key words： port machinery manufacturing enterprise; supply chain network; multi-objective optimization; non-dominated sorting genetic algorithm Ⅱ （NSGA-Ⅱ）

0 引 言

大型港機制造企业的供应商、制造基地、客户遍布世界各地，在市场竞争越来越依赖于供应链竞争的当下，稳定的供应链有助于保持供应稳定、缩短生产周期、降低物流成本、促进快速交货，并对提升港机制造企业的市场竞争力具有重要支持作用。近年来，国际经贸关系中不确定因素增多，企业在追求供应链网络利润最大化的同时，也在力求供应链网络稳定性的提升。

目前，对供应链网络优化的研究，主要与相关网络特性相结合，但由于大型港机制造企业供应链网络的自身特点，对其研究极少。LALMAZLOUMIAN等[1]指出制造企业供应链网络中的不确定性主要体现在供应能力、制造能力和需求上，并指出风险主要存在于交付或运输阶段;KHALIFEHZADEH等[2]为提升整个供应链网络的稳定性，将多级供应链网络不同层级之间的稳定性之和作为优化目标;NEJAD等[3]对随机中断情况下能快速响应的供应链网络展开研究，以供应链期望成本最小为目标，并考虑网络的响应时间和拥堵情况;AZAD等[4]通过条件风险值法展开对供应链网络的风险控制，以此对分销和运输网络面临随机中断的情况展开研究;李梦[5]在复杂网络理论的基础上，对物流、商流、决策流等“流”的时滞和企业之间的耦合强度与供应链系统的关系进行研究;张虹[6]对制造产能、运输量及运输方式等问题展开研究，并以最小化成本、最大化环境绩效为供应链优化目标。

对算法进行改进的目的是提升算法性能，获得问题最优解。在关于多目标问题求解的算法中：SHIM等[7]把遗传算法中的目标分解与非支配排序组合，再进行进化梯度局部搜索;QIU等[8]引入自适应差分算法，并在算法收敛性、参数敏感性分析的基础上，加入跨代变异机制;时思思等[9]提出一种基于动态拥挤度和自适应t分布交叉算子的第二代非支配排序遗传算法（non-dominated sorting genetic algorithm Ⅱ，NSGA-Ⅱ），通过每次删除拥挤度最低的解后更新非支配解的拥挤度，选出所需非支配解;路艳雪等[10]构建了多输入多输出的反向传播神经网络作为适应度函数的评价体系;吴暖等[11]引入双向随机变异算子，并嵌入非劣解的局部搜索，对NSGA-Ⅱ的性能进行提升。

本文在前人研究的基础上，结合港机制造企业供应链网络的实际情况，建立由供应商、制造基地、港口和客户构成的四级供应链网络，对网络各级节点之间的稳定性和港口的物流能力进行评估，并以供应链网络的利润最大和稳定性最高为目标，建立多目标优化模型。结合算例对NSGA-Ⅱ进行改进，引入矩阵实数编码、行列交叉操作、差分变异算子等，以期能够提升港机制造企业供应链网络的经济性和稳定性。

1 问题描述

港机制造企业一般采用订单生产模式[12]，其供应链网络中包括多个供应商、多个制造基地和多个客户。由于港机等大型装备多采用海运，所以其供应链网络中还应包括港口这一关键节点。为研究方便又不失一般性，本文结合港机制造企业实际情况，构建“供应商—制造基地—港口—客户”4层供应链网络，见图1。在该网络中，供应商向制造基地供给部件，制造基地具有制造、交付等功能，经过制造基地加工制造后最终将产品经由港口运输交付给客户。不同供应商供应的部件会存在价格差异，且各供应商与各制造基地之间关系的稳定性不同，通常供应价格较低的供应商由于市场广阔，与制造基地之间关系的稳定性反而表现较为普通。对于港机制造企业而言，由于是面向订单生产，其库存量较低，为提升供应链网络稳定性，通常会采用多元供应模式。在港机制造企業供应链网络中除考虑供应商选择、供需关系分配、成本控制外，结合实际运营情况，还应考虑影响供应能力的重要因素——港口物流能力[13]。因此，本文要解决的关键问题是：在满足能力约束的条件下，以港机制造企业供应链网络的利润和稳定性为优化目标对供应链网络进行优化。

2 模型建立

2.1 模型假设

①在整个供应链网络中，相同功能的节点处于网络的同一层级，分别代表供应商、制造基地、港口和客户。产品从供应链上游向下游传递，不相邻层级之间不存在跳跃的情况。②港机制造企业采用订单生产模式。在制造基地中，产品一旦加工制造完成，就会被立刻运往港口送至客户，因此制造基地无库存。③每个制造基地的部件可以来自多个供应商，产品可运至多个港口;每个港口运输的产品可以来自多个制造基地，并可以运往多个客户;每个客户所需的产品可从不同的港口运达。也就是说，在供应商至制造基地、制造基地至港口、港口至客户的环节中，供需关系可以是多对多的情况。④各供应商、制造基地由于受生产能力的影响，产品的价格不同，加工的成本也不同，且各节点由于所处的位置不同运输成本也不同。⑤各港口的物流能力不得超过该港口的能力限制，且供应商的供应能力、制造基地的制造能力和港口的物流能力是已知的。

2.2 符号定义

基本参数。S为供应商集合，s∈S;M为制造基地集合，m∈M;P为港口集合，p∈P;E为客户集合，e∈E;T为时段集合，t∈T;qsjit表示供应商s在时段t对生产产品j所需的部件i的供应能力;rmjt表示制造基地m在时段t对产品j的加工制造能力;wpjt表示港口p在时段t对产品j的物流能力;dejt表示客户e在时段t对产品j的需求量;θ表示投入产出系数;Γsmt表示在时段t供应商s与制造基地m之间供应关系的稳定性;Λmpt表示在时段t制造基地m与客户p之间供应关系的稳定性;Θp表示港口p物流能力评分。

成本参数。bsit表示在时段t从供应商s处采购部件i的单位价格;vsmit表示部件i在时段t从供应商s运到制造基地m的单位运输成本;gmjt表示在时段t在制造基地m加工制造产品j的单位成本;kmpjt表示产品j在时段t从制造基地m运到港口p的单位运输成本;ypejt表示产品j在时段t从港口p运到客户e的单位运输成本;cejt表示在时段t客户e采购产品j的采购价格。

决策变量。αmsit表示在时段t制造基地m从供应商s处采购的部件i的数量;βsmit表示部件i在时段t从供应商s运到制造基地m的数量;γmpjt表示产品j在时段t从制造基地m运到港口p的数量;λpejt表示产品j在时段t从港口p运到客户e的数量;ωsmt为0-1变量，若在时段t供应商s为制造基地m供应部件，则ωsmt=1，否则ωsmt=0;σmpt为0-1变量，若在时段t将产品从制造基地m运往港口p，则σmpt=1，否则σmpt=0;ω～pet为0-1变量，若在时段t将产品从港口p运往客户e，则ω～pet=1，否则ω～pet=0。

3 模型求解

在多目标优化问题中，通常各目标之间相互制约，即某些目标的优化会使其他目标的期望降低;对于同一个问题，由于决策者偏好不同，可能会做出不同的决策：因此，对于多目标优化问题，重在找到Pareto最优解集，从而提供更多决策支撑。NSGA-Ⅱ在多目标优化领域求解效果显著，具有简单、高效、适应性强且应用广泛的优点，是其他算法所不能比拟的[14]。然而，NSGA-Ⅱ也存在容易陷入局部最优、计算效率不高、解集分布性较差等不足。结合本文双目标优化模型，对NSGA-Ⅱ进行有针对性的改进，以期获得Pareto最优解集。经典NSGA-Ⅱ流程见图2。

NSGA-Ⅱ的关键在于基因编码、适应度函数选择、选择操作、交叉操作和变异操作[15]。根据本文算例需求，采用矩阵实数编码和行列交叉操作，并引入差分法将变异算子改进为差分变异算子，对算法进行改进。选择操作采取锦标赛选择法。为使算法与算例结合，以及提升算法的收敛性、稳定性和全局搜索能力，对算法进行设置，具体如下。

3.1 染色体编码与解码

基于供应链网络的层级和供应关系的特性，选用矩阵实数编码方法，并以矩阵作为染色体个体展开遗传操作，以降低运算复杂度和保持个体基因的完整性。

编码方式如下：种群规模为s′，第k代种群Pk={A1，A2，…，As′}，其中Ai表示第k代种群中的第i个个体，即矩阵染色体，Ai=（auv）n×m，auv表示基因元素，其中i∈{1，2，…，s′}，u∈{1，2，…，n}，v∈{1，2，…，m}。

矩阵Ai的大小取决于供应链网络层级数和供应关系中最多的同级节点数，基因元素auv与供应链层级之间具有相关性，反映与上层供应者之间的关系。如矩阵Ai为一个4×5阶矩阵，则表示有4层供应网络，各级节点数最大值为5，其中a32=（100，0，0，0，200）表示第3层第2个节点接受第2层第1节点的100单位供货量和第2层第5个节点的200单位供货量，而0则表示节点之间零供应。

3.2 交叉操作

针对算法所采用的矩阵实数编码，为有效进行个体间的交叉操作，进行行交叉操作和列交叉操作。

行交叉操作。对于采用n×m阶矩阵编码的个体Ai和Aj，随机产生两个由0、1构成的n维向量Bi和Bj，若Bi与Bj相乘后特征值为1，则交换相应的Ai与Aj的任意一行，若相乘后特征值为0则停止。以此类推，种群中任何两个个体都将完成行交叉。对通过行交叉操作产生的子代都要检验其是否满足约束条件（8）～（10），若不满足，则进行剔除。对满足约束条件的，采用局部锦标赛法，保留父代和子代个体中适应值较大的个体。

列交叉操作。列交叉操作类似于行交叉操作，对于种群中每两个父代个体都随机产生两个由0、1构成的n维向量。区别在于，由于供应商、制造基地、港口和客户数量的不同，列交叉操作后产生的子代个体可能会存在不满足约束条件（3）～（5）的情况，对不满足条件的进行剔除。对满足约束条件的，采用局部锦标赛法，保留适应值较大的个体。

3.3 变异操作

针对NSGA-Ⅱ存在种群多样性不足的问题，引入差分变异算子，取代NSGA-Ⅱ中原本的变异算子，以增强算法局部搜索能力。经过变异操作后，父代个体Ai更新为A*i=rAbest+（1-r）Ai式中：r为变异影响因子，反映了经迭代寻优后得到的最优个体Abest对变异方向的影响程度，其值越大则影响越大，通常r∈[0，1]。

差分变异算子搜索方法涉及距离阈值、相邻个体的选择等。距离阈值的确定方法是寻找种群非支配解集Ω在子目标Fi下的2个极值端点，求得目标值差，记为Δ，再根据公式求出子目标Fi的距离阈值D：D=2Δ/（Ω-1）D在进化过程中随Ω规模的变化而变化，从而确保得到的结果沿Pareto前沿均勻分布。

在对相邻个体进行选择前，要先对Ω按子目标Fi排序，对比相邻个体的距离与子目标Fi的距离阈值D，如果大于或等于距离阈值D，则需要对该相邻个体对进行差分局部搜索。

4 案例研究

某港机制造企业有4个制造基地，分布在3个港口附近，并有5个部件供应商和 5个需求客户，构成了一个4级供应链网络。将供应周期划分为3个时段。各供应商、制造基地、港口和客户的相关数据见表1，供应链网络各级节点之间的单位运输成本及稳定性系数分别见表2和3。各港口物流能力评分分别为Θ1=0.65、Θ2=0.43、Θ3=0.57。投入产出系数θ=0.5。基于此，求出供应商的部件供应、制造基地和港口的任务分配以及港机制造企业与客户之间的供需关系。

为对比NSGA-Ⅱ与改进NSGA-Ⅱ的优劣，采用相同的参数设置，并结合算法运算测试情况，将参数设置为：种群规模为100，最大进化代数为300，交叉概率为0.8，变异概率为0.05，变异影响因子r为0.4。两种算法分别运行50次，其性能比较见表4。

解集的空间分布  图3为两种算法所得的Pareto最优解集的空间分布。由表4可知，改进算法的收敛性更好，运算效果更为稳定;由图3可知，与算法改进前相比，改进算法的局部解更优，可得到较好的Pareto最优解集。因此，利用改进的NSGA-Ⅱ更能获得较优质的Pareto最优解集。从图3还可以看出，随着利润的变化，供应链网络的稳定性也会发生变化。在实际决策中，当现实环境更稳定时，决策者更偏向于经济成本低的方案，而当外部环境不稳定时，决策者更愿意选择网络稳定性高的方案。也可设置目标阈值，如当设置F1≥240亿元、F2≥30时，可选择图3中x轴利润大于240亿元、y轴稳定性大于30所对应的Pareto最优解集中的一个解。这里，选取一个最优解F1=256.1万元、F2=33.87，其对应的决策见表5。总之，利用改进的NSGA-Ⅱ可为决策者提供更多样的选择。

5 结 论

本文结合港机制造企业的实际情况，以其供应链网络的经济性和稳定性为目标建立多目标混合整数规划模型，并结合算例对NSGA-Ⅱ进行改进。结果表明，利用该模型能使供应链网络的经济性和稳定性都得到一定的优化，且改进的NSGA-Ⅱ计算效果更好，更有助于网络优化。本文研究也存在不足之处，具体表现在现实中供应链网络各节点的状态可能随时间而变化，客户需求具有随机性、多样性等特点，这些是下一步港机制造企业供应链网络优化研究的方向。

参考文献：

[1] LALMAZLOUMIAN M， WONG K Y， GOVINDAN K， et al. A robust optimization model for agile and build-to-order supply chain planning under uncertainties[J]. Annals of Operations Research， 2016， 240（2）： 435-470.

[2] KHALIFEHZADEH S， SEIFBARGHY M， NADERI B. A four-echelon supply chain network design with shortage： mathematical modeling and solution methods[J]. Journal of Manufacturing Systems， 2015， 35： 164-175. DOI： 10.1016/j.jmsy.2014.12.002.

[3] NEJAD A E， NIROOMAND I， KUZGUNKAYA O. Responsive contingency planning in supply risk management by considering congestion effects[J]. Omega， 2014， 48： 19-35. DOI： 10.1016/j.omega.2014.03.002.

[4] AZAD N， DAVOUDPOUR H， SAHARIDIS G K D， et al. A new model to mitigating random disruption risks of facility and transportation in supply chain network design[J]. International Journal of Advanced Manufacturing Technology， 2014， 70： 1757-1774. DOI： 10.1007/s00170-013-5404-0.

[5] 李夢. 复杂供应链网络的协作同步动力学模型研究[D]. 天津： 天津工业大学， 2019.

[6] 张虹. 基于多目标决策的供应链网络规划研究[D]. 长沙： 湖南大学， 2018.

[7] SHIM V A， TAN K C， TANG Huajin. Adaptive memetic computing for evolutionary multiobjective optimization[J]. IEEE Transactions on Cybernetics， 2015， 45（4）： 610-621. DOI： 10.1109/TCYB.2014.2331994.

[8] QIU Xin， XU Jianxin， TAN K C， et al. Adaptive cross-generation differential evolution operators for multiobjective optimization[J]. IEEE Transactions on Evolutionary Computation， 2016， 20（2）： 232-244. DOI： 10.1109/TEVC.2015.2433672.

[9] 时思思， 张新燕， 王志浩. 一种基于DCD和a-tDX改进的NSGA-II算法[J]. 计算机仿真， 2019， 36（12）： 257-262. DOI： 10.3969/j.issn.1006-9348.2019.12.053.

[10] 路艳雪， 赵超凡， 吴晓锋. 基于改进的NSGA-II多目标优化方法研究[J]. 计算机应用研究， 2018， 35（6）： 1733-1737. DOI： 10.3969/j.issn.1001-3695.2018.06.029.

[11] 吴暖， 王诺， 黄祺. 基于改进NSGA-II算法的班轮航线配船多目标优化[J]. 工业工程与管理， 2018， 23（1）： 79-85. DOI： 10.19495/j.cnki.1007-5429.2018.01.012.

[12] 褚忠伟. 某港机制造企业装配车间精益改善研究[D]. 南昌： 南昌大学， 2019.

[13] 赖成寿. 考虑不确定性的港口供应链企业合作策略研究[D]. 大连： 大连海事大学， 2019.

[14] 董骏峰， 王祥， 梁昌勇. 基于个体邻域的改进NSGA-II算法[J]. 计算机工程与应用， 2019， 55（5）： 166-174.DOI： 10.3778/j.issn.1002-8331.1711-0358.

[15] 路艳雪. NSGA-Ⅱ多目标优化算法的改进及应用研究[D]. 太原： 太原理工大学， 2017.

（编辑 赵勉）