改進(jìn)蟻群優(yōu)化算法的最優(yōu)物流配送路徑設(shè)計(jì)

張濱麗 卞興超

摘? 要： 針對(duì)傳統(tǒng)蟻群優(yōu)化算法難以找到全局最優(yōu)的物流配送路徑，物流配送的時(shí)效性差等缺陷，為獲得理想的物流配送路徑，提出基于改進(jìn)蟻群優(yōu)化算法的最優(yōu)物流配送路徑設(shè)計(jì)方法。首先，對(duì)物流配送路徑優(yōu)化設(shè)計(jì)問題進(jìn)行分析，建立物流配送路徑優(yōu)化模型;然后，將蟻群置于物流配送的起始點(diǎn)，通過搜索下一節(jié)點(diǎn)、信息激素更新等模擬自然界蟻群尋食機(jī)制，找到從起始點(diǎn)到配送目標(biāo)點(diǎn)的最優(yōu)物流配送路徑，并對(duì)傳統(tǒng)蟻群優(yōu)化算法的不足進(jìn)行相應(yīng)的改進(jìn);最后，通過具體實(shí)例分析改進(jìn)蟻群優(yōu)化算法應(yīng)用于最優(yōu)物流配送路徑設(shè)計(jì)中的有效性。改進(jìn)蟻群優(yōu)化算法可以在短時(shí)間內(nèi)成功找到最優(yōu)物流配送路徑，物流配送時(shí)間要少于其他物流配送路徑設(shè)計(jì)方法，能夠?yàn)樘岣呶锪髌髽I(yè)的經(jīng)濟(jì)效益提供有價(jià)值的參考信息。

關(guān)鍵詞： 物流配送; 物流路徑設(shè)計(jì); 蟻群優(yōu)化算法改進(jìn); 路徑優(yōu)化模型; 算法有效性分析; 企業(yè)效益提升

中圖分類號(hào)： TN02?34; TP183? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)： 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? 引? 言

隨著經(jīng)濟(jì)全球化進(jìn)程的不斷加快，企業(yè)的物流活動(dòng)日益頻繁，電子商務(wù)快速發(fā)展，物流成為企業(yè)的一個(gè)重要環(huán)節(jié)[1]。運(yùn)輸費(fèi)用占用物流費(fèi)用的比重相當(dāng)高，運(yùn)輸費(fèi)用與物流配送路徑選取直接相關(guān)。物流配送的目的就是為顧客提供最優(yōu)的服務(wù)，同時(shí)，盡可能地降低物流配送成本，因此，設(shè)計(jì)最優(yōu)的物流配送路徑具有重要的研究意義[2?3]。

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

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

針對(duì)當(dāng)前物流配送路徑設(shè)計(jì)方法存在求解效率低、求解錯(cuò)誤率大的問題，為提高物流配送路徑求解的成功率，提出了基于蟻群優(yōu)化算法的最優(yōu)物流配送路徑設(shè)計(jì)方法。通過具體實(shí)例分析蟻群優(yōu)化算法應(yīng)用于最優(yōu)物流配送路徑設(shè)計(jì)中的有效性。

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

1.1? 物流配送路徑優(yōu)化問題描述

物流配送路徑優(yōu)化問題就是為了達(dá)到一定的目標(biāo)，如配送時(shí)間最短、配送路徑最短或者配送成本最低，并且滿足一些約束條件，如車輛最大載物量、配送結(jié)束時(shí)間等。對(duì)于不同配送點(diǎn)的客戶，找到最科學(xué)、合理的物流配送路徑，其包括許多關(guān)鍵因素，如下：

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

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

3） 客戶，即服務(wù)的對(duì)象，主要包括服務(wù)時(shí)間期限、優(yōu)先級(jí)、貨物需求量。

1.2? 物流配送路徑優(yōu)化模型

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

最優(yōu)物流配送路徑優(yōu)化問題的數(shù)學(xué)模型可以表示為：

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

式中：[k]表示車輛的編號(hào);[m]表示車輛的數(shù)量;[n]表示客戶的數(shù)量。

物流配送路徑優(yōu)化問題的約束條件如下：

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

[yki=1]? ?（2）

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

[（qi，yki）

3） [λij]表示[A]上的有向弧權(quán)重，[xijk]表示第[k]個(gè)車輛經(jīng)過有向弧[（vi，vj）]時(shí)，[xijk=1]，否則，[xijk=0]，即有：

[xijk=1，? ? ?第k個(gè)車輛經(jīng)過有向弧0，? ? ?第k個(gè)車輛未經(jīng)過有向弧] （4）

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

2? 改進(jìn)蟻群優(yōu)化算法的最優(yōu)物流配送路徑設(shè)計(jì)方法

2.1? 傳統(tǒng)蟻群優(yōu)化算法

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

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

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

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

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

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

式中：[ρ]表示信息素的揮發(fā)系數(shù);[Δτij]表示節(jié)點(diǎn)[i]和[j]之間路徑的信息素增量。

2.2? 蟻群優(yōu)化算法的改進(jìn)

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

[ρ=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分別表示當(dāng)前和最大迭代次數(shù)。

2.3? 改進(jìn)蟻群優(yōu)化算法的最優(yōu)物流配送路徑求解

改進(jìn)蟻群優(yōu)化算法的最優(yōu)物流配送路徑求解步驟如下：

1） 建立最優(yōu)物流配送路徑優(yōu)化問題相對(duì)應(yīng)的有向圖。

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

3） 迭代次數(shù)NC=0。

4） 計(jì)算每一只螞蟻選擇下一個(gè)爬行節(jié)點(diǎn)的概率，并根據(jù)計(jì)算結(jié)果爬行到下一個(gè)節(jié)點(diǎn)。

5） 對(duì)相鄰節(jié)點(diǎn)之間路徑上的信息素進(jìn)行更新。

6） 當(dāng)所有螞蟻對(duì)整個(gè)路徑進(jìn)行爬行后，對(duì)整個(gè)路徑上的信息素進(jìn)行更新。

7） 迭代次數(shù)NC=NC+1。

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

3? 最優(yōu)物流配送路徑設(shè)計(jì)方法的測(cè)試分析

3.1? 測(cè)試環(huán)境

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

3.2? 測(cè)試結(jié)果與分析

采用傳統(tǒng)蟻群優(yōu)化算法的優(yōu)化物流配送路徑設(shè)計(jì)方法，如基于遺傳算法的物流配送路徑設(shè)計(jì)方法作對(duì)比測(cè)試，進(jìn)行5次仿真實(shí)驗(yàn)，統(tǒng)計(jì)每一次實(shí)驗(yàn)的最優(yōu)物流配送路徑長(zhǎng)度，結(jié)果如圖2所示。從圖2可以看出：改進(jìn)的蟻群優(yōu)化算法的最優(yōu)物流配送路徑長(zhǎng)度平均值為111.39;傳統(tǒng)蟻群優(yōu)化算法的最優(yōu)物流配送路徑長(zhǎng)度平均值為114.65;遺傳算法的最優(yōu)物流配送路徑長(zhǎng)度平均值為114.64。改進(jìn)蟻群優(yōu)化算法獲得了更優(yōu)的物流配送路徑，提高了物流配送速度，可以減少物流配送的時(shí)間成本，實(shí)際應(yīng)用價(jià)值更高。

統(tǒng)計(jì)每一次實(shí)驗(yàn)找到最優(yōu)物流配送路徑的迭代次數(shù)，具體如表2所示。

從表2可以看出，改進(jìn)蟻群優(yōu)化算法找到最優(yōu)物流配送路徑的迭代次數(shù)要明顯少于傳統(tǒng)蟻群優(yōu)化算法和遺傳算法，加快了最優(yōu)物流配送路徑的求解效率，可以應(yīng)用于大規(guī)模物流配送路徑設(shè)計(jì)問題的求解，實(shí)際應(yīng)用范圍更加廣泛。

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

研究最優(yōu)物流配送路徑具有十分重要的實(shí)際價(jià)值。為了解決當(dāng)前物流配送路徑設(shè)計(jì)方法存在的一些問題，本文提出了基于蟻群優(yōu)化算法的最優(yōu)物流配送路徑設(shè)計(jì)方法，并與傳統(tǒng)蟻群優(yōu)化算法、遺傳算法進(jìn)行了對(duì)比測(cè)試，結(jié)果表明，改進(jìn)蟻群優(yōu)化算法可以獲得理想的物流配送路徑，而且搜索效率高，具有十分廣泛的應(yīng)用前景。

參考文獻(xiàn)

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

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

[3] 葛顯龍，孔陽(yáng).帶有時(shí)間窗的生鮮物流配送路徑優(yōu)化研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2016，46（12）：78?87.

[4] 戴昕.基于反向?qū)W習(xí)策略粒子群的物流配送路徑優(yōu)化研究[J].物流技術(shù)，2014，33（13）：291?294.

[5] 李周芳，楊樺.基于多蟻群優(yōu)化的糧食物流配送路徑問題研究[J].中國(guó)農(nóng)機(jī)化學(xué)報(bào)，2013，34（4）：283?286.

[6] 姜代紅.改進(jìn)的遺傳算法在多目標(biāo)物流配送路徑中的應(yīng)用[J].科學(xué)技術(shù)與工程，2013，13（3）：762?765.

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

[8] 朱偉，徐克林，孫禹，等.Petri網(wǎng)融合蟻群算法的物流配送路徑規(guī)劃[J].浙江大學(xué)學(xué)報(bào)（工學(xué)版），2011，45（12）：2229?2234.

[9] 羅義學(xué).基于智能Petri網(wǎng)的物流配送路徑優(yōu)化算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2011，32（7）：2381?2384.

[10] 邱榮祖，鐘聰兒，修曉虎.基于GIS和禁忌搜索集成技術(shù)的農(nóng)產(chǎn)品物流配送路徑優(yōu)化[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2011，41（10）：145?152.

[11] 邰曉紅，李璐.改進(jìn)節(jié)約法下的物流配送路徑優(yōu)化問題[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，35（6）：667?672.

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

[13] 侯玉梅，賈震環(huán)，田歆，等.帶軟時(shí)間窗整車物流配送路徑優(yōu)化研究[J].系統(tǒng)工程學(xué)報(bào)，2015，30（2）：240?250.

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

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