帶目標權重的物流路徑優化研究—基于模擬退火蟻群算法

陳 志， 江治杰

(四川輕化工大學a.管理學院；b.數學與統計學院， 四川 自貢 643000)

引 言

隨著我國經濟體量增大，貿易額持續增長，貨物量增多，物流行業的競爭也愈演愈烈。發改委數據顯示，2018年我國社會物流總費用高達13.3萬億元，同比增長9.8%，增速比2017年同期提高了0.7個百分點，其中運輸費用共計6.9萬億元，占社會物流總費用的比重為51.88%，占GDP的比重為7.7%[1]。以上數據顯示，運輸費用在社會物流總費用里的占比最高，也是物流配送中最重要的一個環節。因此，解決運輸費用問題最關鍵的是尋找更好的物流路徑，通過對路徑進行規劃，使得物流企業能有效降低物流配送成本，進一步提高配送效率。

目前，已有許多學者對物流路徑問題進行研究，孫沁等人[2]建立了以配送費用為目標函數的數學模型，對基本蟻群算法的隨機轉移規則以及局部搜索能力進行改進，通過仿真表明改進蟻群算法的性能更好。王垚等人[3]考慮了時間和成本因素，建立了生鮮食品的選址和路徑優化問題模型，通過改進的細菌覓食算法進行仿真，結果表明該算法在處理多目標物流路徑優化問題上有一定優勢。朱杰等人[4]考慮了配送車輛的固定成本以及運輸成本，在時間窗和配送車輛載重的條件限制下，建立了帶時間窗的配送車輛物流路徑的數學模型，通過對基本蟻群算法進行改進，使得改進的算法能很好的解決所建立的模型。蔣麗等人[5]以時間懲罰成本和距離成本綜合最小為目標函數，建立帶時間約束的外賣配送路徑數學模型，實驗結果表明改進算法有效。張立毅等人[6]以碳排放成本為目標函數，建立了低碳物流路徑的數學模型，通過引入混沌系統以及模擬退火思想對基本蟻群算法進行改進，用以解決所建立的模型，結果表明算法的改進合理有效。周顯春等人[7]主要考慮了限行或施工情況下道路的實時情況，構建多約束條件下的質量評價數學模型，利用改進基本蟻群算法的啟發函數和信息素來解決所建立的模型，實驗取得比較滿意的結果。袁亞博等人[8]通過對基本蟻群算法的初始信息素、局部信息素以及全局信息素進行改進，進而求解最短路徑問題，仿真結果表明改進的算法有一定的速度優勢。郭寶恩[9]將Spark并行計算融入到蟻群算法，用以解決大規模TSP問題，結果表明該改進方式有較大的速度優勢。裴小兵等人[10]將配送車輛載重量以及配送車輛數融入到模型中，建立多目標配送路徑優化模型，在模擬退火算法中引入記憶函數并通過GIS手段對其進行改進，實驗結果表明此改進方法提高了求解精度。Kalayci等人[11]通過將變鄰域搜索與基本蟻群算法相結合來解決配送車輛的車容量限制的路徑優化問題，仿真表明改進的蟻群算法有效。

經研究發現，以往的研究主要考慮配送時間最少或配送距離最短或配送成本最小等單方面最優。但考慮到物流企業對物流配送時間、距離以及運輸成本的要求有所不同，本文通過設置目標權重將配送時間、配送距離和配送成本三者統一起來建立物流路徑數學模型，進而解決不同需求的配送問題。若企業更加看重配送時間，則可將時間權重適當放大；若企業不考慮配送時間對本次配送的影響，則可將時間權重置0處理；同樣可對距離權重、成本權重做類似處理。此外，本文模型還有如下考慮：

(1)物流配送距離采用的是兩地之間的實際距離(由高德地圖APP獲得)。目前大多數學者考慮的是兩地之間的直線距離，這與實際距離偏差較大，因而考慮實際距離作為本文研究的距離。

(2)物流配送時間采用的是配送車輛在兩地之間的高速路上行駛時間和非高速路行駛時間，這使得配送時間更接近實際時間。

(3)配送成本采用的是動用配送車輛的固定成本、配送過程中燃料的消耗成本以及高速路上的通行成本。

20世紀90年代，意大利學者Dorigo等人通過模擬螞蟻尋覓食物的過程而提出的一種智能算法，即蟻群算法(Ant Colony Algorithm，ACA)[12-13]。蟻群算法具有較強的正反饋性、魯棒性以及并行計算的特性，廣泛應用于求解路徑優化問題。由于基本蟻群算法易陷入局部最優以及收斂速度過慢的不足，因此本文將基本蟻群算法的轉移規則和信息素的更新作相應改進，在此基礎上融入模擬退火算法，建立模擬退火蟻群算法來求解本文所建立的數學模型。通過實例仿真對比可知：模擬退火蟻群算法能更快搜尋到比基本蟻群算法更優的解，進而證明模擬退火蟻群算法的可行性以及模型的合理性。

1 物流路徑數學模型

1.1 問題的描述

物流配送路徑優化問題的描述為：已知位置的某一物流配送中心有統一車型的配送車輛，其車輛數為m輛，配送車輛的載重為W，共同向n個已知位置和需求量的客戶點提供配送服務，在滿足車輛載重的情況下完成貨物的配送。其目的是使得目標函數值最小，即達到最優。本文綜合考慮了物流配送時間、距離以及運輸成本，其中，運輸成本具體細化為動用配送車輛的固定成本、燃油消耗成本和道路行駛費用三個方面。建立以綜合成本最優為目標的物流路徑優化綜合模型。為了使得本文更貼近現實，本文考慮的距離均為高德地圖APP經過定位所顯示的高速距離與非高速距離，這比直接對兩點的坐標用距離公式求出的距離更接近于實際情況。

1.2 問題的假設

考慮到模型以外的因素對模型的影響，于是簡化數學模型，對數學模型作以下假設：

(1)物流配送中心的位置以及客戶節點的位置均已知；

(2)所有節點的總需求量不超過物流配送中心的總庫存量；

(3)每條路線上的節點需求量總和不超過在這條路線上行駛的物流配送車輛的載重量；

(4)每個節點最多可由一輛物流配送車輛為其服務；

(5)在配送過程中，物流配送車輛到達某個客戶點則必須為其服務，待服務完成后，立即離開此節點，前往下一個節點或者配送中心；

(6)物流配送車輛都是從配送中心出發，最終必須回到出發點；

(7)物流配送車輛在同等程度的道路上均為勻速行駛。

1.3 綜合成本分析

本文綜合考慮了配送過程中配送時間、配送距離以及運輸成本，其中運輸成本是指動用車輛的固定成本、運輸燃油成本和道路行駛通行費用(高速收費)，建立一個綜合成本最優的數學模型，以便配送公司可以根據企業的不同要求進行相應的調整，進而實現高效配送。

1.3.1 配送時間分析

在信息化時代的今天，客戶的時間觀念越來越強，迫使物流公司必須加強時間意識以滿足客戶需求，即配送時間T為：

(1)

(2)

1.3.2 配送距離分析

在物流配送過程中，隨著基礎設施的不斷完善，通往兩地的線路也趨于多樣化，故物流公司會重新調整配送線路來盡可能的減少配送距離，進而降低物流公司的物流成本，即配送距離L為：

(3)

其中，dij表示節點i與節點j之間的實際距離，即高速距離與非高速距離之和。

1.3.3 固定成本分析

物流配送的固定成本為在某地區范圍內動用某車輛的費用，與行駛里程無關的常量，即固定成本C1為：

(4)

其中，fk表示第k輛配送車運行的固定成本，m表示配送中心的車量數，xi0k=1表示車輛k已使用，xi0k=0表示車輛k未被使用。

1.3.4 車輛運輸成本分析

車輛的運輸成本包括車輛通行費用(高速路段費用)以及車輛在行駛過程中所產生的油耗費用，即運輸成本C2為：

(5)

其中，f表示高速路段單位距離收費標準，g表示車輛平均每公里消耗的燃料費用。

1.4 數學模型

基于上述描述，建立帶目標權重的物流路徑優化問題的綜合模型：

目標函數：

minZ=p1T+p2L+p3C1+p4C2

(6)

約束條件：

(7)

(8)

(9)

(10)

(11)

(12)

(13)

其中：(6)式表示目標函數綜合成本最小，p1，p2，p3，p4分別表示時間、距離、固定成本和配送成本的目標權重且均為大于等于0的數，各企業可根據不同需求進行調整；(7)式表示車輛必須從配送中心出發，最終又返回配送中心；(8)式表示完成此次配送任務需要的車輛總數；(9)式表示此次配送任務中，此路徑上的節點總需求量不超過車輛的最大裝載量，qi指節點i的需求量；(10)式表示車輛k到達節點j則必為節點j提供服務；(11)式表示車輛k為節點i提供服務，然后必須離開節點i；(12)式與(13)式表示一個節點只能被訪問一次。

2 模擬退火蟻群算法

2.1 基本蟻群算法的改進

2.1.1 轉移規則的改進

由于基本蟻群算法在搜索過程中的隨機性容易導致局部最優，于是本文將隨機搜索和確定搜索相結合，擴大搜索范圍，進而使蟻群算法盡可能的避免局部最優[7]，即：

(14)

(15)

表示螞蟻k在t時刻節點i與節點j的轉移概率；τij指節點i到節點j的信息素濃度，α指信息素的程度因子；ηij指啟發函數，即螞蟻從節點i到節點j的期望程度，β指啟發函數的程度因子；ωij指節約值，ωij=di0+d0j-dij，ε指節約值的程度因子；allowk表示車輛在滿足載重情況下可訪問的節點集合。若q

2.1.2 信息素的更新改進

本文對蟻群算法信息素的更新方式提出了新的理解，即螞蟻在搜尋過程中，就路徑上原有的信息素而言，其濃度會隨著時間的推移而逐漸降低；就螞蟻經過此路徑攜帶的信息素而言，通過歸一化去量綱的方式將攜帶的信息素Q分布到其途徑的路徑上，其更新公式如下：

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(16)

(17)

(18)

其中，Zmax表示螞蟻在搜尋過程中綜合成本的最大值，Zmin表示螞蟻在搜尋過程中綜合成本的最小值，Zk表示螞蟻k在此次搜尋中的綜合成本。

2.2 引入模擬退火算法思想

模擬退火算法是模擬固體退火過程的一種隨機搜尋算法。由于算法具有概率突跳的特性，這恰好能解決蟻群算法在搜索過程中陷入局部最優的不足，使得算法概率性的跳出局部最優，逐漸向全局最優方向轉化，進而縮短算法收斂用時。因此，本文將模擬退火思想與改進的蟻群算法相結合。

具體結合方式如下：當蟻群中的每一只螞蟻都完成了一次搜索之后，必然存在一個屬于此次搜索的最優解，然后在此最優解的基礎上隨機生成除當前最優解之外的解集，最后再由模擬退火算法中的概率來判斷算法是否接受新解替代此前的最優解[10]。

由于模擬退火算法中的退火過程涉及到溫度變量，故引入模擬退火算法思想時需要設定一個溫度變量T，其范圍為[Tmin,Tmax]且隨迭代次數的變化而變化。算法的初始溫度設置為T(0)=Tmax。當蟻群中每只螞蟻都完成了一次搜尋后，必有一個屬于此次搜尋結果的最優解，不妨設為螞蟻i在此次搜尋過程中搜尋到的最優解，記為Zi。螞蟻i在此次搜尋過程中走過的路徑全部放入禁忌表中，這就表示得到了模擬退火算法中的初始解集[14-15]。在此初始解的基礎上隨機生成除初始解之外的新的可行解，計算新的可行解對應的目標函數值為Zj。由初始解到新的可行解的目標函數值的變化量ΔZ為：

ΔZ=Zj-Zi

(19)

若ΔZ<0，那么算法接受新解作為當前最優解，否則就要考慮退火概率：

(20)

此時算法生成一個隨機數rand，介于0與1之間。若p>rand，那么算法接受新解Zj作為當前最優解；否則，拒絕新解Zj，保持原來的解Zi。

在一次搜索完成及信息素的更新完成后，對算法進行降溫操作，其降溫函數為：

T(t+1)=(1-ζ)T(t)

(21)

其中，1-ζ為降溫系數且為介于0與1之間的常數。當溫度T較高時，算法將以較高的概率來接受相對較差的解加入可行解集，使得更多的路徑上分布有更多的信息素，避免遺漏最優解，即避免陷入局部最優。隨著溫度T的降低，其接受概率也隨之減少，同樣對相對較差的解接收概率也隨之變小，從而使得信息素集中分布在路徑上，故算法能很快的收斂。為了提高算法的收斂速度，縮短算法的搜索時間，一般情況下，算法常常采用相對較小的降溫系數ζ。即使如此，算法也會增加陷入局部最優解的風險，為此，在算法中引進回火機制，當T

3 帶目標權重的物流路徑優化模型求解步驟

利用模擬退火蟻群算法求解帶目標權重的物流路徑問題的具體步驟如下：

步驟1錄入數據。錄入節點的規模n及各節點的經緯度坐標(x,y)，構造無向圖G；錄入高德地圖APP測算的兩地之間的高速路段距離和非高速路段距離；錄入各節點的需求量q及車輛最大裝載量W。

步驟2參數初始化。設螞蟻數為m，令算法的循環次數Nc=0，再設置算法的最大循環次數Ncmax，各路徑信息素的初始化，基本蟻群算法中各參數以及模擬退火算法思想中的參數設置。

步驟3建立解空間，將所有螞蟻全部放置在配送中心，建立禁忌表Tabuk，即螞蟻目前已經訪問的節點和配送中心構成的集合；建立allowk表，即沒有訪問的但可以進行訪問的節點的集合。

步驟4在滿足車輛載重的限制下，每只螞蟻按照(14)式與(15)式確定性以及隨機性概率的搜索下一個將訪問的節點，并將其放入Tabuk中，表示螞蟻在這次搜尋過程中途經了該節點。更新車輛的載重信息，判斷車輛是否出現超載，若超載，則車輛返回配送中心，并將配送中心放入Tabuk中，如此反復執行此步驟，直到所有螞蟻訪問完全部節點，即將所有節點都放入Tabuk中，并返回物流配送中心。

步驟5所有螞蟻都完成了一次搜尋任務，即得到了模擬退火算法中的初始解集。計算每只螞蟻所經過的路徑所產生的綜合成本Zk，再根據退火機制生成一組新的可行解，然后由(19)式表示退火概率來進行判定是否接受剛剛所生成的新可行解為當前解，并判定車輛是否超載；若超載，則重新生成有別于超載時的可行解；若未超載，則算法接受該可行解作為當前最優解。

步驟6得到當前的最優解后，根據(16)式～(18)式進行信息素的更新操作，清空當前的Tabuk，循環次數自加1。

步驟7當循環次數達到設定的最大循環次數時，則算法終止；否則跳轉至步驟4繼續進行迭代，循環次數Nc=Nc+1，同時清空Tabuk；當連續多次迭代后均無更優的解出現時，算法終止，輸出配送路徑以及綜合成本最優值。

4 仿真實驗

經多次重復仿真實驗，基本蟻群算法的參數設置為：α=1.5，β=2，m=40輛，ρ=0.7,Q=100,Ncmax=200；模擬退火蟻群算法的參數設置為：α=1，β=3.5，ε=2，ρ=0.3，m=40輛，Tmax=100 000,Tmin=500,ξ=0.4，Q=100，Ncmax=200。

本文模型參數設置為：配送車輛載重量為20 t，使用一輛配送車輛的費用為fk=500元，配送車輛平均每公里消耗的燃油費用g=1.7元，配送車輛在高速路段上平均每公里的通行費用k1=1.75元，配送車輛在高速路段上的行駛速度v1=80 km/h，在非高速路段上的行駛速度v2=30 km/h，四個目標權重p1，p2，p3，p4分別為1，1，1，1。企業可根據自身的需要對目標權重進行賦值使得滿足其配送需求。

本文以西南地區各市某物流為研究對象，共計40個市，其經緯度坐標(由高德地圖獲取)及需求量見表1。

表1 西南地區40個市的經緯度坐標及需求量

由表1可知，城市節點1的需求量為0，即為配送中心，向其余39個城市進行物流配送。其余39個城市節點的需求量總和為100.43 t，,需要6輛載重量為20 t的車輛為其進行物資配送。

設計適合本文模型的蟻群算法，再由MATLAB 2014a軟件對蟻群算法程序進行多次重復實驗選取最優的解，其迭代尋優曲線如圖1所示，所有車輛的配送線路如圖2所示，由于城市節點比較密集，故沒有對城市節點進行標號處理。

圖1 蟻群算法迭代曲線

由圖1及程序運算結果可知，蟻群算法在第162次迭代時搜尋到較好的綜合成本。

圖2 蟻群算法配送線路圖

由圖2及程序運算結果可知：蟻群算法在解決本文模型所需綜合成本為89 018.547 9元，且6輛車的具體配送情況見表2。

表2 蟻群算法配送車輛配送情況

由MATLAB 2014a軟件對本文的模擬退火蟻群算法程序進行多次重復實驗選取最優的綜合成本，其迭代尋優曲線如圖3所示，所有車輛的配送線路如圖4所示。

圖3 模擬退火蟻群算法迭代曲線

由圖3及程序運算結果可知，模擬退火蟻群算法在第13次迭代時搜尋到較好的綜合成本。

圖4 模擬退火蟻群算法配送線路圖

由圖4及程序運算結果可知：模擬退火蟻群算法在解決本文模型所需綜合成本為62 502.152 1元，且6輛車的具體配送情況見表3。

表3 模擬退火蟻群算法配送車輛配送情況

實驗結果比較分析：由圖1與圖3對比可知，模擬退火蟻群算法的收斂速度明顯比基本蟻群算法快，說明模擬退火蟻群算法能擴大其搜索范圍，很好的跳出了局部最優；由圖2與圖4對比可知，模擬退火蟻群算法安排的配送線路圖比基本蟻群算法更有序，且綜合成本更低，低了26 516.395 8元；由表2與表3可知，兩種算法都將100.43 t物資配送完畢，模擬退火蟻群算法得出的配送時間、配送距離以及運輸成本都分別優于基本蟻群算法。由此可見，模擬退火蟻群算法的綜合成本和收斂速度都比基本蟻群算法低，這證明了本文模型的合理性以及模擬退火蟻群算法解決物流配送問題的有效性。

5 結束語

本文以西南地區各市某物流為研究對象，通過目標權重將配送時間、配送距離以及配送運輸成本構建為一個綜合成本最優的數學模型，企業可根據自身的需要對目標權重進行重新賦值即可滿足其配送需求。由于考慮到時間和距離，因此本文將實際距離分為高速距離與非高速距離，車輛在不同程度的道路上行駛速度不同，進而使得配送時間更準確。將基本蟻群算法的轉移規則和信息素更新作相應修改，再融入模擬退火思想，進而對文中所建立的模型進行求解。實驗結果表明：模擬退火蟻群算法能搜尋到比基本蟻群算法更優的綜合成本，且收斂速度更快，表明本文模型的合理性以及模擬退火蟻群算法的有效性。由于影響物流配送的因素很多，本文所考慮的因素有限，因此，在今后的研究中將考慮其它他更多的影響因素，使得更接近于現實生活。