基于NSGA-II的應急生產任務多目標優化模型及算法研究

鞏玲君， 張紀海

(1.北京理工大學 管理與經濟學院,北京 100081； 2.海南大學 管理學院，海南 海口 570228)

0 引言

近年來，我國災害頻發，給人民的生命財產帶來了巨大的損失。為保障救災的順利進行，需要保證災后的應急物資供應。現如今，災后應急物資供應的手段有調用儲備、應急生產、社會捐贈、應急采購、國際援助等。其中調用儲備、社會捐贈、應急采購和國際援助可以看作是主要調集存量物資。所以，不少的研究重點關注了應急物資配送問題[1～7]。例如，針對多種應急資源的調度問題，汪勇等[1]構建了一個時間和成本的多目標調度模型，并設計了進化規劃算法進行求解。王旭坪等[2]則從公眾心理風險感知程度和應急物資未滿足程度的角度，構建了混合整數規劃模型，并設計了多層搜索求解算法。Zhan等[4]針對應急物流中的多供應商、多受災點、多應急物資和多車輛的應急配送問題，提出了基于災害情景信息更新的多目標優化模型。Alem等[7]構建了新的兩階段隨機網絡流量模型，并將采購、車輛、提前期以及預算分配等特征納入模型。

學者們在應急物資配送方面的研究取得了豐碩的成果。然而，若將所有存量物資調集完畢仍不能保障受災點的需求，決策者就需要考慮采用應急生產的方式來保障應急物資供應。例如，汶川特大地震后，為滿足受災點群眾生活需求，需要緊急生產69.32萬套活動板房[8]。當時采用的是援建省市對口承包建設的組織生產方式。雖然最終順利完成了活動板房的應急生產任務，但是實施過程中也暴露出很多問題。比如有些省市不具備活動板房的生產能力或者雖然具備生產能力但是距離地震受災點較遠，為克服運距長、運費高、板材耗損等問題，所以只能采用異地生產方式，選派工作人員，去其他省市落實生產企業，這樣使得協調生產變得困難，同時也很難做到資源利用的最優化。

因此，很多研究也重點關注了利用生產能力儲備來解決應急生產的問題。Whybark[9]指出要考慮庫存儲備與應急生產能力儲備的均衡，生產能力儲備可以有效的降低庫存水平。張自立等研究了利用生產能力儲備的協議企業選擇問題[10]和應急經費在政企之間的劃分問題[11]。陳濤等[12]關注了協議企業生產能力儲備和實物儲備的協調性問題。陳業華等[13]為達到供應鏈協調，研究了政企共同儲備應急物資生產能力的問題。羅靜等[14]基于演化博弈理論探討了政企聯合實施應急物資生產能力儲備的方式。張琳等[15]研究了物資企業在常規生產和加急生產情況時的政府最優支付決策和物資企業雙儲備決策。除了以上對應急物資生產能力儲備的研究之外，Chakravarty[16]關注了不確定條件下人道救援供應鏈的快速響應問題，確定災后應急物資的供應量及供應時間；Sheu等[17]通過雙層遞歸函數，建立物資供應隨機動態規劃模型；Wang等[18]為解決應急物資供應短缺和采購價格高的問題，用期權契約來協調應急供應鏈，實現了Pareto改進。王茵等[19]從物資供應的時間和供應偏差的影響度出發，研究了多周期的應急物資供應問題。

以上對應急生產的研究可能仍無法保障災后應急物資的供應。這主要是因為：第一，儲備和協議企業生產或轉產的產量總和可能無法滿足重大突發事件后的物資需求；第二，激增的應急物資需求，打破了市場平衡，可能會出現原材料供不應求的情況。還是以汶川特大地震時活動板房的應急生產為例，當時短時間內需要生產1386.4萬平方米活動板房，使得活動板房所需原材料彩鋼板和聚苯乙烯市場供應緊張，政府不得不采取措施來保障活動板房原材料的生產和供應。鑒于以上分析，本文以應急物資需求激增的重大突發事件為研究背景，考慮必須通過應急生產才能滿足需求激增的情況，重點關注原材料生產能力變化對完成應急生產任務的影響，研究應急物資的最優生產和原材料保障問題，確保應急物資高效、低廉地生產并運送到受災點。

1 模型構建

突發事件發生后，調用應急儲備是應急物資籌集的首選方式，物資緊缺時，也可以采用直接征用、市場采購、組織捐贈等籌集方法加以補充。但重大突發事件(特別是重大自然災害)發生后，由于受災面積大，受災人口多，僅靠以上方式籌集到的應急物資仍然不能滿足應急需求，如汶川大地震發生后，帳篷和活動板房的需求激增，需要緊急動員相關廠家進行應急生產。要想順利完成應急生產任務，應選擇應急物資生產能力強、距離受災點較近的制造商，如果制造商的原材料儲備不足，還需要為制造商選擇原材料供應能力強、距離制造商較近的供應商。本文所要解決的是，在考慮上述條件的情況下，構建數學模型，給出完成任務時間最短、成本最低的應急生產方案和應急物資原材料供應方案。由于應急狀況下的生產情況錯綜復雜，本文提出了一系列如下的假設：

(1)應急物資生產的總任務量已通過突發事件的規模、受災人口等情況預測出；

(2)應急物資制造商(以下簡稱“制造商”)的生產成本已知；

(3)應急物資原材料供應商(以下簡稱“供應商”)的生產成本已知；

(4)各供應商向各制造商運送原材料的時間和單位運輸成本已知；

(5)各制造商向受災點運送應急物資的時間和單位運輸成本已知；

(6)供應商的單位時間生產能力已知;

(7)制造商的單位時間生產能力已知；

(8)制造商生產應急物資只需要一種原材料，或者雖然需要多種原材料，但除一種原材料以外，其他原材料都很容易獲得；

(9)各供應商在生產完所有原材料之后再統一向各制造商運輸；

(10)各制造商沒有庫存，所需的原材料全部由供應商提供，并且各制造商是在所需原材料都運送到之后再開始生產。

模型的基本參數描述如下：D：需求地(受災地)；Q：應急物資的生產任務總量；Si(i=1,2,…,s)：供應商；Mj(j=1,2,…,m)：制造商；mcj(j=1,2,…,m)：制造商Mj單位生產成本；mpcj(j=1,2,…,m)：制造商Mj的單位時間生產能力；sci(i=1,2,…,s)：供應商Si單位生產成本；spci(i=1,2,…,s)：供應商Si單位時間生產能力；tcij(i=1,2,…,s;j=1,2,…,m)：從Si到Mj的單位運輸成本；tij((i=1,2,…,s;j=1,2,…,m)：從Si到Mj運輸時間；tcjD(j=1,2,…,m)：從Mj到D的單位運輸成本；tjD(j=1,2,…,m)：從Mj到D的運輸時間；rmj(j=1,2,…,m)：Mj生產單位物資所需的原材料數量；

模型的決策變量描述如下：qij(i=1,2,…,s;j=1,2,…,m)：Si向Mj提供的原材料數量；qjD(j=1,2,…,m)：Mj向D提供的應急物資數量。

本文以完成應急生產任務所需的時間最短和成本最低為目標，考慮應急生產過程中的原材料保障約束，建立重大突發事件應急生產任務多目標規劃模型:

(1)

(2)

模型中，公式(1)表示完成應急物資生產任務的時間最小，包括四個方面，即原材料的生產時間、原材料從供應商運送到制造商的時間、應急物資的生產時間和應急物資從制造商運送到受災點的時間；公式(2)表示完成應急物資生產和運輸任務的成本最小，也包含四個方面，即應急物資原材料的生產成本、從供應商到制造商的運輸成本、制造商的生產成本以及從制造商運送到受災點的運輸成本。約束(3)表示所有供應商向第j個制造商提供的原材料數量應該等于該制造商生產應急物資所需的原材料數量；約束(4)表示所有制造商的應急物資生產數量應該等于應急生產的總任務數量；約束(5)表示決策變量的非負屬性。

2 求解算法

該模型是一個針對時間和成本的多目標規劃模型，直接求解非常困難。文獻[20]針對后勤資源運輸的特殊性，即需要考慮在運輸時間最短的情況下使總運輸成本最低，將涉及時間與成本的多目標規劃模型轉化為單目標規劃模型，然后再運用單目標規劃的求解方法進行求解。本文所構建的模型，針對的也是緊急狀態下的應急物資供應。不過由于應急物資屬性不同，對受災點的作用也不同，因此各類應急物資需要到達受災點的時間也各不相同，所以，我們不能單純地考慮在時間最短的情況下總成本最小，而應該由決策者根據受災點的情況，綜合時間和成本因素做出決定。然而，對于同一個問題，由于決策者偏好不同，可能會做出不同的決策。因此，對于本文的多目標優化問題，我們重在求解Pareto最優解集，為決策者的抉擇提供支撐。

2.1 算法設計

近年來，為求解多目標的優化問題，學者們運用了多種多目標進化算法[21,22]，以便得到Pareto最優解集。相比以上優化算法，Srinivas和Deb于上世紀90年代提出了基于Pareto最優的非支配遺傳算法(NSGA)，廣泛應用于多目標優化領域。但是由于其缺乏精英策略，計算復雜度比較高以及需要人為確定共享參數等缺點，Deb等又在NSGA算法的基礎上進行了針對性的改進，提出了帶精英策略的非支配遺傳算法(NSGA-II)；NSGA-II的針對性改進主要有引入了精英策略，提出了基于分級的快速非支配排序方法以及擁擠度和擁擠度比較算子，增加了采樣空間，降低了算法的復雜度，而且無需再人為制定共享參數[23]。由于NSGA-II具有的眾多優勢，本文借助其求解模型，具體流程如見圖1。

圖1 NSGA-II算法流程圖

步驟1參數初始化及染色體編碼

假定NSGA-II的種群規模為N，交叉和變異率分別為Pc和Pm，最大迭代次數MG。

根據上述模型的特點，給決策變量編碼，令兩個子串組成一條染色體。其中，子串1為實數編碼，長度為m，子串1表示各制造商的應急物資生產任務，即子串1中的第j個基因表示第j個制造商的應急物資生產數量；子串2為實數編碼，長度為m×s，子串2代表各供應商的原材料供應情況，即子串2中的第s×(i-1)+j表示第i個供應商向第j個制造商提供的原材料數量。染色體的總長度為m×(s+1)。

步驟2種群初始化和適應度計算

參考上述編碼規則，用下列方法生成初始種群，規模為N。

當子串1的初始化完成之后，再實施子串2的初始化。鑒于子串1的初始化已經完成，也即各制造商的生產任務已經確定，根據約束條件(3)，也可以確定各制造商所需要的原材料數量。因此，所有供應商向各制造商提供的原材料總數為一個定值。所以，在進行子串2的初始化時，可以將子串2分為m個分串，則各分串的基因和就等于各制造商所需要的原材料數量，因此也是個定值。最后，我們再依據以上子串1的生成方式初始化各個分串。根據以上方法，最終生成初始種群。此外，需要注意的是，在處理一些實際問題時，有些原材料或者應急物資的數量是以整數的形式存在，所以在初始種群的生成時，對這寫基因要隨機生成整數。

在進行適應度計算之前，應該先確定適應度函數。本文中，由于目標函數都是求最小值的函數，因此，可以將目標函數作為適應度函數。基于染色體所代表的應急物資生產及原材料保障方案，根據重大突發事件應急生產任務多目標規劃模型，計算每個個體的目標函數值Z1和Z2，再據此對種群中的所有染色體進行快速非支配解排序，得到Pareto前沿。

步驟3遺傳操作

(1)精英選擇策略

按照NSGA-II的機理，運用錦標賽方法，利用排序結果以及擁擠度的大小，對染色體進行選擇操作。在選出子代種群后，將父代種群與子代種群進行合并，按照快速非支配排序和擁擠度計算，再選擇出N個個體成為新一代的子代種群。

(2)交叉及變異操作

在此，還應注意，由于約束條件的存在，在交叉、變異操作結束前，還需要對約束條件的滿足與否進行檢驗，若不滿足，還需要做相關調整。

步驟4終止條件

當迭代代數達到MC時，則終止迭代，然后將結果輸出。

2.2 算法復雜度分析

NSGA-II的復雜度與染色體編碼的復雜程度相關，文中所用的是兩參數級聯編碼形式：子串1的長度為m，子串2長度為m×s，則一條染色體需要占據的內存為m×(s+1)。若參數出現變化，比如供應商數量增加了u個，那么染色體長度增加到m×(s+u+1)。從需要內存的角度來比較，內存增量為o(mu)，即隨著參數規模的擴大，內存占用量呈線性擴張。

本文NSGA-II中，種群規模為N，迭代次數為MG，問題規模為q=m+s+1(制造商數量+供應商數量+受災點數量)。分析NSGA-II算法的時間復雜度計算如下：初始種群生成后，每次迭代都需要適應度計算、交叉與變異操作。本文NSGA-II時間復雜度為

o(N,MG,m,s,1)=No(m(s+1))+o(Nms)+

o(N1gQ)+o(N1gQ)

≈No(m(s+1))+No(ms)

≈2No(m(s+1))

可見，NSGA-II算法的計算量與研究問題的規模的制造商數量和供應商數量成正比。

3 算例分析

情景假定：在我國某地區發生重大突發事件，對某類應急物資的需求激增，該應急物資需要一種主要的原材料，應急指揮部根據對此項應急物資的需求估計，除去已經調用的應急物資儲備，還需要緊急生產和運輸25000件產品。應急指揮部將此項應急生產任務下達給發展改革委，由其負責組織應急物資的生產。發展改革委根據應急物資生產潛力數據庫中的數據，篩選出5個應急物資原材料供應商S1、S2、S3、S4和S5，3個應急物資制造商M1、M2和M3。它們的相關信息如下表1、表2和表3所示。據此，求出此類應急物資生產和原材料保障的最優方案，具體內容有：完成應急物資動員生產任務的最短時間和最小成本；承擔應急物資動員生產任務的制造商及其具體任務數量；承擔原材料供應任務的供應商及其向各制造商提供的原材料數量。

表1 供應商單位運輸價格和單位生產成本表

表2 供應商運輸時間和單位時間生產能力表

表3 應急物資制造商相關參數表

在仿真計算過程中，對算法的相關參數進行設置：初始種群規模N=200，交叉概率Pc=0.7，變異概率Pm=0.05，最大迭代次數MG=500。采用MATLAB R2015b編程實現NSGA-II，在Intel(R) Core(TM)2 Duo 3.00GHz CPU 和4GB內存的計算機上運行。根據算例所設置的數值精度，對災后應急生產模型進行求解，運行程序得到Pareto最優解集，如圖2中“常規狀態下的Pareto最優前沿”所示。表4列出了Pareto最優前沿上幾個具有代表性的點對應的應急物資生產模型的解，包供應商向制造商提供的原材料數量，以及制造商向受災點提供的應急物資數量。

由圖2“常規狀態下的Pareto最優前沿”可以看出，該算法具有良好的收斂性，能夠得到較好的Pareto前沿。從圖2和表4可以看出，隨著應急物資生產任務所需總時間的增加，完成生產任務的總成本也在降低。在實際的應急處置過程中，由于救援的弱經濟性，政府會盡一切努力進行救援。所以，若給定某個時間閾值，在Pareto最優前沿上便可以找到優于時間的所有可行解。如圖2中“常規狀態下的Pareto最優前沿”所示，當給定閾值T=60時，其可行解范圍是坐標軸中完成任務總時間小于60天所對應的Pareto片段。

表4 Pareto最優前沿上部分點對應的解

圖2 兩種情況下的Pareto最優前沿

本文的核心創新之處在于關注應急物資原材料生產能力變化對完成應急生產任務完成應急生產任務的影響，研究滿足應急物資超常規需求的應急生產策略。因此，為了詳細說明原材料生產能力變化對完成應急生產任務的影響，下面利用上述算例進行參數分析。

假設其他條件不變，各應急物資原材料供應商的單位時間生產能力提升50%，據此，求解應急物資的最優生產和原材料保障方案。同樣運用NSGA-II算法，利用MATLAB編程，得出Pareto最優解集如圖2中“供應商生產能力提升的Pareto最優前沿”所示。

比較圖2兩種狀態下的Pareto最優前沿，可以看出，在“供應商生產能力提升的Pareto最優前沿”中，完成任務的最短時間可以縮短到43天，但是對于“常規狀態下的Pareto最優前沿”，完成任務的最短時間為50天。由此可以看出，如果決策者將完成時間的閾值設定在50天以內，按照原有的應急物資生產和原材料供應能力，無論采取“常規狀態下的Pareto最優前沿”的哪種方案都無法完成應急生產任務。所以，決策者在關注制造商的生產過程時，不能忽視應急物資原材料的生產能力變化對完成應急生產任務的影響。

此外，從算例分析還可以看出，要想在應急處置階段真正按照模型中Pareto最優前沿的方案進行完成應急生產任務，還應該注意兩個方面的問題：一方面，平時需要關注重點應急物資供應鏈的潛力調查和數據更新工作，特別是針對規模以上的制造商和原材料供應商，因為只有平時做好了數據調查工作，急時才可能迅速從數據庫中篩選出符合要求的企業；第二，由于原材料供應商、制造商以及電力、交通等各方面的配套保障分屬不同的主體控制，所以，在急時需要政府相關部門加強協調溝通，使資源能夠順暢流通，保障應急生產的順利進行。

4 結論

重大突發事件(特別是重大災害)發生后，受災點對應急物資的需求激增，通過調用儲備來保障受災點需求是決策者的首選，但是當所有存量的應急物資調集完畢都難以保障受災點供應時，決策者就需要通過應急生產來保障受災點應急物資的供應。因此，如何快速有效地完成應急生產任務是需要解決的重要課題。基于此，本文研究了重大突發事件發生后應急生產任務多目標規劃問題，關注原材料生產能力變化對應急生產任務完成的影響，以應急生產任務完成時間最短、完成成本最低為決策目標，研究了包含多個供應商、多個制造商以及單個受災點的應急物資生產任務多目標規劃模型。針對NSGA-II在求解多目標規劃時的眾多優勢，本文運用NSGA-II進行模型求解，并在MATLAB軟件中進行算例仿真。結果表明，NSGA-II可以得到較好的Pareto前沿，并且可以根據不同情況給出最優的應急物資生產和原材料保障方案。本文的研究還表明，由于應急生產與企業平時的生產活動不同，在時間緊、任務重的情況下，要想更快完成應急生產任務，需要做好原材料、資金、電力、交通等各種要素的配套保障工作。

不過，本文僅考慮了一種原材料的保障對應急物資生產能力的影響，需要注意的是，應急物資的生產可能會受到多種原材料供給的影響，還有本文只考慮了對一個受災點的應急物資保障問題，然而，重大突發事件發生后，可能需要同時滿足多個受災點的應急物資需求，因此下一步將從以上幾個方面來繼續開展研究。