基于蟻群優化的糧食物流調度算法研究

[摘要] 糧食物流調度是一個組合優化問題。用蟻群共同測試不同的組合，并選擇一個優化的解決方案，采用該方案能使糧食運輸成本降低。研究及實驗結果表明蟻群算法在糧食物流調度中具有良好的性能。

[關鍵詞] 蟻群 糧食物流 調度 優化

一、糧食物流調度路線安排模型

根據糧食物流約束條件，可以表示如下:

記G=(V，E)為賦權圖;E為邊集，各糧庫間的(距離)權值為dij。

V-糧庫集合V={i}，i=1， …，n， 且i=0指初始糧庫；M-散糧車輛集合，M={k}，k=1， …，m，(散糧車輛數) ；qi-糧庫i的糧食需求量，； dij-糧庫i到糧庫j的距離；散糧車輛的載重量，。

二、基于蟻群的糧食物流調度算法

1.基本的蟻群系統模型。為模擬蟻群系統的尋徑方法，我們定義如下參數:m:蟻群中螞蟻的數量；:路徑（i，j）的能見度；:t時刻在路徑ij上的信息量;:螞蟻k在本次循環中留在路徑ij上的信息量;:螞蟻k在t時刻由位置i轉移到位置j的概率;α:軌跡的相對重要性（α≥0）;β:能見度的相對重要性(β≥0）;：信息素的持久性（0≤＜1），1-表示信息素的衰減度。初始時刻，設所有路徑上的信息素都相等，(0)=C(C是一個常數)。螞蟻k（k=1，2，…，m）在運動過程中，根據各條路徑上的信息素的大小以一定的概率決定轉移方向，表示為：

2.算法的改進。遺傳算法(GA)與螞蟻算法(ant algorithm，AA)融合的算法稱為GAAA算法。我們直接把這種算法改進應用到糧食物流調度上來。我們對信息素的處置設置及信息素更新做以下處理:

(1)信息素的初值設置是把各路徑信息素初值設為最大值max，這里通過遺傳算法得到了一定的路徑信息素，所以把信息素的初值設置為。其中是一個根據求解問題規模給定一個信息素常數，相當于MASS算法中的，是遺傳算法求解結果轉換的信息素值。

(2)信息素更新模型。采用一周模型進行信息素更新，即一周中只有最短路徑的螞蟻才進行信息素修改增加，而所有路徑的軌跡更新方程采用:

這樣對本次螞蟻所走過的路徑上信息素進行更新，使得不可行解不能進入解空間，可以加快算法的收斂速度。

三、糧食物流實例分析

問題描述：某一個初始糧庫要向10個糧庫運輸糧食，有22輛散糧運輸車，6噸的4輛；8噸的4輛；10噸的13輛和20噸的1輛。表1是各個糧庫之間的距離和各個糧庫的糧食運輸量。要求合理安排車輛的行駛路線，使總運輸里程最小。

運用本文提供的蟻群算法對上述問題進行求解，以matlab7.0為工具，在P-4 PC機運算，初始參數設置為：

得最終的糧食物流優化路徑為 ：使用三種散糧車輛，10噸一輛，8噸一輛，6噸一輛。10噸散糧車的路徑是: 初始糧庫，糧庫1，糧庫2，糧庫3，糧庫9，回路行程220公里，載糧食運距947.6噸公里。 8噸散糧車的路徑是: 初始糧庫，糧庫5，糧庫7，糧庫8，初始糧庫，回路行程145公里，載糧食運距193.9噸公里。 6噸散糧車的路徑是: 初始糧庫，糧庫4，糧庫6，糧庫10，初始糧庫，回路行程148公里，載糧食運距493.9噸公里。 總行駛513公里，載糧食運距1832.8噸公里。

四、結論

通過Matlab編制的程序對糧食物流調度的散糧車輛進行優化，可以看出：蟻群算法是成功的，在糧食物流的散糧車輛上的應用是可行的，并取得了比較理想的效果。這將為糧食企業在散糧車輛路線安排，車輛調度都將起到好的優化效果，為糧食企業快速決策，迅速對糧食做出反應提供了一定的參考價值。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。