基于自適應(yīng)遺傳算法的生鮮產(chǎn)品冷鏈物流配送中心選址研究

張亦弛，劉曉佳 （集美大學(xué)航海學(xué)院，福建 廈門 361000）

0 引 言

在一個(gè)物流網(wǎng)絡(luò)系統(tǒng)中，配送中心是非常重要的基礎(chǔ)設(shè)施，配送是最末端的環(huán)節(jié)，也是極為關(guān)鍵的環(huán)節(jié)。配送中心發(fā)揮著承上啟下的作用，對上承接來自發(fā)件網(wǎng)點(diǎn)貨物的集運(yùn)任務(wù)，對下承接收件網(wǎng)點(diǎn)的配送運(yùn)輸任務(wù)，其選址結(jié)果將會對配送路徑的規(guī)劃、運(yùn)營成本、配送效率等產(chǎn)生直接的影響。由于生鮮冷鏈產(chǎn)品具有價(jià)值高、需求大、易腐敗、不宜長時(shí)間儲藏的特點(diǎn)，所以對于生鮮冷鏈產(chǎn)品來說，其配送中心選址就顯得尤為重要。

張于賢等人[1]利用DEA 方法對已有配送中心的效率進(jìn)行評估，根據(jù)評估的結(jié)果代入選址分析模型中，得到物流配送中心再選址的DEA 評估規(guī)劃模型，以配送收益與物流成本之差作為目標(biāo)函數(shù)，以供需均衡關(guān)系、配送中心流出量與流入量平衡、選址變量與流量內(nèi)在聯(lián)系構(gòu)建約束條件，通過算例并借助于MATLAB 軟件驗(yàn)證了模型的有效性。宋瑞敏等人[2]提出一種基于布谷鳥搜索算法求解平面選址問題，仿真結(jié)果表明，該算法具有平衡全局優(yōu)化與局部搜索的優(yōu)點(diǎn)，但不適用于多目標(biāo)選址。生力軍[3]將量子進(jìn)化算法融入經(jīng)典粒子群算法中，采用量子理論中獨(dú)有的疊加態(tài)和概率幅特性，粒子最優(yōu)位置的搜尋采用量子自旋門完成，粒子位置的多樣性變異采用量子非門完成，以免出現(xiàn)局部最優(yōu)解和早熟收斂缺陷。李晶晶[4]運(yùn)用灰色GM 1,（ ）1 模型，預(yù)測太原市某地區(qū)未來五年的需求量，并分析降價(jià)銷售對顧客購買需求的影響，建立以滿足需求為前提、總成本最小為目標(biāo)的冷鏈配送中心選址模型，并用lingo 軟件求解。冉昊杰等[5]將遺傳算法與模擬退火算法融合，實(shí)現(xiàn)選址過程的整體優(yōu)化。這些研究中，大多對智能算法進(jìn)行了改進(jìn)，使其更加適用于選址問題。

在上述學(xué)者研究內(nèi)容的基礎(chǔ)上，本文將不同地段的建設(shè)價(jià)格、生鮮產(chǎn)品的運(yùn)輸途中變質(zhì)速度等因素考慮在內(nèi)，建立生鮮產(chǎn)品冷鏈物流配送中心選址模型，并采用自適應(yīng)的遺傳算法對模型求解。分析遺傳算法的原理和步驟，針對算例進(jìn)行編碼，通過仿真，得出配送中心的選址與分配。

1 模型假設(shè)與參數(shù)設(shè)定

1.1 模型假設(shè)

（1） 一個(gè)生產(chǎn)基地可以給多個(gè)配送中心供貨；

（2） 一個(gè)配送中心只能接收一個(gè)生產(chǎn)基地的貨物；

（3） 一個(gè)配送中心可以服務(wù)于多個(gè)需求網(wǎng)點(diǎn)；

（4） 一個(gè)需求網(wǎng)點(diǎn)只能被一個(gè)配送中心服務(wù)；

（5） 生產(chǎn)基地的供貨量不超過配送中心倉儲的最大容量；

（6） 配送中心的容量總和大于各需求網(wǎng)點(diǎn)的總需求量；

（7） 運(yùn)輸距離用單位運(yùn)輸成本體現(xiàn)，二者線性相關(guān)；

（8） 部分受運(yùn)輸儲存影響的商品仍可以降價(jià)出售。

運(yùn)輸過程如圖1 所示。

圖1 生鮮產(chǎn)品的運(yùn)輸基本流程

1.2 變量設(shè)定

本模型的變量及其釋義如表1 所示。

表1 模型變量及其釋義

2 模型構(gòu)建與算法

2.1 模型假設(shè)

本生鮮產(chǎn)品冷鏈物流配送中心選址模型涉及生產(chǎn)基地、配送中心、各需求網(wǎng)點(diǎn)這三層結(jié)構(gòu)；模型目標(biāo)是使得總成本最低，所考慮的3 個(gè)影響因素分別是：固定成本、運(yùn)輸成本、變質(zhì)成本。

（1） 固定成本：固定成本是冷鏈物流配送中心選址中起決定性作用的因素，它主要包括建設(shè)配送中心的土地費(fèi)用和建設(shè)費(fèi)用、冷鏈設(shè)備等大型機(jī)器的購置費(fèi)用、配送中心每個(gè)運(yùn)營周期所產(chǎn)生的維護(hù)費(fèi)用。同時(shí)，地理位置不同，地價(jià)也會改變。交通便利，地理位置優(yōu)越，環(huán)境良好的場地價(jià)格會高，反之則低。本文中固定成本由設(shè)備運(yùn)營成本和地段建設(shè)成本共同決定，二者都與配送中心的容量有關(guān)。引入θj作為反映地價(jià)高低的系數(shù)，引入b作為反映購置冷鏈設(shè)備和維護(hù)的成本系數(shù)，則配送中心的總固定成本可用如下公式表示。

（2） 運(yùn)輸成本：運(yùn)輸分為兩個(gè)階段，一是從生產(chǎn)基地到配送中心；二是從配送中心到各個(gè)需求網(wǎng)點(diǎn)。本文單位運(yùn)輸成本指每單位重量的生鮮商品的運(yùn)輸成本，運(yùn)輸距離越遠(yuǎn)，則單位運(yùn)輸成本越高。在確定運(yùn)輸線路的距離且不考慮交通擁堵和交通事故的情況下，假設(shè)運(yùn)輸成本與運(yùn)輸貨量成正比，可以得到如下公式。

（3） 變質(zhì)成本：生鮮商品的新鮮度是其最重要的屬性之一，直接影響商品的價(jià)格。在儲存和運(yùn)輸過程中，生鮮產(chǎn)品會因時(shí)間、溫度、擠壓等因素而不再新鮮，甚至?xí)冑|(zhì)。對于未完全腐敗，仍可以降價(jià)出售的生鮮產(chǎn)品，可以用變質(zhì)成本來計(jì)算其損耗。假設(shè)變質(zhì)成本與運(yùn)輸時(shí)間有關(guān)，根據(jù)文中的假設(shè)7，兩地之間的單位運(yùn)輸成本越高，兩地之間的距離就越遠(yuǎn)，從而運(yùn)輸?shù)臅r(shí)間就越長，商品越容易變質(zhì)。因此變質(zhì)成本與單位運(yùn)輸成本相關(guān)。生鮮產(chǎn)品變質(zhì)對成本損耗是實(shí)時(shí)變化且沒有特定標(biāo)準(zhǔn)來衡量的，本文引入變質(zhì)成本系數(shù)來表示生鮮產(chǎn)品的新鮮度隨運(yùn)輸距離長短而變化的速率。

其中：q為變質(zhì)成本系數(shù)。根據(jù)假設(shè)，對于新鮮度明顯降低的商品，其價(jià)格會降低，成本損失如下：

綜上所述，本模型的總成本C是C1,C2,C3之和，結(jié)合模型成本最小化的目標(biāo)，可以得到如下函數(shù)：

2.2 模型算法

自適應(yīng)遺傳算法（Adaptive Genetic Algorithm，AGA） 是對基本遺傳算法的一種改進(jìn)，它通過對遺傳參數(shù)的自適應(yīng)調(diào)整，大大提高了遺傳算法的收斂精度，加快了收斂速度。自適應(yīng)遺傳算法在保持群體多樣性的同時(shí)，保證了遺傳算法的收斂性。自適應(yīng)遺傳算法的遺傳參數(shù)是自適應(yīng)的，提高了基本遺傳算法的收斂速度和收斂精度。該算法的實(shí)現(xiàn)步驟如下：

Step1：編碼。將問題的候選解用染色體表示，實(shí)現(xiàn)解空間向編碼空間的映射過程。將空間的決策變量轉(zhuǎn)換成由基因按一定結(jié)構(gòu)組成的染色體。編碼方式有很多，如二進(jìn)制編碼、實(shí)數(shù)向量編碼、整數(shù)排列編碼、通用數(shù)據(jù)結(jié)構(gòu)編碼等。本文將采用二進(jìn)制編碼的方式，將十進(jìn)制的變量轉(zhuǎn)換成二進(jìn)制，用0 和1 組成的數(shù)字串模擬染色體，可以很方便地實(shí)現(xiàn)基因交叉、變異等操作。

Step2：種群初始化。產(chǎn)生由n條染色體（Chromosome） 組成的初始群體。群體（Population） 的規(guī)模（即n值） 設(shè)置的過小很可能會導(dǎo)致過早收斂，最終不能獲取到全局最優(yōu)解；而如果群體規(guī)模設(shè)置過大又會影響計(jì)算時(shí)間。

Step3：計(jì)算個(gè)體適應(yīng)度。利用適應(yīng)度函數(shù)（Fitness Function） 計(jì)算各個(gè)個(gè)體的適應(yīng)度大小。適應(yīng)度函數(shù)值越大，則種群中優(yōu)良基因作為父代基因遺傳到下一代的可能性越大；否則可能性越小。目標(biāo)函數(shù)為最小時(shí)，建立如下與目標(biāo)函數(shù)之間存在映射關(guān)系的適應(yīng)度函數(shù)：

Cmax為f（x）的最大值，并且會隨著遺傳的代數(shù)不斷變化。

Step4：選擇、交叉和變異。通過選擇、交叉、變異，產(chǎn)生出代表新的解集的群體。

（1） 選擇（Selection）：根據(jù)個(gè)體適應(yīng)度大小，按照優(yōu)勝劣汰的原則，淘汰不合理的個(gè)體。最常見的選擇方法是輪盤賭法，假設(shè)種群數(shù)目n, 某個(gè)個(gè)體其適應(yīng)度為fi, 則其被選中的概率為：

其中：n為種群規(guī)模，fi為個(gè)體i的適應(yīng)度。

（2） 交叉（Crossover）：將交叉算子作用于群體，對選中的成對個(gè)體，以某一概率交換它們之間的部分染色體，產(chǎn)生新的染色體，也叫做基因重組。如圖2 所示，即是最簡單的一種交叉。

圖2 遺傳算法中的交叉算子示例

交叉的概率決定著交叉算子操作效果的好與壞。交叉概率如果很大，會使得模型收斂速度過快，從而導(dǎo)致局部收斂；交叉概率如果很小，則收斂速度又會過慢。因此，本文引入自適應(yīng)交叉算子操作，計(jì)算過程中交叉概率會隨著適應(yīng)度函數(shù)值的不同而自動調(diào)整，其計(jì)算公式如下：

其中：Pc為自適應(yīng)交叉概率，fmax為群體中個(gè)體最大的適應(yīng)度函數(shù)值，favg為每代群體的平均適應(yīng)度函數(shù)值，f為產(chǎn)生交叉的兩個(gè)個(gè)體其中一個(gè)個(gè)體為較大的適應(yīng)度函數(shù)值，C1,2為區(qū)間（0,1）的常數(shù)。

（3） 變異（Mutation）：將變異算子作用于群體，對選中的個(gè)體，以某一概率改變某一個(gè)或一些基因值為其他的等位基因，類似于基因突變。如圖3 所示，即是最簡單的一種變異。

圖3 遺傳算法中的變異算子示例

當(dāng)變異概率過小時(shí)，不利于染色體新個(gè)體結(jié)構(gòu)的產(chǎn)生；當(dāng)變異概率過大時(shí)，染色體結(jié)構(gòu)遭到破壞的可能性會增大，遺傳算法搜索的有效性隨之降低。針對變異算子操作中的尋優(yōu)問題，本文引入自適應(yīng)變異算子操作，其計(jì)算公式如下。

其中：Pm為自適應(yīng)變異概率，C3,C4為區(qū)間（0,1）的常數(shù)。

Step5：循環(huán)操作并判斷終止。當(dāng)達(dá)到預(yù)先設(shè)定的最大迭代次數(shù)Tmax時(shí)，終止迭代。

3 算例分析

為了驗(yàn)證改進(jìn)的自適應(yīng)遺傳算法模型在生鮮冷鏈物流配送中心選址中的可靠性，本文結(jié)合算法模型設(shè)計(jì)了具體的算例，通過對算例的求解來驗(yàn)證遺傳算法模型在配送中心選址問題研究中的有效性和實(shí)用性。以廈門市某地為例，設(shè)生產(chǎn)基地共有3處，分別記為A1,A2,A3；可供選擇配送中心地址共有6 處，分別記為B1,B2,B3,B4,B5,B6；需求網(wǎng)點(diǎn)有12 處，分別為C1,C2,C3,C4,C5,C6,C7,C8,C9,C10,C11,C12。可供選擇的配送中心的容量和固定成本如表2 至表5 所示：

表2 可供選擇的配送中心的固定成本和最大容量

表3 各需求網(wǎng)點(diǎn)的需求量

表4 生產(chǎn)基地到配送中心的單位運(yùn)輸成本

表5 配送中心到需求網(wǎng)點(diǎn)的單位運(yùn)輸成本

設(shè)變質(zhì)成本系數(shù)q=0.005，生鮮產(chǎn)品單價(jià)p=25，采用自適應(yīng)遺傳算法，運(yùn)用MATLAB 編程進(jìn)行仿真, 具體參數(shù)為：初始種群規(guī)模N=100，設(shè)置最大迭代次數(shù)Mmax=1 000，基因交叉的概率Pi=0.7，基因變異的概率Pc=0.07，經(jīng)過求解，得出的結(jié)果如圖4 和表6、表7 所示。

圖4 MATLAB 仿真最優(yōu)解變化圖

表6 生產(chǎn)基地到配送中心的供貨仿真結(jié)果

表7 生配送中心到需求網(wǎng)點(diǎn)的分配仿真結(jié)果

配送中心B1為需求網(wǎng)點(diǎn)C1,C4,C6提供服務(wù)，配送中心B2為需求網(wǎng)點(diǎn)C7提供服務(wù)，配送中心B4為需求網(wǎng)點(diǎn)C5,C8,C9,C12提供服務(wù)，配送中心B6為需求網(wǎng)點(diǎn)C3,C10,C11提供服務(wù)，配送中心B3,B5將不被考慮。遺傳算法迭代了150 次左右時(shí)，解已經(jīng)趨于穩(wěn)定。

4 結(jié) 論

本文采用自適應(yīng)遺傳算法對生鮮產(chǎn)品冷鏈物流配送中心選址的問題進(jìn)行了研究，將影響選址的成本因素分為固定成本、運(yùn)輸成本和變質(zhì)成本，建立了生鮮產(chǎn)品冷鏈物流中心選址模型并用自適應(yīng)遺傳算法進(jìn)行求解，仿真結(jié)果表明該模型和算法可以較好地應(yīng)用于實(shí)際選址問題當(dāng)中。在構(gòu)建最小成本目標(biāo)函數(shù)時(shí)；地段價(jià)格系數(shù)來體現(xiàn)不同地段建設(shè)配送中心的地價(jià)不同；用單位運(yùn)輸成本來體現(xiàn)運(yùn)輸距離和運(yùn)輸時(shí)長；引入變質(zhì)成本系數(shù)來控制生鮮產(chǎn)品在運(yùn)輸途中變質(zhì)造成損失的速率。

由于配送中心選址是一個(gè)相對多樣且復(fù)雜的研究問題，本文在理論和實(shí)例研究部分還有諸多不足，有待進(jìn)一步深入研究。