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

何宇翔

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

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

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

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

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

1.1 模型設(shè)計(jì)

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

假設(shè)物流配送任務(wù)有一個(gè)中心倉(cāng)庫(kù)及若干個(gè)目標(biāo)節(jié)點(diǎn)，每輛車均從中心倉(cāng)庫(kù)出發(fā)，且運(yùn)輸不超過(guò)核定載重。按照指定路線到達(dá)目標(biāo)節(jié)點(diǎn)，卸載該節(jié)點(diǎn)所需的貨物，然后再返回中心倉(cāng)庫(kù)的路線模型，如圖1所示。

圖1 物流配送模型

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

1）每個(gè)目標(biāo)節(jié)點(diǎn)僅會(huì)被訪問(wèn)一次。

2）每條配送路徑的長(zhǎng)度均不能超過(guò)車輛滿油時(shí)的最大行駛距離。

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

4）所有目標(biāo)節(jié)點(diǎn)必須包含在配送路線中。

1.2 問(wèn)題公式化

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

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

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

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

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

2 路徑優(yōu)化算法設(shè)計(jì)

2.1 蟻群算法的改進(jìn)

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

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

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

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

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

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

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

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

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

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

式中，El為第l條路徑的總長(zhǎng)度，且El＞Ebest。

2.2 算法描述

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

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

2）生成目標(biāo)節(jié)點(diǎn)距離矩陣DN×N，構(gòu)建每只螞蟻m的待訪問(wèn)節(jié)點(diǎn)集合N(m)，并建立禁忌表。

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

4）計(jì)算每只螞蟻的路徑長(zhǎng)度。

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

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

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

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

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

3 算法仿真

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

為了驗(yàn)證路徑優(yōu)化算法的可行性，該文在無(wú)量綱的網(wǎng)格地圖中，使用一個(gè)中心倉(cāng)庫(kù)與隨機(jī)生成的11 個(gè)或34 個(gè)目標(biāo)節(jié)點(diǎn)進(jìn)行路徑求解測(cè)試，實(shí)例描述如下：

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

圖2 11個(gè)目標(biāo)節(jié)點(diǎn)分布圖

圖3 34個(gè)目標(biāo)節(jié)點(diǎn)分布圖

3.2 仿真結(jié)果

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

圖4 11個(gè)目標(biāo)節(jié)點(diǎn)規(guī)劃的配送路徑

圖5 34個(gè)目標(biāo)節(jié)點(diǎn)規(guī)劃的配送路徑

而計(jì)算得到的路徑總長(zhǎng)度，分別如圖6-圖7所示。

圖6 11個(gè)目標(biāo)節(jié)點(diǎn)規(guī)劃路徑的總長(zhǎng)度

圖7 34個(gè)目標(biāo)節(jié)點(diǎn)規(guī)劃路徑的總長(zhǎng)度

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

3.3 算法對(duì)比

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

實(shí)驗(yàn)計(jì)算得到3 種算法訪問(wèn)34 個(gè)目標(biāo)節(jié)點(diǎn)的最終路徑總長(zhǎng)度，如表1 所示。

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

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

4 結(jié)束語(yǔ)

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