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

李靜

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

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

李靜

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

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

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

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

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

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

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

1　單向物流問題描述

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

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

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

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

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

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

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

2　配送模型

2.1符號定義

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

2.2配送模型構建

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

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

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

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

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

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

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

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

4　蟻群算法改進

4.1對ρ的改進

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

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

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

當其運行到Z=Zmax的時候，則可以對其中的ρ進行調整，并對其再次進行Z次的重復計算，如此反復。

4.2基于遺傳算法的改進蟻群

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

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

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

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

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

4.3改進算法流程圖

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

圖1　改進算法流程圖

5　實例及仿真

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

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

表1　20客戶部分坐標

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

表2　改進算法仿真結果

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

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

6　結束語

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

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

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

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

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

［5］鄧亮，趙進，王新.基于遺傳算法的網絡編碼優(yōu)化［J］.軟件學報，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］祁金佺.遺傳蟻群算法在軟件測試用例生成中的應用［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—），女，新疆昌吉人，講師。研究方向：物流工程與管理。