基于改進(jìn)蟻群算法的物流配送路徑優(yōu)化研究

鄧 波，蒲保興

(邵陽(yáng)學(xué)院 信息工程學(xué)院，湖南 邵陽(yáng)，422000)

基于改進(jìn)蟻群算法的物流配送路徑優(yōu)化研究

鄧 波，蒲保興

(邵陽(yáng)學(xué)院 信息工程學(xué)院，湖南 邵陽(yáng)，422000)

物流配送行業(yè)不但要求所有貨物能及時(shí)進(jìn)行配送，而且也要求盡可能降低整個(gè)物流運(yùn)輸成本。所以物流配送車輛路徑優(yōu)化問(wèn)題是重點(diǎn)亟待解決的關(guān)鍵問(wèn)題，由于傳統(tǒng)的優(yōu)化方法搜索時(shí)間較長(zhǎng)，且難以找到全局最優(yōu)路徑，從而造成配送成本高，效率低。為了降低成本，提高車輛路徑優(yōu)化率，本文以蟻群算法為基礎(chǔ)，并加以改進(jìn)，首先建立優(yōu)化物流配送路徑的全局?jǐn)?shù)學(xué)模型,然后采用改進(jìn)信息素更新規(guī)則、改進(jìn)啟發(fā)信息更新策略獲取最優(yōu)物流路徑，通過(guò)優(yōu)選算法參數(shù)，改進(jìn)蟻群算法對(duì)全局?jǐn)?shù)學(xué)模型進(jìn)行求解。從而有效避免只有局部?jī)?yōu)化解的出現(xiàn)。仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法效率提高較大，算法在實(shí)驗(yàn)環(huán)境下收斂性好，是解決物流配送路徑優(yōu)化問(wèn)題的有效算法。

物流配送；蟻群算法；路徑優(yōu)化；仿真；VRP

隨著社會(huì)實(shí)體經(jīng)濟(jì)的高速發(fā)展，整個(gè)物流行業(yè)也得以快速發(fā)展，物流行業(yè)中的物資配送越發(fā)成為當(dāng)今企業(yè)生產(chǎn)過(guò)程中一個(gè)非常重要環(huán)節(jié)，物流配送指的是依照用戶的訂單要求,并在配送中心進(jìn)行準(zhǔn)確地分貨、配貨，然后將配好的貨物及時(shí)送交給用戶的活動(dòng)[1]。由于油價(jià)、人力資源等成本的不斷上漲，物流運(yùn)輸費(fèi)用已逐漸成為商家成本主要部分，又由于現(xiàn)代擁擠的城市交通與及時(shí)物資配送服務(wù)之間存在著難以調(diào)和的矛盾，因而優(yōu)化物流車輛路徑相對(duì)于整個(gè)物流效益、速度以及運(yùn)輸成本都顯得至關(guān)重要，因此怎樣選擇最優(yōu)配送路徑，及時(shí)將貨物配送到用戶手中，也已成為物流行業(yè)相關(guān)領(lǐng)域里的關(guān)鍵問(wèn)題[2]。

配送車輛路徑問(wèn)題(vehicle routing problem，VRP)的關(guān)鍵是整個(gè)物流系統(tǒng)優(yōu)化環(huán)節(jié)。通過(guò)系統(tǒng)選擇配送車輛的最佳輸送路徑，并對(duì)運(yùn)輸車輛調(diào)度進(jìn)行優(yōu)化，合理安排配送車輛配送順序，可以減少車輛的行駛距離和空駛率。在物流配送中，存在很多決策優(yōu)化問(wèn)題(例如距離、時(shí)間、費(fèi)用等)[3]，大部分僅探討物流配送路徑的優(yōu)化問(wèn)題，即在滿足客戶需求的前提下，制定出合理的貨物配送路徑，通過(guò)派遣數(shù)量最少的車輛并為配送車輛指派運(yùn)輸時(shí)間和運(yùn)輸最省的路線費(fèi)用，迅速地將貨物輸送客戶手中。優(yōu)化配送路徑其實(shí)是一個(gè)NP問(wèn)題，只有當(dāng)客戶節(jié)點(diǎn)和線路較少時(shí)，才能求得精確解，然而當(dāng)問(wèn)題的規(guī)模增大時(shí)，精確求解會(huì)存在耗時(shí)較長(zhǎng)，并且效果低現(xiàn)象；而采用人機(jī)互動(dòng)法，又需要管理者具備足夠的物流配送專業(yè)知識(shí)，且會(huì)增加對(duì)車輛配送路徑選擇的隨意性[4]。對(duì)于這類問(wèn)題的求解一般應(yīng)采用啟發(fā)式算法，該算法是指通過(guò)對(duì)已經(jīng)解決具體問(wèn)題的經(jīng)驗(yàn)不斷進(jìn)行歸納、分析、推理，并產(chǎn)生解決此類問(wèn)題的方法[5]。其目標(biāo)是在適當(dāng)?shù)拇鷥r(jià)下得到即將要解決的全局問(wèn)題的滿意解或最優(yōu)解，這樣不但節(jié)省了時(shí)間，也會(huì)滿足用戶的實(shí)際要求。又由于啟發(fā)式算法具有效率高、實(shí)現(xiàn)簡(jiǎn)單等多種優(yōu)點(diǎn)，所以引起了當(dāng)今優(yōu)化研究領(lǐng)域的廣泛關(guān)注，近年來(lái)發(fā)展非?？?。

蟻群算法是一種群智能優(yōu)化算法，該算法是通過(guò)正反饋并行機(jī)制和螞蟻間協(xié)作定能找到巢穴與食物之間的最短路徑[6]。蟻群算法一被提出就受到研究領(lǐng)域的廣泛關(guān)注，因?yàn)樵撍惴ú坏哂胁⑿行院?、求解速度快等?yōu)點(diǎn)，而且在解決路徑優(yōu)化、任務(wù)分配等方面表現(xiàn)出優(yōu)良的性能，但是蟻群算法同時(shí)也存在一定的缺陷，例如當(dāng)問(wèn)題變成大規(guī)模時(shí)，就會(huì)出現(xiàn)運(yùn)算時(shí)間長(zhǎng)、收斂速度較慢、容易陷入局部最優(yōu)解等現(xiàn)象[7，8]。

1 構(gòu)建VRP數(shù)學(xué)模型

假定某個(gè)物流公司具有N個(gè)客戶以及M個(gè)集散中心，物流車輛配送路徑的目標(biāo)是要在使配送成本最小的情況將貨物從M個(gè)集散中心送到N個(gè)客戶點(diǎn)上。在車載量q和客戶需求量gi(i=1,2…n)均已知的前提下，可以確定至少應(yīng)派多少臺(tái)車才能滿足應(yīng)用需求且車輛所經(jīng)的總路徑最短，從而找到配送方案中最小成本的方案，在進(jìn)行數(shù)學(xué)模型構(gòu)建時(shí)首先作如下假設(shè)：

1)車輛對(duì)每個(gè)客戶點(diǎn)服務(wù)，途中只卸貨無(wú)裝貨的情況。

2)每一臺(tái)配送車輛均以同一集散中心為起點(diǎn)和終點(diǎn)。

3)車載量要大于每條配送路徑上客戶量之和(q>gi)。

4)每輛車只服務(wù)一條路線，每一個(gè)客戶只被一輛車配送。

5)每輛配送車所經(jīng)過(guò)的路線均不能重復(fù)。

可以由下列公式求得所需車輛數(shù)目m:

(1)

其中：m表示所選擇車輛數(shù)，a是參數(shù)，且0

建立物流配送路徑選擇問(wèn)題的求解數(shù)學(xué)模型。首先定義以下變量：

Xik=1 (客戶i的配送由車輛k完成，i、K分別表示客戶、車輛的編號(hào))

(2)

或Xik=0 (客戶i的配送車輛k未完成配送)

Yijk=1 (車輛k從i客戶點(diǎn)行駛到j(luò)客戶點(diǎn)完成)

(3)

或Yijk=0(車輛k從客戶點(diǎn)i行駛到客戶點(diǎn)j未完成)

(4)

minZ=∑i∑j∑kCijYijk

(5)

設(shè)置如下限制條件：

∑iYki=1i=1,2,…,m

(6)

∑iGiXki≤qi=1,2…,m?k

(7)

∑jXkijk=Ykii=0,1,…,?k

(8)

∑iYkijk=Ykjj=0,1,…,?k

(9)

X=Xijk∈S

(10)

Xijk=0或1i,j=0,1,…,?k

(11)

Yki=0或1i,j=0,1,…,?k

(12)

上述條件約束了車輛的配送總?cè)萘浚渲?，Cij表示從點(diǎn)i到點(diǎn)j的所有運(yùn)輸成本，Gi表示任務(wù)i的運(yùn)輸量，q表示貨物配送總?cè)萘?，所有貨物運(yùn)輸任務(wù)均由m臺(tái)配送車輛去完成，保證每個(gè)客戶的所有貨物僅由唯一臺(tái)輛車來(lái)配送完成，即保證了服務(wù)的唯一性[9]。

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

通過(guò)專家們多年來(lái)的研究，蟻群算法的應(yīng)用研究已經(jīng)取得了較大進(jìn)展，在各種工程領(lǐng)域中得以廣泛應(yīng)用，但由于該算法收斂速度慢，且容易陷入局部最優(yōu)解等多種缺點(diǎn)。作者力求通過(guò)對(duì)局部信息素更新規(guī)則的改進(jìn)，優(yōu)化組合動(dòng)態(tài)調(diào)整相關(guān)參數(shù)和全局更新策略，實(shí)現(xiàn)算法優(yōu)化，從而提高了蟻群算法的收斂速度，達(dá)到了增強(qiáng)全局搜索的隨機(jī)性，極大地抑制了算法出現(xiàn)早熟現(xiàn)象。

2.1 信息素更新規(guī)則改進(jìn)

在所研究基本蟻群算法中，發(fā)現(xiàn)存在兩種信息素更新策略，即實(shí)時(shí)更新、全局更新。前者是指螞蟻在從一個(gè)節(jié)點(diǎn)完成到達(dá)另一節(jié)點(diǎn)后，就馬上更新路徑的信息素;而后者是指螞蟻在遍歷完所有節(jié)點(diǎn)后才更新整條路徑上的信息素。這兩種方式相比較，全局更新策略可以迅速加快收斂速度。目前很多研究已表明全局更新效果好，但同時(shí)也有一些缺陷，例如該方法下全局更新通常收斂過(guò)早，在同一條路徑上會(huì)使大量螞蟻很快集中，從而無(wú)法發(fā)現(xiàn)和得到更優(yōu)解，也即陷入局部最優(yōu)解情況[10]。

在信息素更新過(guò)程中，系統(tǒng)通常只會(huì)更新找到最優(yōu)路徑的螞蟻的信息素。對(duì)于這只螞蟻信息素的更新，通?？刹捎靡韵聝煞N方式進(jìn)行，一種是在循環(huán)過(guò)程中找到表現(xiàn)最佳的螞蟻，該方式的收斂速度通常比較慢，不會(huì)過(guò)早導(dǎo)致迅速收斂到某條路徑上，蟻群還會(huì)繼續(xù)去找新的路徑，也就更易于去發(fā)現(xiàn)更好的路徑；另一種則是找到在整個(gè)運(yùn)算中表現(xiàn)最佳的螞蟻，該更新方式可以迅速提高收斂速度，從而得到較優(yōu)解，但這也阻礙了蟻群再去尋找更優(yōu)解，容易使整個(gè)蟻群困在相對(duì)較差的某路徑上。因此，本文提出了一種新的混合更新信息素策略，也即在搜索前幾次循環(huán)過(guò)程中，采用迭代最優(yōu)法不斷進(jìn)行及時(shí)信息素更新，進(jìn)行信息素更新是為發(fā)現(xiàn)本輪循環(huán)中表現(xiàn)最佳的螞蟻，該方法通?？煞奖阏业胶芏噍^優(yōu)解，可有效避免蟻群過(guò)早陷入到較差解中；經(jīng)多次循環(huán)(在此以十次循環(huán)為例)完成更新以后，然后再采用全局最優(yōu)解進(jìn)行更新，也即信息素更新是利用整個(gè)運(yùn)算以來(lái)最佳表現(xiàn)的螞蟻來(lái)進(jìn)行的。在混合信息素更新規(guī)則被采用后，本算法會(huì)收斂到較優(yōu)解集中，從而也就可以找到更多可行解，并且還能繼續(xù)去搜尋其他更優(yōu)解，并且保持著快的收斂速度，可有效地去克服采用單一全局更新時(shí)易過(guò)早出現(xiàn)陷入局部最優(yōu)解的不足。

改進(jìn)后信息素更新規(guī)則如下:

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

(13)

其中：Δτbest= 1 /f(sbest)；全局最優(yōu)解sob用f(sbest)、本次迭代所得最優(yōu)解用sib表示。再則為了防止搜尋停滯，應(yīng)將路徑上的信息素限定在某個(gè)可以預(yù)定的范圍之內(nèi)，而對(duì)于全部信息素τij(t)都必須滿足

τij(t)∈[τmin，τmax]，如果τij(t)≥τmax，那么將設(shè)置為τij(t)=τmax，如果

τij(t)≤τmin，那么將設(shè)置為τij(t)=τmin，如果在某個(gè)迭代過(guò)程中產(chǎn)生了可行解，且其信息素的量是τmax，而其他路徑上信息素的量卻是τmin，那么收斂就會(huì)出現(xiàn)?？梢詣?dòng)態(tài)地按照以下策略進(jìn)行信息素的改進(jìn)：

1)在初始狀態(tài)下，信息素未加以更新，采用式(7)、(8)來(lái)確定初始更新范圍，其中L(sbest)表示全局最優(yōu)解或本次迭代所得最優(yōu)解，而每次迭代運(yùn)算過(guò)程中出現(xiàn)新增的信息素最高值則用1 /L(sbest)表示。

(14)

(15)

2)若信息素更新完成后，則開(kāi)始采用式(16)來(lái)確定τmax(t)，而τmin(t)仍采用式(15)來(lái)確定。

(16)

2.2 啟發(fā)信息更新策略的改進(jìn)

在進(jìn)行路徑規(guī)劃時(shí)，可以根據(jù)式(5)來(lái)進(jìn)行相應(yīng)路徑選擇，但式(5)中只反映了當(dāng)前結(jié)點(diǎn)與其相鄰接結(jié)點(diǎn)之間的關(guān)系，并沒(méi)有反映出其鄰接結(jié)點(diǎn)與終點(diǎn)之間的關(guān)系，它搜索的空間是以起點(diǎn)為中心近似圓形的區(qū)域，由于這種沒(méi)有方向性的搜索很容易造成搜索失敗或收斂速度過(guò)慢等原因。為此，可將與當(dāng)前結(jié)點(diǎn)i相鄰的下一可選結(jié)點(diǎn)j到終點(diǎn)z的直線距離djz引入啟發(fā)函數(shù)，這樣得到

(17)

定義在t時(shí)刻第k只螞蟻從位于節(jié)點(diǎn)i上選擇下一個(gè)j節(jié)點(diǎn)為目標(biāo)的概率為:

ifj∈allowedk

(18)

這里,ηij是由i轉(zhuǎn)移到j(luò)的啟發(fā)信息，由要解決的問(wèn)題函數(shù)給出。參數(shù)α和參數(shù)β分別用來(lái)表示控制信息素濃度以及啟發(fā)信息相對(duì)重要程度。而allowedk表示第k只螞蟻下一步可選擇所有節(jié)點(diǎn)的集合[11]。

通過(guò)將djz引入到啟發(fā)函數(shù)，改變了無(wú)向搜索，使搜索的方向性加強(qiáng)，搜索的空間也轉(zhuǎn)化為由起點(diǎn)到終點(diǎn)的橢圓形區(qū)域，縮小了搜索區(qū)域，搜索的成功率大大提高，然而，對(duì)于實(shí)際道路交通狀況，由于交通環(huán)境(如快速路、高速路)等因素的影響，該方向啟發(fā)的方法并不一定得到最優(yōu)路徑，這是因?yàn)榉较騿l(fā)的過(guò)早所致，使得初始搜索空間有限，為此，特引入當(dāng)前結(jié)點(diǎn)i與起點(diǎn)o之間的直線距離dio作為初始搜索空間的大小，等搜索到一定的程度以后再引入方向啟發(fā)進(jìn)行搜索空間縮減，從而在利用蟻群算法進(jìn)行路徑規(guī)劃時(shí)，首先應(yīng)按基本蟻群算法去進(jìn)行路徑搜索，當(dāng)距離dio大于給定的閾值ε時(shí)，應(yīng)采用式(15)來(lái)進(jìn)行具有方向啟發(fā)的路徑搜索，確定了方向，不僅提高了搜索到最優(yōu)路徑的可能性，而且也盡可能地縮減了搜索空間，因此提高了該算法的執(zhí)行效率[12]，對(duì)于起點(diǎn)o與當(dāng)前結(jié)點(diǎn)i的直線距離閾值ε應(yīng)根據(jù)地方區(qū)域規(guī)模來(lái)加以確定，常見(jiàn)的方法是參照起點(diǎn)o與終點(diǎn)z直線距離dOz進(jìn)行確定。

3 改進(jìn)后的蟻群算法實(shí)現(xiàn)步驟

算法改進(jìn)后的詳細(xì)流程實(shí)現(xiàn)步驟如下:

步驟1 首先對(duì)參數(shù)進(jìn)行初始化。設(shè)Nc= 0(Nc表示迭代次數(shù))，并設(shè)置最大迭代次數(shù)為Ncmax，初始化信息素強(qiáng)度Q，設(shè)置最大信息素強(qiáng)度為τmax、最小信息素強(qiáng)度為τmin和α、β的值，每條路徑上的信息素濃度值τij(0)=c(c為常數(shù))，并設(shè)置Δτij= 0，然后隨機(jī)將m個(gè)螞蟻放置到初始點(diǎn)上。

步驟2 設(shè)置循環(huán)搜索次數(shù)Nc，其值變化趨勢(shì)Nc=Nc+ 1。

步驟3 設(shè)置螞蟻禁忌表，將禁忌表的索引號(hào)設(shè)成n，并且n= 1。

步驟4 設(shè)置螞蟻數(shù)目m，其數(shù)目的變化趨勢(shì)為m=m+ 1。

步驟5 確定搜索熱區(qū)，判斷某路徑是否在熱區(qū)以內(nèi)，然后計(jì)算出每一只螞蟻移動(dòng)到下一條路徑的概率值。

步驟6 當(dāng)螞蟻從某節(jié)點(diǎn)i出發(fā)到達(dá)下一節(jié)點(diǎn)j時(shí)，應(yīng)當(dāng)對(duì)其所經(jīng)全部路徑上的信息素及時(shí)進(jìn)行更新并及時(shí)修改禁忌表，然后按照當(dāng)前狀況將修改禁忌表值，并將新節(jié)點(diǎn)j也置于禁忌表中。

步驟7 循環(huán)執(zhí)行步驟 2到步驟 6 ，一直到每只螞蟻都能找到一條包含區(qū)域內(nèi)所有節(jié)點(diǎn)的可行路徑。

步驟8 并在新搜索到的所有可行解集內(nèi)產(chǎn)生一條最短路徑，即這條路徑就是本次迭代產(chǎn)生的最優(yōu)路徑。

步驟9 不斷判斷循環(huán)次數(shù)Nc，只要循環(huán)次數(shù)沒(méi)有超過(guò)十次，則一直對(duì)螞蟻所找到的最優(yōu)路徑依照本迭代最優(yōu)值法去進(jìn)行信息素更新；如果循環(huán)次數(shù)已經(jīng)超過(guò)十次，則立即按照全局更新進(jìn)行信息素更新。

步驟10 對(duì)全部螞蟻經(jīng)過(guò)的任何一條路徑，都必須按式(11)到(14)進(jìn)行一次全局更新信息素。

步驟11 重復(fù)執(zhí)行步驟2到步驟7 ，直到在連續(xù)的多次迭代中沒(méi)有出現(xiàn)更優(yōu)解或者次數(shù)Nc的值已經(jīng)達(dá)到最大的迭代次數(shù)Ncmax，才停止運(yùn)算，然后將當(dāng)前值作為算法最優(yōu)解。

4 仿真實(shí)驗(yàn)研究

通過(guò)以上對(duì)算法加以改進(jìn)和詳細(xì)流程的介紹，本實(shí)驗(yàn)將用測(cè)試數(shù)據(jù)對(duì)改進(jìn)后的蟻群算法進(jìn)行仿真，通過(guò)對(duì)測(cè)試結(jié)果進(jìn)行分析，評(píng)價(jià)改進(jìn)算法的好壞。

4.1 數(shù)據(jù)集

已知某物流公司的有 8臺(tái)配送車，每臺(tái)車的最大載重量為10噸，每臺(tái)車的最大行駛距離100公里，需同時(shí)向 30個(gè)客戶提供服務(wù)，物流配送中心與客戶的基本資料及位置情況如表1與圖1所示。

表1 客戶基本資料表

4.2 仿真平臺(tái)及參數(shù)優(yōu)化設(shè)置

仿真系統(tǒng)的運(yùn)行平臺(tái)為：CPU為2.6GMHz，內(nèi)存為4GB，OS為windows 7，采用VB6.0 語(yǔ)言編程實(shí)現(xiàn)。蟻群算法的參數(shù)設(shè)置如下：螞蟻?zhàn)畲髷?shù)目為100，α= 1，β= 1.5，實(shí)驗(yàn)進(jìn)行了10次，最大迭代次數(shù)為 200，ρ= 0.85。

圖1 客戶地理位置信息圖Fig.1 Customer location information map

4.3 仿真實(shí)驗(yàn)所得結(jié)果與分析

4.3.1 算法改進(jìn)前后的最優(yōu)車輛路徑搜索結(jié)果

采用改進(jìn)后的蟻群算法對(duì)最優(yōu)配送路徑進(jìn)行求解，可用3臺(tái)車3個(gè)路徑即可完成，改進(jìn)前，在迭代60次時(shí)，就產(chǎn)生局部最優(yōu)解，最短路徑為220公里，而改進(jìn)后，按此算法在迭代100次時(shí)，就找到了問(wèn)題全局最優(yōu)解，最優(yōu)路徑長(zhǎng)度為200公里，從仿真實(shí)例中可以看出，改進(jìn)后，它能夠以更快的速度收斂到全局最優(yōu)解，也就是說(shuō)本算法是一種有效的配送車輛路徑優(yōu)化方法。最短路徑的收斂情況如圖2所示。

圖2 基本蟻群算法改進(jìn)前后的收斂曲線Fig.2 The basic ant colony algorithm improves the curve of convergence before and after

4.3.2 算法改進(jìn)前后對(duì)比分析

從圖2可以看出，改進(jìn)后的蟻群算法最優(yōu)路徑長(zhǎng)度比改進(jìn)前減少了20 km，而且收斂速度快了很多，所以無(wú)論是從收斂速度還是對(duì)最終結(jié)果進(jìn)行比較，本文算法都要優(yōu)于基本蟻群算法，基本蟻群算法容易停滯于局部最優(yōu)解上的問(wèn)題在改進(jìn)后的算法中得到了有效的解決?？梢?jiàn)，本文改進(jìn)后的蟻群算法具有較大的優(yōu)越性，也證明了改進(jìn)后的蟻群算法的正確性和有效性。本例是在單一物流配送中心的情況下求解的，若是存在多個(gè)物流配送中心，則只需將多個(gè)配送中心通過(guò)分解法來(lái)進(jìn)行區(qū)域劃分，然后進(jìn)行各自獨(dú)立求解即可，所得解可能不是全局最優(yōu)解，但仍然還是非常有效的、可行的。

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

物流中規(guī)劃好車輛配送路徑是提高物流企業(yè)經(jīng)濟(jì)效益的關(guān)鍵，本文通過(guò)對(duì)基本蟻群算法進(jìn)行改進(jìn)，包括啟發(fā)信息更新的改進(jìn)、信息素更新的改進(jìn)等，設(shè)計(jì)出新的改進(jìn)蟻群算法，針對(duì)物流系統(tǒng)當(dāng)前存在的問(wèn)題，對(duì)車輛路徑優(yōu)化問(wèn)題進(jìn)行了深入研究，并利用蟻群算并行性度、高法速度快、魯棒性強(qiáng)的特點(diǎn)，創(chuàng)造性提出了基于蟻群算法的車輛配送路徑優(yōu)化問(wèn)題的求解方法。在通過(guò)仿真實(shí)驗(yàn)對(duì)其進(jìn)行驗(yàn)證后，其試驗(yàn)結(jié)果表明改進(jìn)后的方法可以很好地提高效率，并能夠非?？焖俚卣业剿惴ㄗ顑?yōu)解，因而在以后車輛路徑優(yōu)化中肯定會(huì)展現(xiàn)出廣闊的市場(chǎng)前景。

[1]唐爐亮，常曉猛，李清泉，等.基于蟻群優(yōu)化算法與出租車GPS 數(shù)據(jù)的公眾出行路徑優(yōu)化[J].中國(guó)公路學(xué)報(bào)，2011，24(2):89-95.

[2]余玥,胡宏智.基于改進(jìn)遺傳算法的物流配送路徑求解[J].計(jì)算機(jī)技術(shù)與發(fā)展,2009,19(3):52- 55.

[3]CHEN Yaorong，LIANG Bo，ZHOU Meihua.Optimization for vehiclescheduling in iron and steel works based on semi-trailer swap transport[J].中南大學(xué)學(xué)報(bào):英文版，2010，17(4):873-879.

[4]鐘石泉，賀國(guó)光.有時(shí)間窗約束車輛調(diào)度優(yōu)化的一種禁忌算法[J].系統(tǒng)工程理論方法應(yīng)用，2005，14(6):523-527.

[5]CHAO Yiming.A tabu search method for the truck and trailer rou-ting problem[J].Computer and Operations Research，2002，29(1):33-51.

[6]姜宏岸，王剛.優(yōu)先級(jí)隊(duì)列的緩存管理機(jī)制的性能分析[J].計(jì)算機(jī)工程與應(yīng)用，2009，45(25)：86-88.

[7]宋留勇，王銳，周永旺，等.動(dòng)態(tài)城市交通網(wǎng)絡(luò)優(yōu)化模型研究及算法設(shè)計(jì)[J].測(cè)繪科學(xué)，2011，36(1):134-136.

[8]程明輝,齊名軍.基于粒子群算法的物流配送路徑優(yōu)化問(wèn)題研究[J].中國(guó)外資,2008,(8):254- 256.

[9]陳以,萬(wàn)梅芳.RBF神經(jīng)網(wǎng)絡(luò)在物流系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)仿真,2010,27(4):159- 163.

[10]SEO JB，LEUNG V.Approximate queuing performance of amultipacket reception slotted ALOHA system with an ex-ponentialbackoff algorithm[C]∥4th International Conference on Communications and Networking in China，2009:1-5.

[11]楊中秋，張延華.改進(jìn)蟻群算法在交通系統(tǒng)最短路徑問(wèn)題的研究[J].科學(xué)計(jì)算與信息處理，2009，32(8):76-78.

[12]KARSTEN M.FIFO service with differentiated queueing[C]∥7th ACM/IEEE Symposium on Architectures for Networking and Communications Systems，2011:122-133.

Logistics distribution path optimization research based on improved ant colony algorithm

DENG Bo,PU Baoxing

(School of Information Engineering,Shaoyang University,Shaoyang 422000,China)

Logistics industry can not only requires that all the goods in a timely manner and distribution,but also the requirement as far as possible to reduce the logistics cost.So the logistics distribution vehicle routing optimization problem is focused on the key problems to be solved,due to the traditional optimization method to search for a long time,and hard to find the global optimal path,resulting in the distribution cost is high,the efficiency is low.In order to reduce costs,increase the rate of vehicle routing optimization,in this paper,based on the ant colony algorithm,and improved it,the first to establish the mathematical model of the logistics distribution path of global optimization and then with the improved pheromone update rule,improvement of heuristic information update strategy,obtain the optimal logistics path,through the parameter optimization algorithm,ant colony algorithm for solving global mathematical model.Thus effectively avoid the occurrence of only local optimization solution.The simulation experimental results show that the improved algorithm efficiency is larger,convergence algorithm in experiment environment is good,and it is effective to solve the problem of logistics distribution route optimization algorithm.

logistics distribution;ant colony algorithm;path optimization;simulation;VRP

1672-7010(2017)04-0069-07

2017-04-21

湖南省科技計(jì)劃項(xiàng)目(2012FJ3108)；湖南省教育廳科學(xué)研究項(xiàng)目(13C845)

鄧波(1973-)，男，湖南邵陽(yáng)人，講師，碩士，從事嵌入式系統(tǒng)、數(shù)據(jù)挖掘研究蒲保興(1965-)，男，湖南城步人，教授，博士，碩導(dǎo)，從事網(wǎng)絡(luò)安全、數(shù)據(jù)挖掘研究

TP311

A