基于遺傳算法的多源多周期采購決策優化

楊 倩， 胡燕海

(寧波大學 機械工程與力學學院, 浙江 寧波 315211)

訂單分配決策作為多源采購決策的核心議題，直接影響企業的生產成本。如何將訂單數量在供應商之間進行科學地分配，是企業采購過程中的重要決策。

國內關于多源采購決策的相關研究較多。劉鈺琛等[1]研究了單分銷商向多供應商的訂貨批次及批量問題；潘偉[2]在供應中斷風險下對選擇單源或雙源采購進行了研究；戴卓[3]討論了需求量和距離對供應鏈總成本的影響；龍菲[4]構建了供應中斷風險下，總成本及服務水平的雙目標模型；郝娟[5]研究了在缺貨情況下，供應鏈的生產-分銷協同優化問題；徐艷飛[6]闡述了在價格折扣、不確定需求、多供應商及多產品等約束下的最優訂單分配模型。

國外Meena等[7]將價格折扣、供應中斷考慮進多源采購問題。Christoph等[8]研究了隨機需求下的多源采購問題。

但是目前的研究大多討論單周期的采購問題，較少考慮多種原材料，有的只考慮到整個供應鏈的采購是多供應商，從單個制造商的角度而言只選擇最優的某個供應商，還是屬于單源采購[3]5。課題組在確保每個制造商的每種原材料至少由2個供應商供貨以降低風險的前提下，引入價格折扣及訂貨量約束，建立多源采購模型，設計合適的遺傳算法，通過算例驗證該算法優于啟發式算法，適合解決此類問題。

1 問題描述及數學模型

1.1 問題描述

如圖1 所示，該多源供應鏈的多個制造商生產同一種產品，生產該產品所需的每種原材料有多個供應商供貨，且各供應商給出的價格折扣不同。每個制造商在每個周期中所需的每種原材料都必須在多個供應商中選擇2個或2個以上供應商。多源采購供應鏈優化旨在從整體的角度協同優化多個制造商的訂單分配，以取得制造商總成本最低的目的。

1.2 模型的假設條件

模型的假設條件：

1) 本模型涉及多周期、多種原材料。

2) 各制造商每周期所需的產品數量已知。

3) 各個周期、每個制造商的每一種原材料都必須從2個或2個以上供應商處采購，各供應商可向多個制造商供貨。

4) 供應商到制造商的距離及單位運費是確定的。

5) 各供應商有最低采購量和生產能力約束。

6) 若某一周期某制造商的采購量大于需求量，則產生庫存費用; 反之,則產生缺貨費用。

7) 各周期各制造商都按一定比例采購各種原材料。

8) 各供應商給出的價格折扣已知。

1.3 參數設置

本模型中，參數定義如表1所示，決策變量定義如表2所示。

表1 模型參數定義

表2 決策變量定義

1.4 模型建立

目標函數：

(1)

其中，

st.:

(2)

(3)

Lmn≤xmnitymnit≤Dmn,?n,mn,i,t;

(4)

(5)

(6)

(7)

ymnit∈{0,1},?n,mn,i,t;

(8)

xmnit,xitE,xitF為非負整數，?n,mn,i,t。

(9)

目標函數式(1)的第1項表示N種原材料的購買成本及運輸成本，第2項表示制造商過度購買引起的庫存成本和未滿足需求引起的缺貨成本。式(2)表示各周期各制造商采購的各種原材料要保持適當的比例。式(3)表示各周期各制造商的產品量與缺貨、庫存之間的平衡關系。式(4)是各供應商采購量的取值范圍限制。式(5)表示各周期各制造商的每種原材料不能只選擇一個供應商。式(6)是不同原材料每個供應商的生產能力限制。式(7)表示每個制造商各周期生產產品總量等于各周期產品需求總量。式(8)表示各供應商有被選擇和不被選擇兩種情況。式(9)表示各變量都為非負整數。

2 遺傳算法

2.1 遺傳算法描述

遺傳算法是借鑒遺傳學原理的優化算法，被廣泛用于求解運輸問題、供應鏈網絡問題以及選址分配問題等。

遺傳算法的基本步驟如下：

1) 選擇染色體的編碼和解碼策略；

2) 確定適應度函數；

3) 生成初始種群；

4) 按照適應度大小進行選擇操作；

5) 按照一定的概率進行交叉和變異操作；

6) 若滿足終止條件，則以適應度最大個體作為最優解輸出，終止迭代；否則返回步驟4)。

2.2 編碼設計

本模型采用雙層編碼，第1層ymnit采用0～1編碼，供應商未被選擇時為0，供應商被選擇時為1。第2層xmnit采用整數編碼，每個整數代表制造商向供應商的采購量。該編碼方式含義明確，并且不需要解碼，提高了傳輸速率。

根據本研究中供應鏈結構的特點，設計的染色體X，Y都由N個子染色體構成，即X=[X1X2…XN]，Y=[Y1Y2…YN]，N為原材料個數，X的每個子染色體分別代表其對應原材料的各供應商的采購量，Y的每個子染色體分別代表其對應原材料的各供應商被選擇情況。

以子染色體n為例，Xn為(Mn*T)×I的矩陣，其表示I個制造商在T個周期內分別向原材料n的Mn個供應商的采購量。

2.3 適應度函數

本模型需要獲得制造商總成本最小時的采購方案，所以直接選取目標函數作為適應度函數，評價解的優劣。

2.4 生成初始種群

根據約束，隨機產生具有確定規模的可行解作為初始種群。

2.5 遺傳策略

1) 交叉

設置種群的交叉概率為Pc。隨機選取2條染色體，當滿足交叉條件時，隨機產生2個交叉點t1,t2∈[1,T],將染色體1的t1周期數據與染色體2的t2周期數據進行交換。

2) 變異

設置種群的變異概率為Pm。隨機選取一條染色體，當滿足變異條件時，隨機產生2個變異點t1,t2∈[1,T],將染色體t1,t2周期的數據進行交換。

3) 修復

染色體經過交叉和突變后，將存在染色體所有周期的總采購量不等于總需求量的情況，即不滿足約束(7)，所以需要修復這些非法染色體。以采購總量小于需求總量為例，修復步驟為：根據當前采購量計算原材料1的各供應商提供的單價，按價格由低到高依次增加采購量，同時調整同周期其他原材料的采購量，使染色體滿足原材料比例約束，調整方式也是根據該周期內供應商單價由低到高增加采購量。

3 啟發式算法

每個周期制造商按照各供應商的生產能力將訂單按比例分配給每個供應商[9-10]，因此不存在缺貨和庫存。以原材料1為例，第t周期制造商i向原材料n的mn供應商的采購量

(10)

4 算例分析

4.1 符號賦值

本研究中的模型考慮以下情況：4個周期，3個制造商，2種原料，每種原料有3個供應商。原料1的單位運輸費用Vm1=0.02元/km，原料2的單位運輸費用Vm2=0.01元/km，缺貨成本為20元/件，庫存成本為5元/件。原料1的基礎價格Cm1=200元/件，xmnit原料2的基礎價格Cm2=100元/件，供應商的產能和價格折扣如表3所示。供應商到制造商的距離如表4所示。制造商4個周期的需求如表5所示。其他相關數:θ1=1,θ2=1。

表3 供應商的產能與價格折扣

表4 供應商與制造商的距離

表5 制造商各周期需求量

4.2 算例結果

課題組以MATLAB 8.3為平臺進行編程及仿真求解，算法各參數設置如下：種群大小N=2 000，最大遺傳代數Gen=2 000，交叉概率Pc=0.6,變異概率Pm=0.05。遺傳算法得到的最優解是11 482 340，2種原材料相應的訂單分配方式分別如表6和7所示。采用啟發式算法獲得的最優解為12 702 711，遺傳算法比啟發式算法求解的期望成本降低9.61%。

表6 制造商向原材料1供應商的采購量

表7 制造商向原材料2供應商的采購量

5 結語

課題組為研究降低制造商的總成本，在多供應商多制造商的采購問題中，引入價格折扣和采購量約束，綜合考慮各項成本，建立了帶有多個約束的非線性規劃模型，利用MATLAB軟件設計遺傳算法，仿真求解，確定每個制造商在各周期向每個供應商的采購量，與啟發式算法求解結果相比制造商成本大大降低，說明該算法可以協同優化多制造商對多供應商的訂單分配問題。