何小虎

摘要：為了有效地降低車輛在糧食運輸中的成本，采用改進的蟻群算法對糧食物流配送路徑進行優(yōu)化。通過建立數(shù)學(xué)模型，提出改進的螞蟻轉(zhuǎn)移規(guī)則、優(yōu)化信息素濃度、改進全局信息素更新策略。結(jié)果表明，改進的蟻群算法比基本蟻群算法可以更好地解決糧食運輸車輛的路徑問題，使得運輸距離明顯縮短。

關(guān)鍵詞：蟻群算法；車輛運輸；路徑優(yōu)化

中圖分類號：TP301.6；S274 文獻標識碼：A 文章編號：0439-8114（2016）20-5372-03

DOI：10.14088/j.cnki.issn0439-8114.2016.20.052

Abstract： A modified ant colony algorithm was adopted and optimized in grain logistics distribution path in order to reduce transportation cost effectively. The results showed that the modified algorithm provide a better solution in grain logistics distribution path optimization than the basic ant colony algorithm. It can cut down path length about 9% and therefore play a bigger role in utilization of the limited resources.

Key words： ant colony algorithm； grain logistics； path optimization

糧食問題關(guān)乎國家的國計民生，其價格高低直接影響國家經(jīng)濟的發(fā)展。在糧食價格的組成中，糧食流通成本比重很高，許多加工糧食企業(yè)對糧食配送采用人工方式，運輸線路不合理，導(dǎo)致運輸成本居高不下。因此，研究如何有效地降低糧食的運輸成本，將有十分重要的現(xiàn)實意義。

降低糧食的流通成本，要根據(jù)各個配送點，設(shè)計出運輸線路最短的路徑，合理利用車輛的資源，用最小的成本達到糧食配送的目的。解決這類問題的方法較多，但是都存在一定的缺陷。蟻群算法是意大利學(xué)者Marco Dorigo等于1991年受自然界螞蟻覓食過程啟發(fā)而提出的一種新型智能搜索優(yōu)化算法。隨后將蟻群算法成功地應(yīng)用于旅行商問題求解上，并取得了很好的試驗結(jié)果。蟻群算法受到許多研究者的關(guān)注，并不斷應(yīng)用于實際問題求解，蟻群算法已經(jīng)被廣泛地應(yīng)用到各個領(lǐng)域解決復(fù)雜組合優(yōu)化問題。因此，本研究對基本蟻群算法進行改進優(yōu)化，建立數(shù)學(xué)模型，進而對糧食配送線路進行了試驗仿真。結(jié)果表明，改進優(yōu)化的蟻群算法對配送線路優(yōu)化取得了較好的效果。

1 糧食物流配送數(shù)學(xué)模型

由一個糧食配送中心向多個糧食配送點送糧，每個糧食配送點的地理位置和需求量固定，每輛運糧車輛的載重量和最大行駛距離固定，要求以最低的運輸成本合理安排配送線路，同時滿足每個糧食配送點的需求。為了保證數(shù)學(xué)模型滿足配送要求，該模型應(yīng)該滿足以下條件：

1）各條配送線路上各個糧食配送點的糧食需求量之和不超過送糧車輛的最大載重量；

2）糧食配送中心能夠完全滿足各個配送點的糧食需求；

3）糧食必須在有效的時間內(nèi)送到各個配送點；

4）糧食運輸總費用與運輸?shù)目偭渴浅烧取?/p>

多配送點糧食物流配送模型如下：設(shè)共有M個配送點，分別用1，2，3，…M表示。

式（2）表示糧食運輸車在運輸線路上成本最小。式（3）表示所有運輸車都是從配送中心出發(fā)，完成后回到配送中心。式（4）表示每輛車運輸糧食的重量不能超過車的最大載重量。式（5）表示每一條線路上只能由一輛運輸車完成。式（6）表示變量的取值。

2 改進蟻群算法

蟻群算法是模擬自然界中螞蟻覓食行為的隨機仿生優(yōu)化算法[1]，螞蟻之間通過傳遞信息素和協(xié)同合作，從而找到食物到巢穴間最短路徑。蟻群算法具有較好的魯棒性、并行性、全局尋優(yōu)、正反饋機制、分布性等優(yōu)點，但是也存在收斂速度過慢和容易陷入局部最優(yōu)等缺點[2]。

2.1 螞蟻轉(zhuǎn)移規(guī)則的改進[3]

為了避免螞蟻在搜索過程中陷入局部最優(yōu)而沒有得到最優(yōu)解，本研究對螞蟻的轉(zhuǎn)移規(guī)則進行了改進。初始路徑上各個節(jié)點的信息素是相同的，當螞蟻經(jīng)過某個節(jié)點時信息素的值就會增加。螞蟻就會快速聚集到這些節(jié)點上，從而導(dǎo)致算法陷入局部最優(yōu)。因此，提出干擾策略，提高螞蟻的搜索空間。

干擾因子表示路徑上的螞蟻擁擠程度，其計算公式為：

參數(shù)α是螞蟻在運動過程中的信息素影響因子，主要表示螞蟻在進行路徑搜索時路徑上所積累的信息素濃度對螞蟻進行路徑選擇所起的作用大小。

參數(shù)β是期望因子或稱為能見度因子，表示螞蟻在運動過程中能見度對路徑選擇的重要性。

2.2 信息素濃度初始值的改進策略[4]

基本蟻群算法的信息素濃度初始值是一個常數(shù)，為了提高算法的收斂速度，提出了信息素濃度初始值的改進策略，在初始化信息素的同時加入了引導(dǎo)功能，讓螞蟻移動時趨向于終點移動，信息素初始化的公式是：

2.3 全局信息素更新策略[4，5]

采用最大最小螞蟻系統(tǒng)MMAS，就是螞蟻在進行一次搜索完后，僅對所走過的路徑進行全局更新，可以大大縮小螞蟻的搜索范圍，使得螞蟻的搜索更具有方向性。這種改進策略不但可以提高搜索效率，而且可以保證搜索到的最優(yōu)解的充分利用。全局信息素更新如公式（10）所示：

2.4 蟻群算法主要步驟[6-8]

1）初始化參數(shù)α，β等參數(shù)以及螞蟻的數(shù)量和迭代次數(shù)NCmax，利用公式（9）初始化每條邊的信息素。

2）把n個螞蟻放到糧食配送中心，利用公式（8）選擇螞蟻下一次移動的糧食配送點，同時把該配送點加入螞蟻的禁忌表。

3）當螞蟻完成一次路徑搜索后回到出發(fā)點，并利用公式（10）更新當前較好路徑的信息素。

4）判斷迭代次數(shù)是否小于NCmax，如果成立，跳回步驟2，重復(fù)上述步驟，否則，程序結(jié)束。

5）當?shù)螖?shù)等于NCmax，則輸出糧食配送最優(yōu)路徑和長度，程序結(jié)束。

3 改進蟻群算法仿真試驗

以某地區(qū)1個糧食配送中心和20個糧食配送點為例，使用改進的蟻群算法在實驗室中用MATLAB2010進行模擬測試，配送中心用編號0，其他配送點分別用1，2，…，20，要求運輸費用最少。各配送點的橫縱坐標和需求量如表1所示。

參數(shù)設(shè)置為：NCmax=30，Q=2，m=20，α=1，=0.5，β=3，改進算法運行15次后得到了最優(yōu)配送線路如圖1所示。由圖1可以看出，共需要4輛車，4輛車的具體配送線路是：0-18-4-3-9-0；0-2-12-5-7-14-15-0；0-8-10-13-11-0；0-6-17-16-20-19-1-0，路徑長度為382.01 km。

4 小結(jié)

從仿真試驗結(jié)果來看，用改進的蟻群算法求解糧食物流配送路徑優(yōu)化問題時，有以下幾個優(yōu)點：①找到最優(yōu)解的概率更高；②求解效率和性能都進一步提升。但蟻群算法作為一種仿生智能優(yōu)化算法，仍有許多問題和不足之處，需要以后進一步深入研究和完善。

參考文獻：

[1] 余昌艷.基于蟻群算法的糧食加工企業(yè)物流配送路徑優(yōu)化研究[D].武漢：武漢科技大學(xué)，2009.

[2] 高 尚.蟻群算法理論、應(yīng)用及其與其他算法的混合[D].南京：南京理工大學(xué)，2005.

[3] 龍 汀.基于蟻群算法的車輛路徑問題的研究[D].合肥：合肥工業(yè)大學(xué)，2009.

[4] 汪采萍.蟻群算法的應(yīng)用研究[D].合肥：合肥工業(yè)大學(xué)，2007.

[5] 劉 霞，楊 超.最小-最大車輛路徑問題的蟻群算法[J].解放軍理工大學(xué)學(xué)報，2012，13（3）：336-341.

[6] 郭天池.基于蟻群算法的糧食應(yīng)急調(diào)度問題研究[D].鄭州：河南工業(yè)大學(xué)，2011.

[7] 陳迎欣.基于改進蟻群算法的車輛路徑優(yōu)化問題研究[J].計算機應(yīng)用研究，2012，29（6）：2031-2034.

[8] 吳虎發(fā).蟻群優(yōu)化算法在求解最短路徑問題中的研究與應(yīng)用[D].合肥：安徽大學(xué)，2012.