蟻群優化算法下農村生鮮配送車輛路徑對比研究

韓榮騰

摘?要：近幾年，美團優選、多多買菜等生鮮電商涌入農村市場，開始針對性地解決農村生鮮物流配送的“最后一公里”的難題。文章通過引入生鮮電商的“社區團購”配送模式，綜合考慮農村用戶的商品需求量、生鮮商品送達用戶時的鮮活度、商品履約率、容量受限開放式路徑規劃配送車輛等因素，以總配送成本最小為目標構建開放式帶時間窗容量受限車輛路徑優化模型，利用蟻群優化算法對該模式求解。通過算法求解的結果表明：在農村生鮮產品配送中，開放式容量受限車輛路徑規劃，能有效地降低農村生鮮物流配送的總成本，縮短車輛行駛距離，提高商品履約率。

關鍵詞：農村生鮮配送；開放式車輛路徑規劃；容量受限；帶時間窗車輛路徑規劃

中圖分類號：F259.23???文獻標識碼：A?文章編號：1005-6432（2023）10-0189-05

DOI：10.13939/j.cnki.zgsc.2023.10.189

1?引言

生鮮行業是我國民生的剛需行業。隨著疫情的出現，生鮮電商大量涌現，生鮮電商市場迅速成長，已經在生鮮行業占據一席之地。根據中國電商委的數據，農村生鮮網購消費人群更加關注生鮮產品的價格和質量，對生鮮產品的時效性關注度不高。而社區團購模式保證了消費者的低價高質，物流配送為T+1天，商品為次日達，可以滿足農村消費者的需求，解決了生鮮產品農村配送“最后一公里”的難題。農村生鮮電商平臺的商品價格競爭較為激烈，生鮮電商要保證盈利與占據農村市場份額，就要降低物流配送成本，提高商品履約率。物流配送成本的降低，商品履約率的提高，將推動生鮮電商的核心競爭力的提高，更多的讓利于農村消費者，促進農村生鮮電商的發展。

降低農村生鮮物流成本的關鍵是如何規劃車輛路徑的問題，通過構建開放式車輛路徑規劃，探索規劃車輛路徑的解決方案，提高商品履約率。農村生鮮產品的物流配送多使用普通車輛配送，并不涉及冷鏈車輛配送。王邦兆［1］針對生鮮配送中訂單較少以及消費者較為分散，提出了結合改進遺傳算法的社區搜索算法，對以成本為導向的多中心共同配送進行優化，但是要求分揀率的提高。王可山［2］認為降低生鮮電商的配送成本應該對配送成本、包裝成本等進行優化，并沒有針對配送的路徑成本進行分析。李昌兵［3］綜合物聯網技術優勢和生鮮農產品的特點，使用RFID技術降低分揀和配送成本。付朝暉［4］引入了時變路網條件，構建了生鮮配送的開放式路徑規劃車輛路徑問題優化模型，以期降低生鮮電商的總配送成本。范厚明［5］提出車輛在完成配送任務后可繼續補貨進行配送或自行結束配送任務的一種半開放式配送模式。余海燕［6］提出結合生鮮產品訂單的動態性、硬時間窗等因素，設計滾動時域延遲配送算法模式，并對其模型參數進行敏感性分析。

現存的文獻對深入研究末端生鮮物流配送提供了大量的參考。但由于已有的文獻主要研究城市生鮮物流配送問題，多針對封閉式車輛路徑規劃問題，對開放式帶時間窗容量受限車輛路徑配送問題以及農村生鮮物流配送涉及較少。文章針對農村消費者網購關注度以及社區團購時效性等特點，考慮到“T+1”的配送模式、開放式車輛路徑規劃、車輛容量受限以及商品履約率等因素，以配送成本最低為優化目標，建立開放式車輛路徑規劃模型，并設計蟻群優化算法求解該模型。

2?問題建模

2.1?問題描述

社區團購主要是以多多買菜、美團優選等生鮮電商企業為主的一種生鮮電商模式。該模式下的農村生鮮物流配送路徑主要涉及從配送中心到團長門店和第三方車輛配送或自營車輛配送。大多數生鮮電商為了降低成本，多使用第三方車輛進行配送，司機可以進一步利用車輛的價值，因此第三方車輛在完成配送任務后，不必返回配送中心。社區團購下的農村生鮮物流配送，有多個“團長”門店需要配送，各門店的地理位置已知道，配送容量不超過車輛容量，每個門店只能被一輛車服務一次。為了提高客戶滿意度，文章將針對商品的新鮮度以及客戶需求設置bj點履約率。假設：①每輛配送車輛從站點出發，配送任務完成后，不必要返回站點。②車輛會產生一定的固定成本。③車輛可提前到達門店位置，但需等待該門店最早開始服務時間進行配送，存在一定的車輛等待時間與卸貨時間。通過上述條件構建開放式（帶時間窗容量受限）車輛路徑規劃模式。

2.2?模型構建

2.2.1?已知參數

S1?表示開放式路徑規劃車輛總配送距離；dij?表示客戶節點i到達客戶節點j之間的距離；Q?表示車輛的最大載裝量；Wo?表示開放式路徑規劃車輛司機的固定工資；K表示車輛的集合；FCij?表示每輛車k單位距離的燃油補貼，其中FCij≤Fk1;N?表示客戶的集合；qi?表示一個客戶的需求量；R?表示一組客戶的路徑（c1，?c2，?…，?cn）；?r表示一組客戶的路徑規劃（r1，?r2，?…，?rk）；?CBest?表示最優的成本；?Li?表示在節點i還沒拜訪的客戶；Rej表示配送車輛在客戶節點j所增加的一定獎勵成本；Puj表示配送車輛在客戶節點j所增加的一定懲罰成本；tij表示配送車輛從客戶i到達客戶節點j的時間；aj表示配送車輛最早到達客戶節點j的時間；bj表示配送車輛最晚到達客戶節點j的時間；ej表示配送車輛實際到達客戶節點j的時間。

決策變量：xijk?表示車輛k是否從節點i行駛到節點j，如果是，值為1，否則為0；vk表示車輛k是否被啟用，如果是，值為1，否則為0；yik表示車輛k是否完成客戶節點i的任務，如果是，值為1，否則為0。

2.2.2?模型約束條件

∑k∈K∑（i，?j）∈Ndijxijk（1）

CBest=FCij∑k∈Kvk∑k∈K∑（i，?j）∈Ndijxijk+Wo∑k∈Kvk+Rej∑k∈Kvk∑（i，?j）∈Nxijk+Puj∑k∈Kvk∑（i，?j）∈Nxijk（2）

s.t.

∑k∈K∑j∈Δ+（i）xijk=1，?i∈N（3）

∑i∈N∑k∈Kxijk=1，?j∈N（4）

∑i∈Nqi∑j∈Δ+（i）dijk≤Q，?k∈K（5）

xk0j=vk，?k∈K，?j∈N（6）

∑j∈Nx0jk≤1，?k∈K（7）

時間窗約束：（8）

xijk∈{0，?1}，?k∈K，（i，?j）∈N（9）

yik∈{0，?1}，?k∈K，i∈N（10）

其中：目標函數（1）表示車輛行駛總距離最優。目標函數（2）為最優的開放式路徑規劃車輛配送成本。約束（3）限制每個客戶只能被分配到一條路徑上。約束（4）表示每個客戶節點只能被訪問一次。約束（5）表示每輛車在配送中心裝配的貨物不大于車輛自身的最大承載量。約束（6）表示當車輛被啟用時，必須從配送中心出發。約束（7）表示每輛車只能啟用一次。約束（8）將分為硬時間窗和軟時間窗?？蛻艄濣cj的時間窗范圍為［aj，?bj］，?［aj，?bj］為客戶點最早及最晚送達時間，對［aj，?bj］時段車輛到達客戶節點j將增加一定的獎勵成本，對超過bj時段車輛到達客戶節點j將增加一定的懲罰成本，對早于aj時間點到達的車輛，并不設獎懲，雖可能導致配送效率降低，但是仍可達到履約率。硬時間窗要求車輛必須在［aj，?bj］完成配送任務，即aj≤tij≤bj，軟時間窗允許車輛送達時間早于aj，晚于bj。在不超過bj時段車輛到達節點j，客戶j的滿意度為1，在超過bj時段車輛到達節點j，客戶滿意度為-1。其獎勵成本為式（11），懲罰成本為式（12）。

Rej=1（aj≤tij≤bj）（11）

Puj=－1（bj≤tij）（12）

決策變量（9）表示當車輛k從節點i行駛到節點j時，xijk=1，否則為0；決策變量（10）表示車輛k完成i的任務時，yik=1，否則為0。

3?算法驗證及分析

車輛路徑規劃是經典的組合優化問題，而開放式帶時間窗容量受限車輛路徑規劃屬于VRP的衍生問題，因此需要求解的模型同樣具有NP-hard形式。蟻群算法是一種啟發式智能算法，具有降低編碼復雜性、提高效率的特點。

為檢驗文章采用的蟻群優化算法的有效性以及可行性，文章采用聊城市某多多買菜農村社區站點所提供的數據。其中，車輛行駛的距離為坐標點之間的距離。該多多買菜站點，主要配送社區為鄉鎮轄區內的農村門店。文章選取了其中25家多多買菜門店數據。涉及車輛的最大載重量為4500千克，車輛的行駛速度設為60千米/小時。每輛車的司機工資采用當地工資平均值為4500元/月，金杯汽車的百千米油耗為12升，當地92號汽油價格的平均值為6.5元/升，因此每輛車的百千米油料補貼為10元。送達時間即為簽單時間，懲罰成本設為50元/每門店，獎勵成本設為50元/每門店。

設配送中心以及25個門店分布在有向圖G中，配送中心為（40，50），門店等待以及卸貨時間設為90分鐘/門店，25個門店其他數據如表1所示。

文章所設螞蟻數量m=50，車輛最多使用數目kmax=25，最大迭代次數iter_max=100，其他參數設置如上文。利用Matlab工具，將蟻群優化算法進行運算，所得最小成本為15371.74元，最小距離均為187.174。

為防止存在誤差，文章在計算機上運行10次所得最小配送總成本均為15371.74，最小配送總距離均為187.174，算法結果具有穩定性，其中運行101次時間平均為26.522679秒，運行時間較短，效率較高。車輛最優路徑規劃如圖1所示，其搜索各代最小成本變化過程如圖2所示。

如圖2所示，文章所實驗的結果具有可行性和有效性，所展示出的配送路徑為：配送路線1為0→5→3→7→8→10→11→9→6→4→2→1，配送路線2為0→13→17→18→19→15→16→14→12，配送路線3為0→22→24→25→23→22→21。

文章為證明開放式車輛路徑規劃相比封閉式車輛路徑規劃更加節省成本，采用蟻群算法計算25個門店的封閉式車輛路徑規劃，所得最優路徑規劃如圖3所示，其搜索各代最小成本變化過程如圖4所示。其中封閉式最佳車輛配送路徑與開放式最佳車輛配送路徑相對比，多出了回到配送中心的路程，使得油料補貼成本有所增加，增加70元，但使用車輛一致，司機工資成本一致，獎懲成本一致。

4?結語

文章將傳統的TSP問題加入開放式、帶時間窗及容量受限等元素，并考慮配送司機的獎懲成本、對比封閉式車輛路徑規劃，以配送最小總距離與配送最佳成本為目標，從而構建蟻群優化算法，為現實生活中農村生鮮社區配送路徑規劃提供一個新思路。實驗結果證明：①開放式車輛路徑規劃可以節省配送成本，縮小配送距離，節約車輛配送時間。在配送任務完成后，司機可以自由支配時間，提高了車輛使用的靈活性。②農村一直存在的配送“最后一公里”難題得以解決，為振興農村物流提供了一定借鑒。③與封閉式車輛路徑規劃相對比，開放式車輛路徑規劃具有更好的優化效果，不易陷入局部最優。

參考文獻：

［1］王邦兆，李慧.生鮮農產品同城配送復雜網絡布局設計［J］.統計與決策，2019，35（12）：40-44.

［2］王可山，張麗彤，劉彥奇.生鮮電商配送成本影響因素及控制優化研究［J］.經濟問題，2019（1）.

［3］李昌兵，汪爾晶，袁嘉彬.物聯網環境下生鮮農產品物流配送路徑優化研究［J］.商業研究，2017（4）：1-9.

［4］付朝暉，劉長石.生鮮電商配送的兼職時變車輛路徑問題研究［J］.計算機工程與應用，2021，57（1）：271-278.

［5］范厚明，楊翔，李蕩，等.基于生鮮品多中心聯合配送的半兼職車輛路徑問題［J］.計算機集成制造系統，2019，25（1）：256-266.

［6］余海燕，唐婉倩，吳騰宇.帶硬時間窗的O2O生鮮外賣即時配送路徑優化［J］.系統管理學報，2021，30（3）：584-591.