李成嚴,林英麗,趙紹航
1.哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院,哈爾濱 150001
2.哈爾濱理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院,哈爾濱 150080
供應(yīng)鏈庫存的模糊機會約束規(guī)劃模型
李成嚴1,2,林英麗2,趙紹航2
1.哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院,哈爾濱 150001
2.哈爾濱理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院,哈爾濱 150080
研究了不確定環(huán)境下的供應(yīng)鏈庫存優(yōu)化問題??紤]需求為模糊量,且可能在一定條件下不滿足約束條件的決策前提,用三角模糊數(shù)表示需求,結(jié)合可能性理論中的可信性測度,建立了多品種聯(lián)合補充的模糊機會約束規(guī)劃模型,目標函數(shù)為最小化供應(yīng)鏈訂貨成本和庫存成本的期望值。用遺傳算法對優(yōu)化模型求解,以目標函數(shù)值作為染色體適應(yīng)度,給出了編碼方案及選擇、交叉、變異算子。用數(shù)值實例進行了仿真計算,證明了模型和算法的有效性和性能,并給出了不同置信水平下的計算結(jié)果。
供應(yīng)鏈管理;聯(lián)合補充問題;模糊機會約束規(guī)劃;三角模糊數(shù);遺傳算法
經(jīng)濟全球化帶來的競爭壓力使各企業(yè)不斷提高供應(yīng)鏈庫存管理水平以降低運行成本。多個供應(yīng)商之間的多品種聯(lián)合補充問題(Joint Replenishment Problem,JRP)就是在多品種庫存補充過程中確定每種產(chǎn)品的訂貨批量大小及訂貨周期,從而在滿足需求的前提下最小化單位時間內(nèi)的總成本。研究表明,聯(lián)合補充可以有效地降低供應(yīng)鏈庫存成本[1]。
針對實際供應(yīng)鏈庫存中普遍存在的不確定性,文獻[2]將具有隨機需求和資源約束的JRP問題用差分進化算法進行求解;文獻[3]運用模糊規(guī)劃求解了模糊需求下的聯(lián)合補充問題,由已知模糊集的隸屬函數(shù)求出相應(yīng)的模糊目標函數(shù)的隸屬函數(shù),將其轉(zhuǎn)化為是目標函數(shù)并求解。但是,模糊規(guī)劃模型對約束條件只是做了模糊處理,卻缺少對模糊事件發(fā)生的可能程度的度量。
模糊機會約束規(guī)劃模型用于描述模糊事件發(fā)生的可能程度。其基本思想是允許所做的決策在某種程度上不滿足約束條件,但是模糊約束條件成立的可能性不小于決策者預(yù)先給定的置信水平[4];文獻[5]又進一步提出可信性測度,具有自對偶特性,在某些方面優(yōu)于可能性測度。目前,模糊機會約束規(guī)劃已應(yīng)用于庫存控制[6-7]、產(chǎn)品組合[8]、電力[9]、金融[10]、物流[11]等工程領(lǐng)域。
遺傳算法以其擅長全局搜索,具有高度魯棒性,避免在最優(yōu)解附近徘徊等優(yōu)勢,在解決JRP的問題中得到了廣泛的應(yīng)用[12]。文獻[13]結(jié)果表明遺傳算法求解過程中效率較高。文獻[14]表明遺傳算法在尋優(yōu)能力,穩(wěn)定性和運算速度上優(yōu)于克隆選擇算法和粒子群算法。
本文采用模糊機會約束規(guī)劃來討論不確定環(huán)境下供應(yīng)鏈庫存問題。用三角模糊數(shù)表示模糊需求,針對多品種的獨立庫存優(yōu)化問題進行分析,建立模糊機會約束規(guī)劃模型,并用遺傳算法進行求解,目標是最小化庫存總成本并確定訂貨周期。
2.1 聯(lián)合補充問題的數(shù)學(xué)模型
聯(lián)合補充模型主要假設(shè)如下:
產(chǎn)品的總資源不確定;
年需求為模糊數(shù),用三角模糊數(shù)來表示;
庫存補充時間為基本補充周期的整數(shù)倍數(shù);
模型不考慮缺貨損失。
主要符號如下:
ki為每種產(chǎn)品相對于基本補充周期的倍數(shù);
si為產(chǎn)品i在每個基本補充周期的次要準備成本;
hi為單位庫存持有成本系數(shù);
bi為第i中產(chǎn)品的單價;
S為每個基本補充周期的主要準備成本;
n為聯(lián)合訂購的品種數(shù);
T為基本補充周期;
B為資金確定值。
將每種產(chǎn)品的需求看作模糊量Di,在實際決策中,Di的可能范圍為[a-d,a+d],d為一彈性因子,表示不確定的波動范圍,而[a,b]為Di的最可能范圍值。采用模糊集的思想,將這種不確定需求用三角模糊數(shù)來表示,式(1)為年需求的模糊隸屬度函數(shù):
其對應(yīng)的函數(shù)圖形為如圖1所示。
圖1 年需求模糊隸屬度函數(shù)
結(jié)合文獻[3]中的確定性聯(lián)合補充模型如公式(2)(3)所示,式(4)為模糊資源約束,表示在單位時間內(nèi)訂貨不超過資金上限,式(1)至(5)構(gòu)成了模糊需求的聯(lián)合補充問題模型,依據(jù)該模型再根據(jù)文獻[5]和文獻[15],設(shè)表示模糊需求下的庫存成本,將目標函數(shù)當成機會約束對待,模糊目標函數(shù),可推導(dǎo)出本文所需的基于可行性測度的模糊機會約束模型如下:
因此總成本可表示成:
2.2 遺傳算法求解模糊機會約束規(guī)劃模型
遺傳學(xué)是生物學(xué)的重要分支,主要研究基因進化以及其帶來的影響。遺傳算法將生物進化理論與最優(yōu)化技術(shù)和計算機技術(shù)有機結(jié)合在一起,遺傳算法以其自身優(yōu)勢在解決JRP問題中得到廣泛的應(yīng)用。因此本文采用遺傳算法對模糊機會約束規(guī)劃模型進行求解,基本補充周期長度T和產(chǎn)品相對于基本補充周期的倍數(shù)ki是需要確定的決策變量,根據(jù)文獻[12]設(shè)計如下步驟:
(1)編碼。根據(jù)有意義的最小字符集編碼規(guī)則和積木塊編碼規(guī)則,將決策變量n用整數(shù)表示,編碼的長度為n,也就是對n個周期乘子(k1,k2,…,kn)進行整數(shù)編碼,其中n為聯(lián)合補充物料的種類。對于策變量T可由公式(8)計算得出。由于在一個基本補充周期內(nèi)每種產(chǎn)品至少補充1次,所以不比計算ki的下限kiLB,其值為1;而上界k是要滿足條件(k+1),其中要求由于ki不會受交叉和變異的影響,只是在可行域內(nèi)取值,因此可以取n個隨機整數(shù)來進行編碼。
(3)生成初始群體。定義pop_size為染色體個數(shù),并隨機產(chǎn)生pop_size個初始的染色體作為初始群體。
(4)適應(yīng)值函數(shù)。適應(yīng)值函數(shù)是基于目標函數(shù)來確定并區(qū)分群體中個體好壞的標準,是選擇操作的依據(jù)。本文目標函數(shù)TC為最小化總成本,則每個染色體的適應(yīng)值函數(shù)為:
(5)選擇。采用賭輪方法選擇算子,每個個體進入下一代的概率依據(jù)適應(yīng)度值與整個種群中個體適應(yīng)度值總和的比例。個體適應(yīng)值越高,被選中的可能性則越大。
(6)交叉。交叉操作是遺傳的核心,采用由二進制編碼演變的單點交叉。其操作過程是隨機選取斷點,然后選取第二個、第一個雙親的斷點后部分作為后代的一部分,再從第一個、第二個雙親中按順序選取合法基因填充余下部分,即要保證每個[1,n]之間的自然數(shù)在染色體中只出現(xiàn)m次,這樣可避免產(chǎn)生非法個體。例如:
隨機選擇交叉位置5(由隨機數(shù)產(chǎn)生):
(7)變異。變異操作是生物進化的總要組成部分采用單點變異法。從步驟(5)、(6)所生成的交配池中,按變異概率選擇個體,隨機產(chǎn)生一個變異的基因位,對該位置的基因進行變異,新基因的范圍為1≤Gene(i)≤k。
(8)終止循環(huán)條件。以預(yù)先設(shè)定的最大進化代數(shù)Nmax作為停止循環(huán)條件。
本文用VC++實現(xiàn)所提出的模型,當需求Di為三角模糊數(shù)時,設(shè)a=Di,彈性因子d=0.1Di,各種產(chǎn)品的需求率Di最可能值為在[a-d,a+d]范圍內(nèi)。采用文獻[3]中數(shù)值實例,如表1所示,設(shè)某企業(yè)對六種產(chǎn)品進行聯(lián)合補充,其中主要成本S=$200,每個補充周期可用資金上限B=$25 000,目標為確定決策變量并使總成本值最小。
表1 實例數(shù)據(jù)
遺傳算法的參數(shù)設(shè)置為:種群大小為POPSIZE=30,變異概率為Pm=0.2,交叉概率為Pc=0.3,迭代次數(shù)為100次。當置信水平α=0.9,β=0.9時,得到的結(jié)果如表2所示。
表2 計算結(jié)果
求解過程中,達到最好解的平均迭代次數(shù)為8,算法的效率是比較高的。表2中的結(jié)果表示基本補充周期的長度為0.168 4,對應(yīng)的產(chǎn)品1~6的補充周期分別為基本補充周期的1,1,1,2,2,4倍,最優(yōu)總成本為$4 341.845 0,大于文獻[3]實驗結(jié)果的最優(yōu)總成本$4 331.003 1,這是由于不確定因素越來越多導(dǎo)致的。為了得到更多數(shù)據(jù),當α在[0.5,0.9]區(qū)間取值,β=0.9時,得到的結(jié)果如表3所示。
表3 不同置信水平計算結(jié)果比較
由表3的結(jié)果可知,置信水平α在[0.5,0.9]區(qū)間的值越大,聯(lián)合補充庫存成本越高,證明了算法的有效性。
本文主要針對聯(lián)合補充問題中每種產(chǎn)品需求率進行研究,結(jié)合實際應(yīng)用,利用模糊機會約束規(guī)劃的思想,用模糊變量表示每種產(chǎn)品的需求率,建立了聯(lián)合補充問題的模糊機會約束規(guī)劃模型,利用遺傳算法對模型進行求解,并采用數(shù)值實例證明了模型和算法的有效性。實現(xiàn)了企業(yè)決策者可以通過主觀經(jīng)驗判斷而非客觀概率來確定模糊需求的聯(lián)合補充問題,本文資源約束的可信性以及對目標函數(shù)機會約束處理后的可信性達到?jīng)Q策者設(shè)定值時,得到的補充周期和庫存總成本,即為基于模糊機會約束規(guī)劃模型的聯(lián)合補充問題。所得結(jié)果可以為實際應(yīng)用提供依據(jù)。
[1]Moon I K,Cha B C.The joint replenishment and freight consolidation of a warehouse in a supply chain[J].Production Econom ics,2011,133(1):344-350.
[2]王林,陳璨,曾宇容.資源約束情況下隨機性聯(lián)合采購模型的差分進化算法[J].計算機集成制造系統(tǒng),2011,17(7):1541-1546.
[3]包美玲,李成嚴.模糊需求的聯(lián)合補充問題研究[J].計算機應(yīng)與軟件,2010,27(9):91-93.
[4]Xu J,Yao L,Zhao X.A multi-objective chance-constrained network optimal model with random fuzzy coefficients and its application to logistics distribution center location problem[J].Fuzzy optimization Decision Making,2011,10(1):255-285.
[5]Liu B,Liu Y K.Expected value of fuzzy variable and fuzzy expected value models[J].IEEE Transactions on Fuzzy Systems,2002,10(4):445-450.
[6]Chien C L.A fuzzy integrated vendor-buyer inventory policy of deteriorating items under credibility measure[C]// IEEE IEEM,2010:1666-1670.
[7]吳杰康,唐力.基于模糊機會約束規(guī)劃的水火電力系統(tǒng)多目標隨機調(diào)度模型[J].中國電機工程學(xué)報,2011,31(25):26-34.
[8]張會娟,張強.基于模糊機會約束規(guī)劃的最優(yōu)產(chǎn)量決策[J].運籌與管理,2009,18(6):89-96.
[9]Zhang Y M,Huang G H,Lin Q G.Integer fuzzy credibility constrained programming for power system management[J].Energy,2012,38(1):398-405.
[10]Li X,Shou B,Qin Z.An expected regret m inim ization portfolio selection model[J].Europe Journal Operation Research,2012,218(2):484-492.
[11]Pishvaee M S,Torabi S A,Razm i J.Credibility-based fuzzy mathematical programming model for green logistics design under uncertainty[J].Computer Industrial Engineering,2012,62(2):624-632.
[12]Liu B,Iwamura K.Chance constrained programming with fuzzy parameters[J].Fuzzy Sets and System,1998,94(2):227-237.
[13]李成嚴,徐曉飛,戰(zhàn)德臣.模糊資源約束的聯(lián)合補充問題[J].計算機集成與制造系統(tǒng),2008,13(2):113-117.
[14]稅文兵,葉懷珍,張詩波.物流配送中心動態(tài)選址模型及算法研究[J].計算機應(yīng)用研究,2010,27(12):4476-4479.
[15]劉寶碇,趙瑞清,王綱.不確定規(guī)劃與應(yīng)用[M].北京:清華大學(xué)出版社,2008.
LI Chengyan1,2,LIN Yingli2,ZHAO Shaohang2
1.School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China
2.School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China
Abstract:Supply chain inventory optimization problem under uncertain environment is concerned. Fuzzy chance constrained programming model for multi-item joint replenishment is thus proposed, which can take into account fuzzy demand quantity, as well as the constrained conditions are not satisfied to a certain degree. Demand quantity is a triangular fuzzy number, combined with the possibility of credibility measure theory. The objective function is to minimize the expected discounted cost of ordering and inventories in the supply chain. Genetic Algorithm(GA)is used to solve the obtained optimalityconditions equations, and the fitness function value of the chromosome is the objective value of fuzzy chance constrained programming model. Chromosome coding, selection, crossover and mutation operations are also studied. The feasibility of the model and the effectiveness of the algorithm are illustrated by simulation numerical examples. Some results under different probability level are presented and discussed.
supply chain management; joint replenishment problem; fuzzy chance constrained programming; triangular fuzzy number; genetic algorithm
LI Chengyan, LIN Yingli, ZHAO Shaohang. Fuzzy chance constrained programming model for supply chain inventory.Computer Engineering and Applications, 2014, 50(17):241-244.
A
TP399
10.3778/j.issn.1002-8331.1311-0468
哈爾濱市攻關(guān)項目(No.2011AA 1CG063);黑龍江省教育廳資助項目(No.12541142)。
李成嚴(1972—),男,在讀博士,教授,研究領(lǐng)域為企業(yè)智能計算;林英麗(1989—),女,碩士研究生;趙紹航(1989—),男,碩士研究生。E-mail:linyinglide@163.com
2013-12-02
2014-03-13
1002-8331(2014)17-0241-04