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