李靜

（陜西工業(yè)職業(yè)技術(shù)學(xué)院陜西咸陽712000）

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

李靜

（陜西工業(yè)職業(yè)技術(shù)學(xué)院陜西咸陽712000）

針對單向物流配送中遇到的路徑優(yōu)化問題，提出一種蟻群算法對單向物流路徑進(jìn)行優(yōu)化。同時針對傳統(tǒng)蟻群算法存在著易滯性和收斂速度比較緩慢的問題，提出采用信息素更新、螞蟻轉(zhuǎn)移策略的方式，對傳統(tǒng)蟻群算法進(jìn)行改進(jìn)。最后通過實例和仿真軟件，對改進(jìn)算法與傳統(tǒng)算法進(jìn)行比較，證明改進(jìn)算法收斂速度和迭代次數(shù)方面都較傳統(tǒng)算法有著很大的改進(jìn)，并進(jìn)一步證明本文所提出的改進(jìn)方法與策略是正確和可行的，有利于更好的對當(dāng)前的物流配送路徑進(jìn)行優(yōu)化。

蟻群算法；信息素；物流配送；螞蟻轉(zhuǎn)移；路徑優(yōu)化

物流業(yè)作為促進(jìn)消費的先導(dǎo)產(chǎn)業(yè)，實現(xiàn)對其物流配送路徑的優(yōu)化，成為提高物流企業(yè)運行效率的重要手段。如何實現(xiàn)對物流路徑的優(yōu)化，也成為當(dāng)前學(xué)術(shù)界研究的熱點。

現(xiàn)實中物流配送考慮的因素很多，并根據(jù)這些因素又可以衍生出很多的問題，如多個配送中心問題，根據(jù)特征也可分為單向物流（單純?nèi)?、送貨）和雙向物流（即送又?。??？梢妼ξ锪髋渌偷穆窂絻?yōu)化問題非常復(fù)雜，約束條件也非常多。因此，如何運用現(xiàn)代計算機技術(shù)實現(xiàn)對該問題的求解與優(yōu)化，成為本文討論的重點。

同時物流配送路徑優(yōu)化問題已經(jīng)被當(dāng)前學(xué)界證實屬于NP_hard問題，對其進(jìn)行求解具有很大的難度。而通過廣大研究人員的研究發(fā)現(xiàn)，蟻群算法子啊求解該類問題的時候，具有顯著的優(yōu)越性。

對此，本文則以單向物流作為研究對象，對其路徑優(yōu)化進(jìn)行深入研究，通過構(gòu)建數(shù)學(xué)模型，并對傳統(tǒng)蟻群算法求解過程中存在的問題進(jìn)行改進(jìn)，并最終通過仿真證明該改進(jìn)算法具有可行性。

1　單向物流問題描述

當(dāng)前針對單向物流路徑優(yōu)化的解決方式通常是采用一路線一車輛，也就是每條優(yōu)化后的子路線由一兩專門的車輛進(jìn)行負(fù)責(zé)。因此，該問題可以被描述為：

假設(shè)在一配送中心擁有N個不同客戶的需求點，并且具有V輛不同車輛。由于路徑優(yōu)化包含很多影響因素，因此，在對單向物流進(jìn)行研究之前，需要對本研究的問題進(jìn)行一定的抽象和范圍界定：

1）在該區(qū)域內(nèi)，配送中心可向多個不同的分散客戶進(jìn)行貨物的配送，并滿足在該區(qū)域內(nèi)的所有客戶的貨物需求；

2）客戶位置與配送中心位置不變；

3）客戶的需求量不超過車輛的裝載量或者是車輛自身的容量，同時每個客戶的需求量都是一次性完成，并且該需求量都是提前已知的。

4）將配送中心距離和客戶距離，以及客戶與客戶的距離都抽象為直線距離以此方面對其進(jìn)行計算。

5）每輛車都具有固定的負(fù)載和最大的行駛距離。

2　配送模型

2.1符號定義

將配送中心和在該區(qū)域內(nèi)的每個客戶抽象為不同的點，并且由這些不同的點構(gòu)成的網(wǎng)絡(luò)，則為物流配送的網(wǎng)絡(luò)。G=（R，E）表示為N個客戶和1個配送點的有向圖，公式中的R則表示為頂點集合，而其中的E則表示為有向邊集合。R=｛r0，r1，r2，.....rn｝，n則表示為客戶的節(jié)點數(shù)量，0則表示為配送中心。而Sij則表示該區(qū)域內(nèi)的客戶i和客戶j兩者的距離；di則為客戶i的貨物需求量；Q表示該配送車輛的最大的負(fù)載；V表示該配送中心車輛的全部數(shù)量；L表示車輛行駛的最大距離。同時定義Xk為車輛配送的客戶總數(shù)，當(dāng)k=0的時候，表示其沒有進(jìn)行配送。

2.2配送模型構(gòu)建

根據(jù)上述的定義，需要求解該配送中心到客戶，客戶到客戶配送的最短的距離F，因此，其數(shù)學(xué)模型則為：

其中公式（1）則表示為整個配送網(wǎng)絡(luò)的最短距離，為本研究需要求解的目標(biāo)函數(shù)；公式（2）則表示每輛車行駛的距離不得超過其額定的距離；公式（3）則為每輛車的負(fù)載不超過其額定的負(fù)載；公式（4）、（5）表示一個客戶由一個車輛進(jìn)行服務(wù)。

3　傳統(tǒng)蟻群函數(shù)對模型的求解過程

根據(jù)張勇等人的研究，提出采用螞蟻系統(tǒng)進(jìn)行求解，其求解公式為：

在公式（6）當(dāng)中，Mk表示螞蟻沒有到過的點，而其中的α、β作為啟發(fā)因子，則分別控制其中的函數(shù)τ（i，j）、η（i，j）所對應(yīng)的參數(shù)。

通過螞蟻在上述節(jié)點留下不同的信息素，并在每次運動結(jié)束之后，信息素全部消失。而在這個過程中，其中的信息素的更新規(guī)則分為局部更新和全局更新。其公式分別為：

其中ρ為信息素殘留系數(shù)，ρ∈［0，1］；τ0表示為初始的信息素量。

通過上述公式（6）看出，α、β對整體的影響非常的大，如當(dāng)α的值比較大的時候，說明在路徑當(dāng)中其信息素受到高度重視，螞蟻對該點的搜索也會提高，如果此時的β值過大的話，則很可能使得局部最優(yōu)路徑的信息正反饋作用變強，由此導(dǎo)致該算法過早的出現(xiàn)收斂問題。而如果α較小，則很難出現(xiàn)正反饋，并以此導(dǎo)致其產(chǎn)生隨機搜索，很難得到該模型的最優(yōu)解，對此需要對其進(jìn)行改進(jìn)。

4　蟻群算法改進(jìn)

4.1對ρ的改進(jìn)

通過分析認(rèn)為，導(dǎo)致原來經(jīng)典算法出現(xiàn)過早的收斂和停滯的問題，其根本的原因在于次優(yōu)路徑上的信息素不斷增強，而在最優(yōu)路徑的信息素卻因為長時間的揮發(fā)，使得其含量變?yōu)榱肆?。對此，要提高該算法的全局與局部搜索的能力，其最為主要的方式就是要處理好其中螞蟻路徑的選擇和信息素累計問題，也即是要極大其中最優(yōu)解的信息素的含量，同時也要防止其出現(xiàn)過早的收斂。對此，提出一種動態(tài)判斷與調(diào)整結(jié)合的改進(jìn)方式。其具體的方式則為：

1）設(shè)定常數(shù)Zmax、ρmin、λ；ρmin為認(rèn)為隨機設(shè)定；λ∈（0，1），用于防止其中的ρ對收斂速度的影響；Zmax表示其接近過早收斂時候沒變化的次數(shù)；

2）對其中的ρ進(jìn)行動態(tài)調(diào)整，其具體則如下：

當(dāng)其運行到Z=Zmax的時候，則可以對其中的ρ進(jìn)行調(diào)整，并對其再次進(jìn)行Z次的重復(fù)計算，如此反復(fù)。

4.2基于遺傳算法的改進(jìn)蟻群

在實踐中，遺傳算法具有變異、交叉等優(yōu)點，從而使得原來的經(jīng)典算法可有效的跳出原來的循環(huán)中。因此，本文提出將著兩種算法進(jìn)行融合，具體步驟為：

1）復(fù)制。也就是在每次對結(jié)果進(jìn)行搜索之后，將上一輪得到的最優(yōu)結(jié)果復(fù)制給其下一輪，從而使得其最優(yōu)的解能夠得到延續(xù)；

2）編碼。對其中的物流模型進(jìn)行編碼，將其中的數(shù)學(xué)數(shù)字轉(zhuǎn)為遺傳基因，如在模型中的n個不同的客戶由V個不同的運送車輛進(jìn)行運輸，對其進(jìn)行編碼則為1到n對n個不同客戶進(jìn)行標(biāo)識，同時用0，n+1，n+2，…n+m_1表示為從該配送中心出發(fā)的車輛的數(shù)量，其中的某個車如果第二次出發(fā)則為n+m。

3）交叉。將每輪搜索的結(jié)果中的最優(yōu)解和次優(yōu)解進(jìn)行編碼方面的交叉操作，從而增加整個種群的數(shù)量和多樣性，以此提高全局搜索的能力。

4）變異。在上述的編碼中，選擇其中的編碼S，隨機確定其中的兩個位置，并將這兩個位置進(jìn)行交換，重復(fù)N次，由此得到新的S'，比較兩者的值，從而得到最優(yōu)的解，并將該最優(yōu)解作為下一輪搜索的初始的值。

4.3改進(jìn)算法流程圖

通過上述的改進(jìn)，從而可以得到如圖1所示的算法流程。

圖1　改進(jìn)算法流程圖

5　實例及仿真

為驗證該算法改進(jìn)的有效性，采用在因特爾酷睿5處理器的電腦上進(jìn)行測試，并以C++語言對算法進(jìn)行實現(xiàn)。同時為更好的驗證該改進(jìn)算法的效果，以文獻(xiàn)［6］當(dāng)中的實例作為參考，從而比較兩者之間的結(jié)果。

假設(shè)該配送中心自有車輛為5輛，最大重量為8T，最大配送距離為50公里，向該配送中心覆蓋區(qū)域內(nèi)的20個客戶進(jìn)行配送。配送中心坐標(biāo)（x，y）=（14.5 km，13.0），其余20個客戶的坐標(biāo)如表1（僅列出部分坐標(biāo)）。

表1　20客戶部分坐標(biāo)

通過其10次的迭代，可得到其最優(yōu)路徑為107.33km，最優(yōu)的路徑包含四條，具體如表2所示。

表2　改進(jìn)算法仿真結(jié)果

而通過本文提出的文獻(xiàn)［6］，其計算的結(jié)果為117.58 km，由此可以看出該改進(jìn)算法具有很大的優(yōu)勢。

同時通過仿真對其收斂性的觀察發(fā)現(xiàn)，改進(jìn)算法其整體的迭代次數(shù)在第92次的時候，則獲取到了最優(yōu)解，并在第150次迭代的時候得到最短距離。而傳統(tǒng)的算法則在第200次迭代時候獲得最優(yōu)解，并在500次得到最短距離，遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)算法。

6　結(jié)束語

結(jié)合物流配送路徑自身的特點，從更新信息量和引入遺傳算法的方式，對傳統(tǒng)算法進(jìn)行改進(jìn)，從而得到具有良好收斂速度的配送模型。由此，為今后物流配送的路徑優(yōu)化提供了參考。

［1］智登奎，李國勇.基于GA_NP算法的約束廣義預(yù)測控制［J］.計算機應(yīng)用與軟件，2014（2）：259_262.

［2］段愛民，陳澤琳，陳海波.基于改進(jìn)蟻群算法的物流配送路徑優(yōu)化［J］.計算機技術(shù)與發(fā)展，2011（12）：178_181.

［3］張勇.基于改進(jìn)蟻群算法物流配送路徑優(yōu)化的研究［J］.控制工程，2015（2）：252_256.

［4］邊霞，米良.遺傳算法理論及其應(yīng)用研究進(jìn)展［J］.計算機應(yīng)用研究，2010（7）：2425_2429，2434.

［5］鄧亮，趙進(jìn)，王新.基于遺傳算法的網(wǎng)絡(luò)編碼優(yōu)化［J］.軟件學(xué)報，2009（8）：2269_2279.

［6］Lang M X，Hu S J.Study on the optimization of physica1 distributionroutingprob1embyusinghybridgenetic a1gorithm［J］.Chinese Journa1 of Management Science，2002，10 （10）：51_56.

［7］祁金佺.遺傳蟻群算法在軟件測試用例生成中的應(yīng)用［J］.工業(yè)儀表與自動化裝置，2013（6）：112_116.

0ne Way loglstlcs dlstrlbutlon route oPtlmlzatlon based on ant colony oPtlmlzatlon algorlthm

LI Jing
（Shaanxi Polytechnic Institute，Xianyang 712000，China）

Aiming at the prob1em of path optimization in the unidirectiona1 1ogistics distribution，an ant co1ony a1gorithm is proposed to optimize the way of one_way 1ogistics.And the traditiona1 ant co1ony a1gorithm exists to 1ag and s1ower convergence speed prob1em，the pheromone update，ants'transfer strategy is put forward，the traditiona1 ant co1ony a1gorithm was improved. Fina11y through the examp1es and simu1ation software，to the improvement of the a1gorithm and the traditiona1 one are compared that to improve the a1gorithm convergence speed and number of iterations are compared to the traditiona1 a1gorithm has a great improvement，and further prove that the proposed improved methods and strategies are correct and feasib1e，is conducive to better on the current 1ogistics distribution path optimization.

ant co1ony a1gorithmj pheromonej 1ogistics distributionj ant transferj path optimization

TP393

A

1674_6236（2016）10_0068_03

2015_06_11稿件編號：201506116

李靜（1982—），女，新疆昌吉人，講師。研究方向：物流工程與管理。