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

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

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

1 配送成本模型

1.1 模型假設(shè)

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

1.2 符號(hào)說(shuō)明

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

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

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

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

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

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

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

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

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

2.1 算法改進(jìn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算例

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

表2 各客戶節(jié)點(diǎn)的需求量和時(shí)間窗

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

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

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

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

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

4 結(jié)語(yǔ)

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