角度懲罰精英策略的綠色供應鏈伙伴選擇研究

郭海東,王麗萍,章鳴雷

1(浙江工業大學 經貿管理學院,杭州 310023) 2(浙江工業大學 計算機科學與技術學院,杭州 310023) 3(浙江工業職業技術學院 商貿學院,浙江 紹興 312000) 4(浙江工業大學 教育科學與技術學院,杭州 310023)

1 引 言

隨著經濟全球化和信息技術的飛速發展,市場需求越來越多樣化、不確定,產品更新換代越來越快.在這種環境下,企業需要與其他擁有互補資產或產品的企業或公司建立良好的聯系[1].供應鏈管理被認為是解決上述問題、提高企業競爭力的有效組織模式.其核心要素是將所有類型的企業組織成一個合作聯盟,以獲得其資源和能力的充分共享[2].因此,伙伴選擇已成為供應鏈管理(Supply Chain Management,SCM)領域的一項重要決策.綠色供應鏈(Green Suppy Chain,GSC)將環境問題納入商業活動中,它以綠色制造理論和供應鏈管理技術為基礎,通過產品設計、材料采購、制造過程、最終產品交付和最終壽命管理,將環境因素集成到供應鏈管理中.在綠色供應鏈管理中,供應鏈伙伴選擇過程是最重要的因素,因為它有助于實現高質量的產品和環境保護[3].

綜述文獻,求解供應鏈伙伴選擇問題的具體方法中層次分析法[4]、模糊評價法[5,6]和線性權重法[7]過于依賴專家的經驗,當決策者進行供應鏈伙伴的初次選擇或是市場動向不明朗時,決策者很難事先給出符合實際的權重系數.人工智能法[8,9]中的支持向量機學習速度較慢,灰色理論對非遞增模型的擬合度較差,而神經網絡優化參數較多且優化對象具有唯一性.多目標優化法[10]利用基于Pareto支配關系的進化算法進行求解,通過快速非支配排序,在一次求解過程中得到多個Pareto非支配解,不僅可以避免傳統求解方法需要確定各個目標函數權重造成的主觀誤差,而且優化參數較少,具有較低的計算復雜度.然而,綠色供應鏈伙伴選擇問題由于考慮了產品綠色度,其優化目標進一步增大,成為典型的高維目標優化問題.在高維目標優化問題中,個體之間幾乎不存在支配關系,使得基于Pareto支配關系的優化方法難以在高維空間中篩選出較優解,造成算法對種群的選擇壓力降低、收斂速度放緩等困難[11].

本文提出一種APD精英策略的高維目標進化算法NS-RVEA對綠色供應鏈伙伴選擇問題進行求解.該算法通過種群劃分策略將高維目標空間分解為多個子區域,并引入角度懲罰距離(APD)機制作為個體評價標準進行優化,具有較強的搜索能力和較低的計算成本.由于APD機制僅使用分解策略優化種群,而不考慮個體間的Pareto支配關系,使得在算法搜索后期,子種群中分布性好但收斂性差的劣解反而容易獲得更高的APD值,從而導致較優解的淘汰以及種群的退化.因此,本文在分解策略的基礎上引入非支配排序方法,先對子種群內的個體進行Pareto非支配排序,再通過APD機制對剩余個體進行篩選,提高種群的選擇壓力和收斂速度.

2 模型建立

2.1 問題描述

Altiparmak等人[12]以土耳其某塑料產品生產企業為原型,以生產成本、服務質量和生產利用率為優化目標,提出一個多產品、多階段供應鏈網絡模型,通過選擇合適的供應鏈伙伴和物流倉庫,以滿足市場需求和生產能力的限制.在此基礎上,Yah等人[10]以臺灣某電子生產企業為原型,將供應鏈綠色度作為第四優化目標,提出一個三階段綠色供應鏈網絡模型該模型有以下3個假設:1)客戶需求和供應鏈伙伴的數量是已知的;2)各階段所需的供應鏈伙伴需求是已知的;3)各階段的運輸方向是單向的.

2.2 模型描述

該綠色供應鏈模型分為供應商、制造商、物流倉庫共三個供應鏈階段,每個階段有四位可選擇的合作伙伴,其數學模型如公式(1-8)所示.該綠色供應鏈伙伴選擇的評價標準主要考慮以下四個目標:產品成本和運輸成本構成的總成本最小化;運輸時間所占總時間的最小化;平均產品質量的最大化;綠色度評價得分最大化.

1)模型參數

Di表示客戶i的需求;

s(m,w)表示供應商(制造商,物流倉庫)的合作伙伴個數;

Gl(k,j)表示供應商l(制造商k,物流倉庫j)的綠色度評分;

MCl(k,j)表示供應商l(制造商k,物流倉庫j)的生產成本;

PQl(k,j)表示供應商l(制造商k,物流倉庫j)的產品質量;

CPl(k,j)表示供應商l(制造商k,物流倉庫j)的生產能力;

TClk(kj,ji)表示供應商l至制造商k(制造商k至物流倉庫j,物流倉庫j至客戶i)的單位運輸成本;

BTlk(kj,ji)表示供應商l至制造商k(制造商k至物流倉庫j,物流倉庫j至顧客i)的單位運輸時間.

LQlk(kj,ji)是實數變量,表示供應商l至制造商k(制造商k至物流倉庫j,物流倉庫j至客戶i)的物流量;

2)決策變量

3)數學模型

minf1=∑lMClSl+∑kMCkMk+∑jMCjWj+∑l∑kTClkLQlk+
∑k∑jTCkjLQkj+∑j∑iTCjiLQji

(1)

minf2=∑l∑kBTlkLQlk+∑k∑jBTkjLQkj+∑j∑iBTjiLQji

(2)

minf3=∑lPQlSl+∑kPQkMk+∑jPQjWj

(3)

minf4=∑lGlSl+∑kGkMk+∑jGjWj

(4)

s.t. ∑lSl=s,∑kMk=m,∑jWj=w

(5)

∑kLQlk=∑jLQkj=∑iLQji=∑iDi

(6)

∑lLQlk≤CPl,∑kLQkj≤CPk,∑jLQji≤CPj

(7)

LQlk≥0,LQkj≥0,LQji≥0

(8)

公式(1)-公式(4)表示綠色供應鏈伙伴選擇問題的4個待優化目標.為方便起見,f3和f4優化目標已轉化成最小化問題,其中:公式(1)表示供應鏈網絡的總成本f1,包括生產成本和運輸成本兩部分;公式(2)表示供應鏈網絡的總運輸時間f2;公式(3)表示供應鏈網絡的總生產質量f3;公式(4)表示供應量網絡的總綠色度f4.公式(5)-公式(8)表示綠色供應鏈伙伴選擇問題的約束條件,其中:公式(5)表示供應鏈各階段合作伙伴數量;公式(6)為物流量守恒式,即供應鏈上階段的物流輸出量總和應等于下階段的物流接收量總和;公式(7)表示供應鏈各階段物流量不超過其生產能力;公式(8)表示供應鏈各階段物流量不能為負.

3 算法設計

3.1 染色體表示

供應鏈網絡模型的實質是一個多級的運輸網絡問題.Gen等人[13]提出,運輸網絡問題的染色體可以表示為一串自由排列的自然數:v=[6 4 8 1 5 2 7 3],其長度等于供應鏈上游數量(K)和下游數量(J)之和,各基因位上的數值表示上游和下游的優先級.通過給定染色體,依次選擇優先級最高的上游(或下游),并將其連接到與之運輸成本最低的下游(或上游),從而形成運輸網絡.其算法流程框架如算法1所示.

算法1.基于優先級的染色體解碼

輸入:上游數量K,下游數量J,生產能力P,

用戶需求D,運輸成本C,染色體v(K+J)

輸出:上游k到下游j的物流量LQkj

1.LQ=Φ

2. WHILED≠Φ

3.l=argmax{v(K+J)}

4. IF 1≤l≤K

5.k=l;j=argmin{Ckj|v(K+j)≠0,j∈J}

6. ELSE

7.j=l-K;k=argmin{Ckj|v(k)≠0,k∈K}

8. END

9.LQkj=min{Pk,Dj}

10.Pk=Pk-LQkj;Dj=Dj-LQkj

11. IFPk=0 orv(k)=0

12.v(k)=0 orv(K+j)=0

13. END

14.END

表1是以圖1所示運輸網絡(K=3,J=4)為背景的基于優先級的染色體解碼的具體過程.以第1次循環為例:第1步,確定優先級最高的基因位l=2;第2步,由于l≤K=3,選擇上游k=l=2,同時選擇與之運輸成本最低的下游j=2,并確定其物流量LQ22=min{P2,D2}=100;第3步,更新生產能力P2=100-100=0,客戶需求D2=150-100=50;第4步,由于生產能力P2=0,更新染色體v(2)=0.如此循環,直至用戶需求D=Φ,則停止循環,并輸出物流量LQkj.

圖1 3個供應商和4個制造商的運輸網絡染色體解碼示意圖Fig.1 Schematic diagram of chromosome decoding for transport network of 3 suppliers and 4 manufacturers

染色體v(K+J)生產能力P用戶需求DlkjLQkj1[374|2615](100,100,150)(50,150,100,50)2221002[304|2615](100,0,150)(50,50,100,50)532503[304|2015](100,0,100)(50,0,100,50)734504[304|2010](100,0,50)(50,0,100,0)333505[300|2010](100,0,0)(50,0,50,0)111506[000|2010](50,0,0)(0,0,50,0)413507[000|0000](0,0,0)(0,0,0,0)

本文的多級供應鏈網絡模型可分為3個階段:供應商l至制造商k的第1階段,制造商k至物流倉庫j的第2階段,物流倉庫j至客戶i的第3階段.因此,該供應鏈網絡的染色體由三部分組成,每一部分對應該階段的運輸網絡,其解碼具體步驟如圖2所示.

圖2 多級供應網絡染色體解碼示意圖Fig.2 Schematic diagram of chromosome decoding in a multilevel supply network

首先,對供應鏈網絡第三階段進行解碼:根據物流倉庫生產能力CPW、用戶需求D和優先級v3確定待選擇的物流倉庫j及其物流量LQji;其次,對供應鏈網絡第二階段進行解碼:將物流倉庫物流量作為物流倉庫需求DW,并根據制造商生產能力CPM和優先級v2確定待選擇的制造商k及其物流量LQkj;最后,對供應鏈網絡第一階段進解碼:將制造商物流量作為制造商需求DM,根據供應商生產能力CPS和優先級v1確定待選擇的供應商l及其物流量LQlk.

3.2 交叉與變異

3.2.1 交叉操作

本文采用基于片段的均勻交叉方法對染色體進行交叉操作,其主要思想為:隨機選擇父代的染色體片段作為子代的染色體組成.首先,隨機產生一個二進制代碼,其長度等于供應鏈網絡的階段數;然后,根據二進制代碼對父代進行交叉操作:“0”表示從父代1中選擇對應階段的染色體片段,“1”表示從父代2中選擇對應階段染色體片段.這種交叉方法有利于保留父代的良好基因片段.

3.2.2 變異操作

本文采用基于片段的移動變異方法對染色體進行變異操作,其主要思想為:父代的各染色體片段獨立進行變異操作,每個染色體片段采用移動變異方式.首先,隨機產生一個二進制代碼,其長度等于供應鏈網絡的階段數;然后,根據二進制代碼對父代進行變異操作:“0”表示對應階段的染色體片段不發生變異操作,“1”表示對應階段的染色體片段發生移動變異操作.這種變異方法有利于維護染色體各片段的獨立性.

3.3 評價與選擇

本文采用五種方法對該綠色供應鏈伙伴選擇問題進行對比分析:1)傳統多目標遺傳算法MOGA[14];2)基于快速非支配排序的多目標遺傳算法NSGA-II[15];3)經典分解多目標進化算法MOEA/D[16];4)參考向量引導的高維目標進化算法RVEA[17];5)本文提出APD精英策略的高維目標優化算法NS-RVEA.

RVEA 通過種群劃分策略將高維目標空間分解為多個子區域,并提出APD機制作為子種群內個體的評價標準,具有較高的搜索能力和較低的計算成本.APD計算方式如公式(9)所示:

dt,i,j=(1+P(θt,i,j))·Ft,i

(9)

式中,θt,i,j表示個體與參考向量之間的夾角,Ft,i表示個體與目標原點的距離,P為懲罰函數,其表達式如下所示.

(10)

(11)

式中,M表示懲罰系數,也是目標維度,表明高維目標空間下目標向量與參考向量的偏差值會遭到更多懲罰;tmax表示算法迭代次數;t表示當前迭代次數;α是控制P(θt,i,j)隨當前迭代次數t的變化率,一般情況下取α=0.1;γVt,j表示各參考向量Vt,j之間的最小夾角.

由于候選解在高維目標空間中是稀疏分布的,因此在整個搜索過程中對收斂性和多樣性側重點是不同的.理想情況是在搜索過程的早期階段,對種群收斂性施加很高的選擇壓力以將種群推向PF,而在搜索過程的后期階段,一旦種群接近PF,應強調種群多樣性以生成分布良好的候選解集.

懲罰函數P就是為了滿足該搜索思想而設計的.在搜索的早期階段(t?tmax),此時P(θt,i,j)≈ 0,即dt,i,j≈ ‖Ft,i‖.這意味著,搜索前期個體的APD值主要由‖Ft,i‖決定.而在搜索的后期階段,隨著當前迭代次數t逐漸接近tmax,θt,i,j對APD值的影響逐漸增大,從而保證解集的分布性.

但是APD機制僅使用分解策略優化種群,而不考慮個體間的Pareto支配關系,使得在算法搜索后期,子種群中分布性好但收斂性差的劣解反而容易獲得更高的APD值,從而導致較優解的淘汰以及種群的退化[18].

因此,為彌補APD機制的缺陷,本文提出APD精英策略:在分解策略的基礎上引入非支配排序方法,先對子種群內的個體進行Pareto非支配排序,再通過APD機制對剩余個體進行篩選,從而提高種群選擇壓力和收斂速度.

1)對子種群中的個體先進行Pareto非支配排序,再計算APD值,目的是通過非支配排序方法剔除子種群中與參考向量偏離夾角較小但是離目標原點較遠的個體,加快種群的收斂能力.

2)考慮到搜索初期子種群規模的不穩定性,即在算法運行前期產生的部分子種群中可能不存在個體.因此,引入Pareto非支配排序方法的具體時間顯得尤為重要.若過早對子種群個體進行非支配排序,會延緩子種群規模的增長速度,進而影響收斂速度;若非支配排序方法引入過遲,則造成算法中期產生的大量較優解的遺失.本文采用參數n=‖Pt,j‖控制非支配排序方法對劣解進行篩選,n表示當前迭代次數下的子種群個數,具體方法如下:隨著算法迭代的進行,目標空間中的子種群數量逐漸增大,當參數n達到參考向量個數(也是種群規模)N時,算法立即調用Pareto非支配排序方法對子種群個體進行排序和篩選.其算法流程框架如算法2所示.

算法2.APD精英策略

輸入:種群規模N、參考向量V、子種群Pt,j

輸出:下代種群Pt+1

1.j=1

2. WHILEj

3. IF‖Pt,j‖=N

4. FORi=1 TO ‖Pt,j‖

5.Pt,j=Nondominated-sort(Pt)

6.dt,i,j=(1+P(θt,i,j))·‖Ft,i‖

7. END FOR

8. ELSE

9. FORi=1 TO‖Pt,j‖

10.dt,i,j=(1+P(θt,i,j))·‖Ft,i‖

11. END FOR

12. END WHILE

4 仿真實驗及結果分析

仿真實驗采用“4-4-4-4”綠色供應鏈網絡模型,包括供應商、制造商、物流倉庫和客戶4個部分組成.除客戶以外,每個部分有4個候選者,需要決策者從中挑選合適的合作伙伴,以滿足供應量網絡的生產能力和客戶需求.其中,各階段生產能力、生產成本、產品質量、運輸成本、運輸時間、綠色度和客戶需求的具體參數已知,如圖3所示.

圖3 “4-4-4-4”綠色供應鏈網絡模型具體參數Fig.3 Specific parameters of the 4-4-4-4 green supply chain network model

為驗證本文所提算法NS-RVEA的有效性,將其與MOGA、NSGA-II、MOEA/D和RVEA四種算法在3個測試問題上進行性能對比實驗,各算法相關參數設置為:1)目標維數為2、3、4維;2)種群大小為100、105、120;3)進化代數:100、200、300;4)交叉概率均為0.9;5)變異概率均為0.1;6)特殊參數:MOEA/D(T=20);RVEA和NS-RVEA(α=0.1;fr=0.2).其中,測試問題一是考慮運營成本(f1)和運輸時間(f2)的兩目標優化問題;測試問題二是考慮運營成本(f1)、運輸時間(f2)和產品質量(f3)的三目標優化問題;測試問題三是一個四目標優化問題,也是一個高維目標優化問題,綜合考慮運營成本(f1)、運輸時間(f2)、產品質量(f3)以及綠色度(f4).為了能直觀地表達5種算法所得解集在目標空間中的分布情況,本文分別繪制了5種算法在2-4目標優化問題上的Pareto前沿對比圖,如圖4-圖6所示.

圖4表示MOGA、NSGA-II、MOEA/D、RVEA和NS-RVEA五種算法在兩目標優化問題上的Pareto前沿對比圖.仿真結果表明:僅考慮f1和f2兩個優化目標時,NS-RVEA所得解集最靠近Pareto近似前沿,表明APD精英策略有效增強子種群內部的選擇壓力,加快種群的收斂速度;NSGA-II所得解集的收斂性僅次于NS-RVEA,表明基于快速非支配排序方法仍能較好地篩選種群中的非支配解;RVEA所得解集多樣性優于NAGA-II,但和Pareto近似前沿的距離也更遠,表明RVEA在搜索后期為維持種群多樣性,犧牲了解集收斂性;MOEA/D所得解集的在目標空間中的分布情況最好,但沒有收斂到近似Pareto前沿,表明MOEA/D的分解策略能較好地維護種群多樣性,但其收斂能力有所不足;由于MOGA將多目標問題轉化為單目標問題進行求解,其所得解集在目標空間中僅有一個最優解,且明顯被支配于其他四種算法所得解集,表明MOGA不適合求解多目標優化問題.

圖5表示5種算法在三目標優化問題上的Pareto前沿對比圖.仿真結果表明:當考慮f1、f2和f3三個優化目標時,NS-RVEA的性能表現依然強勢,其所得解集明顯優于其他四種算法所得解集;與兩目標優化問題相比,NSGA-II所得解集的Pareto非支配解個數有所增加,但其收斂性有所降低,表明隨著目標維度的增加,種群間的非支配解比例上升,基于Pareto占優關系的非支配排序方法對種群的選擇壓力不足,導致算法收斂速度放緩;RVEA算法所得解集依然保持較好的空間分布情況,但仍然難以收斂到Pareto近似前沿;MOEA/D所得解集次之,其所得解集被支配于NS-RVEA、NSGA-II和RVEA,表明其篩選個體時僅考慮聚合函數值,忽略了個體間的支配關系,不利于種群的收斂;MOGA在一次求解過程中只能給出一個最優方案,不利于決策者的選擇.

圖4 5種算法在兩目標優化問題上的Pareto前沿對比圖Fig.4 Pareto frontier comparison of the five algorithms on two objective optimization problems

圖5 五種算法在三目標優化問題上的Pareto前沿對比圖Fig.5 Pareto frontier comparison of the five algorithms on three objective optimization problems

圖6 五種算法在四目標優化問題上的平行坐標系對比圖Fig.6 Comparison of the five algorithms in parallel coordinate system on four objective optimization problems

圖6表示MOGA、NSGA-II、MOEA/D、RVEA和NS-RVEA五種算法在四目標優化問題上的平行坐標系對比圖.

仿真結果表明:當進一步考慮供應鏈綠色度(f4)作為待優化目標時,NS-RVEA所得解集反映在平行坐標系上的折線寬度最大且最密集,表明APD精英策略在高維目標優化問題上,能在有效保持較高選擇壓力的同時較好地維護種群多樣性;NSGA-II所得解集反映在平行坐標系上的折線寬度較大,但密集程度有所下降,表明在高維目標優化問題中,NSGA-II的多樣性劣于NS-RVEA;RVEA所得解集在平行坐標系上的折現寬度較大且分布均勻,表明其種群劃分策略有效維護了種群在高維優化問題中的多樣性;MOEA/D所得解集反映在平行坐標系上折線寬度和密集程度進一步下降,表明MOEA/D在高維目標優化問題上的求解性能出現明顯的衰減;而MOGA求得的Pareto最優解只有一個,因而其反映在平行坐標系上為一條折線.

為進一步對比五種算法在綠色供應鏈伙伴選擇問題上的求解性能,本文從IGD*指標、Pareto最優解平均個數和平均運行時間三個方面,對5種算法進行統計分析,具體結果如表2所示.其中,IGD*指標用于衡量算法所得解集Pi的求解精度,包括算法所得解集Pi與近似Pareto前沿P*之間的平均距離和算法所得解集Pi在目標空間中的分布多樣性兩個方面,如公式(12)所示.式中,P1、P2、P3、P4表示MOGA、NSGA-II、MOEA/D和NS-RVEA五種算法所得解集.

(12)

從表2中可以看出,在綠色供應鏈伙伴選擇問題中,NS-RVEA的求解精度最高,其所得解集的IGD*指標均優于其他四種算法.同時,NS-RVEA所得Pareto最優解的平均個數也均大于其他四種算法,表明NS-RVEA具有良好的多樣性,在一次求解過程中能提供給決策者較多的選擇方案. 而在算法平均運行時間上,除RVEA外,NS-RVEA的平均運行時間遠低于其他三種算法,其平均運行時間增長幅度較小,具有較低的時間復雜度.且隨著目標維度的增加,NS-RVEA的平均運行時間與RVEA的差距均小于3%.

5 結 論

在環境保護和供應鏈競爭的雙重壓力下,綠色供應鏈伙伴選擇問題的研究具有重要的現實意義,同時也是一個典型的高維目標優化問題.本文在綜述現有供應鏈伙伴選擇問題求解方法的基礎上,以運營成本、配送時間、產品質量和綠色度為優化目標,為綠色供應鏈伙伴選擇問題建立了一個四目標優化模型.針對高維目標優化問題中種群選擇壓力降低、收斂速度放緩等問題,本文在分解算法的框架中引入非支配方法,并采用高維目標優化算法NS-RVEA對綠色供應鏈伙伴選擇問題進行求解.仿真結果表明,該算法在降低計算復雜度的同時增強了種群的收斂能力.所得解集在IGD*指標、Pareto最優解平均個數和算法運行時間等多個方面均優于MOGA、NSGA-II、MOEA/D和RVEA,證明該算法在解決具有實際物流背景的多約束非線性的復雜高維目標優化問題的優越性.與以往求解綠色供應鏈伙伴選擇問題的方法相比,本文利用高維目標優化算法,在一次求解過程中盡可能給出多組互不支配的最優解,為決策者提供多種選擇方案,具有較高的實際應用價值.

表2 IGD*指標、Pareto最優解個數和運行時間統計表
Table 2 Statistical table of IGD*index,the number of Pareto optimal solutions and the running time

測試問題所用算法IGD?指標Pareto最優解平均個數算法平均運行時間/s兩目標問題(f1,f2)MOGA31.4917.69NSGA-II7.288.0511.83MOEA/D13.787.409.17RVEA9.448.337.63NS-RVEA5.778.707.76三目標問題(f1,f2,f3)MOGA149.38115.62NSGA-II60.6912.7021.27MOEA/D76.0110.1020.55RVEA65.8613.2112.16NS-RVEA15.1216.0812.47四目標問題(f1,f2,(f3,f4)MOGA533.29124.64NSGA-II75.2625.4032.70MOEA/D138.7515.3024.51RVEA91.1833.6413.36NS-RVEA37.3143.0713.51