何小虎

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

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

中圖分類號(hào)：TP301.6；S274 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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ì)民生，其價(jià)格高低直接影響國家經(jīng)濟(jì)的發(fā)展。在糧食價(jià)格的組成中，糧食流通成本比重很高，許多加工糧食企業(yè)對(duì)糧食配送采用人工方式，運(yùn)輸線路不合理，導(dǎo)致運(yùn)輸成本居高不下。因此，研究如何有效地降低糧食的運(yùn)輸成本，將有十分重要的現(xiàn)實(shí)意義。

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

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

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

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

2）糧食配送中心能夠完全滿足各個(gè)配送點(diǎn)的糧食需求；

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

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

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

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

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

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

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

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

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

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

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

2.2 信息素濃度初始值的改進(jìn)策略[4]

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

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

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

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

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

2）把n個(gè)螞蟻放到糧食配送中心，利用公式（8）選擇螞蟻下一次移動(dòng)的糧食配送點(diǎn)，同時(shí)把該配送點(diǎn)加入螞蟻的禁忌表。

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

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

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

3 改進(jìn)蟻群算法仿真試驗(yàn)

以某地區(qū)1個(gè)糧食配送中心和20個(gè)糧食配送點(diǎn)為例，使用改進(jìn)的蟻群算法在實(shí)驗(yàn)室中用MATLAB2010進(jìn)行模擬測試，配送中心用編號(hào)0，其他配送點(diǎn)分別用1，2，…，20，要求運(yùn)輸費(fèi)用最少。各配送點(diǎn)的橫縱坐標(biāo)和需求量如表1所示。

參數(shù)設(shè)置為：NCmax=30，Q=2，m=20，α=1，=0.5，β=3，改進(jìn)算法運(yùn)行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é)

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

參考文獻(xiàn)：

[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é)報(bào)，2012，13（3）：336-341.

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

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

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