考慮數(shù)量折扣的多中心倉(cāng)庫(kù)聯(lián)合采購(gòu)-配送集成優(yōu)化研究

王思睿 王 林 王志剛 曾宇容

(1.華中科技大學(xué) 管理學(xué)院, 湖北 武漢 430074; 2.湖北經(jīng)濟(jì)學(xué)院, 湖北 武漢 430205)

0 引言

聯(lián)合采購(gòu)問(wèn)題(Joint Replenishment Problem, JRP)是指多個(gè)零售商通過(guò)一個(gè)中心供應(yīng)商對(duì)多種商品進(jìn)行分組集體采購(gòu),從而分擔(dān)主要訂貨成本,節(jié)約采購(gòu)總成本。在過(guò)去的幾十年中,JRP的學(xué)術(shù)價(jià)值和實(shí)用性得到了廣泛的認(rèn)同[1-2]。在企業(yè)采購(gòu)管理實(shí)踐中,當(dāng)一組物品都是由同一供應(yīng)商或供應(yīng)地供應(yīng),或一組物品同時(shí)采用一種運(yùn)輸工具運(yùn)輸時(shí),特別適用于聯(lián)合采購(gòu)策略。例如,對(duì)我國(guó)大型電站的一些專用成套設(shè)備(如核電核能反應(yīng)堆、大型水電站關(guān)鍵設(shè)備)而言,所用備件往往為不常用備件,由于技術(shù)的制約,經(jīng)常面向國(guó)際環(huán)境進(jìn)行采購(gòu)。而且設(shè)備的制造商往往就是備件的供應(yīng)商,非常適用于聯(lián)合采購(gòu)策略。課題組在大亞灣和嶺澳核電站進(jìn)行的一項(xiàng)備件聯(lián)合采購(gòu)優(yōu)化的前期結(jié)果表明,該策略可降低8%~12%的成本[2]。而在公共采購(gòu)領(lǐng)域,聯(lián)合采購(gòu)策略也十分流行。例如,2017年中國(guó)殘聯(lián)的數(shù)據(jù)顯示,從2011年到2016年政府通過(guò)聯(lián)合采購(gòu)策略,大幅降低了物資采購(gòu)價(jià)格,僅相當(dāng)于市場(chǎng)價(jià)格的30%左右;2018年到2020年,國(guó)家醫(yī)保局主持了跨區(qū)域、跨省份的藥品聯(lián)合帶量采購(gòu)聯(lián)盟,藥品價(jià)格平均降幅達(dá)到52%。在學(xué)術(shù)上,不少學(xué)者對(duì)經(jīng)典JRP進(jìn)行了擴(kuò)展,一類擴(kuò)展是放松經(jīng)典JRP的假設(shè)或者調(diào)整約束,如:Moon等[3-4]討論了供應(yīng)商提供數(shù)量折扣的JRP和存在資源約束的JRP,Wang等[5]討論了模糊參數(shù)的JRP、Boctor等[6]討論了動(dòng)態(tài)需求下的JRP,Chen等[7]討論了運(yùn)輸車輛與運(yùn)輸約束的JRP,張?jiān)曝S等討論了[8]非瞬時(shí)補(bǔ)貨下改良品的JRP;另一類擴(kuò)展是將JRP與其他決策問(wèn)題相結(jié)合,比如將JRP與選址-庫(kù)存問(wèn)題(Location-Inventory Problem, LIP)結(jié)合的聯(lián)合采購(gòu)-選址庫(kù)存問(wèn)題(JR-LIP)[9]、將JRP與配送相結(jié)合的聯(lián)合采購(gòu)-配送問(wèn)題(Joint Replenishment and Delivery,JRD)[10]。盡管JRP問(wèn)題應(yīng)用廣泛,但在早期JRP的研究中,擴(kuò)展問(wèn)題的研究主要集中在第一類擴(kuò)展,而第二類擴(kuò)展則比較少,而伴隨著企業(yè)對(duì)精益化管理的要求以及成本壓力的上升,最近十年聯(lián)合采購(gòu)-配送集成優(yōu)化問(wèn)題得到了廣泛的關(guān)注,這也是本文研究重點(diǎn)。

將聯(lián)合采購(gòu)與配送相結(jié)合的JRD模型是非常具有現(xiàn)實(shí)意義:一方面這符合供應(yīng)鏈協(xié)同管理的原則,貼合企業(yè)的實(shí)際情況;另一方面通過(guò)聯(lián)合采購(gòu)策略整合配送資源可以取得規(guī)模經(jīng)濟(jì)效應(yīng),可降低企業(yè)的配送成本。因此,JRD自提出以來(lái)就得到了許多學(xué)者的關(guān)注,如:Qu等[11]考慮異質(zhì)品的JRD,Cui等[12]研究改進(jìn)配送策略的JRD以及高效求解算法,Liu等[13]研究多個(gè)中心倉(cāng)庫(kù)的M-JRD模型,崔利剛等[14]等將JRD與RFID投資決策相結(jié)合。目前JRD問(wèn)題還有較大的拓展研究空間,特別是還沒(méi)有同時(shí)考慮數(shù)量折扣、資源約束、多中心倉(cāng)庫(kù)運(yùn)作等貼近企業(yè)管理實(shí)踐的因素。從現(xiàn)實(shí)性考慮,聯(lián)合采購(gòu)策略的一個(gè)目的便是實(shí)現(xiàn)數(shù)量折扣,這也是現(xiàn)實(shí)中采取聯(lián)合采購(gòu)策略時(shí)?？紤]的一個(gè)因素,由于多種商品被聯(lián)合訂購(gòu),必然會(huì)加大采購(gòu)的總數(shù)量/金額,有機(jī)會(huì)爭(zhēng)取到較大的數(shù)量折扣。同時(shí)已有的研究表明,資源約束對(duì)于JRP問(wèn)題的影響較大[4],如果不考慮資源約束,模型假設(shè)會(huì)與實(shí)際情況產(chǎn)生較大的偏差。而將JRD與多中心倉(cāng)庫(kù)的選址決策進(jìn)行集成優(yōu)化則非常有現(xiàn)實(shí)意義,如前文討論的醫(yī)藥行業(yè)興起的跨區(qū)域聯(lián)合帶量采購(gòu)問(wèn)題,在這類運(yùn)營(yíng)模式中,由一個(gè)統(tǒng)一的采購(gòu)聯(lián)盟負(fù)責(zé)管理所有消費(fèi)者所需物資的采購(gòu),在獲得數(shù)量折扣的情況下通過(guò)聯(lián)合采購(gòu)策略節(jié)省補(bǔ)貨成本;由于最終用戶可能分布在相距幾百公里的地區(qū),如果要保證物資交付及時(shí),將會(huì)產(chǎn)生高額的運(yùn)輸費(fèi)用,需要從多個(gè)候選點(diǎn)中選擇合適的地點(diǎn)建立恰當(dāng)數(shù)量的中心倉(cāng)庫(kù),并確定中心倉(cāng)庫(kù)的最佳服務(wù)方案和最優(yōu)的訂貨策略。因此,基于多中心倉(cāng)庫(kù)的多物品聯(lián)合采購(gòu)-配送集成優(yōu)化模式是一種常見(jiàn)且有效的運(yùn)營(yíng)策略,這樣使得供應(yīng)鏈具有更好的柔性。

因此,本文擬研究考慮資源約束與數(shù)量折扣的M-JRD模型(M-JRD with Resource Constraint and Quantity Discount,CD-M-JRD),本文的問(wèn)題與文獻(xiàn)[3-4,13]較接近,然而文獻(xiàn)[3-4]都沒(méi)有考慮配送階段的優(yōu)化,并且是分別考慮資源約束和數(shù)量折扣,文獻(xiàn)[13]則是沒(méi)有考慮資源約束和數(shù)量折扣,因此應(yīng)用價(jià)值都比較有限。文獻(xiàn)[3-4]沒(méi)有集成配送決策,未綜合考慮多種資源約束,這可能會(huì)導(dǎo)致模型與實(shí)踐產(chǎn)生較大偏差,故本研究將分別研究聯(lián)合采購(gòu)和配送階段的資源約束對(duì)決策結(jié)果影響程度的大小,尤其是問(wèn)題規(guī)模較大情形下,期望獲得有益的管理啟示,比如若聯(lián)合采購(gòu)的資源約束明顯的話,企業(yè)決策者可加大在聯(lián)合采購(gòu)階段的基礎(chǔ)設(shè)施投資,如引進(jìn)RFID技術(shù)[14]等。另外,本研究還將探索資源約束與數(shù)量折扣之間的相互影響,期望明確不同資源約束和問(wèn)題規(guī)模時(shí),數(shù)量折扣對(duì)降低成本的貢獻(xiàn)是否顯著。在企業(yè)實(shí)踐中,如果不深入考慮這種影響,所構(gòu)建的模型往往也難于成功應(yīng)用。此外,盡管文獻(xiàn)[13]基于武漢的三個(gè)大型中心倉(cāng)庫(kù)進(jìn)行了一項(xiàng)優(yōu)化研究,但沒(méi)有對(duì)多中心倉(cāng)庫(kù)的情況進(jìn)行成本的邊際分析,多中心倉(cāng)庫(kù)運(yùn)營(yíng)模式的采用能給系統(tǒng)帶來(lái)多大的成本節(jié)約也是一個(gè)有待深入研究的問(wèn)題。綜上所述,CD-M-JRD的研究具有較重要的學(xué)術(shù)價(jià)值。

作為典型的NP-hard問(wèn)題[10],JRD問(wèn)題屬于混合整數(shù)非線性規(guī)劃,問(wèn)題難度較大,目前不存在有效、通用的精確算法。傳統(tǒng)的數(shù)學(xué)規(guī)劃方法并不適用,對(duì)問(wèn)題的精確求解一般采用特定的枚舉法,而對(duì)于中規(guī)模的問(wèn)題(商品數(shù)量大于50)便已經(jīng)很難求解[15],本研究集成了多種假設(shè),數(shù)學(xué)模型相較以前的研究更加復(fù)雜,從而對(duì)求解算法提出了更大的挑戰(zhàn)。因此,本文還分析了最優(yōu)解的數(shù)學(xué)性質(zhì),得到了最優(yōu)決策變量的界限以及原問(wèn)題的拉格朗日松弛界限,并根據(jù)這兩類性質(zhì)設(shè)計(jì)了兩種高效的求解算法,以供參考。

故本文的貢獻(xiàn)如下:構(gòu)建了一種考慮資源約束與數(shù)量折扣的多中心倉(cāng)庫(kù)聯(lián)合采購(gòu)-配送新模型;通過(guò)分析模型的數(shù)學(xué)性質(zhì)設(shè)計(jì)了兩種啟發(fā)式的算法;針對(duì)不同的資源約束和中心倉(cāng)庫(kù)數(shù)量,進(jìn)行了大規(guī)模算例的敏感性分析,獲得一些有益的管理性啟示如下:(1) 數(shù)量折扣與資源約束之間存在影響關(guān)系,當(dāng)資源約束較為寬松或者采購(gòu)的物品數(shù)量較少時(shí),數(shù)量折扣能夠有效的降低成本,而當(dāng)物品規(guī)模較大、資源約束限制明顯時(shí),數(shù)量折扣作用減弱;(2) 聯(lián)合采購(gòu)階段的資源約束對(duì)成本的影響非常大,而配送階段的資源約束對(duì)成本的影響非常小,企業(yè)決策者應(yīng)該多投資聯(lián)合采購(gòu)階段的設(shè)施,擴(kuò)大運(yùn)輸能力;(3) 增加中心倉(cāng)庫(kù)能有效降低成本,但其效果存在邊際收益遞減的現(xiàn)象。更詳細(xì)的結(jié)論列于第4章,這些結(jié)論能為企業(yè)采購(gòu)-配送集成優(yōu)化提供科學(xué)的決策參考。

1 問(wèn)題描述及模型建立

考慮一個(gè)包含m個(gè)中心倉(cāng)庫(kù)、n個(gè)供應(yīng)商、n個(gè)零售商的多中心JRD模型,如圖1所示。每個(gè)中心倉(cāng)庫(kù)基于下游需求從上游供應(yīng)商處聯(lián)合采購(gòu)商品,然后將商品再由中心倉(cāng)庫(kù)以一定頻次發(fā)送到下游零售商處。在模型中,每個(gè)供應(yīng)商只能供應(yīng)一種商品,同時(shí)每個(gè)零售商只能采購(gòu)一種商品,每種商品只由一個(gè)中心倉(cāng)庫(kù)采購(gòu)(根據(jù)Wang等[17]的證明,由I(I＞1)個(gè)供應(yīng)商和J(J＞1,IJ)個(gè)零售商組成的 JRD 模型中,即使每個(gè)零售商能從任意多個(gè)供應(yīng)商處采購(gòu)不同商品,這個(gè)模型也總能轉(zhuǎn)化為一個(gè)供應(yīng)商與零售商相等且每個(gè)零售商只從一個(gè)供應(yīng)商處采購(gòu)一種商品的模型,也即是說(shuō)我們的模型是一個(gè)通用模型)。模型考慮了每種商品的數(shù)量折扣,也加入聯(lián)合采購(gòu)階段和配送階段運(yùn)輸配送的容量限制。系統(tǒng)優(yōu)化目標(biāo)是找出使整個(gè)系統(tǒng)費(fèi)用最小的采購(gòu)、庫(kù)存與配送方案。

圖1 CD-M-JRD結(jié)構(gòu)圖Figure 1The structure of CD-M-JRD

與基本JRD[10]和M-JRD[13]等模型假設(shè)相同,CD-M-JRD模型也采用以下假設(shè):(1) 需求與各種費(fèi)用為常數(shù)且已知;(2) 不允許有缺貨;(3) 每個(gè)中心倉(cāng)庫(kù)不存在容量限制;(4) 不考慮中心倉(cāng)庫(kù)的建設(shè)成本。相關(guān)參數(shù)定義如表1所示。

表1 符號(hào)標(biāo)示Table 1Notations used in the model

在考慮數(shù)量折扣的情況下,總成本由兩大部分構(gòu)成,分別是M-JRD的基本成本和考慮數(shù)量折扣后增加的商品成本,下面對(duì)相關(guān)成本分別分析:

1) M-JRD的基本成本TC1

總訂貨成本Cs,中心倉(cāng)庫(kù)的總庫(kù)存成本Cwh,向零售商配送的成本Co,零售商的庫(kù)存成本Crh,這四部分構(gòu)成了基本成本:

2) 考慮數(shù)量折扣的商品成本TC2

其中Ci(ki,j,T)為商品i通過(guò)第j個(gè)中心倉(cāng)庫(kù)的采購(gòu)價(jià)格,一般來(lái)說(shuō),數(shù)量折扣的邊際增長(zhǎng)是遞減的,故?i∈N滿足:

由式(1)和式(2)可得總成本函數(shù):

另外還必須考慮以下約束條件:K、F為正整數(shù),X為0-1變量,聯(lián)合采購(gòu)階段和配送階段的商品重量不得超過(guò)最大運(yùn)載能力,每種商品只能通過(guò)一個(gè)中心倉(cāng)庫(kù)采購(gòu)。將以上內(nèi)容歸納總結(jié),可得到CD-M-JRD的數(shù)學(xué)模型如下所示,這是一個(gè)混合整數(shù)非線性規(guī)劃問(wèn)題。

2 決策變量的界限分析

CD-M-JRD模型中的決策變量有四個(gè):K、F、X、T,其中K、F、T的最優(yōu)上界是難以確定的,如果能對(duì)部分決策變量的上下界進(jìn)行一定分析,將能夠有效縮小算法的尋優(yōu)空間,使得算法便于找到更好的解。文獻(xiàn)[17]就提出了一種針對(duì)經(jīng)典JRD的定界算法用于尋找決策變量的最優(yōu)邊界并取得了非常好的效果,在大規(guī)模算例上,這種效果尤為明顯。因此,有必要針對(duì)CD-M-JRD的決策變量進(jìn)行分析。

為了便于表達(dá)和推導(dǎo),以下定義多個(gè)等式,并規(guī)定和分別代表變量G的上界和下界,「G■為大于或等于G的整數(shù)。

2.1 最優(yōu)T的性質(zhì)

命題1對(duì)于任意給定的K、F、X,定義T1= 2A/B,Ti,l=qi,l/(Diki,j),Tr= min (T2,T3),T2=Bw/其最優(yōu)基本周期一定在(0,Tr]內(nèi)。如果Tr＜T1,那么最優(yōu)基本周期為T*=Tr;如果T1＜Tr,那么最優(yōu)基本周期為(Ta)),其中Ta包括T1和Ti,l(滿足條件T1＜Ti,l＜Tr)。

證明:首先由于兩個(gè)資源約束條件,因此T*∈(0,Tr]成立,然后分兩種情況:

(1)如果Tr＜T1,則最優(yōu)基本周期T*滿足T*≤Tr＜T1,對(duì)于任意給定的K、F、X,TC1為凸函數(shù),T1為其最小值點(diǎn),TC2為遞減的階梯函數(shù),那么在(0,Tr]上TC為減函數(shù),此刻必然在Tr處取得最小值。(2)如果T1＜Tr,由于數(shù)量折扣的存在,最優(yōu)基本周期T*滿足T1≤T*≤Tr,在這個(gè)區(qū)間內(nèi)TC1遞增,TC2遞減,因此T*必然為T1或大于T1的某價(jià)格斷點(diǎn)Ti,l。

命題2對(duì)于任意給定的K、F、X,TC1的最優(yōu)的基本周期T1滿足如下條件:

其中,

證明:對(duì)于TC1而言,其最小值在處取得,故T1的一個(gè)界限為:

還可以發(fā)現(xiàn)以下關(guān)系:

又因?yàn)閷?duì)于最優(yōu)的K、F,存在下面的不等式:

故有:

即

綜上,T1的上下界為

命題3對(duì)于任意給定的K、F、X,最優(yōu)基本周期T*的下界滿足

證明:根據(jù)命題1,T1是T*的一個(gè)下界,根據(jù)命題2,T1是T1的一個(gè)下界,故也是T*的一個(gè)下界。又因?yàn)橐獫M足資源約束,故也是T*的一個(gè)下界。兩者中較大者為T*的一個(gè)更嚴(yán)格的下界。

命題4對(duì)于任意給定的K、F、X,最優(yōu)的基本周期T*的上界滿足

證明:根據(jù)命題1,T1、Tr的上界和Ti,l的上界中較小者為T*的一個(gè)上界,根據(jù)命題2可知T1的上界為的一個(gè)上界為

由命題3和4,顯然對(duì)于任意給定的K、F,最優(yōu)的基本周期T*′的界限為:

2.2 最優(yōu)K的性質(zhì)

命題5對(duì)于無(wú)約束問(wèn)題,任意給定F、T,對(duì)應(yīng)的最優(yōu)K滿足

證明:對(duì)于無(wú)資源約束的問(wèn)題,任意給定對(duì)于任意給定F、T,可以使TC達(dá)到最優(yōu)的K需要滿足如下條件:

因此,K要滿足下面的條件:

其中

故最優(yōu)的K滿足

因此,對(duì)于任意給定F、T,TC對(duì)應(yīng)的最優(yōu)的K滿足上式。

由命題5,我們還可以進(jìn)一步得到無(wú)資源約束下TC1的最優(yōu)的K:

其中

由此可得K的上下界:

2.3 最優(yōu)F的性質(zhì)

命題6對(duì)于無(wú)資源約束的問(wèn)題,任意給定K、T,最優(yōu)的F為

證明:對(duì)于無(wú)約束問(wèn)題,最優(yōu)的F滿足

由命題6,還可以進(jìn)一步得到F的一個(gè)界限

命題7對(duì)于存在資源約束的問(wèn)題,任意給定K、T,最優(yōu)的F為

其中

證明:由命題6可知fi,j,1為無(wú)資源約束下最優(yōu)的F,由資源約束(8)可知0,TC(fi,j)為凸函數(shù),故必為fi,j,1與fi,j,r中較大者。

2.4 最優(yōu)X的性質(zhì)

對(duì)于無(wú)資源約束的問(wèn)題,任意給定的K、F、T,顯然此時(shí)最優(yōu)的X可以由以下的規(guī)劃問(wèn)題得到:

其中

對(duì)于這個(gè)問(wèn)題,即使通過(guò)遍歷,求解最優(yōu)的X的時(shí)間復(fù)雜度也僅為O(mn)。

而對(duì)于存在資源約束的問(wèn)題,由于命題7,我們可以先不用考慮資源約束(9),則存在以下規(guī)劃問(wèn)題:

對(duì)于問(wèn)題(SP-2),通過(guò)拉格朗日松弛放松資源約束(8),可以得到其松弛問(wèn)題:

與(SP-1)相同,即使通過(guò)遍歷,求解(LRSP-2)的時(shí)間復(fù)雜度也僅為T_,而對(duì)于其對(duì)偶問(wèn)題:

可以采取一種次梯度法來(lái)進(jìn)行求解,并采用以下的公式更新λ:

其中,0＜ur≤2,UB為原問(wèn)題(SP-2)的一個(gè)上界,顯然如果(SP-2)存在可行解,一個(gè)上界為

3 模型求解算法設(shè)計(jì)

JRD問(wèn)題作為NP-hard問(wèn)題,求解難度大,其求解算法的研究也一直是一個(gè)重要的研究方向,這方面的研究詳見(jiàn)于Khouja的一篇綜述[15],對(duì)于JRD問(wèn)題的算法的設(shè)計(jì)一直有兩種思路,一種是基于連續(xù)變量T,通過(guò)切割連續(xù)變量T,得到一個(gè)個(gè)固定的T的斷點(diǎn),對(duì)于每個(gè)斷點(diǎn)進(jìn)行迭代搜索,尋找最優(yōu)的K、F, 代表性的算法是RAND 算法[10];另一種思路則是對(duì)整數(shù)變量K、F進(jìn)行搜索,一旦固定一組K、F的值,再找到對(duì)應(yīng)的最優(yōu)的T的值,代表性算法是GA[10]和DE[11,15-16],如在文獻(xiàn)[11]中自適應(yīng)混合差分算法(Adaptive Hybrid Differential Evolution, AHDE)在求解復(fù)雜JRD問(wèn)題上得到了目前最好的效果。由于JRD問(wèn)題的結(jié)構(gòu),前一種思路適合設(shè)計(jì)結(jié)構(gòu)化的啟發(fā)式算法,對(duì)于一個(gè)固定的T值,可以設(shè)計(jì)各種領(lǐng)域結(jié)構(gòu)或搜索策略來(lái)尋優(yōu);而后一種思路則適合以遺傳算法為代表的進(jìn)化算法,可以設(shè)置K、F的上下界,每一個(gè)變量作為遺傳算法的一個(gè)基因,很簡(jiǎn)單地完成遺傳算法的編碼工作。沒(méi)有明顯的證據(jù)表明兩種思路孰優(yōu)孰劣,本文根據(jù)這兩種思路設(shè)計(jì)了兩種完全不同的算法:定界-自適應(yīng)混合差分算法和M-RAND算法。

3.1 定界-自適應(yīng)混合差分算法

定界-自適應(yīng)混合差分算法的思想屬于JRD問(wèn)題算法的第二種思路,即首先通過(guò)定界算法縮小K、F的上下界,再通過(guò)算法進(jìn)行搜索,本文采用了之前在JRD問(wèn)題上取得了最好的效果的AHDE算法[11]來(lái)進(jìn)行搜索。

3.1.1 定界啟發(fā)式算法

對(duì)于CD-M-JRD問(wèn)題來(lái)說(shuō),問(wèn)題涉及的決策變量有K、F、X、T四部分,尋優(yōu)空間非常龐大,并且由于K、F兩個(gè)變量之間相互影響,其上界是難以確定的,常規(guī)的做法是直接設(shè)定其上界,K、F的上界常被設(shè)定為20,遠(yuǎn)大于Cha等[10]得到的最優(yōu)解的5倍,由此來(lái)確保尋優(yōu)空間包含了最優(yōu)解,并且在文獻(xiàn)[12][17]中這種設(shè)定都得到了很好的應(yīng)用效果,但是當(dāng)問(wèn)題的規(guī)模擴(kuò)大時(shí),尋優(yōu)空間呈指數(shù)級(jí)上升,如果仍然將K、F的上界直接設(shè)定為20,算法往往難以取得比較好的效果,這里就引入一種BH算法用于確定決策變量的邊界,其思路如下:

(4) 循環(huán)步驟(1)-(3)直至K和F的界限收斂。

3.1.2 自適應(yīng)混合差分進(jìn)化算法

DE算法作為一種簡(jiǎn)單有效的進(jìn)化算法,自提出以來(lái)[18]在眾多領(lǐng)域得到了很好的應(yīng)用[19],該算法主要包括三個(gè)操作:變異、交叉、選擇,在DE基礎(chǔ)上,AHDE算法在變異操作中引入自適應(yīng)算子,在選擇操作中使用改進(jìn)的選擇策略來(lái)加快搜索速度,已被證實(shí)是解決JRD問(wèn)題的一種有效算法[11]。本文直接采用了文獻(xiàn)[11]的AHDE算法,與DE相比,其改進(jìn)主要有兩點(diǎn):

(1) 變異操作:差分算子采用如下自適應(yīng)公式(34),其中g(shù)代表當(dāng)前迭代次數(shù),GenM代表最大迭代次數(shù),Fmin和Fmax是事先設(shè)定的差分算子上下界,這種自適應(yīng)算子使得算法能夠在初期保持較大的種群多樣性避免早熟,在后期則能夠保留優(yōu)良個(gè)體,加強(qiáng)局部搜索能力。

(2)選擇操作:AHDE與DE“一對(duì)一”的選擇策略不同,采用了局部截?cái)嗟姆绞?這點(diǎn)與GA類似,具體來(lái)說(shuō),第g代種群經(jīng)過(guò)變異交叉之后,根據(jù)適應(yīng)度的優(yōu)劣,留下其中一半的個(gè)體組成下一代種群,相比DE的“一對(duì)一”選擇策略,這種選擇策略往往具有更高的運(yùn)算效率。

AHDE算法的其他詳細(xì)步驟可以參考文獻(xiàn)[11]。

3.1.3 定界-自適應(yīng)混合差分算法流程

由于CD-M-JRD問(wèn)題較為復(fù)雜,算法準(zhǔn)確性和穩(wěn)定性難以保證,本文通過(guò)將BH算法嵌套在AHDE中,設(shè)計(jì)了一種混合算法(下簡(jiǎn)稱AHDE-BH)來(lái)解決CD-M-JRD問(wèn)題。通過(guò)BH算法,可以使得尋優(yōu)空間大大降低,使得AHDE能夠搜索到更優(yōu)的解,AHDE-BH的主要流程如下:

(1) 初始化:隨機(jī)生成初始種群。

(2) 變異操作:根據(jù)公式(34)進(jìn)行變異操作。

(3) 交叉操作。

(4) BH算法:根據(jù)章節(jié)3.1.1的BH算法流程,計(jì)算決策變量K、F的邊界,從而縮小尋優(yōu)空間。

(5) 選擇操作:局部截?cái)嗟倪x擇方式。

(6) 判斷終止條件:當(dāng)?shù)螖?shù)達(dá)到最大迭代次數(shù)時(shí),迭代停止,否則重復(fù)步驟(2)~(5)。

3.2 M-RAND算法

本論文還基于JRD-RAND算法[10]的思想設(shè)計(jì)了一種M-RAND(Modified RAND)算法,算法通過(guò)切割連續(xù)變量T將問(wèn)題轉(zhuǎn)化為整數(shù)規(guī)劃問(wèn)題,并且對(duì)于每一個(gè)切割點(diǎn),通過(guò)拉格朗日松弛界限來(lái)進(jìn)行篩選,從而達(dá)到剪枝的效果,剔除掉一些切割點(diǎn),最后對(duì)剩下的點(diǎn)進(jìn)行求解。新算法的步驟可以總結(jié)為:

(1) 根據(jù)公式(18)(17)計(jì)算決策變量T的上下界,將其分為η-1個(gè)區(qū)間,區(qū)間斷點(diǎn)為{T1,T2,…,Tl,…,Tη}。

(2) 通過(guò)啟發(fā)式方法得到問(wèn)題的上界,我們論文中選擇計(jì)算T=Tη時(shí)的最優(yōu)解TCη來(lái)得到上界。

(3) 對(duì)于每一個(gè)Tl,計(jì)算松弛問(wèn)題(SP-1)得到下界,并進(jìn)行剪枝:對(duì)于下界高于TCη的Tl不需要進(jìn)一步尋優(yōu)。

(4) 對(duì)于下界低于TCη的Tl,計(jì)算問(wèn)題(SP-2)進(jìn)一步尋優(yōu),所求解如果滿足資源約束則結(jié)束,否則進(jìn)行修復(fù)。

(5) 使用貪心算法對(duì)于不滿足資源約束的解進(jìn)行修復(fù)。

(6) 找到所有Tl中最優(yōu)的解。

為了驗(yàn)證算法的效果,我們?cè)O(shè)計(jì)了3個(gè)實(shí)驗(yàn)。部分實(shí)驗(yàn)數(shù)據(jù)隨機(jī)生成,生成規(guī)則參考文獻(xiàn)[17]如表2所示,商品的單價(jià)參考文獻(xiàn)[20]設(shè)定為6.25,價(jià)格折扣率根據(jù)實(shí)際情況設(shè)定為:數(shù)量超過(guò)25為0.9,超過(guò)50為0.8,超過(guò)100為0.7,bi根據(jù)文獻(xiàn)[4]設(shè)定為6.25,所有算法采用 Matlab 2016b進(jìn)行編碼,算例都在一臺(tái)配置為 Intel Corei7-4790K 4.0 GHz CPU, 16 GB RAM且操作系統(tǒng)為 Windows 7的個(gè)人電腦中完成。

表2 算例規(guī)則Table 2The range of parameters

4.1 實(shí)驗(yàn)1:不同商品規(guī)模下各種算法的性能表現(xiàn)

設(shè)計(jì)n= 10, 50, 100, 200 四種規(guī)模下的算例實(shí)驗(yàn),每個(gè)規(guī)模隨機(jī)生成20個(gè)算例,一共80個(gè)算例,所有算例的中心倉(cāng)庫(kù)數(shù)m=2、主要訂貨成本S為0.01倍的商品總價(jià)值、采購(gòu)階段的運(yùn)輸約束為25000、配送階段的運(yùn)輸約束為2000。

在算法上選擇DE、ADE、AHDE、GA(Genetic Algorithm)、PSO(Particle Swarm Optimization)、FOA(Fruit Fly Optimization Algorithm)來(lái)與AHDE-BH和M-RAND進(jìn)行對(duì)比,原因如下:文獻(xiàn)[21]已經(jīng)證實(shí)在解決復(fù)雜JRD問(wèn)題時(shí),DE具有超過(guò)ACO、GA、JRD-RAND、JRD-SH的準(zhǔn)確性和穩(wěn)定性,而AHDE的性能也在文獻(xiàn)[11]中有很好的體現(xiàn),作為DE和AHDE中間變種的ADE之前則未有文獻(xiàn)用于求解JRD,因此我們也納入備選;GA作為一種經(jīng)典的進(jìn)化算法也在JRD的求解上有著出色的表現(xiàn)[10];PSO則作為與DE和GA不同思路的一種經(jīng)典的群體智能算法在各種工程優(yōu)化問(wèn)題上被廣泛應(yīng)用[21];FOA則作為一種新型的群體智能算法在JRD的求解上也表現(xiàn)不俗[22]。除M-RAND外所有算法的最大迭代次數(shù)GenM=500,種群大小Np=100,M-RAND算法的η設(shè)定為1000,統(tǒng)計(jì)計(jì)算結(jié)果的平均值、最優(yōu)次數(shù)占比以及算法的平均偏差如表3所示,幾種算法在各種規(guī)模下的收斂表現(xiàn)如圖2所示。

表3 各種算法得到的平均成本Table 3The average costs got by different algorithms

從表3可看出在問(wèn)題規(guī)模較小時(shí)(n=10,50),AHDE-BH算法求解結(jié)果的偏差是最小的,也尋找到了最多的最優(yōu)解,即使在n=100時(shí),仍具有很好的性能,這說(shuō)明了AHDE-BH算法的準(zhǔn)確性和穩(wěn)定性;而從圖2不難看出,在收斂速度方面AHDE-BH也具有相對(duì)優(yōu)勢(shì),考慮到實(shí)驗(yàn)的最大迭代次數(shù)GenM=500,已經(jīng)較大,可以適當(dāng)調(diào)小迭代次數(shù),提高運(yùn)算效率。另一方面,在問(wèn)題規(guī)模較大時(shí)(n=100,200),M-RAND算法則效果最好,并且算法的運(yùn)算效率非常高,求解n=200的算例只需要17.58秒,算法的偏差也較小,平均不超過(guò)0.01%,即使在計(jì)算小規(guī)模算例時(shí)也與AHDE-BH能相當(dāng),在大規(guī)模算例下,則明顯比AHDE-BH好。從綜合性能來(lái)講,M-RAND算法更優(yōu),只有在計(jì)算小規(guī)模算例時(shí),AHDE-BH具有微小的優(yōu)勢(shì),但即使計(jì)算小規(guī)模算例時(shí)M-RAND算法的偏差也不超過(guò)0.01%。因此,對(duì)于小規(guī)模算例可以使用AHDEBH算法,而對(duì)于大規(guī)模算例,M-RAND算法更好。從算法的普適性來(lái)說(shuō),AHDE-BH的操作更加簡(jiǎn)單,更容易實(shí)現(xiàn),面對(duì)其他擴(kuò)展問(wèn)題也有一定的普適性。從現(xiàn)有研究來(lái)看,計(jì)算決策變量K和F的界限是相對(duì)容易實(shí)現(xiàn)的[17],可以簡(jiǎn)單地套用這一套算法框架,即先縮小決策變量的界限再使用某種元啟發(fā)式算法進(jìn)行搜索;而M-RAND算法使用了較多的CD-M-JRD的模型特性,包括拉格朗日松弛下界和決策變量T的界限,操作起來(lái)更麻煩,也不容易擴(kuò)展到其他問(wèn)題中。

圖2 不同規(guī)模問(wèn)題下七種算法的收斂過(guò)程圖Figure 2The converge plots of different algorithms under different problem scales

考慮到現(xiàn)實(shí)中,聯(lián)合采購(gòu)規(guī)模不能太大也不能太小,太大則管理困難,太小則規(guī)模優(yōu)勢(shì)不明顯,n=50的規(guī)模與現(xiàn)實(shí)問(wèn)題更接近,而AHDE-BH在n=50時(shí)展現(xiàn)了最好的準(zhǔn)確性,因此在實(shí)驗(yàn)2和3中,僅使用AHDE-BH算法進(jìn)行求解。

4.2 實(shí)驗(yàn)2:不同資源約束下的算例實(shí)驗(yàn)

為了進(jìn)一步檢驗(yàn)算法的性能以及資源約束和數(shù)量折扣對(duì)CD-M-JRD模型的影響,隨機(jī)生成了一個(gè)n=50,m=2的算例,針對(duì)該算例設(shè)定了如下參數(shù)組合:主要訂貨成本S為0.01倍-0.05倍的商品總價(jià)值,資源約束B(niǎo)w和Bri分別為1倍、5倍、10倍的M和N(M=25000,N=2000),一共45種組合,每種組合使用AHDE-BH算法重復(fù)計(jì)算10次,最后取10次中的最優(yōu)值,計(jì)算結(jié)果如表4、5、6所示,從計(jì)算結(jié)果可以得到以下結(jié)論:

表4 Bw = M時(shí)的成本Table 4The result of Bw = M

(1) 采購(gòu)階段的運(yùn)輸約束B(niǎo)w對(duì)成本的影響非常大,特別是對(duì)TC1的影響。與Bw=M的情況相比,Bw=5M,10M時(shí),TC的均值分別降低到原先的49.54%和44.48%,TC1降低到22.32%和13.97%,TC2降低到91.19%和91.19%,產(chǎn)生這種情況的原因也不難理解,由于采購(gòu)階段的商品是所有商品一起采購(gòu),運(yùn)輸量非常大,Bw的影響就會(huì)非常明顯,導(dǎo)致Bw=M時(shí)采購(gòu)成本TC1甚至超過(guò)了商品自身成本TC2,但是一旦放松運(yùn)輸約束B(niǎo)w,TC1和TC2都明顯降低。

表5 Bw = 5M時(shí)的成本Table 5The result of Bw = 5M

表6 Bw = 10M時(shí)的成本Table 6The result of Bw = 10M

(2) 配送階段的運(yùn)輸約束對(duì)成本的影響非常小。在Bw=M時(shí),5N,10N并不能改變總成本的大小;Bw=5M時(shí),TC的均值分別降低到原先的99.89%和99.89%;Bw=10M時(shí),TC的均值分別降低到原先的99.90%和99.90%。產(chǎn)生這種情況的原因在于配送階段對(duì)于每一個(gè)零售商的需求是分別配送的,這是不同于聯(lián)合采購(gòu)階段的,因此每次配送量較小,除非約束條件非常嚴(yán)格,否則影響較小。

(3) 主要訂貨成本S對(duì)總成本的影響較顯著,特別是對(duì)TC1的影響。在Bw=M,5M,10M三種情況下,與S=s的情況相比,S=2 s,3 s,4 s,5 s時(shí):①TC的均值分別上升到原先的127.08%、154.17%、 181.25%、208.34%,TC1上升到169.33%、238.66%、307.99%、377.32%,TC2則沒(méi)有改變;②TC的均值分別上升到原先的108.28%、116.54%、124.81%、133.07%,TC1上 升 到 154.09%、208.15%、262.35%、316.55%,TC2則為100.04%、100.06%、100.06%、100.06%;③TC的均值分別上升到原先的104.29%、108.58%、112.87%、117.15%,TC1上 升 到 135.58%、171.16%、206.75%、242.31%,TC2則不變。由于TC1是直接受S影響的,TC2則與S沒(méi)有直接聯(lián)系,因此產(chǎn)生這種結(jié)果比較好解釋。并且值得注意的是S=2s,3s,4s,5s時(shí),TC1每次增長(zhǎng)的幅度基本保持在同一個(gè)水平。

(4) 數(shù)量折扣對(duì)成本有一定的影響。在Bw=M,5M,10M時(shí),平均折扣率分別為0.7679、0.7003、0.7000,商品的成本能夠有效降低,并且折扣率只對(duì)Bw的變化有明顯的敏感性,對(duì)主要訂貨成本S的變化則不敏感。

值得注意的是,我們發(fā)現(xiàn)聯(lián)合采購(gòu)階段和配送階段的資源約束對(duì)于成本的影響是顯著不同的,聯(lián)合采購(gòu)階段的資源約束影響非常大,而配送階段的資源約束影響則非常小,這對(duì)于聯(lián)合采購(gòu)-配送策略的一個(gè)現(xiàn)實(shí)問(wèn)題:“投資決策”有很重要的指導(dǎo)意義[14],企業(yè)的投資應(yīng)當(dāng)優(yōu)先滿足聯(lián)合采購(gòu)階段對(duì)運(yùn)輸、人力資源的需求。

4.3 實(shí)驗(yàn)3:不同中心倉(cāng)庫(kù)數(shù)量下的算例實(shí)驗(yàn)

在企業(yè)實(shí)際運(yùn)作管理中,中心倉(cāng)庫(kù)的數(shù)量往往是多個(gè)的,為了研究中心倉(cāng)庫(kù)數(shù)量對(duì)模型成本的影響,設(shè)計(jì)了m=2,3,4,5四種情形的算例進(jìn)行研究。為了避免個(gè)別算例影響實(shí)驗(yàn)結(jié)果,在隨機(jī)生成m=2的算例后,我們?cè)谄鋽?shù)據(jù)基礎(chǔ)上隨機(jī)生成一個(gè)新的中心倉(cāng)庫(kù)的數(shù)據(jù)從而計(jì)算m=3的情況,同理去計(jì)算m=4,5的情況,算例均使用AHDE-BH算法求解,每個(gè)算例重復(fù)計(jì)算10次取最優(yōu)值,主要訂貨成本S為0.01倍的商品總價(jià)值,資源約束B(niǎo)w=25000,Bri=2000計(jì)算結(jié)果如表7所示,其中ΔTC(%)代表新增加中心倉(cāng)庫(kù)帶來(lái)的成本變化及比例。

表7 多個(gè)中心倉(cāng)庫(kù)的結(jié)果Table 7The result of multi-warehouse

從表7的數(shù)據(jù)可以看出:存在更多中心倉(cāng)庫(kù)的模型成本更優(yōu),但增加中心倉(cāng)庫(kù)主要影響的是TC1,而對(duì)TC2沒(méi)有影響;而且隨著中心倉(cāng)庫(kù)數(shù)量的增加,增加中心倉(cāng)庫(kù)的邊際效益是下降的,雖然本模型沒(méi)有考慮中心倉(cāng)庫(kù)的建設(shè)成本或租用成本,但通過(guò)這種邊際分析可以幫助企業(yè)決定是否建設(shè)或租用新倉(cāng)庫(kù)。

5 結(jié)論

本文的主要貢獻(xiàn)如下:(1)設(shè)計(jì)了一種考慮資源約束與數(shù)量折扣的多中心倉(cāng)庫(kù)聯(lián)合采購(gòu)與配送模型,模型貼合企業(yè)實(shí)際情況,具有較好的學(xué)術(shù)價(jià)值和實(shí)用價(jià)值;(2)針對(duì)模型的數(shù)學(xué)性質(zhì)進(jìn)行了一定分析,得到了最優(yōu)決策變量的較好的界限,并據(jù)此設(shè)計(jì)了兩種求解算法,兩種新算法在精度和穩(wěn)定性上相較已有算法都有較明顯的優(yōu)勢(shì);(3)設(shè)計(jì)了不同資源約束以及不同中心倉(cāng)庫(kù)數(shù)量下的大規(guī)模算例實(shí)驗(yàn),實(shí)驗(yàn)證明:聯(lián)合采購(gòu)階段的運(yùn)輸約束B(niǎo)w對(duì)成本的影響非常大而配送階段的運(yùn)輸約束對(duì)成本的影響非常小,主要訂貨成本和數(shù)量折扣則對(duì)成本有一定的影響,增加中心倉(cāng)庫(kù)數(shù)量能夠帶來(lái)明顯的收益,但具有邊際效益遞減的現(xiàn)象。根據(jù)這些結(jié)論,可得到以下管理啟示:由于聯(lián)合采購(gòu)階段的資源約束對(duì)成本的影響非常大,如果約束比較嚴(yán)格,數(shù)量折扣往往也難以實(shí)現(xiàn),而配送階段的資源約束則影響很小,故應(yīng)該增加在聯(lián)合采購(gòu)階段的投資,如購(gòu)買更大更多的貨運(yùn)卡車或者采取RFID[14]等新技術(shù)提高聯(lián)合采購(gòu)階段的能力;增加中心倉(cāng)庫(kù)確實(shí)能帶來(lái)一些收益,盡管本文沒(méi)有考慮中心倉(cāng)庫(kù)的建設(shè)成本,但從邊際分析來(lái)看,增加中心倉(cāng)庫(kù)的邊際收益是遞減的,因此中心倉(cāng)庫(kù)不宜過(guò)多,從本研究實(shí)驗(yàn)結(jié)果來(lái)看,不宜超過(guò)5個(gè)。

未來(lái)擬將此模型拓展到不確定需求下允許缺貨的情形或者在模型中考慮中心倉(cāng)庫(kù)的建設(shè)成本或租用成本[23],這樣模型將變得更貼合現(xiàn)實(shí),擬結(jié)合果蠅優(yōu)化算法[24]或者帝國(guó)競(jìng)爭(zhēng)算法[25]設(shè)計(jì)更高效的智能求解新算法。