人工蜂群算法在連鎖超市物流配送中的應(yīng)用案例綜述目錄TOC\o"1-2"\h\u30946人工蜂群算法在連鎖超市物流配送中的應(yīng)用案例綜述 142451.1改進(jìn)的人工蜂群算法流程 16651.1.1路徑編碼和解碼 1203231.1.2目標(biāo)函數(shù)和適應(yīng)度計算 2220011.1.3采蜜蜂鄰域搜索 3151551.1.4觀察蜂的選擇 5268891.2仿真實驗及結(jié)果分析 6110651.2.1數(shù)據(jù)介紹 6168771.2.2仿真環(huán)境和結(jié)果分析 7鑒于人工蜂群算法的優(yōu)點及其在優(yōu)化問題中的廣泛應(yīng)用，本文提出了一種采用序列編碼、解碼、鄰域搜索和交叉變異的人工蜂群算法模型。該模型將連鎖超市的可能配送路徑投影到排列空間，并利用采蜜蜂的鄰域搜索和偵查蜂的探測來尋找最優(yōu)路徑，同時引入遺傳算法對排列問題的交叉、變異策略，大大提升了模型的求解性能。1.1改進(jìn)的人工蜂群算法流程連鎖超市的物流配送問題是從所有可能的配送路徑中選擇一種最優(yōu)的配送方案，其可行解的范圍是非連續(xù)的。然而，傳統(tǒng)的人工蜂群算法無論采蜜蜂的鄰域搜索還是偵查蜂的生成初始蜜源操作都是針對連續(xù)的變量提出的，這對物流配送問題的離散問題并不適用?；诖耍疚膶鹘y(tǒng)的人工蜂群算法進(jìn)行改進(jìn)，通過借鑒遺傳算法的交叉、變異等操作，針對人工蜂群算法提出了一種新的鄰域搜索、蜂群變異策略。1.1.1路徑編碼和解碼本文利用序號編碼的方式對配送中心和超市進(jìn)行編碼和解碼操作。具體的，首先利用0來表示配送中心，則所有的超市對應(yīng)于集合S={1,?,N},其中N表示超市的個數(shù)。以5個超市為例對編碼進(jìn)行介紹，偵查蜂隨機生成排列{3,2,1,4,5}，這表示配送車輛從0開始依次經(jīng)過超市3、超市2、超市1，超市4和超市5，然后回到配送中心0。然而，由于配送車輛的的容量有限，所以該編碼并不是配送車輛的實際運輸路線。因此，對于任意編碼X={x1,x2,?,xN}Step1:配送車輛從配送中心出發(fā)，車輛的已經(jīng)裝載的貨物重量為CAPcur=CAPStep2:判斷若CAPcur≥demi,執(zhí)行Step3Step3:對當(dāng)前超市進(jìn)行配送。將超市xi放入實際解碼路徑Y(jié)中，即Y={Y,xi}，車輛的當(dāng)前載重量Step4:回配送中心。此時解碼路徑Y(jié)={Y,0}，車輛的當(dāng)前載重量CAPcurStep5:當(dāng)i>N,表示此時已經(jīng)遍歷所有的超市，則配送車輛回到配送中心，此時Y={Y,0}。在實際蜂群算法中，偵查蜂生成N個超市的隨機排列作為初始蜜源。1.1.2目標(biāo)函數(shù)和適應(yīng)度計算針對任意蜜源，即任意的編碼方案X=x1,x2,?,xN，通過1.1.1得到解碼后的實際運輸方案X=y1,y2,?,yf本文中，fX表示蜜源X的目標(biāo)函數(shù)值。但是，由于適應(yīng)度應(yīng)該越大越好，所以對ffit在上式中，fitX表示蜜源X1.1.3采蜜蜂鄰域搜索由于傳統(tǒng)的采蜜蜂的鄰域搜索是針對連續(xù)性變量提出的，但是本文中的蜜源都是排列。根據(jù)遺傳算法提出的交叉、變異操作在組合優(yōu)化問題中取得很好的應(yīng)用，我們利用部分映射交叉和鄰域變異來執(zhí)行采蜜蜂的鄰域搜索。（1）部分映射交叉部分映射交叉的主要思想是，對于當(dāng)前蜜源X1，首先，采蜜蜂隨機選擇待交叉的蜜源X2。其次，隨機生成待交叉的區(qū)域，交換X1和X2對應(yīng)區(qū)域的排列。最后，建立映射表，消除交叉后重復(fù)的基因?，F(xiàn)以7個超市為例進(jìn)行介紹，令當(dāng)前的蜜源X1={3,2,4,6,1,7,5},隨機選擇的交叉蜜源為X2={1,7,5,2,6,4,3}。隨機選擇待交叉區(qū)域，比如待交叉的區(qū)域為3,4,5。此時交叉后的蜜源變成X1={3,2,5,2,6,7,5}，X2={1,7,4,6,1,4,3}。此時，需要建立的映射表為：4?5,6?2,1?6，即4?5,1?2。此時，將圖4-1-1部分映射交叉示意圖（2）鄰域變異鄰域變異的主要思想是：任意選擇兩個超市，改變兩個超市的位置，即完成鄰域變異操作?，F(xiàn)以7個超市為例進(jìn)行介紹，令當(dāng)前的蜜源X={3,2,4,6,1,7,5},首先，隨機選擇兩個位置比如2,5，交換這兩個位置上的對應(yīng)元素生成新的蜜源X={3,1,4,6,2,7,5}1.1.4觀察蜂的選擇當(dāng)所有的偵查蜂完成蜜源生成或者采蜜蜂完成鄰域搜索后，此時進(jìn)行蜜源解碼并生成運輸車輛的實際運輸方案。根據(jù)1.1.2所示的方法計算所有蜜源的適應(yīng)度。由于蜜量大的蜜源（即適應(yīng)度大的蜜源）具有較大的概率吸引觀察蜂前來采蜜。本文采用輪盤賭的方式進(jìn)行蜜源選擇。此時，蜜源X被選擇的概率為：PX由上式可以看出，當(dāng)Fit(X)越大表示該蜜源具有較大的概率被選中，進(jìn)而后代蜜源中可以保留更多的個體。適應(yīng)度較低的蜜源被選中的概率很小，逐漸被淘汰。綜上，給出人工蜂群算法求解連鎖超市的物流配送流程如下：人工蜂群算法物流配送流程圖人工蜂群算法物流配送流程圖1.2仿真實驗及結(jié)果分析根據(jù)以上的人工蜂群算法流程，結(jié)合實際的超市配送問題進(jìn)行求解并對結(jié)果進(jìn)行分析，主要包含以下步驟：數(shù)據(jù)介紹，仿真環(huán)境，模型求解和分析。1.2.1數(shù)據(jù)介紹我們隨機生成1個配送中心和50個連鎖超市的具體位置坐標(biāo)數(shù)據(jù)（見附件1），以及每個超市的需求量（見表1），配送車輛的載重Cap=40。表1連鎖超市的需求量表1連鎖超市的需求量超市12345678910需求1.11.61.42.130.22.62.13.30.6超市11121314151617181920需求1.93.23.640.62.71.82.524超市21222324252627282930需求3.23.31.61.81.41.73.223.52.4超市31323334353637383940需求1.61.52.93.43.91.91.93.82.11.7超市41424344454647484950需求0.42.22.31.81.90.92.451.73.1為了觀察配送中心和連鎖超市的相對位置，我們畫出連鎖超市和配送中心的具體位置，如圖4-2-1所示。圖4圖4-2-1超市和配送中心的實際位置1.2.2仿真環(huán)境和結(jié)果分析為了驗證改進(jìn)的人工蜂群算法的有效性，實驗以電腦配置為i5-8250MCPU,3.83G可用內(nèi)存電腦，MTALABR2018為編程平臺，利用隨機生成配送路徑和人工蜂群算法的配送路徑進(jìn)行對比。人工蜂群算法的最大迭代代數(shù)maxcycle=200，蜜源停留的最大代數(shù)limit=50，蜜源的個數(shù)NS=100。首先，我們隨機生成可行蜜源為：3→19→37→40→9→27→48→47→1325→20→22→4→30→5→29→39→49→33→10→32→7→46→12→35→11→4→15→2→18→17→38→8→16→31→24→6→43→26→23→50→21→44→36→1→41→28→34→14→42，解碼后得到的配送車輛的運輸方案：0→319→37→40→9→27→48→47→13→2→20→22→0→4→30→25→29→3949→33→10→32→7→46→12→35→11→0→45→15→2→18→17→38→8→16→31→24→6→43→26→0→23→50→21→44→36→1→41→28→34→14→42→0車輛回配送中心的次數(shù)為：5-1=4次對應(yīng)的實際配送距離為：5100.1。對應(yīng)的配送路徑如下圖所示：圖4圖4-2-2隨機方案的實際配送路徑其次，通過人工蜂群算法得到的最優(yōu)蜜源為：2→38→47→15→50→3020→18→28→2→3→46→10→35→11→43→12→19→27→34→29→39→8→42→4→44→26→48→13→31→33→37→45→23→1→41→14→24→7→9→17→6→5→25→49→32→36→16→40→22對應(yīng)的配送方案為：0→2→38→47→15→50→30→20→18→28→21→3→46→10→35→11→43→12→0→19→27→34→29→39→8→42→4→44→26→48→13→0→31→33→37→45→23→1→41→14→2→7→9→17→6→0→5→25→49→32→36→16→40→22→0車輛回配送中心的次數(shù)為：5-1=4次車輛的行駛里程為：2