改進蟻群優化算法的最優物流配送路徑設計

張濱麗 卞興超

摘? 要： 針對傳統蟻群優化算法難以找到全局最優的物流配送路徑，物流配送的時效性差等缺陷，為獲得理想的物流配送路徑，提出基于改進蟻群優化算法的最優物流配送路徑設計方法。首先，對物流配送路徑優化設計問題進行分析，建立物流配送路徑優化模型;然后，將蟻群置于物流配送的起始點，通過搜索下一節點、信息激素更新等模擬自然界蟻群尋食機制，找到從起始點到配送目標點的最優物流配送路徑，并對傳統蟻群優化算法的不足進行相應的改進;最后，通過具體實例分析改進蟻群優化算法應用于最優物流配送路徑設計中的有效性。改進蟻群優化算法可以在短時間內成功找到最優物流配送路徑，物流配送時間要少于其他物流配送路徑設計方法，能夠為提高物流企業的經濟效益提供有價值的參考信息。

關鍵詞： 物流配送; 物流路徑設計; 蟻群優化算法改進; 路徑優化模型; 算法有效性分析; 企業效益提升

中圖分類號： TN02?34; TP183? ? ? ? ? ? ? ? ? ? 文獻標識碼： A? ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2020）09?0105?04

An optimal logistics distribution path design based on improved ant colony optimization

ZHANG Binli， BIAN Xingchao

（Suihua University， Suihua 152061， China）

Abstract： Since there are shortcomings in the traditional ant colony optimization， like difficulty in getting the global optimal logistics distribution path and poor time efficiency of logistics distribution， an optimal logistics distribution path design method based on the improved ant colony optimization is proposed to obtain an ideal logistics distribution path. The optimization design of logistics distribution path is analyzed. The optimization model of logistics distribution path is established. The ant colony is placed at the start point of logistics distribution. And then， by searching for the next node and information hormone updating， the ant colony feeding mechanism in the nature is simulated， and the optimal logistics distribution path from the start point to the distribution target point is found. In addition， the shortcomings of the traditional ant colony optimization are improved. In the end， the effectiveness of the improved ant colony optimization applied to the optimal logistics distribution path design is analyzed by means of some specific examples. The improved ant colony optimization can find the optimal logistics distribution path successfully in a short time， and its duration of logistics distribution is shorter than that of other logistics distribution path design methods. Therefore， it can provide valuable reference information for improving the economic benefits of logistics enterprises.

Keywords： logistics distribution; logistics path design; ant colony optimization improvement; path optimization model; algorithm effectiveness analysis; enterprise benefit improvement

0? 引? 言

隨著經濟全球化進程的不斷加快，企業的物流活動日益頻繁，電子商務快速發展，物流成為企業的一個重要環節[1]。運輸費用占用物流費用的比重相當高，運輸費用與物流配送路徑選取直接相關。物流配送的目的就是為顧客提供最優的服務，同時，盡可能地降低物流配送成本，因此，設計最優的物流配送路徑具有重要的研究意義[2?3]。

由于國內物流起步比較晚，因此，物流配送路徑設計研究時間相對較短，最初主要通過司機憑借自己的經驗規劃最優物流配送路徑，由于缺乏科學指導，得到的物流配送路徑并非最優，物流配送效率低，物流配送的成本高[4?6]。隨后有學者提出了基于貪婪法的物流配送路徑設計方法，但是貪婪法求解最優路徑的時間長，故有學者提出了動態規劃算法的物流配送路徑設計方法、基于整數規劃算法的物流配送路徑設計方法、基于分支定界法的物流配送路徑設計方法，這些方法屬于精確算法[7?9]，雖然可以獲得比貪婪法更優的物流配送路徑，但是由于本質上和貪婪法均屬于窮舉搜索算法，物流配送路徑求解問題屬于NP?Hard 問題，因此，同樣存在物流配送路徑求解時間長、效率低等局限性[10]。

隨著非線性優化理論、人工智能技術、群智能優化理論的不斷發展和融合，近些年學者們提出了一些基于啟發式搜索算法的物流配送路徑設計方法，如基于遺傳算法的物流配送路徑設計方法、基于模擬退火算法的物流配送路徑設計方法、基于禁忌搜索算法的物流配送路徑設計方法、基于蟻群算法的物流配送路徑設計方法，它們具有全局優化和通用性等特點，通過模擬自然界生物進化、群體搜索等行為，可以較快地找到物流配送路徑[11?13]。在實際應用中，物流配送路徑設計過程中，不確定性因素多，因素之間存在交叉影響，它們大多數集中于單一因素的物流配送路徑設計問題，同時，這些啟發式搜索算法存在一些不足，如發生早熟概率相當高，易找到局部最優的物流配送路徑[14?15]。

針對當前物流配送路徑設計方法存在求解效率低、求解錯誤率大的問題，為提高物流配送路徑求解的成功率，提出了基于蟻群優化算法的最優物流配送路徑設計方法。通過具體實例分析蟻群優化算法應用于最優物流配送路徑設計中的有效性。

1? 物流配送路徑優化問題和模型

1.1? 物流配送路徑優化問題描述

物流配送路徑優化問題就是為了達到一定的目標，如配送時間最短、配送路徑最短或者配送成本最低，并且滿足一些約束條件，如車輛最大載物量、配送結束時間等。對于不同配送點的客戶，找到最科學、合理的物流配送路徑，其包括許多關鍵因素，如下：

1） 配送中心，通常是物流配送過程中的車輛行駛路線的起點或終點，承擔全部車輛調度，通常情況下，其位置是固定的。

2） 車輛，主要包括車輛數量、車輛的最大行駛距離、規定最大載重等。

3） 客戶，即服務的對象，主要包括服務時間期限、優先級、貨物需求量。

1.2? 物流配送路徑優化模型

物流配送路徑優化問題可以使用有向圖[G=（V，A）]進行描述，[V={v0，v1，v2，…，vn}]表示客戶、配送點，[A={（vi，vj）vi，vj，i≠j}]表示客戶之間、配送點之間以及客戶與配送之間的有向弧，物流配送路徑優化問題采用圖1表示。

最優物流配送路徑優化問題的數學模型可以表示為：

[f=max F（S）=mink=1mi=0nj=1n（λij，xijk）]? （1）

式中：[k]表示車輛的編號;[m]表示車輛的數量;[n]表示客戶的數量。

物流配送路徑優化問題的約束條件如下：

1） 車輛訪問客戶[i]有且只有一次，即：

[yki=1]? ?（2）

2） 客戶點[i]的貨物需求量為[qi]，客戶需求的總量不能超過配送中心的所有車輛最大容量，即：

[（qi，yki）

3） [λij]表示[A]上的有向弧權重，[xijk]表示第[k]個車輛經過有向弧[（vi，vj）]時，[xijk=1]，否則，[xijk=0]，即有：

[xijk=1，? ? ?第k個車輛經過有向弧0，? ? ?第k個車輛未經過有向弧] （4）

綜上可知，物流配送路徑優化問題是一個典型的組合優化問題，蟻群優化算法是一種通過正反饋與分布式協作對問題進行求解的啟發式搜索算法。由于蟻群在尋找食物時，總是尋找一種從食物源到蟻穴的最短路徑，這與物流配送路徑優化問題十分相似，因此，引入改進蟻群優化算法對其進行求解。

2? 改進蟻群優化算法的最優物流配送路徑設計方法

2.1? 傳統蟻群優化算法

第[t]個時刻，節點[i]上的螞蟻數量為[Bi（t）]，那么螞蟻數量為[m=i=1nBi（t）]，[n]表示節點數，即客戶的數量，節點[i]和[j]之間的距離為[dij]，最初，全部路徑沒有螞蟻爬行過，初始信息素相同，即[τij（0）=C]，那么第[t]個時刻，節點[i]上的螞蟻[k]向節點[j]轉移的概率為：

[pkij（t）=ταij（t）ηβij（t）s∈allowedkταij（t）ηβij（t），? ? j∈allowedk0，? ? ?otherwise] （5）

式中：[allowedk]表示螞蟻[k]可以選擇的節點集合;[α]和[β]分別表示啟發因子和期望因子;[ταij（t）]和[ηβij（t）]分別表示節點[i]和[j]之間路徑的信息素量和能見度。

由于蟻群優化算法具有正反饋機制，路徑越短，那么該路徑上的信息素量越大，每一只螞蟻爬行一步后，對路徑上的殘留信息素進行更新，具體如下：

[τnewij=（1-ρ）τoldij+Δτij] （6）

[Δτij=k=1mτkij] （7）

式中：[ρ]表示信息素的揮發系數;[Δτij]表示節點[i]和[j]之間路徑的信息素增量。

2.2? 蟻群優化算法的改進

由于傳統蟻群優化算法存在一些不足，如搜索時間長、容易過早收斂等，從而影響了物流配送路徑的求解，因此本文對其進行改進。信息素的揮發系數[ρ]用于描述信息素量的持久程度，由于采用固定取值方式無法體現蟻群算法的特點，因此，本文采用適應變化取值方式加快了收斂速度，且減少了出現過早收斂的概率，具體如下：

[ρ=0.2，? ?NC∈[0，0.25NC_max]0.3，? ?NC∈[0.25NC_max，0.75NC_max]0.4，? ?NC∈[0.75NC_max，NC_max]]? （8）

式中NC和NC_max分別表示當前和最大迭代次數。

2.3? 改進蟻群優化算法的最優物流配送路徑求解

改進蟻群優化算法的最優物流配送路徑求解步驟如下：

1） 建立最優物流配送路徑優化問題相對應的有向圖。

2） 初始化蟻群，將所有螞蟻分別放置于節點之上，所有路徑上的初始信息素相同。

3） 迭代次數NC=0。

4） 計算每一只螞蟻選擇下一個爬行節點的概率，并根據計算結果爬行到下一個節點。

5） 對相鄰節點之間路徑上的信息素進行更新。

6） 當所有螞蟻對整個路徑進行爬行后，對整個路徑上的信息素進行更新。

7） 迭代次數NC=NC+1。

8） 如果NC>NC_max，那么輸出最優物流配送路徑。

3? 最優物流配送路徑設計方法的測試分析

3.1? 測試環境

為了分析改進蟻群優化算法的最優物流配送路徑設計方法的性能，采用Matlab軟件編程實現仿真測試。物流配送路徑參數設置為：有8個客戶點，1個配送中心，配送中心的位置為（0，0），車輛數量為3，車輛的最大載重為125，客戶點的位置和貨物需求量如表1所示，改進蟻群優化算法的最大迭代次數為200。

3.2? 測試結果與分析

采用傳統蟻群優化算法的優化物流配送路徑設計方法，如基于遺傳算法的物流配送路徑設計方法作對比測試，進行5次仿真實驗，統計每一次實驗的最優物流配送路徑長度，結果如圖2所示。從圖2可以看出：改進的蟻群優化算法的最優物流配送路徑長度平均值為111.39;傳統蟻群優化算法的最優物流配送路徑長度平均值為114.65;遺傳算法的最優物流配送路徑長度平均值為114.64。改進蟻群優化算法獲得了更優的物流配送路徑，提高了物流配送速度，可以減少物流配送的時間成本，實際應用價值更高。

統計每一次實驗找到最優物流配送路徑的迭代次數，具體如表2所示。

從表2可以看出，改進蟻群優化算法找到最優物流配送路徑的迭代次數要明顯少于傳統蟻群優化算法和遺傳算法，加快了最優物流配送路徑的求解效率，可以應用于大規模物流配送路徑設計問題的求解，實際應用范圍更加廣泛。

4? 結? 語

研究最優物流配送路徑具有十分重要的實際價值。為了解決當前物流配送路徑設計方法存在的一些問題，本文提出了基于蟻群優化算法的最優物流配送路徑設計方法，并與傳統蟻群優化算法、遺傳算法進行了對比測試，結果表明，改進蟻群優化算法可以獲得理想的物流配送路徑，而且搜索效率高，具有十分廣泛的應用前景。

參考文獻

[1] 葛顯龍，許茂增，王偉鑫.基于聯合配送的城市物流配送路徑優化[J].控制與決策，2016，31（3）：503?512.

[2] 蘭輝，何琴飛，邊展，等.考慮道路通行狀況的冷鏈物流配送路徑優化[J].大連海事大學學報，2015，41（4）：67?74.

[3] 葛顯龍，孔陽.帶有時間窗的生鮮物流配送路徑優化研究[J].數學的實踐與認識，2016，46（12）：78?87.

[4] 戴昕.基于反向學習策略粒子群的物流配送路徑優化研究[J].物流技術，2014，33（13）：291?294.

[5] 李周芳，楊樺.基于多蟻群優化的糧食物流配送路徑問題研究[J].中國農機化學報，2013，34（4）：283?286.

[6] 姜代紅.改進的遺傳算法在多目標物流配送路徑中的應用[J].科學技術與工程，2013，13（3）：762?765.

[7] 周艷聰，孫曉晨，余偉翔.基于改進遺傳算法的物流配送路徑優化研究[J].計算機工程與科學，2012，34（10）：118?122.

[8] 朱偉，徐克林，孫禹，等.Petri網融合蟻群算法的物流配送路徑規劃[J].浙江大學學報（工學版），2011，45（12）：2229?2234.

[9] 羅義學.基于智能Petri網的物流配送路徑優化算法[J].計算機工程與設計，2011，32（7）：2381?2384.

[10] 邱榮祖，鐘聰兒，修曉虎.基于GIS和禁忌搜索集成技術的農產品物流配送路徑優化[J].數學的實踐與認識，2011，41（10）：145?152.

[11] 邰曉紅，李璐.改進節約法下的物流配送路徑優化問題[J].遼寧工程技術大學學報（自然科學版），2016，35（6）：667?672.

[12] 胡麗麗，王戰備，趙峰.考慮駕駛員滿意度的高斯和聲搜索物流配送路徑優化算法[J].計算機應用研究，2015，32（12）：3622?3625.

[13] 侯玉梅，賈震環，田歆，等.帶軟時間窗整車物流配送路徑優化研究[J].系統工程學報，2015，30（2）：240?250.

[14] 鄧必年.基于蟻群優化算法的物流配送路徑研究[J].現代電子技術，2017，40（15）：167?170.

[15] 李杰，趙旭東，王玉霞.面向電商終端物流配送路徑優化的改進蟻群算法[J].制造業自動化，2017，39（10）：90?94.