基于蟻群算法的配送路徑優化研究

安曉雯 董福貴

隨著信息技術的進步，電子商務也在迅速發展，當前制約電子商務發展的關鍵問題是物流配送成本過高、配送效率過低。合理的配送路徑可以更好的縮減企業的成本，提高服務質量，因此對于電商企業配送路徑優化的研究具有很大的價值。本文針對某電商企業，對路徑優化問題展開了討論。首先建立VRP模型，提出利用蟻群算法對VRP問題進行求解，借助MATLAB軟件進行仿真實驗，實例分析結果發現優化后的方案縮短了配送路徑，減少了配送成本。

一、引言

信息技術的日新月異，促使電子商務迅速崛起，并帶動了物流業快速發展，但是與此同時物流配送也成為制約電子商務發展的關鍵因素，因此優化配送路線，降低物流成本，提高顧客滿意度是提高企業競爭力的關鍵。

羅梓瑄等在物流配送路徑優化中，以成本最小化和最小碳排放量為目標構建了多目標優化模型，利用蟻群算法對其進行求解，他們認為蟻群算法能多點同時搜索獨立解，具有較強魯棒性。最后通過仿真，計算出最優配送路徑。張曉娜等以果蔬配送路線最優、最大化保持果蔬新鮮為目標，構建路徑優化模型，通過蟻群算法求解。吳雨婷等以配送路徑最短、時間最少、成本最低、客戶滿意度最高為目標，構建基于蟻群算法的冷鏈物流配送路徑優化研究模型。吳競鴻先分析了上海某連鎖商店配送中存在的問題，針對現狀建立了VRP模型。最后借助MATLAB軟件以及真實數據對模型進行了求解，提出配送路徑優化方案。汪越等認為在配送過程中加入時間窗限制可以更好的減少配送成本，他在文章中采用路徑長度和空載率兩個指標對帶時窗物流運輸車輛路徑進行優化，結果表明配送中心車輛調度效率提高了，為配送中心合理進行配送車輛調度提供借鑒。馬貴平等在傳統蟻群算法基礎上加入運輸時間、成本和道路通暢程度等約束條件，提出改進蟻群算法，并和CSAACO算法和ACO算法對比，結果顯示改進蟻群算法尋優能力更強。張肖琳等在構建路徑優化模型時考慮到了車輛在配送中對環境產生的影響，通過蟻群算法進行優化求解，結果證實了該模型可以達到路徑最短和對環境影響最小的目的。萬國海建立了以成本最小化為目標的電子商務配送路徑優化模型，并在傳統蟻群算法基礎之上做出了改進，結果表明改進后的蟻群算法提高了物流配送效率，降低了成本。

本文在查閱資料基礎之上，研究了針對某電商企業的路徑優化問題。本文首先建立了VRP模型，通過蟻群算法對模型進行求解，實例分析結果顯示蟻群算法在配送路線優化中的有效性。

二、物流配送路徑優化數學模型

（一）問題描述

電商企業配送路徑優化可描述為：已知某地區的客戶數量、每位客戶的坐標和需求量，由配送中心的配送車輛向客戶配送所需量的貨物。車輛從配送中心出發，每位客戶只能由一輛配送車輛配送，且每個客戶點只能被訪問一次，最后配送車輛回到配送中心，實現路徑最短、時間最少或成本最低等目標，同時還需要滿足一些約束條件：車輛負載和配送時間等。

（二）物流配送路徑優化模型

1.參數說明

M={1，2，…，m}表示客戶點集合

n表示配送車輛的數量

q是配送車輛的最大負載

c表示配送車輛的固定成本

cij表示配送車輛從客戶點i到客戶點j的運輸成本

qi表示客戶點i的需求量

0-1變量

2.數學模型

以配送路徑總成本最低作為目標函數：

上式表示每個客戶點只能由一輛配送車輛進行配送

上式表示每輛配送車輛向客戶點配送的時候載重量不能超過自身最大負載

上式表示到達客戶點和離開客戶點的配送車輛有且僅有一輛

（三）蟻群算法的最優路徑設計

第t時刻，節點i上的螞蟻數量為Bi（t），那么螞蟻數量為，n是節點數，即客戶數i，j節點距離為dij。螞蟻沒爬過時，初始信息素是相同的，τij（0）=C，第t時刻，節點i上的螞蟻k向節點j轉移的概率為：

allowedk是螞蟻k選擇的節點集合，α，β是啟發因子和期望因子，表示節點i和j間的信息素和能見度。

蟻群優化具有正反饋機制，路徑越短，信息素越多，螞蟻每爬行一步，信息素就會進行更新。

ρ是信息素揮發系數，Δτij是i和j間的信息素增量。

三、實例分析

（一）測試環境

某電商企業有5輛配送車，車輛最大負載為4噸，由配送中心向15個客戶點點進行配送，配送中心編號為0，客戶點編號從1-15。配送點坐標及需求量如表1所示。

表1 配送點坐標及需求量

（二）測試結果

用MATLAB進行仿真實驗時，設置最大迭代次數為100，螞蟻個數為30，車輛載重為4噸。測試結果如圖1所示，表2是MATLAB求解結果，路徑變化如圖2所示：

由表2可知通過蟻群算法優化之后的最優配送路徑方案總共有三條：

路徑1 由配送中心出發，經過1-2-3-4-5-6-8-7，最終回到配送中心，路徑1總配送距離為184.411km，運輸量為3.84t。

路徑2 由配送中心出發，經過10-9-12-13-11，最終回到配送中心，路徑2總配送距離為40.216km，運輸量為3.76t。

路徑3 從配送中心出發，經過14-15，最終回到配送中心，路徑3總配送距離為50.836，運輸量為1.04t。最終某電商企業的總配送距離為275.463km。

由上圖和表可知，本文某電商企業的路徑在蟻群算法優化之后由之前的336.6km，縮減到后來的275.4629km，減少了61.1371km。路徑縮短，配送效率也提高了，可以看出優化效果還是很明顯的。

四、結語

在物流快速發展的今天，物流配送的重要性不言而喻。運輸成本作為物流成本中重要的一環，對企業的發展也存在一定的影響。本文首先建立VRP模型，然后通過蟻群算法對模型進行求解，最后針對某電商企業進行實例分析，結果表明蟻群算法可以優化配送路線，提高配送效率，且效果較為明顯。我認為本文還存在一些不足之處，綠色發展已經成為各國大力追逐的目標，物流運輸業作為一個不可或缺的行業理應承擔起推動各國綠色發展的重任，因此在今后的研究中除了考慮配送路徑和成本，還需要加入對碳排放量、時間窗、貨車裝載率等的考慮。

（作者單位：華北電力大學 經濟與管理學院）

基金項目：華北電力大學哲學社會科學繁榮計劃專項項目（2019FR003）。