多基地果蔬農產品供應鏈物流優化

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

（甘肅農業大學 信息科學技術學院，甘肅 蘭州 730000）

0 引言

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

1 相關研究

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

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

2 問題描述

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

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

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

3 模型建立

本文模型相關變量的定義如表1所示。

Table 1 Definition of variables表1 相關變量定義

模型中包含物流運輸時整體路徑的時間成本，以及運輸過程中考慮果蔬農產品因存儲環境而產生的損失值，且加入保證產品質量的成本，例如制冷材料等，根據以上條件建立如下目標函數：

式中，ZC1表示車輛始發過程中隨著時間推移產生的運輸成本，表示為：

ZC2表示加入運輸過程中保證產品質量的成本，表示為：

ZC3表示產品在運輸時以及在接收點的服務時間中因儲存環境變化產生的損失值，例如在接收點服務過程中裝卸導致的產品損失值，以及在運輸過程中受時間影響使得農產品品質下降而導致的成本等，表示為：

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

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

4 改進蟻群優化算法

4.1 算法描述

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

4.2 算法流程

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

本文算法參數及設定函數為：

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

計算歐幾里得距離為：

信息素更新函數為：

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

本文算法流程為：

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

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

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

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

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

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

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

改進蟻群優化算法流程如圖2所示。

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

4.3 算法驗證

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

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

Table 2 Comparison of optimization results of different algorithms表2 不同算法優化結果比較

5 實驗分析

5.1 仿真實驗

選取西北地區甘肅省、青海省為例的果蔬農產品供應鏈物流問題，相應的供應基地與接收點的實驗坐標如圖3所示。

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

5.2 參數實驗分析

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

Table 3 Experimental coordinate point表3 實驗坐標點

步驟1：確定運輸車輛數量，接收點數量/蟻群規模≈1.5。

步驟2：參數粗調，將信息啟發式因子a，期望啟發式因子β，信息素強度Q設定為取值范圍內的較大值。

步驟3：參數細調，信息素揮發因子ρ取值過大時容易影響隨機性和全局最優性，因此選取取值范圍內的較小值。

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

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

調整取值范圍較大的因子，設置如下：信息啟發式因子α=1，期望啟發式因子β=5，信息素強度Q=20，信息素揮發因子ρ=0.2。

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

5.3 實驗結果與分析

5.3.1 單例驗證

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

Fig.4 Coordinate scatter map of Gansu province圖4 甘肅省坐標散點圖

5.3.2 實驗應用及分析

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

Fig.6 Algorithm path optimization in Gansu province圖6 甘肅省算法路徑優化

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

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

Fig.7 Convergence curve of algorithm path optimization in northwest China圖7 西北地區算法路徑優化收斂曲線

Fig.8 Algorithm path optimization in northwest China圖8 西北地區算法路徑優化

6 結語

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

Table 5 Optimal route allocation scheme in northwest China表5 西北地區最優路徑分配方案