基于改進NrGA的易腐品生產-庫存-分銷集成優化

劉巍巍 王詩雅

(沈陽工業大學機械工程學院 遼寧 沈陽 110870)

0 引 言

易腐品具有生命周期較短，受供應鏈中時間延遲而腐爛、貶值和作廢等顯著特征，比較典型的有生鮮食品和血液等[1-2]。近年來，我國易腐品分銷網絡的快速擴張加劇了冷鏈生產、存儲與運輸環節聯合調度難度，導致每年庫存損耗巨大，運力浪費嚴重，成本居高不下[3-4]。因此，如何對多周期環境下的易腐品生產-庫存-分銷集成問題進行有效調度，提高供應鏈整體運作效率，實現易腐品供應鏈整體收益的提升成為冷鏈物流行業內關注的焦點。

多周期環境下的易腐品生產-庫存-分銷聯合調度問題是具有大量離散變量的NP-hard(non-deterministic polynomial hard)問題。精確式算法對數據規模、決策變量數目有嚴格的限制，難以在較短時間內找到最優解，現有文獻鮮有研究。啟發式算法則可以在合理的時間內求解復雜系統優化問題，成為近年來研究的主流。文獻[5-7]分別提出基于進化的啟發式算法、設計改進遺傳算法和隨機模擬技術相結合的混合智能算法及采用自適應大規模鄰域搜索算法，求解多周期易腐品的生產和分銷一體化問題。吳瑤等[8]設計了基于雙子串編碼的帶精英策略的非支配排序遺傳算法，求解具有最低新鮮度限制的易腐品生產-配送協同調度雙目標優化模型。

上述啟發式算法在解決此類問題時具有較好的有效性和穩定性，但也因其隨機搜索特性會產生重復搜索，導致計算收斂速度慢，且可能陷入局部最優。無重訪遺傳算法(non-revisiting genetic algorithm，NrGA)使用空間二叉分割(binary space partitioning，BSP)將已訪問的解存儲在存檔設計中來完全消除重訪。文獻[9-10]分別提出NrGA、NrPGA求解輸電網絡規劃問題，Dolgui等[11]提出NrGA求解多級供應鏈中易腐品集成庫存策略優化問題，證明了NrGA具有參數設定區間廣泛、受網絡結構和規模變化干擾小等優勢。但傳統NrGA存在空間搜索時間過長、求解精度較低等問題。

為提升NrGA性能，本文首先采用歸一化方法重構了實數編碼規則，消除多維解空間數據規模影響，以提高算法收斂速度；其次對多維解空間同時分割，使BSP樹節點的數量等于生成解的數量，來降低空間搜索時間；最后設計基于田口方法的無重訪遺傳算法參數調整實驗，選取最大信噪比參數組合，以提高獲得解的精度。

1 多周期生產-庫存-分銷集成模型

1.1 問題描述及條件假設

本文考慮在多周期內由多工廠向多市場供應單一易腐品的二級供應鏈系統，研究其生產-庫存-分銷聯合調度優化問題，以供應鏈中包括工廠設置成本、訂單的設置成本、可變和固定的運輸成本、市場庫存持有成本和損失成本在內的總成本最小為目標。

假設工廠生產能力和市場容量不隨時間變化且市場需求已知，在每個周期的開始時都滿足；只考慮市場庫存費用；產品生產和運輸的提前期各為一期；不允許延期交貨；每天生產產品在下一個期間開始時裝運，并且在該生產期間無庫存成本；不考慮運輸、裝卸過程中產品變質而產生的費用；無車輛數量限制。

1.2 變量描述

相關符號和變量如下：Nt為周期數；Ni為工廠數量；Nk為市場數量；Mi為工廠i的生產能力；Mk為市場k的容量；Vi為工廠i的每個生產期的設置成本；Vk為市場k的每個訂單的訂單成本；dik為從工廠i至市場k的距離；Dkt為第t期市場k的需求量；Cik為從工廠i至市場k的單位運輸成本；γqt為在q時期生產的產品在t時期惡化的比例；Wf和Wh分別為滿載冷藏車和半載冷藏車額定載重量；Ff和Fh分別為租用滿載冷藏車和半載冷藏車的單輛冷藏車的固定成本；hk為市場k的單位庫存持有成本；l為單位損失成本；sl為服務水平；σkt為第t期市場k需求波動。

1.3 多周期生產-庫存-分銷模型建立

考慮庫存的可變壽命，假設導致惡化的微生物的生長速率呈指數增長，其表達式為：

f(t)=αet/β

(1)

式中：常數α和β隨產品類型和季節等環境條件而變化；常數α表示產品在批次生產結束后材料的初始腐敗率；常數β是指產品的腐敗率變為其初始值e的時間，在此之后，產品被認為不適合消費。

在q時期生產的產品在t時期惡化的比例為：

(2)

t時期庫存總成本為在q時期生產的產品在t時期惡化的損失成本與t時期庫存持有成本之和，其表達式為：

H(γqt,Okqt)=hk(1-γqt)Okqt+lγqtOkqt

(3)

本文采用Sinha等[12]采取的滿載冷藏車和半載冷藏車兩種運輸類型，其運輸成本是一個分段線性函數，表達式為：

Trc=Fi+CikXikt

(4)

式中：Fi是租用冷藏車的固定成本；Cik是單位可變成本。當0≤Xikt≤Wh時，Fi=Fh；當Wh

模型及約束條件如下：

(5)

(6)

(7)

(8)

(1-γk,q,t-1)Ok,q,t-1-Ykqt=Okqt
?k,q,t1≤q

(9)

(10)

(11)

(12)

(13)

(14)

(15)

式(6)表示工廠容量限制；式(7)表示如果市場k在第t時期沒有下訂單(即Pkt=0)，那么在該時期不向市場k發貨(即Xikt=0)；式(8)表明，在Xikt消耗Yktt單元滿足需求之后，剩余產品作為庫存；式(9)表明，在考慮到每個時期的產品惡化情況，平衡了連續各時期的庫存；式(10)表明，必須由較早生產的產品或當期生產產品來滿足需求；式(11)表明，每個市場任何時期的庫存量都不能超過其最大容量且保持安全庫存，在此模型中，提前期(LT)為兩個周期；式(12)至式(15)表示第t期從工廠i到市場k的運輸車輛數量；規定優先選用由滿載冷藏車Wf運輸，而其余產品由半載冷藏車Wh按所需數量運輸。

2 改進的無重訪遺傳算法設計

2.1 歸一化多維實數編碼

采用變量的值作為等位基因。由于本文為數據規模較大的多維優化問題，設其一般形式為：minf(X),X=(x1,x2,…,xn)，對不同特征維度首先進行歸一化，其解的每一分量可行域映射到[0，1]范圍內，使各個特征維度下對目標函數的影響權重相同，歸一化值=(變量值-下界)/(上界-下界)。然后，將這些歸一化的離散值存儲在染色體的基因中。離散區間大小稱為分辨率極限，分辨率限制越小，搜索越精細，解越好。染色體解碼需要從染色體基因中存儲的歸一化值計算出變量的實值。

2.2 多維子空間同時分割機制

BSP樹(BSP tree)存儲至少一次訪問的解及其適應度值，在交叉之后，其基于解空間的維度值來存儲解，但它將候選個體的適應度值與BSP樹中現有個體的適應度值比較判斷是否重訪，并對重訪解使用自適應變異算子獲取新解，然后在BSP樹中重復插入候選個體。

BSP樹父節點表示解空間部分，它是樹中父節點級別以下任意給定級別的子節點的不相交解空間部分的并集。因此，樹的根表示整個解空間，每個子節點表示父節點的解搜索空間的子空間。

由于本文數據規模較大，因此以兩個變量舉例演示本文改進的NrGA工作原理。令目標函數G(x,y)由x和y兩個變量組成，如本文中決策變量Okqt和Ykqt，其解搜索空間具有兩個維度，且每個維度可以具有或不具有唯一的分辨率限制。每個BSP樹節點由其存儲的解的目標函數值和它在BSP中表示的搜索空間組成。設變量的可能值為：x={1,3,5,7,9}，y={2,4,6,8,10}。最大可能的不同解的數量是5×5=25，該函數用以限制變量x、y的分辨率及上限和下限。根據計算能力的可用性和搜索的準確性，可相應地設置這些限制。

設第一次迭代生成G1={1,6}，其搜索空間是解的整個搜索空間，它被插入到存檔樹的根節點中。存儲在任意節點中的解必須位于由同一節點表示的搜索子空間中，如圖1所示。

圖1 根節點

第二次迭代生成G2={7,8}。優選左子節點優先于右子節點，G2存儲在左子節點。在沒有第二個子節點的情況下，除G1={1,6}之外，現有子節點的解空間與父節點的解空間相同，如圖2所示。

圖2 G1、G2樹結構

第三次迭代生成G3={3,6}。由于右子節點為空，因此它存儲在右子節點中，并與左子節點共享搜索空間。取兩個解中的維度值的平均值來計算每個維度的分離點，同時進行多維子空間分割，來定義兩個子節點新的子空間，且形成解的唯一解空間，使BSP樹節點的數量等于生成解的數量。如維度x，在G2和G3中維度x的平均值為5，再次優先考慮搜索子空間中包含分離點的空間維度的左側。因此，G3的維度x的搜索空間變為{1,3,5}，G2維度x的搜索空間變為{7,9}，如圖3所示。G3是右子節點，如果優先級是左子節點，則將5移至G2維度x的搜索空間。對于非整數分離點，分離點左、右維度值分配類似。

圖3 G1、G2、G3樹結構

再次迭代生成G4={7,10}。當父節點具有兩個子節點，并且需要插入新節點時，需在左子節點和右子節點之間進行比較，選擇要添加新節點的節點。首先，對所有變量進行歸一化處理。然后，計算每個維度的兩個節點的歸一化值之間的差值，并選擇具有最大差值的維度。對于所選維度，計算要插入的節點的變量的歸一化值與兩個子節點歸一化值之間的差值。新節點被添加到與其具有較小差值的子節點。G2nx=0.75，G2ny=0.75，G3nx=0.25，G3ny=0.5。Δx23=|G2nx-G3nx|=0.5,Δy23=|G2ny-G3ny|=0.25。由于Δx23>Δy23，因此選擇維度x。G4nx=0.75，Δx24=|G2nx-G4nx|=0，Δx34=|G3nx-G4nx|=0.5，由于Δx24<Δx34，因此將解G4添加到包含解G2的節點，如圖4所示。

圖4 G1、G2、G3、G4樹結構

若解已經存在BSP樹中，NrGA使用自適應變異算子將染色體隨機突變為與現有解相關聯的子空間中的另一個解，變異解的可行性標準是它必須位于所考慮的現有解的子空間內。如果子空間是單例集合或者搜索子空間已經全部被訪問(即該子空間為封閉狀態)，則回溯到該子節點的直接父節點的子空間并將其用于可行性標準，以此類推。

2.3 田口實驗設計

元啟發式算法的有效性高度依賴于適當的參數調整，以往算法參數多由文獻的參考值或實驗和誤差來設定，采用單組參數進行求解，求解精度較低。本文采取Azadeh等[13]基于田口實驗設計方法調整NrGA參數，包括種群規模、交叉率、變異率和迭代次數。田口實驗設計基于正交陣列(OA)和信噪比(S/N)。OA是一個包含基于不同水準的實驗方案的數字矩陣。S/N是衡量變化的指標，保證了實驗設計的魯棒性。“signal”表示“平均響應變量”為期望值，“noise”表示“標準偏差”為不良值。田口方法試圖在穩健性的基礎上最大程度地降低噪聲的影響，同時找到最佳的可控參數水準[14-15]。其旨在使S/N最大化，以使每個因子i在其相關水準j上的問題最小化。

(16)

式中：Zij為因子i在j水準上目標函數值；n為在所有實驗的運行中重復因子i的水準j的次數。

3 實 驗

3.1 田口實驗參數設置

本文研究某豬肉食品加工廠在4個周期內由2個子工廠向4個市場供給冷鮮豬肉的實際情況，并對數據進行簡化處理，設Vi=30 000元、Vk=10 000元、Cik=8 元/(t×km)、Wf=10 t、Wh=5 t、Ff=500元/輛、Fh=300元/輛、hk=250元/t、l=500元/t，工廠與市場的距離如表1所示，各時期的市場需求量如表2所示。

表1 工廠和市場節點間距 單位：km

表2 各周期不同市場需求量 單位：t

企業采用先進的制冷技術和設備保證冷鮮豬肉在加工、貯藏、運輸和銷售過程中始終處于0 ℃～4 ℃冷鏈控制之下，因此可忽略環境溫度隨季節因素的改變而產生的溫差浮動，即不考慮季節性因素對腐敗率和腐敗時間的影響；綜合對文獻[16-18]中在0 ℃～4 ℃冷鏈控制的環境條件下，導致冷鮮豬肉腐爛的微生物生長數量與冷藏時間的關系的研究，設α=0.03，β=0.7。

考慮本文算法的全局尋優能力和求解效率，算法參數(包括種群大小、交叉率、變異率)的取值范圍是基于文獻[5-11]的研究，并結合實際的工程經驗綜合而成的，分別為：Nind∈[50,90]，Pc∈[0.07,0.09]，Pe∈[0.006,0.010]；迭代次數的取值范圍經過測試求得，Gmax∈[100,160]。設計3水準4因子的正交陣列的標準表3。模型和改進的NrGA在MATLAB中進行編碼實現。

表3 參數調整的不同水準

3.2 結果分析

從正交陣列的標準表3中，選L9(34)，如表4所示，行表示每個實驗方案中的因子水準，列表示每個方案中可變因子的特定水準。

表4 田口實驗設計結果

使用Minitab對種群規模、交叉率、變異率及迭代次數在其不同水準下的信噪比取平均值，如圖5所示，選取最大信噪比的最佳控制參數分別為：Nind=90、Pc=0.09、Pe=0.010、Gmax=160。

圖5 田口實驗設計信噪比圖

本文對改進的NrGA在基于田口實驗設計已獲得的最佳組合參數下運行50次的求解結果，與傳統NrGA、GA、模擬退火算法(Simulated Annealing，SA)在200次實驗統計數據結果在相同模型參數設置下進行了比較，其計算結果如表5所示。

表5 模擬運行的計算結果

由表5中數據可知，本文改進的NrGA求解的最低總成本較傳統NrGA、GA、SA求解最低總成本降低了約2%～8%，證明了其求解精度更高，同時可知改進的NrGA計算速度較文中其余三種算法提升了約3倍。

3.3 不同需求情景下模型魯棒性分析

對實例的計算驗證了改進NrGA在求解確定需求情景下的易腐品成本模型具有較高的精度。而在市場需求不確定的條件下，產品的庫存、運輸等成本是根據市場需求在一定幅度內變化的。假設隨機生成需求呈正態分布，需求方差(Skt)對于所有市場和所有時期都是相同的，不考慮缺貨成本，通過改變成本參數構造9組不同需求情景算例。各項成本參數取值范圍如下：Cik∈(7,8)元/(t×km)、l∈(500，600)元/t、Ff∈(400，550)元/輛、Fh∈(250，350)元/輛。運用改進NrGA在已獲得最佳參數組合Nind=90、Pc=0.09、Pe=0.010、Gmax=160下獨立運行50次，計算平均總成本(u)與預期總成本(TC)的比率及平均總成本的標準差(δ)，結果見表6。

表6 不同Skt下的u/TC和δ計算結果

由表6中數據可知，u/TC非常接近1，期望通過增大樣本數量，使u/TC收斂到1。可觀察到(δ)對(Skt)敏感度低，證明了該模型的魯棒性。在改變庫存、運輸等成本參數時，運用改進NrGA獲得解的質量較高，驗證了基于田口實驗設計的參數選擇的合理性和改進NrGA的有效性。

4 結 語

本文針對多周期環境下的易腐品生產-庫存-分銷聯合調度問題的NP-hard性，從NrGA的編碼規則、BSP樹中解空間分割及解的存儲機制、參數選擇上進行改進。結果表明，該模型運用改進的NrGA保證了搜索的全面性和精確性，計算時間更短，求解精度更高，能夠為不同的需求情景提供接近最優的結果，有效降低了冷鏈總成本，實現了生產系統和物流系統的良好運營，可為求解易腐品生產-庫存-分銷集成優化問題提供參考。

由于田口實驗設計將方案局限在給定的算法參數各因子的各自水準中，可能無法保證獲得最優解，因此，未來的研究將進一步探尋最佳的參數組合以提高獲得最優解的概率。