基于蟻群算法的物流配送路徑優(yōu)化方法研究

何宇翔

（長沙理工大學水利與環(huán)境工程學院，湖南長沙 410114）

近年來，物流配送網(wǎng)絡智能規(guī)劃得到了廣泛的研究與應用。但由于配送車的數(shù)量有限，且其最大行駛距離為固定值。因此，在每輛配送車均不超過最大行駛距離的條件下優(yōu)化配送路線，使其可在訪問所有目標倉庫的同時確保行駛路徑最短，可以直接節(jié)省時間與能耗成本[1-4]。

優(yōu)化配送路徑，不僅能縮短配送時間、減少成本并提升用戶滿意度，還可緩解交通壓力、降低運輸污染并保護環(huán)境，因此具有重要的研究價值。物流配送路徑優(yōu)化(Logistics Distribution Path，LDP)是一個經(jīng)典的組合優(yōu)化問題[5-8]，該問題的計算量大、復雜程度也較高。目前，國內(nèi)外用于求解此類問題的方法主要有精確優(yōu)化方法(Precise Optimization Method)、啟發(fā)式算法(Heuristic Algorithm)、亞啟發(fā)式方法(Metaheuristics Algorithm)與智能優(yōu)化方法等。

蟻群優(yōu)化(Ant Colony Optimization，ACO)算法是一種仿生學智能算法，其通過使用信息素來選擇路徑，并朝著最優(yōu)解的方向不斷改進，故具有較強的自組織性。然而該算法存在易進入早熟狀態(tài)及過早陷入局部最優(yōu)解的問題，由此便會造成最終解并非全局最優(yōu)解。所以將該算法加以改進，克服其所存在的不足后，即可作為最優(yōu)配送路徑的求解方法。

1 物流配送路徑優(yōu)化問題建模

1.1 模型設計

在港口物流配送的場景中，來自海外的貨物首先需要被分撥至目的倉庫中進行一級分配，或需將來自各地區(qū)的貨物轉(zhuǎn)移到同一艘貨輪上。算法應合理規(guī)劃每輛車的運輸路線[9-11]，進而令車輛間的運輸任務不會相互沖突，并使整個物流配送任務的運輸效率達到最高。

假設物流配送任務有一個中心倉庫及若干個目標節(jié)點，每輛車均從中心倉庫出發(fā)，且運輸不超過核定載重。按照指定路線到達目標節(jié)點，卸載該節(jié)點所需的貨物，然后再返回中心倉庫的路線模型，如圖1所示。

圖1 物流配送模型

根據(jù)配送問題中的實際情況，可總結(jié)出以下幾個約束條件：

1）每個目標節(jié)點僅會被訪問一次。

2）每條配送路徑的長度均不能超過車輛滿油時的最大行駛距離。

3）一條配送路徑上所有目標節(jié)點的貨物總和不能超過一輛汽車的核定載貨量。

4）所有目標節(jié)點必須包含在配送路線中。

1.2 問題公式化

假設一共有M個目標節(jié)點需要到達，目標節(jié)點i處的貨物量為qi，i∈[1,2,…,M]，而中心倉庫的編號為0，節(jié)點i與j之間的最短路徑長度則為dij。可調(diào)配的汽車共有K輛，車輛k的核定載貨量為Qk，滿油時的最大行駛距離為Dk，k∈[1,2,…,K]，nk是需要分配的目標節(jié)點數(shù)。將該目標節(jié)點的集合定義為，其中表示該目標點在車輛k的配送路線中所處的位置為i。

若將運輸效率最高定義為整個路徑優(yōu)化的總距離最短，則總運輸距離表示為：

其中，符號函數(shù)sgn(·)可定義為：

將約束條件歸納為數(shù)學公式，則有：

因此，在滿足式（3）-（6）所有的條件下，物流配送路徑優(yōu)化問題可公式化為：

2 路徑優(yōu)化算法設計

2.1 蟻群算法的改進

在經(jīng)典蟻群算法中，螞蟻會直接選擇由信息素濃度所決定的、概率值最大的節(jié)點來作為下個目標節(jié)點[12-14]。故在一定迭代步數(shù)后，不同節(jié)點對應的路徑信息素含量差距越來越大，螞蟻便越難以探索新的路徑，進而使尋路過程陷入早熟的狀態(tài)。

為使螞蟻能有充分探索新路徑的可能性，文中采用強化學習中的貪心算法(Greedy Algorithm)思想來對ACO 加以改進，并選擇螞蟻下一個要訪問的節(jié)點[15-16]。具體選擇規(guī)則如下：

式中，ε為探索概率，k為衰減系數(shù)，p為迭代過程中產(chǎn)生的選擇概率。

經(jīng)典蟻群算法中，更新規(guī)則如下：

式中，ρ為信息素揮發(fā)因子，ρ∈(0,1)；τ為信息素濃度，σ為初始系數(shù)；Lk為當前路徑長度。當螞蟻k經(jīng)過路徑i→j時，該路徑上的信息素才會更新，并增加

此處螞蟻默認為可以無限次地訪問目標節(jié)點，且不存在約束條件。然而，實際路徑規(guī)劃問題中的車輛存在最大行駛距離約束。因此，經(jīng)典蟻群算法中的信息素濃度更新策略無法篩除不滿足約束條件的路徑，故需根據(jù)具體問題設計不同的信息素濃度更新方法。

該設計的更新思路為：當K只螞蟻完成節(jié)點訪問后，對產(chǎn)生的K條路徑進行評估。標記滿足單個車輛最大行駛距離約束的規(guī)劃路徑，使之成為可行解；而對不滿足約束條件的規(guī)劃路徑，則朝著滿足約束的方向轉(zhuǎn)化。令最終的解空間均為滿足約束條件的規(guī)劃路徑，從中選擇總路徑長度最短的規(guī)劃方案便一定是滿足約束條件下的最優(yōu)解。

此次設計的局部最優(yōu)解信息素濃度更新方法如下：

式中，Ebest為當前最優(yōu)路徑上所有螞蟻路徑的總長度。

對于非最優(yōu)解，所設計的信息素濃度更新方法為：

式中，El為第l條路徑的總長度，且El＞Ebest。

2.2 算法描述

基于ACO 的路徑優(yōu)化算法步驟可描述如下：

1）初始化螞蟻數(shù)K、信息素啟發(fā)因子α、路徑啟發(fā)因子β、信息素揮發(fā)因子ρ、探索概率ε、衰減系數(shù)k、初始選擇概率p0以及最大迭代次數(shù)Nc。

2）生成目標節(jié)點距離矩陣DN×N，構建每只螞蟻m的待訪問節(jié)點集合N(m)，并建立禁忌表。

3）從中心倉庫開始，為每只螞蟻選擇下一個目標節(jié)點，直至所有節(jié)點均被訪問。首先對螞蟻k，根據(jù)式（9）計算路徑選擇概率p；然后根據(jù)式（8）選擇下個目標節(jié)點j，并將其加入禁忌表；最終判斷所有螞蟻是否訪問完全部節(jié)點，若是，則轉(zhuǎn)至步驟4），否則重新計算選擇概率p，并完成后續(xù)步驟。

4）計算每只螞蟻的路徑長度。

5）判斷每只螞蟻的路徑長度是否滿足約束，是則判定為可行解，且選擇長度最小的解作為局部最優(yōu)解。

6）對可行解，根據(jù)式（12）更新每條路徑的信息素濃度。

7）對不可行解，則依據(jù)式（14）更新每條路徑的信息素濃度。

8）重復步驟3）～步驟8），直至Nc達到最大迭代次數(shù)。

9）輸出全局最優(yōu)解，作為路徑優(yōu)化的最終結(jié)果。

3 算法仿真

3.1 仿真數(shù)據(jù)

為了驗證路徑優(yōu)化算法的可行性，該文在無量綱的網(wǎng)格地圖中，使用一個中心倉庫與隨機生成的11 個或34 個目標節(jié)點進行路徑求解測試，實例描述如下：

假設中心倉庫（標號0）位于坐標（70，40）處，共有20 輛車可供調(diào)度，且每輛車載重1 t。則目標節(jié)點的分布，如圖2-圖3 所示。

圖2 11個目標節(jié)點分布圖

圖3 34個目標節(jié)點分布圖

3.2 仿真結(jié)果

算法采用Matlab 軟件平臺進行仿真，輸入仿真數(shù)據(jù)并通過路徑優(yōu)化算法進行求解，兩種不同目標節(jié)點所獲得的規(guī)劃路徑結(jié)果分別如圖4-圖5 所示。

圖4 11個目標節(jié)點規(guī)劃的配送路徑

圖5 34個目標節(jié)點規(guī)劃的配送路徑

而計算得到的路徑總長度，分別如圖6-圖7所示。

圖6 11個目標節(jié)點規(guī)劃路徑的總長度

圖7 34個目標節(jié)點規(guī)劃路徑的總長度

從上述仿真結(jié)果圖可看出，無論是11 個或是34個目標節(jié)點，文中所設計的路徑優(yōu)化算法均能夠設計出較為合理的配送路徑，并能快速收斂得到最短的路徑長度，從而優(yōu)化配送成本。

3.3 算法對比

為驗證所提算法的有效性，將本算法與標準蟻群算法、遺傳算法(Genetic Algorithm，GA)進行對比，以此來分析算法的性能。3 種算法的初始仿真參數(shù)設置如下：該算法和標準蟻群算法的螞蟻數(shù)量均為50 個，信息素啟發(fā)因子均為1，路徑啟發(fā)因子均為5。遺傳算法的交叉率設置為0.8，變異率為0.3。

實驗計算得到3 種算法訪問34 個目標節(jié)點的最終路徑總長度，如表1 所示。

表1 規(guī)劃路徑總長度

由表1 可以看出，根據(jù)該文算法所規(guī)劃出的路徑總長度最小，標準蟻群算法則達到了所提算法的兩倍以上。這是由于標準蟻群算法陷入了局部最優(yōu)，故無法找到全局最優(yōu)解。而遺傳算法雖收斂速度快，但最終解的質(zhì)量較差。

4 結(jié)束語

配送環(huán)節(jié)是現(xiàn)代物流行業(yè)中的關鍵，提高配送效率可大幅縮減物流業(yè)的成本。針對普遍存在的配送路徑優(yōu)化問題，文中首先歸納出此問題的一般模型及實際問題的約束條件，并將其總結(jié)為數(shù)學形式的表達。然后介紹了蟻群算法能尋找最短路徑的根本原理及其過程，最終將蟻群算法融入物流配送的路徑優(yōu)化問題中，并分析二者的相似性。同時還將路徑優(yōu)化問題的各個條件對應到蟻群算法的各要素中，進而設計出基于ACO 的路徑優(yōu)化算法，再根據(jù)兩個實例仿真分析了算法的有效性。結(jié)果表明，該算法能夠滿足路徑優(yōu)化的設計目標。