NSGAⅡ在供应商选择中的应用

杨桂芝 王广泽 胡楠楠

摘要：针对传统多目标优化过程中参数难以选择的情况，采用NSGAⅡ解决供应商选择问题，为企业选择供应商提供一套有效的决策方案。首先，建立以质量最大化、售后服务最大化、价格最小化和时间最小化为实现目标，以总需求、供应能力、采购策略、采购量为约束条件的供应商选择模型。其次，供应商选择模型将采用NSGAⅡ对其进行求解。最后，将NSGAⅡ和加权求和法进行实验比较。实验结果表明，与传统的加权求合法方法相比，NSGAⅡ不需要引入权重或约束条件，从而避免了人为干预，只需要一次运算就可以获得一组能同时接近各个目标的Pareto解，为供应商选择提供较好的选择。

关键词：

供应商选择；多目标优化问题；NSGAⅡ；加权求和法

DOI：1015938/jjhust201705018

中图分类号： TP399

文献标志码： A

文章编号： 1007-2683（2017）05-0097-06

Supplier Selection Problem Based on Nondominated Sorting Genetic AlgorithmⅡ

YANG Guizhi，WANG Guangze，HU Nannan，ZHAO Lihua

（1.School of Computer Science and Technology，School of Mechanical and Power Engineering， Harbin 150080， China；

2.Library， School of Computer Science and Technology， Harbin 150080， China）

Abstract：In view of the traditional multiobjective optimization of process parameters is difficult to choose， this paper adopts the NSGA Ⅱ to solve the problem of supplier selection， for enterprises to choose suppliers to provide a set of effective decision schemeSpecific methods are as follows： first， set up to maximize quality and aftersales service to maximize， minimize the price and time minimizing your goal， to aggregate demand， supply， procurement strategy， procurement for supplier selection model of constraint conditionSecond， vendor selection model will use the NSGA Ⅱ to solve itFinally， compare the NSGA Ⅱ with weighted summation method experimentExperimental results show that compared with the traditional method of weighting for legitimate， the NSGA Ⅱ don't need to introduce weights or constraint conditions， so as to avoid the manual intervention， need only an operation can be close to the targets at the same time can get a set of Pareto solutions， the better choice for supplier selection

Keywords：supplier selection； multiobjective optimization problem； nondominated sorting genetic algorithm Ⅱ； weighted sum method

收稿日期： 2017-08-17

基金項目： 黑龙江省自然科学基金（QC2013C060）

作者简介：

杨桂芝（1963—），女，高级工程师

通信作者：

王广泽（1965—），男，高级实验师，Email：cs2011why@126.com.

0引言

近些年来，随着经济全球化的快速推进，以生产和产品为中心的管理模式已经不适合现代市场的需要，取而代之的是以顾客为中心的供应链管理模式，供应商选择则是供应链管理中的一个非常重要的环节[1]。例如，在高新技术为主体的大型制造服务公司中，产品和服务的供给成本占其销售额的80%，而30%的质量问题和80%的交货期问题都是由供应商所引起的[2]。可见，供应商选择不仅会降低制造企业的运营业绩，也会严重影响整个供应链的性能和核心竞争力。因此，在近几年中，供应链中的一个热门话题就是供应商选择，并且在国内外都引起来许多学者的关注。

供应商选择是在一定生产环境下，采购商根据预先设定的选择标准，从一定数量的候选供应商中选出最符合本企业或行业利益的一家或多家供应商[3]。在实际生产环境中，采购商选择往往需要根据多个标准对供应商进行评估，最后根据评估标准进行选择[4]。本文根据实际情况将质量最大化、售后服务最大化、价格最小化和时间最小化作为本文模型中的目标。并将供应商选择问题建模为一个多目标优化问题（multiobjective optimization problem， MOP）的数学模型。endprint

传统的求解多目标优化问题的方法是将多目标问题转化为单目标化问题，然后借助数学规划工具来求解，文[5]中利用加权和求解方法，通过分配以一定的权重值，将多目标函数聚合成单目标函数，最终得到Pareto最优解；ε约束法将运用到文[6]中，首先要优化多个目标中最重要的一个目标，而其他的目标则作为需要考虑的约束条件，将多目标问题转化为单目标问题；目标规划法则运用到文[7]中，通过求解给出每个目标所期望获得的目标值得到最优解。虽然利用传统方法解决多目标优化问题简单高效、并且能够保证收敛到 Pareto 最优解集，但是也存在着一些需要解决与完善的缺陷问题，其中，传统方法的最大的困难在于是需要决策者对实际问题具有足够深刻的认识，才能选取合适的参数，并且一组参数值往往只能产生一个Pareto 最优解，参数值的选取好坏往往决定着最终Pareto解的优劣。

人类通过自然选择的进化机理以及生物的遗传机理而总结出的一类智能群体算法称为进化算法。因为进化算法的优点在于不需要求导或者其它的辅助知识、能够并行并且一次可以得到多个解、算法简答容易实现，所以该算法成为MOP求解的最有效方法。近几年中，研究学者提出了很多用于多目标求解的进化算法，并且将这些算法应用于供应商选择问题。如：VRankovic等人采用了SPEA（strength paretooptimal evolutionary algorithm）算法对基于质量和价格两个目标的供应商选择模型进行求解[8]。Yan利用MOGA（Multiobjective sorting genetic algorithm）算法来解决核电设备采购的供应商选择问题[9]。AIsolina 等人将NSGA用于求解机会约束与批量折扣的供应商选择模型[10]。通常认为，决策者需要根据自己需要达到的多个目标，在一定的约束条件下选择供应商，一般情况下，能同时接近多个目标的解，往往是较为理想的Pareto解，可以接近于实际情况。本文采用的所有技术都旨在求得最接近于各目标的最优解，为供应商选择问题中决策者提供更好的选择。

因此，针对供应商选择问题如何能避免参数的选择对Pareto解的影响，而采用其它办法绕开参数选择问题成为我们探索的一个方向。本文针对这些问题采用非支配排序遗传算法Ⅱ（nondominated sorting genetic algorithm Ⅱ， NSGAⅡ）对供应商选择问题进行解决。

1模型设计

11多目标优化问题

简单的来讲，多目标优化问题就是对两个或者两个以上的目标同时进行优化，而这两个或者两个以上的目标会存在一定的制约，这些目标之间也是相互矛盾、相互冲突的，并且大部分的多目标优化问题不会只有一个最优解，一般都是一个解集。这些解就称为Pareto最优解。

多目标优化问题的定义如下：就是要寻找一组由决策变量组成的向量，这些决策变量满足所有的限制条件，并且优化了一组目标函数。这些目标函数构成了一个目标向量，它们从数学角度描述了各个目标的判定标准，各个目标之间可能相互冲突。因此“优化”意味着寻找各个目标上都可以满足的解[11]。

一般的MOP包括一组n个参数，k个目标函数，以及m个约束。目标函数和约束条件的决策变量的函数。一般来说，我们可以说，优化的目标是：

maximize b=f（a）=（f1（a），f2（a），，fk（a））

subject to c（a）=（c1（a），c2（a），，cm（a））≤0

where a=（a1，a2，，an）∈A

and b=（b1，b2，，bn）∈B（1）

A表示该决定的空间，B表示目标空间中，x为决策向量，b是目标向量。这些约束被定义为C（X）≤0，并确定了一套可行的解决方案。

12模型设计

本文建立一个多目标供应商选择模型。设在某公司服务备件供应链中，存在一个采购商，候选供应商则有I个，该采购商需要将J种商品在一个周期T内完成采购。采购人从供应商处采购xij个商品，其中对于供应商i提供的j种的质量水平为q，它的价格为p，交货时间为t，售后服务水平为s。模型符号如下所示：

I为供应商数量；

i第i个供应商；

T采购周期；

J商品数量；

j第j个商品；

G采购预算；

P供应商所提供商品的总价格；

Q供应商所提供商品的总质量；

xij供應商i处采购商品j的数量；

yij供应商i对于第j种商品的供应上限；

qj供应商i所提供的第j种商品的质量；

pij供应商i所提供的第j种商品的价格；

tij供应商i所提供第j种商品的交货时间；

sij供应商i所提供的第j种商品的售后服务水平；

Dj采购商对第j种商品的需求；

Li供应商i所提供的商品总量。

我们根据服务备件供应商选择问题中的质量、价格、时间、售后服务四条最主要的标准来建立模型。本模型以商品总质量最大化、商品价格最小化、售后服务水平最大化和供应时间最小化四个目标：

设目标函数F1为最大化商品总质量，即

F1=max∑Jj=1∑Ii=1xijqij（2）

设目标函数F2为最小化商品总价格，即

F2=min∑Jj=1∑Ii=1xijpij（3）

设目标函数F3为最大化商品售后服务水平，即

F3=max∑Jj=1∑Ii=1xijtij（4）

目标函数F4为最小化供应时间，即

F4=min∑Jj=1∑Ii=1xijtij（5）endprint

供应商能力约束、采购策略约束、采购量非负约束、采购预算约束以及总需求约束是需要考虑的主要约束。

供应商能力约束：采购量不能高于其供应能力的上限，因为供应商在某时段上的资源是有限的，即

∑Tt=1xij≤yij（6）

采购策略约束：出于从供应商之间产生的良性竞争的角度考虑，某个供应商所提供的商品总数不能高于一个设定的上限。即

∑Jj=1xij≤Li（7）

采购量的非负约束：采购量显然是非负值，即x≥0。

采购预算约束：设f2为商品总价格，G为采购预算。采购商品的总支出必须在采购预算内。即

∑Jj=1∑Ni=1xijpij≤G（8）

总需求约束：供应商提供的商品必须满足采购商在一定时期内对于数量和种类的需求即

∑Tt=1xij=Dj（9）

本文根据多目标优化问题，通过对供应商选择问题的描述，主要以质量、价格、时间、售后服务作为问题的优化目标，并根据实际情况给出目标的几个约束条件，最终建立了一个基于多目标的供应商选择问题的数学模型，为问题的解决建立基础。

2算法设计

多目标优化与单目标优化不同，由于多目标优化中的目标相互之间存在着制约关系，所以某些目标的优化将会导致其他目标的降低，由于问题的最优解较多，甚至可以使无穷大的，一般情况下通常采用非劣解或Pareto解表示。Pareto解是指最接近目标的最优解，对于多目标问题来说，有时可能找不到一个最优解，这时候就需要尽可能找到分布均匀的最接近目标的Pareto解集。也就是指Pareto的前端。进化算法与传统的多目标优化算方法相比较而言，多目标优化问题的求解更适合采用该算法。首先，进化算法是在种群的搜索算法上演变而来的，因此它能搜索多个目标，从而找到多个最优解。其次，进化算法无法找到Pareto的连续的前端解，并且无法描述Pareto解得形状，所以能更好的解比非凸或者不联系的最优前端。

21NSGAⅡ

本文采用NSGAⅡ算法对供应商选择问题进行求解，NSGAⅡ算法主要具有以下三个方面优点：

1）采用新的基于分级的快速非支配解排序方法，其中。目标函数的个数有m表示，种群中个体的数目也就是指种群的规模用N表示。

2）为了标记出快速非支配排序后在同级中出现的不同个体适应度的数值，与此同时，整个Pareto前沿将被当前Pareto前沿的个体所涉及到，并且能够最大限度的均匀遍布，拥挤距离的定义就是在该算法的基础上提出来的，NSGAⅡ中的适值度共享方法将呗拥挤距离比较算子所替代。

3）将精英保留机制引入到其中，经过一系列的选择之后，其父代的个体将与参加法治的提提所产生的后代同时竞争，然后将产生下一代的种群，它的优点是能够保持优良的个体以及提高种群的整体水平。

对于每个存在于NSGAⅡ中的解来讲，需要确定的是有多少个解能支配它以及它能够支配的解集。中群众的一个特定解的解密度需要由NSGAⅡ估计围绕，也就是指沿着每个目标来进行两个解之间的平均距离的计算，计算出来的值被称为密集距离。在进行选择的过程中，NSGAⅡ密集比较算子需要同时考虑密集距离和种群中个体的非劣解秩。但是需要优先考虑非劣解秩。如果两个解存在相同的非劣解秩时，则需要放弃那个处于拥挤距离区域内的解。NSGAⅡ与之前算法中的经营保留策略使用外部种群不相同，前者的精英保存策略使用选择，其中包括最好的父代和子代个体。由于这种机制使得新一代的种群比前一代的种群效果更好。

22NSGAⅡ流程

首先，采用NSGAⅡ對初始种群P进行遗传操作时，将会得到一个种群Q，然后将种群P与种群Q进行合并后，再进行非劣排序与用具距离排序的操作，进而形成一个新的种群P0，最后进行反复直到结束，图1为具体的算法流程图。

具体过程如下：

Step 1：随机产生初始种群P0，然后对初始种群P0进行非劣排序并且赋秩于每个个体；最后将P0进行遗传操作，将会得到一个新的种群Q0，令t=0。

Step 2：合并种群Pt和种群Qt后将会得到一个新的种群Rt，再对Rt进行非劣排序，进而得到非劣前端H1，H2，…。

Step 3：按照拥挤距离将所有的Fi进行排序，并按锦标赛法选取最好的N个（种群规模）个体形成种群Pt+1。

Step 4：对Pt+1这个种群进行遗传操作，得到新的Qt+1种群，一直到终止条件成立即可结束，否则令t=t+1再重复Step2。

NSGAⅡ算法对种群Q进行非劣排序的具体步骤：

1）种群R中的每个解由x（或个体x）表示，x的支配数由n表示，x是指Q中个体的个数劣于解x的个数，S为x的支配集合，x是指R中个体劣于解x的个体组成的集合。首先设x的支配数为n且x为0，S是x的支配集合，x为空集。然后将x与种群Q中每个个体x′（除解x外）相比较，当x′劣于x时，x′进入Sx，且nx=nx+1。在Pareto前端中加入nx=0的个体，且令解x的秩xrank=1。

2）令i=1。

3）令为空集，对每个存在于Fi中的解x执行的操作步骤如下：

如果x属于Sx，则nx=nx-1；如果nx=0，则xrank=i+1且x进入。

4）如果不为空集，则i=i+1，且Fi=，转到步骤（3），否则迭代将终止。

如图1所示，Pareto前端Fi的拥挤距离是用来估计一个解周围其他解的密集程度。对每个目标函数来讲，首先需要通过该目标函数的大小对非劣解集中的解进行排序，然后计算每个解i，也就是指解i的拥挤距离id，它是由解i+1和i-1构成的超立方体的平均边长，其中，边界解的拥挤距离为无穷大。按拥挤距离对Fi中的个体进行排序的具体步骤如下：endprint

首先按秩xrank进行排序，当秩越小时，解x的排序则越靠前；当秩相等时，再按拥挤距离id进行排序，当拥挤距离越大时，解x的排序则越靠前。

精英策略具体操作表述为：规模大小为2N的种群Rt是由一个规模大小都是N的父代种群Pt与子代种群Qt合并后所产生的，然后再对Rt进行快速非支配排序分层操作，同时分层计算出它的拥挤度，最后在种群Rt中通过个体优劣程度选择出前N个个体形成一个新的父代种群，如图3所示。

3算例仿真分析

本文中的实验数据取自某汽车备件供应商数据库，在汽车供应链中，存在1个汽车零件采购公司，3个汽车零件供应企业；该采购公司需要在采购周期T时间内采购2种汽车零件；采购两种商品的总数为100，采购预算为1500，供应商采购时间和价格等数据如表1所示。

选择操作、交叉操作以及变异操作都属于遗传操作，在NSGAⅡ中主要选择采用锦标赛法对二进制交叉进行模拟，变异采用多项式变异。锦标赛选择是在局部竞争选择策略的基础上提出来的。其本质是：每次都随机的选取n个个体，在这些个体中选择一个适应度最高的个体到下一代中，直至新群体选满，在本文中n取2。

模拟二进制交叉主要是模仿基于二进制串中的单点交叉的工作原理而作用于以实数表示的染色体，经过交叉操作可以使两个父代染色体产生出两个子代染色体，并且子代能够继承父代中的染色体中有关的模式信息。交叉概率取09变异采用多项式变异，其参数为变异分布系数，意义同交叉分布系数，根据实际情况，我们一般选择变异分布系数值为01。

将数据代入改进多目标遗传算法中运算，得到10个秩为l的Pareto最优解，如表2所示。

表中的每一种采购方案都与每组的最优解相对应；从表中可以得出，供应商i1和i2能获得市场较大的份额主要是因为本身具有较强的市场竞争力；但是供应商i3因为受到了采购策略约束以及需求约束的保护，所以产品的竞争力也相对较弱，因为获得了极少的市场份额。采购商需要在实际操作中根据具体情况，不给予或少量给予供应商i3任何订单。

将数据代入权重和算法中进行运算，得到6个Pareto最优解，如表3所示，表中每组最优解都对应着一种采购方案。

权重和算法需要引入权重，且每组权重往往只能得到一个最优解，为了得到更多的Pareto最优解，往往Pareto最优解随着权重的改变有着较大的变化，并且权重和法虽然能够求得最优解，但是如果我们所给出的权重不符合实际情况，那么求得出的Pareto解往往不是最优解，没有实际意义。

4结论

在本文中，我们建立以质量最大化、售后服务最大化、价格最小化和时间最小化为实现目标，以总需求、供应能力、等为约束条件的供应商选择模型。并采用多目标进化算法NSGAⅡ对供应商问题进行解决，NSGAⅡ算法通过每一次的计算获得到一组Pareto最优解决方案。决策者可以选择最合适的解决方案。仿真试验结果表明：在权重法中，我们需要确定每个目标的权重，权重值决定了最终的解，因而，一些不符合的权重往往得到错误的解。而在NSGAⅡ算法中，由于算法中无需引入权重或约束转化等步骤，可以直接求解出近似的Pareto最优解集，从而避免人工干预，可以获得较为实用的Pareto最优解。因此NSGAⅡ算法适合求解多目标供应商选择问题。

在今后工作中，针对供应商选择问题计划在以下方面进行探索。第一，供应商选择问题在实际中还存在许多目标约束，例如，很多采购商将供应商信誉、实力等多种目标纳入到供应商选择标准中。第二，多目标进化算法已经成为解决 MOP 问题的主流方法，但是，在多目标进化算法中，个体按照被其它个体支配的个数评价优劣。这种评价准则虽然保证了公平性，但同时也造成了效率的缺失。采用这种方法容易导致退化现象的产生。在今后的工作中，我们计划根据实际情况引入多种约束条件建立模型，并在多目标进化算法中引入博弈论来解决以上问题，使得供应商选择问题能得到更好的解决。

参 考 文 献：

[1]付立坤， 乔佩利， 朱立峰. 供应商选择的分布式搜索算法[J]. 哈尔滨理工大学学报， 2014， 19（4）：106-110.

[2]康永星， 马军海. 基于离差分析的供应商选择模型[J]. 哈尔滨理工大学学报， 2007， 12（4）：90-94.

[3]张树梁， 陈友玲， 张豆. 供应链中供应商选择决策方法[J]. 计算机应用研究， 2015， 32（4）：1024-1027.

[4]VARELAVACA A J， GASCA R M. Towards the Automatic and Optimal Selection of Risk Treatments for Business Processes Using a Constraint Programming Approach[J]. Information & Software Technology， 2013， 55（11）：1948-1973.

[5]PADHI P C， MAHAPATRA S S， YADAV S N， et al. MultiObjective Optimization of Wire Electrical Discharge Machining （WEDM） Process Parameters Using Weighted Sum Genetic Algorithm Approach[J]. Journal of Advanced Manufacturing Systems， 2016， 15（02）：85-100.

[6]AMIRIAN H， SAHRAEIAN R. Augmented εconstraint Method in Multiobjective Flowshop Problem with Past Sequence Setup Times and a Modified Learning Effect[J]. International Journal of Production Research， 2015， 53（19）：1-15.

[7]袁晓， 肖瑾. 应用模糊目标规划方法求解多目标线性分式规划问题[J]. 数学的实践与认识， 2016， 46（6）：158-164.

[8]GUO Z X， WONG W K， LI Z， et al. Modeling and Pareto Optimization of Multiobjective Order Scheduling Problems in Production Planning[J]. Computers & Industrial Engineering， 2013， 64（4）：972-986.

[9]严兆君， 周磊， 王德忠. 基于改进MOGA的供应商选择方法以及在核电设备采购中的应用[J]. 核动力工程， 2007， 28（5）：114-118.

[10]ELAHI Y， AZIZ M I A. MeanVarianceCvaR Model of Multiportfolio Optimization via Linear Weighted Sum Method[J]. Mathematical Problems in Engineering，2014，（2014-3-30）， 2014， 2014（10）：1-7.

[11]马小姝， 李宇龙， 严浪. 传统多目标优化方法和多目标遗传算法的比较综述[J]. 电气传动自动化， 2010， 32（3）：48-50.

（編辑：王萍）endprint