基于改進(jìn)人工蜂群算法的生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化

汪 濤，潘 郁，潘 芳，朱曉峰

（1.南京工業(yè)大學(xué)經(jīng)濟(jì)與管理學(xué)院，江蘇 南京 211816；2.南京中醫(yī)藥大學(xué)衛(wèi)生經(jīng)濟(jì)管理學(xué)院，江蘇 南京 210023）

經(jīng)濟(jì)快速發(fā)展，生活水平提高，人們對生鮮農(nóng)產(chǎn)品的質(zhì)量提出了更高要求。生鮮農(nóng)產(chǎn)品是指由農(nóng)戶生產(chǎn)、養(yǎng)殖的初級農(nóng)畜產(chǎn)品，主要包括新鮮肉蛋奶、蔬菜、水果、水產(chǎn)品，活禽五類產(chǎn)品，常溫下易變質(zhì)，對時間因素具有較強的敏感性［1］。合理高效的配送路徑，一方面大大降低了配送成本，使商家和農(nóng)戶獲得更高的利潤；另一方面，高效率配送大大縮短生鮮農(nóng)產(chǎn)品的配送時間，使得農(nóng)產(chǎn)品的質(zhì)量得以保證，從而提高了客戶的滿意度。因此，在生鮮農(nóng)產(chǎn)品配送系統(tǒng)中，需要采取更合理高效的配送策略，實現(xiàn)高效率、低成本的物流配送。

近年來，由于生鮮農(nóng)產(chǎn)品的配送路徑優(yōu)化研究具有較強的實踐性和理論性，國內(nèi)外學(xué)者對該問題進(jìn)行了大量研究。Hsu等［2］以固定成本、運輸成本、庫存成本和懲罰成本構(gòu)建最小化成本目標(biāo)函數(shù)，提出了利用VRPTW模型優(yōu)化配送路徑問題；Osvald等［3］提出帶時間窗的新鮮蔬菜配送車輛路徑優(yōu)化的數(shù)學(xué)模型，并通過禁忌搜索的啟發(fā)式算法來進(jìn)行求解；趙秀榮等［4］分析當(dāng)前我國生鮮農(nóng)產(chǎn)品冷鏈物流配送的現(xiàn)狀及干擾因素，提出構(gòu)建大型冷鏈物流配送中心、銷地冷鏈物流共同配送聯(lián)盟和"一站式"冷鏈配送網(wǎng)絡(luò)信息平臺等策略；Dabbene等［5］考慮到鮮活農(nóng)產(chǎn)品的易腐特性，以最大程度保證鮮活農(nóng)產(chǎn)品的品質(zhì)和嚴(yán)格控制配送成本作為目標(biāo)，對鮮活農(nóng)產(chǎn)品供應(yīng)鏈流程加以優(yōu)化；康凱等［6］構(gòu)建了考慮碳排放的生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化模型，提出一種結(jié)合2-opt局部搜索機(jī)制的改進(jìn)蟻群算法，并用實例對模型及算法的有效性進(jìn)行驗證，同時對算法參數(shù)進(jìn)行了敏感性分析；JuChia等［7］考慮到生鮮農(nóng)產(chǎn)品對溫度的敏感性，提出一種針對該問題的多溫度共同配送物流模式，并通過相應(yīng)的算例驗證了該模式的合理性與有效性；Brito等［8］利用模糊方法來求解冷凍食品的配送路徑優(yōu)化問題，最終效果良好，且可以有效避免冷鏈的斷裂；呂俊杰等［9］從物流配送商的角度出發(fā)，構(gòu)建基于冷藏車能耗成本分析的路徑優(yōu)化模型，應(yīng)用蟻群算法和MATLAB工具論證了模型的有效性；但斌等［10］以拼好貨為例，分析得出生鮮農(nóng)產(chǎn)品供應(yīng)鏈C2B商業(yè)模式的實現(xiàn)路徑包括產(chǎn)品與服務(wù)、供應(yīng)鏈管理策略、市場營銷策略、關(guān)鍵流程構(gòu)建以及核心能力優(yōu)化等因果關(guān)聯(lián)的五大要素；孫明明等［11］針對生鮮農(nóng)產(chǎn)品冷鏈物流的特殊性，分析和定義冷鏈物流配送過程中的時間、溫度和貨損成本，建立配送總成本最小化模型；丁秋雷等［12］分析了干擾事件對生產(chǎn)商、客戶和物流配送運營商3個行為主體的影響，提出鮮活農(nóng)產(chǎn)品物流配送的干擾管理模型，取得了良好的優(yōu)化效果；張文峰等［13］同時考慮到冷鏈物流的網(wǎng)點布局問題和運輸配送問題，提出了以冷鏈物流運輸成本和網(wǎng)點運營成本為優(yōu)化目標(biāo)的非線性整數(shù)規(guī)劃模型，并采用量子粒子群算法進(jìn)行求解；朱佳祥等［14］考慮到生鮮農(nóng)產(chǎn)品市場需求的時變性、模糊不確定性特點，以“多供應(yīng)點選擇”與“最早分發(fā)”為優(yōu)化目標(biāo)構(gòu)建了模糊決策模型，有效解決了因市場需求信息模糊導(dǎo)致的配送成本增加問題。

通過對比發(fā)現(xiàn)，上述研究在構(gòu)建模型時均存在生鮮農(nóng)產(chǎn)品配送成本考慮不全的問題。大多研究都采用固定成本、運輸成本和懲罰成本作為配送總成本，沒有考慮隨著時間推移，鮮活農(nóng)產(chǎn)品本身也會產(chǎn)生損耗成本。鑒于此，本研究結(jié)合時間價格成本、固定成本、運輸成本和懲罰成本，將鮮活農(nóng)產(chǎn)品在運輸過程中的時間價格成本考慮進(jìn)來，構(gòu)建一個求解鮮活農(nóng)產(chǎn)品配送總成本最小的數(shù)學(xué)模型。在研究過程中，采用改進(jìn)后的人工蜂群算法進(jìn)行求解，避免了模型過早陷入局部最優(yōu)的問題，加速了模型的收斂過程，具有更強的實踐指導(dǎo)作用。

1 配送成本模型

1.1 模型假設(shè)

鮮活農(nóng)產(chǎn)品物流配送模型是由1個配送中心向多個客戶節(jié)點進(jìn)行貨物配送的模型。為簡化模型，本研究作出如下假設(shè)：（1）配送中心有充足的配送車輛和貨源，且每輛車的裝載 重量、配送速度相同；（2）客戶需求量已知，且單一客戶的需求量不得高于車輛最大載重量；（3）客戶需求以及配送中心配送產(chǎn)品相同且只有一種；（4）每輛車可對路徑上任意客戶進(jìn)行配送，每個客戶需求由一輛車完成配送；（5）模型只針對一個配送中心向其他客戶節(jié)點進(jìn)行配送。

1.2 符號說明

模型參數(shù)及其含義如表1所示。

1.3 成本模型構(gòu)建

以生鮮農(nóng)產(chǎn)品物流配送總成本作為最小化目標(biāo)函數(shù)構(gòu)建數(shù)學(xué)模型，總成本主要由固定成本、運輸成本、懲罰成本和時間價格成本4個部分組成，其中固定成本為C1，而運輸成本是生鮮農(nóng)產(chǎn)品在向各個客戶節(jié)點的運輸過程中產(chǎn)生的費用，與車輛數(shù)量以及每輛車的配送距離成正比，運輸成本計算公式為：

式中，Ck為車輛配送時單位里程的運輸成本，xijk為變量0-1，當(dāng)運輸車輛從經(jīng)過客戶節(jié)點（i，j）時，xijk取值為1，否則為0。

懲罰成本的計算需要引入時間窗，時間窗分為軟時間窗和硬時間窗，本研究模型中采用軟時間窗，軟時間窗比硬時間窗在時間范圍內(nèi)更具有彈性，當(dāng)產(chǎn)品在客戶期望時間內(nèi)送達(dá)，懲罰成本為0；當(dāng)產(chǎn)品不在客戶期望時間內(nèi)送達(dá)，按照時間懲罰函數(shù)來計算懲罰成本，M為單位時間懲罰費用，懲罰成本計算公式為：

考慮到隨著時間的推移，鮮活農(nóng)產(chǎn)品本身也會產(chǎn)生損耗成本，也就是時間價格成本，本研究不考慮運輸完成后產(chǎn)品的損耗問題，只考慮到達(dá)客戶節(jié)點i的時間和車輛出發(fā)時間， 再結(jié)合客戶i的產(chǎn)品需求量以及單位產(chǎn)品價格P進(jìn)行計算，時間價格成本計算公式為：

基于以上各類配送成本分析，建立配送總成本模型如下：

式（5）表示配送中心有充足的貨源來滿足所有客戶需求；式（6）表示一條配送路徑上的需求量之和不能超過車輛的最大載重量；式（7）和式（8）表示一個客戶只有一輛車進(jìn)行配送；式（9）表示每個客戶都能夠得到配送。

2 改進(jìn)人工蜂群算法求解

2.1 算法改進(jìn)

人工蜂群算法由埃爾吉耶斯大學(xué)學(xué)者Karaboga［15］首次提出。算法模擬蜜蜂采蜜過程，將蜜蜂分為3種：引領(lǐng)蜂、跟隨蜂和偵察蜂，蜜蜂尋找食物源的過程就是模型求解過程，每個食物源對應(yīng)物流配送路徑優(yōu)化問題中一個可行解，也就是一條路徑。算法工作分為以下3個階段，本研究分別對跟隨蜂和偵察蜂階段加以改進(jìn)，具體如下：

式中，vid為候選食物源，，rid為[-1,1]之間的隨機(jī)數(shù)。找到新的食物源之后，引領(lǐng)蜂采用貪心策略，若新食物源收益度高于當(dāng)前食物源，則替換原來的解； 反之保持不變，隨后引領(lǐng)蜂將收益度信息傳遞給跟隨蜂。

2.1.2 跟隨蜂階段 在傳統(tǒng)人工蜂群算法中，跟隨蜂通常采用輪盤賭策略選擇引領(lǐng)蜂，在這種策略下，適應(yīng)值越大則被選擇的概率也就越大，二者為線性關(guān)系，導(dǎo)致跟隨蜂容易迅速向某一適應(yīng)值高的食物源集中，從而使模型陷入局部最優(yōu)。因此，本研究提出一種基于中位數(shù)的引領(lǐng)蜂選擇策略來避免這個問題?；谥形粩?shù)選擇策略是以中間適應(yīng)值為基準(zhǔn)重新分配選擇概率，從而在不影響高適應(yīng)值食物源被選擇概率的情況下，使適應(yīng)值小的食物源也有被選擇的幾率。依據(jù)此策略跟隨蜂選擇引領(lǐng)蜂的概率公式如下：

式中，F(xiàn)i為第i個食物源的適應(yīng)值，F(xiàn)mid為食物源適應(yīng)值中位數(shù)，SN為表食物源的數(shù)量。通過改進(jìn)后，有效提高了收益度較小食物源被選擇的概率，同時不影響收益度較大的食物源被選擇的概率，保證了選擇的多樣性，避免因某一食物源被集中選擇導(dǎo)致局部最優(yōu)情況的出現(xiàn)。選擇引領(lǐng)蜂之后，跟隨蜂會計算引領(lǐng)蜂傳遞信息中食物源的收益度值，計算公式如下所示：

式中，代表食物源，也就是一個可行解，為目標(biāo)函數(shù)。

2.1.3 偵察蜂階段 如果算法執(zhí)行的搜索次數(shù)超過了設(shè)定值，某個食物源依舊保持不變，那么將拋棄這個食物源對應(yīng)的可行解，對應(yīng)的引領(lǐng)蜂變?yōu)閭刹榉?，開始新一輪的食物源搜索。這種更新方式導(dǎo)致上一輪的有效搜索信息沒有得到利用，使得算法存在一些迂回重復(fù)的搜索，導(dǎo)致算法效率偏低。鑒于此，本研究在新一輪的食物源搜索過程中引入禁忌表,將之前拋棄的食物源放入該禁忌表內(nèi),當(dāng)跟隨蜂在搜索過程中發(fā)現(xiàn)收益率值高的一組食物源后，首先查詢該解是否在禁忌表內(nèi)，如果是則放棄該可行解，除非滿足釋放準(zhǔn)則，否則記錄當(dāng)前解為最優(yōu)解。基于禁忌表的算法可行解更新流程如圖1所示。

圖1中，L為搜索次數(shù)，t為禁忌表長度參數(shù)，表示禁忌對象不被選取的最大迭代次數(shù)，t ＞ SN本文取釋放準(zhǔn)則為，表示當(dāng)禁忌對象被禁次數(shù)超過食物源總數(shù)時，該對象即被解禁。禁忌表的引入，有效利用了上一輪搜索過程保留的食物源信息，避免了一些重復(fù)搜索，加速了算法的收斂。

2.2 改進(jìn)人工蜂群算法實求解步驟

將改進(jìn)后的算法對模型進(jìn)行求解，具體求解步驟如下：

步驟1：設(shè)定算法中初始化階段的各個參數(shù)，包括引領(lǐng)蜂、跟隨蜂以及偵察蜂的數(shù)量，搜索次數(shù)上限limit、迭代次數(shù)上限MaxCycle；

圖1 基于禁忌表的算法可行解更新流程

步驟3：根據(jù)式（10）生成算法初始解，并將初始解分配給對應(yīng)的引領(lǐng)蜂，根據(jù)式（4）和式（13）對計算各個初始解的收益度值；

步驟4：開始迭代，重復(fù)步驟5～11；

步驟5：引領(lǐng)蜂根據(jù)式（11）在解的鄰域內(nèi)進(jìn)行搜索，根據(jù)圖1所示流程進(jìn)行解的迭代更新；

步驟6：所有的解更新完成后，根據(jù)式（12）和式（13）計算引領(lǐng)蜂找到的解被跟隨蜂選擇的概率；

步驟7：根據(jù)步驟所選擇的解，跟隨蜂在該解對應(yīng)的鄰域內(nèi)根據(jù)式（10）搜索新的解，然后根據(jù)式（12）計算對應(yīng)的收益度值，再重復(fù)步驟5進(jìn)行解的更新；

步驟8：如果某個解的limit值達(dá)到設(shè)定上限，則將該解加入禁忌表，偵察蜂重新生成一個新的解；

步驟9：記錄當(dāng)前最優(yōu)解；

步驟10：迭代次數(shù)更新，cycle =cycle+1；

步驟11：判斷算法迭代次數(shù)cycle是否超過MaxCycle，若次數(shù)超過MaxCycle，算法結(jié)束，步驟中所記錄的解即為最優(yōu)解；若沒有超過則跳到步驟開始算法下一輪計算。

3 算例

本研究以某冷鏈物流公司配送中心作為研究對象，通過算例分析驗證模型和算法的有效性。該配送中心需向個客戶節(jié)點進(jìn)行生鮮農(nóng)產(chǎn)品的配送，配送中心農(nóng)產(chǎn)品存貨量為120 t，12個客戶總需求量為52 t，生鮮農(nóng)產(chǎn)品的單價P=10.2元，保鮮時間T=20 h，時間敏感因子η=3，單位時間懲罰費用M=50，車輛從配送中心出發(fā)的時間各個配送車輛型號相同。當(dāng)前市場每臺冷鏈配送車的月固定成本為3萬元左右，即日均約1000元，取固定成本C1=100元，車輛平均車速v=60 km/s，最大載重量為Qmax=15 t，單位里程的運輸成本元Ck=2.3 元/km。表2和表3分別為各個客戶節(jié)點的需求量和時間窗約束以及節(jié)點之間的距離。

表2 各客戶節(jié)點的需求量和時間窗

表3 各客戶節(jié)點之間的距離

本研究的實驗環(huán)境為臺式機(jī)，運行內(nèi)存8GB，64位Windows 7操作系統(tǒng)，算法采用MATLAB 7.0進(jìn)行仿真實驗，設(shè)定算法參數(shù)，仿真試驗重復(fù)執(zhí)行30次。整理匯總得到最終的配送情況如表4所示。從表4可以得出，完成全部客戶節(jié)點的配送任務(wù)需要的車輛數(shù)k=4，4輛車有1輛達(dá)到滿載，其余3輛的裝載率也在80%以上，4輛車總共行駛距離為768 km，本次配送的總成本為C1+C2+C3+C4=6454.4元，比初始解節(jié)約3 733.7元，且懲罰成本為0，說明取得了良好的配送效果。

表4 優(yōu)化后配送情況匯總

為驗證算法改進(jìn)的有效性，將算法改進(jìn)前后的求解過程進(jìn)行對比分析，結(jié)果見圖2。從圖2可以看出，傳統(tǒng)人工蜂群算法求解目標(biāo)函數(shù)值下降很快，但經(jīng)過八輪迭代后算法就陷入局部最優(yōu)值7 400左右，持續(xù)到40輪迭代算法陷入二次局部最優(yōu)，直到40輪迭代后才開始逼近最優(yōu)值，60輪左右收斂。而經(jīng)過改進(jìn)后的算法在10輪迭代后就逼近最優(yōu)解，并在其附近振蕩，迭代40輪算法收斂，最優(yōu)解為6 454.4元。說明在傳統(tǒng)人工蜂群算法中引入中位數(shù)選擇策略來代替原有的輪盤賭選擇策略后，有效解決了算法容易過早陷入局部最優(yōu)的問題，且在解的更新階段引入了禁忌表，加速了算法的收斂速度，因此改進(jìn)后的人工蜂群算法具有更強的模型求解能力，能夠解決生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化問題，有一定的實踐指導(dǎo)意義。

圖2 基于改進(jìn)人工蜂群算法的求解過程

4 結(jié)語

本研究在構(gòu)建生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化模型的基礎(chǔ)上，考慮到鮮活農(nóng)產(chǎn)品隨時間推移產(chǎn)生的損耗成本，即時間價格成本，并結(jié)合配送產(chǎn)生的固定成本、運輸成本和懲罰成本構(gòu)建目標(biāo)函數(shù)構(gòu)建數(shù)學(xué)模型。本研究采用改進(jìn)的人工蜂群算法對模型進(jìn)行求解，算法引入基于中位數(shù)的選擇策略替代輪盤賭選擇策略，解決了算法容易過早陷入局部最優(yōu)的問題，并且在解的更新階段引入禁忌表加速了算法的收斂速度，通過算例仿真實驗驗證了模型和算法的有效性。路徑優(yōu)化問題是NP問題，本研究只考慮了單一配送中心的配送路徑優(yōu)化問題，且只考慮到單一農(nóng)產(chǎn)品，如何解決多個配送中心同時配送多類產(chǎn)品的路徑優(yōu)化問題還有待進(jìn)一步研究。