基于混合果蠅優(yōu)化算法的選址-庫存-配送集成優(yōu)化研究

曾宇容, 王 林, 王思睿

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

0 引言

聯(lián)合補(bǔ)貨問題(Joint Replenishment Problem, JRP)是指多個客戶通過一個中心供應(yīng)商對多種商品進(jìn)行分組集體采購，從而分擔(dān)主要訂貨成本，節(jié)約采購總成本。JRP自提出以來其學(xué)術(shù)價(jià)值就得到廣泛認(rèn)同[1]，其應(yīng)用價(jià)值也備受認(rèn)可。對于供應(yīng)鏈管理而言，多因素集成管理始終是一個重要原則[2]，將采購、選址、庫存、配送進(jìn)行綜合集成優(yōu)化顯然更具有現(xiàn)實(shí)意義。例如，柳州桂中海迅物流股份有限公司是一家第三方物流公司，服務(wù)客戶包括對物資交付及時(shí)性要求非常高的上汽通用五菱汽車股份有限公司、東風(fēng)柳州汽車有限公司和廣西柳工機(jī)械股份有限公司等，公司需從數(shù)十個供應(yīng)商處取貨然后通過廣西不同區(qū)域的十幾個中心倉庫將商品配送至工業(yè)客戶。這些客戶分布在不同的區(qū)域，運(yùn)輸成本不菲，如何制定最優(yōu)的采購、庫存、配送策略并確定合適的倉庫選址與倉庫數(shù)量就顯得迫在眉睫。針對這種管理背景，本文構(gòu)建了一種基于聯(lián)合補(bǔ)貨策略的選址-庫存-配送集成優(yōu)化模型(Joint Replenishment and Location-Inventory-Delivery, JR-LID)。JRP的一個普遍假設(shè)是只考慮一個中心倉庫，不存在倉庫選址決策問題，而將聯(lián)合補(bǔ)貨(Joint Replenishment, JR)策略與選址-庫存(Location Inventory Problem, LIP)相結(jié)合的聯(lián)合補(bǔ)貨-選址-庫存問題(Joint Replenishment and LIP, JR-LIP) 被提出的時(shí)間較短[3]，因此相關(guān)的拓展研究還比較少。而針對聯(lián)合補(bǔ)貨-配送模型 (Joint Replenishment and Delivery, JRD)[4]，目前結(jié)合選址問題的研究較少，因此本文的模型具有一定的學(xué)術(shù)價(jià)值。

此類問題研究的一個瓶頸就是求解高性能算法的設(shè)計(jì)，確定性JRP已經(jīng)被證實(shí)為NP-hard問題[5]，周期性JRP也在最近被證明為Strongly NP-hard[6]。傳統(tǒng)的數(shù)學(xué)規(guī)劃方法難以在多項(xiàng)式時(shí)間內(nèi)給出一個滿意解，因此許多啟發(fā)式算法和元啟發(fā)式算法得到了采用，其中最出名的是 RAND算法[7]。各種變種RAND算法也成為求解JRP的常用方法，如文獻(xiàn)[4]的JRD-RAND與文獻(xiàn)[8]中設(shè)計(jì)的TS-RAND，但RAND算法受限于特殊的啟發(fā)式規(guī)則，對許多復(fù)雜的JRP并不適用。目前JRP的研究中，許多元啟發(fā)式算法得到了采用，如Khouja等[7]將遺傳算法(Genetic Algorithm, GA) 用于求解JRP，與RAND算法相比，GA在大規(guī)模算例下表現(xiàn)出了很好的潛力，但GA也存在操作復(fù)雜、效率較低的缺點(diǎn)，并且算法后期容易陷入收斂停滯。為克服這些缺點(diǎn)，許多改進(jìn)的智能算法得到了采用，如Wang等[9]使用了一種改進(jìn)的回溯搜索算法(Backtracking Search Optimization, BSA)來求解JRP，Braglia等[10]則使用了一種改進(jìn)的GA來求解JRP，這些算法都取得了不錯的效果，并且相對于結(jié)構(gòu)性的啟發(fā)式算法更易于實(shí)現(xiàn)。根據(jù)Khouja等[7]對JRP問題的綜述，由于缺乏穩(wěn)定高效的求解算法，許多考慮更貼近實(shí)際約束(庫存容量、資金約束、最小訂貨量等)的拓展JRP問題未得到深入研究。事實(shí)上，將選址決策與JRD相結(jié)合的JR-LID問題求解難度更大，這就要求找到一種兼具準(zhǔn)確性與穩(wěn)定性的算法，而各種新型群體智能算法則提供了這種可行的途徑。

果蠅優(yōu)化算法(Fruit Fly Optimization Algorithm, FOA)是一種群體智能新算法[11]，具有操作簡單、收斂速度快、全局尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn)，自提出以來已經(jīng)成功應(yīng)用于多個領(lǐng)域，如Mousavi等[12]利用一種改進(jìn)FOA研究了兩級供應(yīng)鏈網(wǎng)絡(luò)下的選址庫存問題；Li等[13]利用一種混合FOA求解鋼鐵鑄造中的混合流水車間調(diào)度問題；秦礪寒等[14]利用FOA中的迭代尋優(yōu)來替代BP神經(jīng)網(wǎng)絡(luò)中的梯度修正，并將優(yōu)化后的BP神經(jīng)網(wǎng)絡(luò)用于夏季空調(diào)降溫負(fù)荷預(yù)測?？傮w而言，F(xiàn)OA已經(jīng)成功應(yīng)用于財(cái)務(wù)危機(jī)預(yù)警建模、多維背包問題、電力預(yù)測、神經(jīng)網(wǎng)絡(luò)參數(shù)優(yōu)化、供應(yīng)鏈選址分配問題、網(wǎng)絡(luò)拍賣物流服務(wù)等許多領(lǐng)域。文獻(xiàn)[15]采用了一種改進(jìn)FOA對JRP問題進(jìn)行求解，結(jié)果展現(xiàn)出了優(yōu)于差分進(jìn)化(Differential Evolution, DE)和GA的穩(wěn)定性和準(zhǔn)確性，但FOA也存在易早熟收斂、易陷入局部最優(yōu)、算法穩(wěn)定性不好、局部搜索能力不強(qiáng)等缺點(diǎn)，針對這些缺點(diǎn)以及本模型面臨的挑戰(zhàn)，本文基于信息交換策略設(shè)計(jì)了一種混合果蠅優(yōu)化算法(Hybrid Fruit Fly Optimization Algorithm with Information Exchange, HFOA)，以便更好地解決JR-LID問題。

故本文的主要貢獻(xiàn)如下：(1)將JRD與LIP相結(jié)合，構(gòu)建了一種采購、庫存、選址、配送集成優(yōu)化的新模型，新模型具有較重要的學(xué)術(shù)價(jià)值和較高的實(shí)用價(jià)值；(2)基于信息交換策略設(shè)計(jì)了一種HFOA算法，算例結(jié)果表明，新算法在處理大規(guī)模問題時(shí)在準(zhǔn)確性和穩(wěn)定性方面優(yōu)于類似研究中的算法。

1 模型描述

模型相關(guān)數(shù)學(xué)符號如表1所示，本文考慮一個包含m個中心倉庫、n個供應(yīng)商、n個零售商的多中心JRD模型的選址問題，如圖1所示，在該模型中，每個供應(yīng)商只能供應(yīng)一種商品，同時(shí)每個零售商只能采購一種商品，每種商品只由一個中心倉庫采購(根據(jù)Wang等[8]的證明，其他情況都能轉(zhuǎn)化為這種基本模型)，中心倉庫的潛在選址點(diǎn)位于每個零售商處，不同選址點(diǎn)的費(fèi)用不同，模型優(yōu)化目標(biāo)是找出使整個系統(tǒng)費(fèi)用最小的采購、選址、庫存、配送方案。

表1 符號標(biāo)識

圖1 JR-LID結(jié)構(gòu)圖

與基本JRD[4]和JR-LIP[3]等模型假設(shè)相同，JR-LID模型也采用了以下假設(shè): (1)需求與各種費(fèi)用為常數(shù)且已知；(2)不允許有缺貨；(3)運(yùn)輸和庫存沒有數(shù)量限制；(4)配送費(fèi)用只與配送距離相關(guān)而與配送量不相關(guān)。

JR-LID模型的庫存運(yùn)作方式類似經(jīng)典的經(jīng)濟(jì)批量訂貨模型，每個物品在中心倉庫和零售商的庫存量變化如圖2所示，總成本函數(shù)刻畫了整個系統(tǒng)單位時(shí)間內(nèi)的平均成本(元/年)。成本主要包括5個部分：總訂貨成本，中心倉庫的總庫存成本，向零售商配送的成本，零售商的庫存成本，選址成本，總成本函數(shù)如式(1)所示：

圖2 庫存變化示意圖

(1)

JR-LID的數(shù)學(xué)模型如下:

(2)

其中，前3項(xiàng)約束表示對于決策變量的基本約束。第4項(xiàng)約束條件表示一個零售商只能被一個倉庫服務(wù)，第5項(xiàng)約束條件表示只有當(dāng)一個倉庫確定建造時(shí)，它才能服務(wù)一個零售商，第6項(xiàng)約束條件表示只有當(dāng)一個倉庫確定建造時(shí)，它才能被選址。顯然，根據(jù)一階和二階最優(yōu)條件，可得到最優(yōu)的T如下:

(3)

2 基于改進(jìn)果蠅優(yōu)化算法的求解方法

2.1 標(biāo)準(zhǔn)果蠅優(yōu)化算法流程

果蠅是一種廣泛存在于溫帶與熱帶地區(qū)的昆蟲，在尋找食物時(shí)，果蠅群體能夠通過嗅覺尋找食物的方位，并將氣味信息傳遞給其他果蠅，每個果蠅個體通過比群體中的氣味濃度，利用視覺飛向擁有最佳的濃度判定值的個體，并繼續(xù)利用嗅覺展開下一步的搜索，通過這種方式，果蠅群體中的所有果蠅最終都能到達(dá)食物位置，F(xiàn)OA就是基于果蠅覓食的這種過程設(shè)計(jì)的，圖3展示了果蠅覓食的一個簡要過程。

圖3 果蠅覓食過程

標(biāo)準(zhǔn)FOA分為以下幾個步驟：

Step1初始化。設(shè)置FOA的參數(shù)：種群大小popsize，最大迭代次數(shù)maxgen，初始位置范圍LR，每次移動的范圍FR。果蠅群體中每個個體的位置信息由其對應(yīng)的(X,Y)二維坐標(biāo)來給出，其初始位置可由式(4)得到。

X_axis=rand(LR),Y_axis=rand(LR)

(4)

Step2嗅覺搜索過程

每個果蠅個體根據(jù)嗅覺搜索食物的位置，對于個體α(1≤α≤popsize)而言，其位置更新通過式(5)來進(jìn)行。

Xα=X_axis+rand(FR),Yα=Y_axis+rand(FR)

(5)

更新位置后，對利用式(6)來計(jì)算每只果蠅與源點(diǎn)的距離，然后通過式(7)計(jì)算其味道濃度判定值，然后通過式(8)計(jì)算群體中每個果蠅的味道濃度值Smellα，其中fitness表示味道濃度的判定函數(shù)，在處理優(yōu)化問題時(shí)即是目標(biāo)函數(shù)。

(6)

Sα=1/DISTα

(7)

Smellα=fitness(Sα)

(8)

根據(jù)式(9)，選擇當(dāng)前群體中具有最佳味道濃度值的果蠅，記錄其味道濃度值和相應(yīng)位置。

[bestSmell,bestIndex]=min(Smell)

(9)

Step3視覺搜索過程。在找到具有最佳味道濃度值的果蠅后，群體中的其他果蠅個體都會通過視覺直接飛向該位置，通過式(10)，更新種群里果蠅個體的位置，并記錄最佳的味道濃度值Smellbest。

Smellbest=bestSmell,X_axis=X(bestIndex),

Y_axis=Y(bestIndex)

(10)

Step4重復(fù)Step 2到Step 3直至達(dá)到算法的最大迭代次數(shù)maxgen，最后輸出最優(yōu)的味道濃度值Smellbest和最優(yōu)的果蠅位置(Xaxis,Yaxis)。

FOA雖然有操作簡單、全局尋優(yōu)能力強(qiáng)的優(yōu)點(diǎn)，但也有容易早熟收斂、性能不穩(wěn)定等缺點(diǎn)。FOA的尋優(yōu)策略存在以下問題：(1) 缺乏有效的信息交換策略。更新果蠅個體的位置時(shí)，其他果蠅直接飛向目前擁有最佳位置的果蠅，通過這種貪心策略加快了尋優(yōu)速度和全局尋優(yōu)能力，但也喪失了每只果蠅個體的歷史信息，缺少有效的信息交換使得標(biāo)準(zhǔn)FOA的局部尋優(yōu)能力和種群多樣性較弱。(2) 缺乏有效的途徑跳出局部最優(yōu)。由于(1)中所說的缺點(diǎn)，標(biāo)準(zhǔn)FOA容易發(fā)生早熟收斂的問題，然而算法中卻缺少一定的途徑從局部最優(yōu)跳出，這就使得算法往往達(dá)到一定的深度后就難以繼續(xù)下降。(3) 缺乏有效的局部尋優(yōu)策略。標(biāo)準(zhǔn)FOA通過在最優(yōu)位置的一定范圍內(nèi)隨機(jī)生成解的方式進(jìn)行尋優(yōu)，這種策略雖然使得FOA的全局尋優(yōu)能力很強(qiáng)，但太過簡單也未利用果蠅個體的歷史信息，這就使得FOA在處理多峰優(yōu)化問題時(shí)表現(xiàn)較差。

2.2 果蠅優(yōu)化算法的改進(jìn)

本文設(shè)計(jì)了一種基于信息交換策略的混合果蠅優(yōu)化算法，主要改進(jìn)如下：

(1)引入信息交換和變異策略

在標(biāo)準(zhǔn)FOA中，除了最優(yōu)的果蠅個體之外，其他果蠅的歷史信息沒有得到有效的利用，因此新算法借鑒進(jìn)化算法的思想，引入了信息交換、變異、選擇操作，當(dāng)果蠅種群進(jìn)行過視覺搜索過程之后，通過式(11)生成一個與父代種群(X,Y)同樣大小的子代種群(X′,Y′)，其中r是(0,1)上的隨機(jī)數(shù)，ct與mu分別是信息交換與變異的閾值，β是果蠅個體的第β個基因，λ(0≤λ≤1)是兩個隨機(jī)不同個體p1和p2間的信息交換比例。對于新的混合種群({X,X′},{Y,Y′})，采取局部截?cái)嗟姆绞?，選擇其中最優(yōu)的50%的個體進(jìn)入下一代。通過個體間的信息交換、基因變異以及選擇繼承到下一代，種群的多樣性將明顯優(yōu)于標(biāo)準(zhǔn)FOA，并且通過這種方式可以有效地進(jìn)行局部尋優(yōu)。

(11)

(2)引入概率性飛行策略

在標(biāo)準(zhǔn)FOA的嗅覺搜索過程中，單次飛行范圍FR決定了FOA的全局尋優(yōu)能力和局部尋優(yōu)能力的強(qiáng)弱，如果FR較大則全局尋優(yōu)能力較強(qiáng)，F(xiàn)R較小則局部尋優(yōu)能力較強(qiáng)，如何設(shè)計(jì)飛行策略平衡全局尋優(yōu)與局部尋優(yōu)也是FOA的一個重要改進(jìn)方向。如Wang等[15]設(shè)計(jì)了一種概率飛行策略：首先設(shè)計(jì)一個飛行范圍池，包含若干數(shù)量級的飛行范圍值。果蠅在每次嗅覺搜索時(shí)會以一定概率選定某個飛行范圍，并且飛行范圍越大，其選擇概率越小。這種隨機(jī)飛行策略使得果蠅種群能夠以一定概率搜索到極佳的位置。鑒于新算法引入了交叉變異的策略，一定程度上彌補(bǔ)了局部尋優(yōu)能力，因此HFOA也采用了概率性的飛行策略，每次嗅覺搜索過程，都有一定幾率選擇飛行或者停留在原地，如果選擇了飛行則獲得了一次全局尋優(yōu)的機(jī)會，如果選擇停留則通過(1)中的策略獲得了更好的局部尋優(yōu)機(jī)會，通過這種概率性的飛行策略，可以有效的平衡新算法的全局尋優(yōu)與局部尋優(yōu)能力，使得算法不容易陷入局部最優(yōu)。具體來說，新的嗅覺搜索過程可用式(12)和(13)表示，其中FPmin和FPmax是設(shè)定的最低概率和最高概率，g是算法當(dāng)前的迭代次數(shù)，r′(0,1)上的隨機(jī)數(shù)，當(dāng)?shù)螖?shù)增加時(shí)，F(xiàn)P會降低，以便算法獲得更好的局部尋優(yōu)能力。

(12)

(13)

2.3 基于改進(jìn)果蠅優(yōu)化算法的求解步驟

如圖4所示，HFOA求解JR-LID的過程如下：

圖4 HFOA流程圖

Step1初始化。設(shè)定HFOA的各種參數(shù)，根據(jù)公式(4)生成算法的初始種群，令g=0。

Step2概率性的飛行策略。根據(jù)式(12)(13)采取概率性的飛行策略來更新果蠅種群的位置。

Step3生成子代種群。根據(jù)式(11)通過信息交換和變異生成子代種群(X′,Y′)。

Step4計(jì)算種群中個體的適應(yīng)度。根據(jù)式(1)(3)計(jì)算種群(X,Y)和(X′,Y′)中個體的適應(yīng)度。

Step5選擇操作。選擇混合種群中適應(yīng)度前50%的個體進(jìn)入下一代種群。

Step6算法終止判定。

3 數(shù)值實(shí)例

為了驗(yàn)證HFOA的性能，本節(jié)設(shè)計(jì)了規(guī)模n=10,30,50的三組實(shí)驗(yàn)，每個規(guī)模下隨機(jī)生成50個算例，算例生成規(guī)則如表2所示，部分規(guī)則參考文獻(xiàn)[16]，算法采用Matlab 2014a 進(jìn)行編碼，運(yùn)行配置為CPU：Intel Corei7- 4790K 4.0GHz CPU，RAM：16GB， OS：Windows 7。

表2 算例規(guī)則

對比算法選擇了DE、自適應(yīng)混合差分進(jìn)化(Adaptive Hybrid Differential Evolution, AHDE)、FOA、粒子群優(yōu)化(Particle Swarm Optimization, PSO)，原因如下：文獻(xiàn)[16]已經(jīng)證實(shí)在解決復(fù)雜JRD問題時(shí)，DE具有較高的準(zhǔn)確性和穩(wěn)定性；文獻(xiàn)[17]將AHDE用于求解JRD也得到了較好的效果；FOA算法則在解決復(fù)雜JRD問題時(shí)得到了廣泛采用[15]；PSO則作為另一種性能優(yōu)異的群體智能算法也在解決JRP問題上展現(xiàn)出滿意的性能[18]。所有算法均運(yùn)行500代，種群大小都設(shè)置為100。HFOA參數(shù)設(shè)置如下：λ=0.5，ct=0.7，mu=0.1，F(xiàn)Pmin= 0.05，F(xiàn)Pmax= 0.95。其他算法參數(shù)設(shè)置可參考對應(yīng)文獻(xiàn)[16,17]。

各種算法在求解JR-LID問題時(shí)的收斂過程如圖5所示，可看出HFOA在各種規(guī)模下的實(shí)驗(yàn)都展現(xiàn)出了較好的性能，尤其是收斂速度遠(yuǎn)超其他算法。表3給出了各種規(guī)模下的算例結(jié)果，每次計(jì)算，取5個算法中最好的解作為最優(yōu)解來與其他算法比較。從表3可以看出，HFOA在準(zhǔn)確性和穩(wěn)定性上都有較好的表現(xiàn)，大多情況都能給出最優(yōu)的解，在沒有得到最優(yōu)的解的情況下，平均偏差也不超過0.25%，并且與標(biāo)準(zhǔn)FOA相比，新算法在準(zhǔn)確性上有了明顯的提高，在全部150次實(shí)驗(yàn)中，有143次(占比95.33%)HFOA給出的解比FOA都要更優(yōu)，這說明HFOA的改進(jìn)策略取得了較好的效果，不過與FOA相比，新算法的耗時(shí)也有一些增加，但與DE、AHDE、PSO相比，在準(zhǔn)確度方面還是具有比較優(yōu)勢，尤其是問題規(guī)模擴(kuò)大時(shí)這種優(yōu)勢更加明顯。

圖5 各種規(guī)模下的算法收斂圖

表3 各種規(guī)模算例的求解結(jié)果

4 結(jié)論

本文的主要貢獻(xiàn)如下：(1)將三階段JRD模型與JR-LIP模型相結(jié)合，構(gòu)建了一個補(bǔ)貨、選址、庫存、配送集成優(yōu)化的新模型，新模型具有一定的學(xué)術(shù)價(jià)值，同時(shí)模型貼合企業(yè)實(shí)際管理背景具有一定的實(shí)用價(jià)值；(2)設(shè)計(jì)了一種改進(jìn)的HFOA新算法，新算法通過引入進(jìn)化算法的信息交換、變異、選擇操作來增強(qiáng)局部尋優(yōu)能力，采取概率性的飛行策略來平衡算法的全局尋優(yōu)與局部尋優(yōu)，利用新算法對模型進(jìn)行求解，算例結(jié)果表明，新算法在準(zhǔn)確性和穩(wěn)定性上較標(biāo)準(zhǔn)FOA有了明顯提高，并且與DE、AHDE、PSO相比也具有優(yōu)勢，尤其是在大規(guī)模問題上，這種優(yōu)勢更加明顯。

本文屬于供應(yīng)鏈管理與智能優(yōu)化算法的交叉研究，新模型的提出不僅豐富了相關(guān)理論研究，更給企業(yè)實(shí)踐提供了一種可參考的科學(xué)決策方法，新算法也在解決該問題上展現(xiàn)出了良好的效果。未來擬在本模型的基礎(chǔ)上進(jìn)一步研究隨機(jī)需求下允許缺貨的情形并結(jié)合其他更現(xiàn)實(shí)性的約束條件，這樣模型將更加實(shí)用和復(fù)雜；針對HFOA仍然可能存在的早熟收斂的情況，擬結(jié)合粒子群優(yōu)化[19]、模擬退火、蛙跳等算法設(shè)計(jì)更加高效穩(wěn)定的混合智能算法。