基于改進人工蜂群算法的生鮮農產品配送路徑優化

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

（1.南京工業大學經濟與管理學院，江蘇 南京 211816；2.南京中醫藥大學衛生經濟管理學院，江蘇 南京 210023）

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

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

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

1 配送成本模型

1.1 模型假設

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

1.2 符號說明

模型參數及其含義如表1所示。

1.3 成本模型構建

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

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

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

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

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

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

2 改進人工蜂群算法求解

2.1 算法改進

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

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

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

式中，Fi為第i個食物源的適應值，Fmid為食物源適應值中位數，SN為表食物源的數量。通過改進后，有效提高了收益度較小食物源被選擇的概率，同時不影響收益度較大的食物源被選擇的概率，保證了選擇的多樣性，避免因某一食物源被集中選擇導致局部最優情況的出現。選擇引領蜂之后，跟隨蜂會計算引領蜂傳遞信息中食物源的收益度值，計算公式如下所示：

式中，代表食物源，也就是一個可行解，為目標函數。

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

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

2.2 改進人工蜂群算法實求解步驟

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

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

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

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

步驟4：開始迭代，重復步驟5～11；

步驟5：引領蜂根據式（11）在解的鄰域內進行搜索，根據圖1所示流程進行解的迭代更新；

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

步驟7：根據步驟所選擇的解，跟隨蜂在該解對應的鄰域內根據式（10）搜索新的解，然后根據式（12）計算對應的收益度值，再重復步驟5進行解的更新；

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

步驟9：記錄當前最優解；

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

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

3 算例

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

表2 各客戶節點的需求量和時間窗

表3 各客戶節點之間的距離

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

表4 優化后配送情況匯總

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

圖2 基于改進人工蜂群算法的求解過程

4 結語

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