張嘉毅，劉 歡，李釗釗，樊慧慧，唐彭燕

（甘肅農(nóng)業(yè)大學(xué) 信息科學(xué)技術(shù)學(xué)院，甘肅 蘭州 730000）

0 引言

果蔬農(nóng)產(chǎn)品作為農(nóng)貿(mào)市場流通中不可或缺的一部分，應(yīng)保證其供應(yīng)鏈完整性，對其物流模式進一步優(yōu)化，以保障果蔬農(nóng)產(chǎn)品的質(zhì)量和物流服務(wù)水平［1］。果蔬農(nóng)產(chǎn)品供應(yīng)鏈?zhǔn)菍⑥r(nóng)產(chǎn)品從產(chǎn)地送到餐桌的過程，人們對果蔬農(nóng)產(chǎn)品的生鮮程度要求較高，而果蔬農(nóng)產(chǎn)品容易受到運輸環(huán)境的影響，保質(zhì)期較短，因此對物流運輸要求較高。好的運輸路徑不僅可以降低果蔬農(nóng)產(chǎn)品的運輸時間、減小運輸路程，還可以降低果蔬農(nóng)產(chǎn)品的貨損，節(jié)約物流成本［2］。然而目前果蔬農(nóng)產(chǎn)品供應(yīng)鏈體系仍不夠完整，主要體現(xiàn)在運輸成本高、物流損失嚴(yán)重、物流信息不健全等方面，因此健全供應(yīng)鏈體系、實現(xiàn)高效率物流運輸是時代的必然趨勢。

1 相關(guān)研究

物流運輸中的車輛路徑問題（Vehicle Routing Problem，VRP）［3］自提出以來一直是路徑優(yōu)化領(lǐng)域的研究熱點，目前對VRP 的研究多集中在客戶需求、車輛配置、電子商務(wù)等方面。在實際運輸過程中影響最優(yōu)路徑的主觀與客觀因素有很多，某些因素在研究中被人為地模糊處理，多著重處理運輸成本方面的問題。例如，包賢哲等［4］針對路徑規(guī)劃提出一種變異擴散蟻群算法，通過極值限定信息素濃度導(dǎo)致算法停滯，而后采用變異機制提高算法精度，再利用信息素擴散加快較近螞蟻之間的交流，加快算法收斂；唐慧玲等［5］構(gòu)建了多目標(biāo)的VRP 線性規(guī)劃模型，采用改進蟻群算法求解，其在螞蟻信息素中引入混沌擾動機制提高算法適應(yīng)性，同時對啟發(fā)因子、狀態(tài)轉(zhuǎn)移概率和信息素更新進行優(yōu)化提高搜索效率；Nie 等［6］提出將神經(jīng)網(wǎng)絡(luò)引入復(fù)雜模型中得到新的蟻群優(yōu)化算法，以解決三維路徑中效率的規(guī)劃問題；方文婷等［7］針對蟻群算法信息素不足收斂慢的問題，將A*算法的全局收斂性與蟻群算法的正反饋性相結(jié)合，構(gòu)建了混合蟻群算法來解決路徑優(yōu)化問題；Wu 等［8］提出一種新的改進遺傳算法，利用貪心算法確定初始種群，然后設(shè)計一種新算子作為組內(nèi)頭對頭變異算子，使其進化更加確定和有效；玄世龍等［9］提出一種優(yōu)化的禁忌算法，將已搜索路徑放入禁忌表中迭代，最后對結(jié)果進行比較，尋找最優(yōu)路徑，結(jié)果表明此算法較A*算法更可行有效；邱志平等［10］提出一種多目標(biāo)禁忌搜索算法，該算法在原有基礎(chǔ)上增加了禁忌搜索算法和帕累托解的融合機制、優(yōu)秀解保留機制、多方向搜索等，最后又與遺傳算法相結(jié)合產(chǎn)生此算法；劉倚瑋等［11］提出在考慮約束條件的基礎(chǔ)上運用Dijkstra-GA 混合算法和模擬退火算法進行優(yōu)化，通過仿真實驗得出此算法可以有效規(guī)劃路線；惠海波等［12］為減少DV-Hop 算法的定位誤差，改進模擬退火算法使其避免重復(fù)搜索，提高全局搜索能力，仿真結(jié)果表明該算法可行；Wu 等［13］提出在無人機輸電鐵塔巡檢路徑中結(jié)合模擬退火算法求出最優(yōu)能耗路徑，然后搭建模型進行數(shù)據(jù)分析，得出該算法提高了效率；徐勝等［14］為解決旅行商的停滯問題，提出基于遺傳-模擬退火的蟻群算法，采用遺傳算法增加解的多樣性，模擬退火算法提高解的質(zhì)量，得出新算法具有較好解的能力。

由上述文獻研究可知，大部分VRP 研究中帶有時間窗。本文從帶有時間窗和容量約束的VRP 兩方面進行研究，利用啟發(fā)式算法［15］將這兩個因素聯(lián)合決策，尋找最優(yōu)解。本文選擇的啟發(fā)式算法為蟻群算法［16］，在前人研究的基礎(chǔ)上增加時間、載重、需求等約束條件改進算法，用于解決帶有時間窗的VRP，以優(yōu)化多基地果蔬農(nóng)產(chǎn)品供應(yīng)鏈的物流問題。

2 問題描述

本文研究西北地區(qū)的果蔬農(nóng)產(chǎn)品供應(yīng)鏈物流優(yōu)化問題，以甘肅省、青海省為例，其整體供應(yīng)基地點和接收點分布如圖1 所示。已知供應(yīng)基地和其他接收點的坐標(biāo)位置，同時考慮接收點的需求量、可接受的時間窗（運輸時間+服務(wù)時間）、運輸車輛的載重量等?，F(xiàn)有多輛運輸車由供應(yīng)基地運送農(nóng)產(chǎn)品到各個接收點，在滿足約束條件下，得到運輸車輛所用距離成本最小的最優(yōu)路徑。

建模時作出以下假設(shè)：①路徑優(yōu)化目標(biāo)值不受車輛狀態(tài)影響（動力充足、型號統(tǒng)一等）；②每條路徑接收點總需求量不超過運輸車輛的極限承重；③每個接收點都必須被經(jīng)過；④每一個接收點僅能一輛車經(jīng)過且運輸車最終返回出發(fā)點；⑤允許運輸車輛提前走到目標(biāo)點，同時必須滿足該點時間窗，如果產(chǎn)生時間損失成本則重置路徑；⑥運輸車輛若晚到目標(biāo)點，超出時間窗則加入懲罰成本，同時算法設(shè)計中對該路徑進行重置；⑦不考慮對一個接收點多次運輸。

Fig.1 Distribution of overall supply base points and reception points in the northwest圖1 西北整體供應(yīng)基地點和接收點分布

3 模型建立

本文模型相關(guān)變量的定義如表1所示。

Table 1 Definition of variables表1 相關(guān)變量定義

模型中包含物流運輸時整體路徑的時間成本，以及運輸過程中考慮果蔬農(nóng)產(chǎn)品因存儲環(huán)境而產(chǎn)生的損失值，且加入保證產(chǎn)品質(zhì)量的成本，例如制冷材料等，根據(jù)以上條件建立如下目標(biāo)函數(shù)：

式中，ZC1表示車輛始發(fā)過程中隨著時間推移產(chǎn)生的運輸成本，表示為：

ZC2表示加入運輸過程中保證產(chǎn)品質(zhì)量的成本，表示為：

ZC3表示產(chǎn)品在運輸時以及在接收點的服務(wù)時間中因儲存環(huán)境變化產(chǎn)生的損失值，例如在接收點服務(wù)過程中裝卸導(dǎo)致的產(chǎn)品損失值，以及在運輸過程中受時間影響使得農(nóng)產(chǎn)品品質(zhì)下降而導(dǎo)致的成本等，表示為：

ZC4表示加入懲罰時間窗限制，主要用于在整體優(yōu)化過程中排除一系列運輸不及時的問題，在約束條件中對超時進行懲罰計算，表示為：

式（1）—式（6）表示模型需要考慮的成本，在基礎(chǔ)運輸費用下同時加入因農(nóng)產(chǎn)品自身問題而產(chǎn)生的損失值，即多基地果蔬農(nóng)產(chǎn)品運輸過程中帶有懲罰函數(shù)限制的損失模型；式（7）表示每個接收點只可被分配到一條路徑；式（8）表示運輸過程所有路徑的使用車輛數(shù)量小于或等于總車輛數(shù)量；式（9）表示每次的路徑優(yōu)化都必須回到初始供應(yīng)基地點；式（10）表示車輛到達接收點完成服務(wù)時間后必須離開該接收點；式（11）表示運輸路徑中有很多規(guī)劃路徑，在逐步求得最優(yōu)時消除之前存在的路徑；式（12）—式（14）表示目標(biāo)函數(shù)中分段函數(shù)ZC4的定義域范圍，在時間區(qū)間不同情況下有不同的懲罰函數(shù)，一種是在懲罰時間內(nèi)的懲罰系數(shù)y，一種是超出時間限制的損失系數(shù)k，當(dāng)全部超出時，則產(chǎn)品無價值，此時懲罰成本為產(chǎn)品價值；式（15）—式（16）表示在供應(yīng)基地和接收點之間的運輸時間的限制，接收點只在一定時間內(nèi)接收運輸車輛并且完成該點的服務(wù)時間；式（17）表示在既定時間區(qū)間內(nèi)完成運輸，則懲罰函數(shù)值為0，結(jié)果趨向于最優(yōu)；式（18）表示車輛運輸路徑中載重量大于或等于各個接收點需求量之和，且等于時為最優(yōu)；式（19）表示車輛載重為一個參數(shù)值，根據(jù)實驗內(nèi)容界定；式（20）表示供應(yīng)基地的存儲量必須要大于或等于各個接收點的需求量之和。

4 改進蟻群優(yōu)化算法

4.1 算法描述

對原始蟻群算法模型作出相應(yīng)約束改變，將其轉(zhuǎn)換為能夠解決多基地帶有時間窗的路徑優(yōu)化問題的算法模型。結(jié)合研究目的，已知接收點和供應(yīng)基地坐標(biāo)，以式（6）目標(biāo)函數(shù)為核心進行優(yōu)化；加入式（3）—式（4），使得算法輸出結(jié)果能夠考慮上述損失情況，減少相關(guān)損失因素干擾。在不斷迭代過程中，根據(jù)螞蟻移動的不確定性以及對信息素濃度的選擇性構(gòu)建出最優(yōu)路徑。

4.2 算法流程

根據(jù)蟻群算法原理，加入各類約束條件以及優(yōu)化程度、優(yōu)化策略，通過對各類參數(shù)的靈活定義衍生出不同優(yōu)化類型，同時在改進蟻群優(yōu)化算法代碼中加入路徑分割算法，即將多基地路徑分開優(yōu)化，分別以某個供應(yīng)基地為主找到所有最優(yōu)路徑，并且將其整合后對比是否為最優(yōu)，從而解決因局部最優(yōu)而產(chǎn)生的優(yōu)化結(jié)果偏差。得到各基地中各車輛參數(shù)后，在滿足運輸規(guī)模的條件下分配最優(yōu)接收點。

本文算法參數(shù)及設(shè)定函數(shù)為：

定義接收點坐標(biāo)集合C以及各個坐標(biāo)之間的距離dij(1 ≤i≤n，1 ≤j≤n，i≠j)，將出發(fā)點和返回點設(shè)為同一供應(yīng)基地。

計算歐幾里得距離為：

信息素更新函數(shù)為：

式（22）表示螞蟻在選擇路徑時會盡量選擇距離近的且信息素濃度較大的方向，其中allowedk表示在t時刻螞蟻k下一步選擇的坐標(biāo)（無訪問）；α表示信息啟發(fā)式因子，反映信息素的相對程度；β表示期望啟發(fā)式因子，反映期望值的相對程度。式（23）表示坐標(biāo)i，j轉(zhuǎn)移的期望程度（先驗知識），dij越小，ηij(t)越大；式（24）、（25）表示降低信息素，防止啟發(fā)信息淹沒：ρ表示信息揮發(fā)系數(shù)，模仿人類記憶，防止無限積累，取值范圍為［0，1］，1 -ρ表示信息殘留系數(shù)；式（25）表示本次循環(huán)的信息素增量；式（26）表示在原信息素更新加入避免停滯現(xiàn)象的出現(xiàn)，在搜索中動態(tài)調(diào)整狀態(tài)轉(zhuǎn)移概率。

本文算法流程為：

步驟1：將時間初始化t=0，循環(huán)次數(shù)NC=0，設(shè)置最大循環(huán)次數(shù)maxNC=0，路徑(i，j)的初始化信息素τij(t)=const，初始時刻Δτij(0)=0。

步驟2：將所有未被訪問過的坐標(biāo)放入集合C。

步驟3：對集合C中元素排列，對于任意i≤j，滿足當(dāng)前路徑Si≤Sj（當(dāng)前路徑S最后一個客戶），則令k=1。

步驟4：若全被訪問完過，則跳至步驟7。

步驟5：當(dāng)路徑合格時，保存當(dāng)前路徑S，重新開辟新路徑，從當(dāng)前集合中未被訪問的坐標(biāo)中重新隨機選擇另一個坐標(biāo)作為出發(fā)點，同時跳至步驟3。

步驟6：如果優(yōu)化后選擇的坐標(biāo)合法，則將該坐標(biāo)加入S路徑中，k=k+1，跳至步驟4。

步驟7：根據(jù)一系列計算，最后得出目標(biāo)值min，此時若該路徑的接收點出現(xiàn)懲罰時間，以式（16）的時間窗范圍為參考，則不會將該返回值加入路徑，并重新選擇路線，跳至步驟3。

改進蟻群優(yōu)化算法流程如圖2所示。

Fig.2 Improved ant colony optimization algorithm process圖2 改進蟻群優(yōu)化算法流程

4.3 算法驗證

為驗證改進蟻群優(yōu)化算法的有效性，將其與禁忌搜索算法、模擬退火算法進行比較。隨機選取5 個數(shù)據(jù)集進行測試，每個數(shù)據(jù)集中均有供應(yīng)基地點4 個，接收點51 個。5 個數(shù)據(jù)集參數(shù)設(shè)置如下：①供應(yīng)基地和接收點的橫縱坐標(biāo)均為［0，100］的隨機數(shù)；②供應(yīng)基地時間窗為［0，12］，所有接收點時間窗均為［0，12］的隨機區(qū)間；③對所有基地的所有車輛統(tǒng)一極限承重為10 噸；④運輸車的車速默認(rèn)為50km/h；⑤所有接收點的需求量均為［1，4］的隨機區(qū)間；⑥所有接收點需要處理車輛的服務(wù)時間均為0.6。

三種算法的參數(shù)設(shè)置如下：①改進蟻群優(yōu)化算法中的信息啟發(fā)式因子α=1，期望啟發(fā)式因子β=4，信息素強度Q=20，信息素?fù)]發(fā)因子ρ=0.2，蟻群規(guī)模popsize=35；②禁忌搜索算法中禁忌表長度TL=8；③模擬退火算法中退火起始溫度T0與終止溫度Tf關(guān)系為T0=10 000Tf，降火速率dT=0.9。以上3 種算法迭代次數(shù)均為100 次，分別運行10 次，提取10 次中物流成本的最優(yōu)解以及其對應(yīng)的運輸時間和車輛使用數(shù)，不同算法優(yōu)化結(jié)果如表2 所示?？梢钥闯觯谶\輸時間近似的情況下，改進蟻群優(yōu)化算法的物流成本和所需車輛數(shù)低于禁忌搜索算法和模擬退火算法。

Table 2 Comparison of optimization results of different algorithms表2 不同算法優(yōu)化結(jié)果比較

5 實驗分析

5.1 仿真實驗

選取西北地區(qū)甘肅省、青海省為例的果蔬農(nóng)產(chǎn)品供應(yīng)鏈物流問題，相應(yīng)的供應(yīng)基地與接收點的實驗坐標(biāo)如圖3所示。

由甘肅省與青海省坐標(biāo)分布可知居民主要居住城市均勻分布在兩省接壤線附近，故選擇4 個供應(yīng)基地（d1-d4）與26個接收點（0-25），具體如表3所示。

5.2 參數(shù)實驗分析

改進蟻群優(yōu)化算法中，如果螞蟻數(shù)量過大，則每條路徑上的信息素濃度趨于平均，正反饋作用減弱，從而導(dǎo)致收斂速度減慢；如果過小，則可能導(dǎo)致一些從未搜索過的路徑信息素濃度減小為0，導(dǎo)致過早收斂，解的全局最優(yōu)性降低。a為信息啟發(fā)式因子，其值越小越容易陷入局部最優(yōu)；β為期望啟發(fā)式因子；ρ為信息素?fù)]發(fā)因子，與全局搜索和收斂速度有關(guān)。根據(jù)蟻群算法的參數(shù)設(shè)置如下步驟：

Table 3 Experimental coordinate point表3 實驗坐標(biāo)點

步驟1：確定運輸車輛數(shù)量，接收點數(shù)量/蟻群規(guī)?！?.5。

步驟2：參數(shù)粗調(diào)，將信息啟發(fā)式因子a，期望啟發(fā)式因子β，信息素強度Q設(shè)定為取值范圍內(nèi)的較大值。

步驟3：參數(shù)細(xì)調(diào)，信息素?fù)]發(fā)因子ρ取值過大時容易影響隨機性和全局最優(yōu)性，因此選取取值范圍內(nèi)的較小值。

改進蟻群優(yōu)化算法參數(shù)空間大且關(guān)聯(lián)性很強，很難確定一種基于各類問題的特殊最優(yōu)組合模型。本文對同等實驗數(shù)量的隨機坐標(biāo)進行大量測試，得到最佳參數(shù)設(shè)置范圍為：

0 ≤α≤5，0 ≤β≤5，0.1 ≤ρ≤0.99，10 ≤Q≤100

調(diào)整取值范圍較大的因子，設(shè)置如下：信息啟發(fā)式因子α=1，期望啟發(fā)式因子β=5，信息素強度Q=20，信息素?fù)]發(fā)因子ρ=0.2。

現(xiàn)存的30 個坐標(biāo)點中，以供應(yīng)基地作為物流始發(fā)點，為確保整體路徑最優(yōu)，對車輛數(shù)目不作限制，即在算法運行中不采用運輸車輛數(shù)量作為約束條件。本次運輸車車速默認(rèn)為50km/h，每輛運輸車的載貨量極限承重為10t，每個接收點所需要的貨物量區(qū)間為［0.5，4］t。通過式（21）以及地圖的比例尺求得距離，結(jié)合速度求出運輸時間。供應(yīng)基地時間窗包含各個接收點時間窗，將供應(yīng)基地時間窗設(shè)置為［0，12］，接收點時間窗為［0，12］的隨機區(qū)間，服務(wù)時間設(shè)為［0.5-1.5］的隨機數(shù)。

5.3 實驗結(jié)果與分析

5.3.1 單例驗證

首先對單省物流優(yōu)化驗證算法的有效性，以甘肅省為例，取表3 中坐標(biāo)編號d1、d2 為供應(yīng)基地坐標(biāo)，取0-12 為接收點坐標(biāo)，得到坐標(biāo)散點圖見圖4。算法路徑優(yōu)化收斂曲線如圖5 所示，設(shè)置迭代次數(shù)為100 次，迭代后趨于一個穩(wěn)定數(shù)值，即目標(biāo)優(yōu)化的距離成本。算法路徑優(yōu)化如圖6所示，表示對圖4 坐標(biāo)散點圖的路徑優(yōu)化結(jié)果。考慮到甘肅省地形狹長，東西跨距過大，運輸時間過長，省內(nèi)整體運輸很難由一個供應(yīng)基地貫穿西北、東南兩端接收點，因此在西北方與東南方形成兩個獨立的運輸網(wǎng)。算法運行輸出得到最優(yōu)路徑分配方案如表4 所示，同時結(jié)合圖6 算法路徑優(yōu)化得出5 條優(yōu)化路徑，并且標(biāo)有每條路徑詳細(xì)的約束參數(shù)。根據(jù)時間窗設(shè)定接收點的服務(wù)時間（裝卸等）、建議載重量（噸），路徑中車輛極限承重大于或等于各個接收點的需求量之和，在得到最優(yōu)路徑的前提下建議車輛的載重量也能同樣達到優(yōu)化目的。在實際物流費用處理時，將所有得到的結(jié)果轉(zhuǎn)換為實際參數(shù)，例如將時間轉(zhuǎn)換為24h制，分別計算出每個路徑的路程，將其累加并與運輸費用等進行相關(guān)數(shù)據(jù)處理即可得出最小物流成本。

Fig.4 Coordinate scatter map of Gansu province圖4 甘肅省坐標(biāo)散點圖

5.3.2 實驗應(yīng)用及分析

Fig.5 Algorithm path optimization convergence curve of Gansu province圖5 甘肅省算法路徑優(yōu)化收斂曲線

Fig.6 Algorithm path optimization in Gansu province圖6 甘肅省算法路徑優(yōu)化

Table 4 Optimal route allocation scheme of Gansu province表4 甘肅省最優(yōu)路徑分配方案

結(jié)合圖3 西北地區(qū)供應(yīng)基地與接收點的實驗坐標(biāo)，得到圖7 所示的西北地區(qū)算法路徑優(yōu)化收斂曲線，表示經(jīng)過迭代運輸路程逐漸最優(yōu)；圖8 為西北地區(qū)算法路徑優(yōu)化，表示經(jīng)過算法優(yōu)化得到11 條路徑。為提高運輸效率，每個接收點只能經(jīng)過一次且所有點都要被經(jīng)過。算法運行輸出得到表5 的西北地區(qū)最優(yōu)路徑分配方案，其中建議載重量是每輛車在每條路徑中每個接收點的需求量之和，用于建議車輛每次出貨大致需要的貨物量。為使所有實驗點都被經(jīng)過，可能會出現(xiàn)一輛車只運輸一個接收點的情況，例如表5 西北地區(qū)最優(yōu)路徑分配方案中車輛編號為v3、v8、v10 的車輛，為了增加車輛利用率以及減少距離成本，存在兩省接壤處的跨省運輸。本次實驗共使用11 輛運輸車，得到每輛車經(jīng)過的接收點和每條路徑的路程。本次實驗加入懲罰時間窗限制，用于在全局優(yōu)化過程中排除一系列運輸不及時問題，在約束條件內(nèi)對超時進行懲罰計算。以上為制約物流運輸成本的主要因素，其中各種因子相互影響，需迭代模擬出最佳運輸方案，使運輸總成本最小。受載貨量的限制，可能有些車輛的路徑大致相似，盡管路徑能做到大致吻合，但是仍然需要安排兩輛運輸車。同時若考慮損失函數(shù)，為減少農(nóng)產(chǎn)品因運輸、存儲環(huán)境、裝卸過程中的損失，則車輛載重必須要大于建議載重量且小于車輛的極限承重，具體措施可以是增加在冷藏保存方面的用物重量等。

Fig.7 Convergence curve of algorithm path optimization in northwest China圖7 西北地區(qū)算法路徑優(yōu)化收斂曲線

Fig.8 Algorithm path optimization in northwest China圖8 西北地區(qū)算法路徑優(yōu)化

6 結(jié)語

本文以西北地區(qū)的兩個省份作為對象構(gòu)建模型，研究了多基地果蔬農(nóng)產(chǎn)品供應(yīng)鏈物流優(yōu)化問題，從現(xiàn)實角度出發(fā)選擇參數(shù)，考慮到果蔬農(nóng)產(chǎn)品會因運輸中存儲環(huán)境產(chǎn)生成本，例如制冷材料等保證生鮮程度的成本，加入核心參數(shù)時間窗，在接收點的時間窗內(nèi)進行路徑優(yōu)化，并且加入帶有懲罰系數(shù)的時間窗，使優(yōu)化后的路徑不被懲罰結(jié)果影響。同時設(shè)計多供應(yīng)基地對多接收點的路徑優(yōu)化算法，利用蟻群算法兼容性強、參數(shù)關(guān)聯(lián)性高的特點尋找參數(shù)以避免陷入局部最優(yōu)。優(yōu)化結(jié)果表明，與傳統(tǒng)集中物流運輸相比，模型得到的優(yōu)化路徑可以減少物流支出。然而，本文算法還有很大改進空間，例如需提高算法的迭代效率和并增加其適用范圍，在未來研究中考慮為減少車輛使用損耗而在路徑選擇中加入對不同載重車輛的選擇性，以便于得到更優(yōu)物流配送方案。

Table 5 Optimal route allocation scheme in northwest China表5 西北地區(qū)最優(yōu)路徑分配方案