基于自適應(yīng)Memetic算法的多級(jí)多商品物流網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)

張光平

（貴州電子信息職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)科學(xué)系，貴州 凱里 556000）

1 引言

物流網(wǎng)絡(luò)包含了物流網(wǎng)絡(luò)中相互作用的組織和設(shè)施。物流網(wǎng)絡(luò)的結(jié)構(gòu)直接決定了物流網(wǎng)絡(luò)的效率，與此同時(shí)，企業(yè)物流網(wǎng)絡(luò)的好壞又在一定范圍內(nèi)代表企業(yè)的綜合管理水平。因此，物流網(wǎng)絡(luò)引起了眾多研究者越來越多的關(guān)注，目前已成為物流系統(tǒng)設(shè)計(jì)中極為關(guān)鍵的一步。然而，當(dāng)前的物流網(wǎng)絡(luò)往往針對(duì)固定的三層或四層的單一商品流進(jìn)行物流網(wǎng)絡(luò)的設(shè)計(jì)，不能更好地適應(yīng)多商品流或網(wǎng)絡(luò)結(jié)構(gòu)拉長(zhǎng)的問題，若根據(jù)情況不斷建立新模型，又增加了物流過程中的建模難度，使得物流配送過程效率低，成本高。

根據(jù)上述情況，本文提出了一種更符合實(shí)際的多級(jí)多商品物流網(wǎng)絡(luò)結(jié)構(gòu)，在建立與實(shí)際情況更符合的物流網(wǎng)絡(luò)模型的基礎(chǔ)上，采用群集智能的方法解決該模型的優(yōu)化問題。所設(shè)計(jì)的多商品物流網(wǎng)絡(luò)與優(yōu)化模型可以根據(jù)多商品流的物流狀況，最大化減少網(wǎng)絡(luò)的存儲(chǔ)費(fèi)用、運(yùn)輸費(fèi)用和建設(shè)費(fèi)用等，設(shè)計(jì)出可解決一般性的多級(jí)多商品物流網(wǎng)絡(luò)設(shè)計(jì)問題并含約束條件的優(yōu)化模型，該模型適用于任意層的物流網(wǎng)絡(luò)（實(shí)際應(yīng)用中層級(jí)數(shù)不小于3），最后利用相應(yīng)的算法框架解決該模型的優(yōu)化問題。

2 多商品物流網(wǎng)絡(luò)數(shù)學(xué)建模

物流網(wǎng)絡(luò)是一個(gè)相互聯(lián)系的組織和設(shè)施集合的結(jié)構(gòu)，其目的是符合客戶需要，提高企業(yè)競(jìng)爭(zhēng)力。物流網(wǎng)絡(luò)的優(yōu)化能夠給用戶越來越多的依賴，越來越靈活的適應(yīng)日益增長(zhǎng)的需求。目前三級(jí)物流網(wǎng)絡(luò)應(yīng)用最為廣泛，但只適用于節(jié)點(diǎn)數(shù)目少或者節(jié)點(diǎn)集中的地區(qū)。隨著物流網(wǎng)絡(luò)越來越復(fù)雜，商品流向少批量、多批次的方向發(fā)展，原來的物流網(wǎng)絡(luò)會(huì)造成物流運(yùn)輸成本增加，運(yùn)輸頻率提高，造成嚴(yán)重的經(jīng)濟(jì)損失。因此，企業(yè)迫切需要設(shè)計(jì)一種合理的多級(jí)多商品物流網(wǎng)絡(luò)，可根據(jù)每一級(jí)物流網(wǎng)絡(luò)的任務(wù)和設(shè)施條件有區(qū)別地設(shè)計(jì)物流網(wǎng)絡(luò)。

圖1 多商品物流網(wǎng)絡(luò)

圖1就是一種典型的多級(jí)物流網(wǎng)絡(luò)。網(wǎng)絡(luò)中選擇合理的地點(diǎn)，再根據(jù)流量密度和交通運(yùn)輸方向來建立適當(dāng)規(guī)模的物流節(jié)點(diǎn)，在節(jié)點(diǎn)處對(duì)集中到此的商品進(jìn)行統(tǒng)一管理，最后通過最佳模式將商品運(yùn)輸至下一層節(jié)點(diǎn)，直到商品抵達(dá)目的地。

本文中多商品物流網(wǎng)絡(luò)數(shù)學(xué)建模問題涉及變量定義如下[2]：

N：多級(jí)多商品物流網(wǎng)絡(luò)的級(jí)數(shù)，實(shí)際問題中通常取N≥3；

：需求點(diǎn)i對(duì)商品l的需求量；

：第n(2 ≤n≤N)級(jí)的第i個(gè)物流網(wǎng)點(diǎn)的建設(shè)費(fèi)用；

Wn：第n級(jí)的建設(shè)數(shù)目；

：第n級(jí)第i個(gè)網(wǎng)點(diǎn)流通和存儲(chǔ)的能力；

：商品l在第n級(jí)第i個(gè)網(wǎng)點(diǎn)的存儲(chǔ)費(fèi)用；

：商品l從第n(n≤N-1)級(jí)第i個(gè)網(wǎng)點(diǎn)流到第n+1 級(jí)第j個(gè)網(wǎng)點(diǎn)的運(yùn)輸費(fèi)用；

：商品l在第n級(jí)第i個(gè)網(wǎng)點(diǎn)的可變存儲(chǔ)成本；

：第n(n≤N-1)級(jí)第i個(gè)網(wǎng)點(diǎn)處商品l的數(shù)量（流通量）；

：商品l從第n(n≤N-1)級(jí)的第i個(gè)網(wǎng)點(diǎn)流到第n+1級(jí)第j個(gè)網(wǎng)點(diǎn)的商品數(shù)；

Mn：第n級(jí)網(wǎng)點(diǎn)處產(chǎn)品的最大數(shù)目。

此外，定義二值變量Xn i代表是否決定修建第n級(jí)第i個(gè)網(wǎng)絡(luò)（修建時(shí)為1，相反為0），實(shí)際中若第n級(jí)第i個(gè)網(wǎng)點(diǎn)的流通量=0，則=0，否則=1，L為商品數(shù)目。二值變量取為0 代表第n 級(jí)節(jié)點(diǎn)對(duì)商品l 的需求由第n+1 個(gè)級(jí)節(jié)點(diǎn)j決定，反之取1。

另外所做的假設(shè)如下：

（1）多層多商品物流網(wǎng)絡(luò)末端需求點(diǎn)的數(shù)量必須小于企業(yè)生產(chǎn)的商品數(shù)目，也就是說，商品數(shù)滿足市場(chǎng)的需求；換一種表示方式為：第n級(jí)第i個(gè)網(wǎng)點(diǎn)處是無(wú)窮大的。

（2）物流網(wǎng)點(diǎn)處不需要商品，也就是網(wǎng)點(diǎn)i處Vi為0。

（3）一個(gè)需求點(diǎn)處的商品只由一個(gè)網(wǎng)點(diǎn)提供。

（4）位于網(wǎng)絡(luò)結(jié)構(gòu)起始級(jí)的一個(gè)工廠只生產(chǎn)一種產(chǎn)品，若一個(gè)工廠生產(chǎn)多種產(chǎn)品，則該產(chǎn)品的物流網(wǎng)絡(luò)起始點(diǎn)為對(duì)應(yīng)的若干工廠。

由此可知，物流網(wǎng)絡(luò)各級(jí)流通量為：

在多層多商品物流網(wǎng)絡(luò)中，起點(diǎn)和終點(diǎn)的位置確定，設(shè)計(jì)該物流網(wǎng)絡(luò)的過程就是每個(gè)節(jié)點(diǎn)的多重選址問題。換言之，就是在各種約束條件下選擇最佳的中心地址，設(shè)計(jì)的目標(biāo)是在最少的成本下滿足用戶要求。

3 多商品物流網(wǎng)絡(luò)模型優(yōu)化設(shè)計(jì)

在多級(jí)多商品物流網(wǎng)絡(luò)的優(yōu)化設(shè)計(jì)中，通常以總費(fèi)用最低作為優(yōu)化的目標(biāo)函數(shù)。正常物流業(yè)務(wù)費(fèi)用包括庫(kù)存費(fèi)用、運(yùn)輸費(fèi)用、建設(shè)費(fèi)用等。其中運(yùn)輸和庫(kù)存的比重大。

（1）目標(biāo)函數(shù)設(shè)計(jì)。多級(jí)多商品物流網(wǎng)絡(luò)的費(fèi)用主要包含庫(kù)存費(fèi)用、運(yùn)輸費(fèi)用和建設(shè)費(fèi)用：

①庫(kù)存費(fèi)用：庫(kù)存費(fèi)用含不變和可變庫(kù)存費(fèi)用。其中，不變庫(kù)存費(fèi)用為，可變庫(kù)存費(fèi)用可由鮑姆沃夫方法得到為，參數(shù)0 ≤θ≤1 的值和物流網(wǎng)絡(luò)節(jié)點(diǎn)的規(guī)模相關(guān)。

②運(yùn)輸費(fèi)用：商品從生產(chǎn)點(diǎn)到需求點(diǎn)過程中產(chǎn)生的所有費(fèi)用，計(jì)算公式為

③建設(shè)費(fèi)用：建設(shè)費(fèi)用產(chǎn)生在網(wǎng)絡(luò)建設(shè)的初期，一次性支付，是建設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)的基本費(fèi)用，其計(jì)算公式為

（2）約束條件設(shè)計(jì)。設(shè)計(jì)物流網(wǎng)絡(luò)的過程中，需要滿足以下的約束條件：

①網(wǎng)絡(luò)節(jié)點(diǎn)的能力約束。節(jié)點(diǎn)的能力范圍是任意中間的節(jié)點(diǎn)，經(jīng)過其的商品數(shù)換成的能力之和不能超過其處理的能力，也就是：

②網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)量限制。出于對(duì)前期建設(shè)費(fèi)用的考慮，需要限制網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)目，約束條件為：

③物流網(wǎng)點(diǎn)的等量限制。對(duì)于任意的物流網(wǎng)絡(luò)節(jié)點(diǎn)，從上級(jí)流入的商品數(shù)應(yīng)等于流向下級(jí)的商品數(shù)。該限制可以寫成：

④非負(fù)限制。一些變量如、等不能為負(fù)數(shù)。

（3）多商品物流網(wǎng)絡(luò)優(yōu)化模型構(gòu)建。假設(shè)建立物流網(wǎng)絡(luò)的總費(fèi)用為Ψ，該優(yōu)化模型為：

4 基于自適應(yīng)Memetic 算法的多商品物流網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)實(shí)現(xiàn)

1975 年J.Holland 教授提出遺傳算法，該算法被廣泛用在優(yōu)化領(lǐng)域，尤其適用于較大規(guī)模的優(yōu)化組合問題。遺傳算法遵循“適者生存”的原則，指導(dǎo)染色體的逐代進(jìn)化（含選擇、交叉和突變等），實(shí)現(xiàn)個(gè)體適應(yīng)性的提高。其特點(diǎn)是可直接對(duì)結(jié)構(gòu)對(duì)象操作，沒有求導(dǎo)和函數(shù)連續(xù)性的約束，不需要輔助信息；易于并行化和全局尋找最優(yōu)解的能力；通過概率化的尋優(yōu)方式，具有內(nèi)在的啟發(fā)式隨機(jī)搜索的特點(diǎn)，可以自適應(yīng)地搜索，不需要確定的規(guī)則。然而，遺傳算法存在運(yùn)算時(shí)間長(zhǎng)、可能陷入局部最優(yōu)的缺點(diǎn)。Memetic 算法是最近一種非常有效的群集智能優(yōu)化算法，它將遺傳算法的全局搜索與局部搜索相結(jié)合，其數(shù)學(xué)模型定義如下：

其中：

C：個(gè)體的編碼方式；

E：個(gè)體適應(yīng)度的評(píng)價(jià)函數(shù)；

M：種群大??；

Γ：交叉算子；

Ψm：變異算子；

Φ：選擇算子；

Β：局部搜索算子；

T：終止條件。

由于多級(jí)多商品物流網(wǎng)絡(luò)費(fèi)用函數(shù)的優(yōu)化是一個(gè)非常復(fù)雜的問題，本文提出基于自適應(yīng)算子的新的自適應(yīng)Memetic算法。自適應(yīng)算子具體介紹如下：

（1）自適應(yīng)度值調(diào)整。Memetic 算法不斷收斂時(shí)，繼續(xù)優(yōu)化的困難增大，使得最優(yōu)解附近搖擺不定。為提高選擇力，應(yīng)放大個(gè)體適應(yīng)度值。標(biāo)定適應(yīng)度值公式:

其中，f為初始適應(yīng)度值，f'為調(diào)整后的適應(yīng)度值，fmax和fmin分別為適應(yīng)度值的上下界，0 ＜α＜1。

由圖2可知，角度α隨著fmax和fmin的差值增大而變小，防止了超常個(gè)體過多，縮小了標(biāo)定后的適應(yīng)度值變化范圍；反之α變大，拉開群體中個(gè)體之間的差距，增大標(biāo)定后的適應(yīng)度值變化范圍，以盡快得到最優(yōu)解。適應(yīng)度值隨實(shí)際情況發(fā)生變化，加快了獲得問題最優(yōu)解的速度。

圖2 標(biāo)定后的適應(yīng)度值隨種群適應(yīng)度差值的變化關(guān)系

（2）群體多樣化。若不限制較大概率成為局部最優(yōu)解的高適應(yīng)度值個(gè)體，算法在初始設(shè)置不合理的狀況下容易陷入局部最優(yōu)。為解決這類問題，本文引入群里多樣化的定義。該方法是在對(duì)個(gè)體選擇之前，比較每?jī)蓚€(gè)個(gè)體在相同地方的相同基因的數(shù)目，定為R，將R是否大于個(gè)體的一般作為是否相似的分界點(diǎn)[6]。選擇不相似的個(gè)體組合到一起構(gòu)成新群體。

綜上所述，所設(shè)計(jì)的自適應(yīng)Memetic 算法的流程如圖3所示。

圖3 自適應(yīng)Memetic算法流程圖

將上述自適應(yīng)Memetic算法應(yīng)用于物流網(wǎng)絡(luò)模型，可利用自適應(yīng)Memetic設(shè)置多層多商品網(wǎng)絡(luò)優(yōu)化模型的初始參數(shù)，分析每一種商品并按需求配送。目前的算法只針對(duì)3級(jí)物流網(wǎng)絡(luò)，而對(duì)于求解多級(jí)多商品的物流網(wǎng)絡(luò)初始解，需要使用更多空間和多次迭代，也就是說按照先前的算法，計(jì)算第一、二級(jí)組成的物流網(wǎng)絡(luò)的初始解，再將第二級(jí)中的物流網(wǎng)點(diǎn)作為假定用戶點(diǎn)，再計(jì)算第二、三級(jí)組成的多商品物流網(wǎng)絡(luò)的初始解，一直劃分與迭代，直到解出所有網(wǎng)絡(luò)節(jié)點(diǎn)的分配決策變量。其框架為：

（1）劃分尋優(yōu)空間，按個(gè)體適應(yīng)度值的大小排序。

（2）計(jì)算自適應(yīng)適應(yīng)度，選出適應(yīng)度值大于個(gè)體平均適應(yīng)度的個(gè)體。

（3）除去最高適應(yīng)度個(gè)體的相似個(gè)體。

（4）重復(fù)（3），選出與適應(yīng)度值最高的個(gè)體不相似的個(gè)體組成新群體。

（5）若群體規(guī)模不滿足規(guī)定，那么將除去的個(gè)體按適應(yīng)值大小依次填補(bǔ)所缺數(shù)量。

（6）判斷是否結(jié)束，若是則結(jié)束，否則將前規(guī)定值個(gè)體所在的字符串子空間作為新的尋優(yōu)空間，進(jìn)行步驟（1）。若全局最優(yōu)解在邊界處，則移動(dòng)尋優(yōu)空間再進(jìn)行步驟（1）。

下面通過實(shí)證分析驗(yàn)證方法的有效性，在本案例中N=3，

在本文所提出的Memetic 算法中，種群數(shù)目M為150，交叉為簡(jiǎn)單交叉，交叉概率為0.7，變異為單點(diǎn)變異，變異概率為0.4，初始的種群采用隨機(jī)初始化，局部搜索采用最速梯度下降，在相同的規(guī)模下對(duì)比了所提出的自適應(yīng)Memetic算法與標(biāo)準(zhǔn)遺傳算法的性能。尋找到最優(yōu)解所需要的最大迭代次數(shù)Max與最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)見表1。從結(jié)果可以看出，自適應(yīng)Memetic 算法相比標(biāo)準(zhǔn)遺傳算法，不僅能夠找到更優(yōu)的解，而且具有更快的收斂速度。

表1 網(wǎng)絡(luò)優(yōu)化結(jié)果對(duì)比分析

5 結(jié)語(yǔ)

隨著企業(yè)規(guī)模的增大，其商品的配送方式和客戶的定位也更復(fù)雜化，為了降低物流成本，且滿足企業(yè)的需要，設(shè)有約束條件的多級(jí)多商品物流分配網(wǎng)絡(luò)應(yīng)運(yùn)而生。本文設(shè)計(jì)了一種新的基于自適應(yīng)Memetic算法的多商品物流網(wǎng)絡(luò)。一方面，自適應(yīng)Memetic 算法框架可有效解決帶有約束條件的多級(jí)網(wǎng)絡(luò)尋找全局最優(yōu)解的問題；另一方面，算法中的局部搜索與自適應(yīng)算子大大降低了群集算法陷入局部極值點(diǎn)的可能性，并且加速了搜索，使得快速高效的實(shí)際復(fù)雜物流網(wǎng)絡(luò)的優(yōu)化成為可能，因此在多商品物流網(wǎng)絡(luò)設(shè)計(jì)上具有較好的應(yīng)用前景。

[1]徐磊.基于遺傳算法的多目標(biāo)優(yōu)化問題的研究與應(yīng)用[D].長(zhǎng)沙:中南大學(xué),2007.

[2]張哲.基于遺傳算法的多商品物流網(wǎng)絡(luò)設(shè)計(jì)的研究[D].大連:大連海事大學(xué),2012.

[3]高自友,孫會(huì)君.現(xiàn)代物流與交通運(yùn)輸系統(tǒng)[M].北京:人民交通出版社,2003.

[4]Gen M,Cheng R.Genetic algorithms and engineering optimization[M].New York,N Y,USA:John Wiley & Sons,2000.

[5]曹友道.基于改進(jìn)遺傳算法的應(yīng)用研究[D].合肥:安徽大學(xué),2010.

[6]Jaramillo,Bhadury, Batta.On the use of genetic algorithms to solve location problems[J].Computers&Operations Research,2002,29(6):761-779.