基于優化蟻群算法在糧食運輸車輛調度中的應用研究

何小虎

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

關鍵詞：蟻群算法；車輛運輸；路徑優化

中圖分類號：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

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

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

1 糧食物流配送數學模型

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

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

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

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

4）糧食運輸總費用與運輸的總量是成正比。

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

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

2 改進蟻群算法

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

2.1 螞蟻轉移規則的改進[3]

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

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

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

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

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

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

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

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

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

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

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

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

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

5）當迭代次數等于NCmax，則輸出糧食配送最優路徑和長度，程序結束。

3 改進蟻群算法仿真試驗

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

參數設置為：NCmax=30，Q=2，m=20，α=1，=0.5，β=3，改進算法運行15次后得到了最優配送線路如圖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 小結

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

參考文獻：

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

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

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

[4] 汪采萍.蟻群算法的應用研究[D].合肥：合肥工業大學，2007.

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

[6] 郭天池.基于蟻群算法的糧食應急調度問題研究[D].鄭州：河南工業大學，2011.

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

[8] 吳虎發.蟻群優化算法在求解最短路徑問題中的研究與應用[D].合肥：安徽大學，2012.