基于蟻群算法的農產品配送路徑優(yōu)化設計

周榮虎 （鹽城工業(yè)職業(yè)技術學院，江蘇 鹽城 224005）

根據(jù)農產品時效性的特點，農產品配送中心路線規(guī)劃時，除了要考慮常規(guī)物流配送一般影響因素外，還要考慮時間約束問題、客服水平問題、農產品保鮮度問題等，配送距離的長短決定了配送費用和效率，司機在選擇派送路徑的時候根據(jù)自己的習慣，隨機或者盲目性的選擇農產品配送路徑，這一習慣往往造成繞路、重復路徑等問題，無形中增加了運輸成本、不能保證派送的時效性、降低了客戶滿意度，農產品配送路徑的優(yōu)化非常有必要，蟻群算法的出現(xiàn)為配送路徑優(yōu)化問題提供了有效的工具。

1 問題描述

20 世紀90 年代Marco Dorigo 在他的博士論文中提出螞蟻算法，蟻群算法是一種模擬進化算法，初步的研究表明該算法具有許多優(yōu)良的性質。針對PID 控制器參數(shù)優(yōu)化設計問題，將蟻群算法設計的結果與遺傳算法設計的結果進行了比較，數(shù)值仿真結果表明，蟻群算法是一種用來在圖中尋找優(yōu)化路徑的概率型算法。它是通過人工模擬螞蟻尋找食物的過程，即個體之間的信息交流和協(xié)作最終找到從蟻穴到食物源的最短路徑。

1.1 蟻群算法特點

1.1.1 較強的魯棒性

相對于其它算法，蟻群算法對初始線路要求不高，即蟻群算法的求解結果不依賴于初始線路的取舍，而且在搜索過程中不需要進行人工的調整。其次，蟻群算法的參數(shù)數(shù)目少，設置簡單，易于蟻群算法應用到其他組合優(yōu)化問題的求解。

1.1.2 是一種正反饋的算法

從真實螞蟻的覓食過程中不難看出，螞蟻能夠最終找到最短路徑，直接依賴于最短路徑上信息激素的堆積，而信息激素的堆積卻是一個正反饋的過程，正反饋是蟻群算法的重要特征，它使得算法演化過程得以進行。

1.2 問題描述

1.2.1 隨機性選擇派送路徑問題

派送員在派送農產品的時候對路徑的選擇存在隨機性問題，沒有一套科學的方法去選擇路徑，大部分派送員的派送路徑都是根據(jù)習慣或者隨機的選擇而定。

1.2.2 盲目性選擇農產品配送路徑問題

派送員在進行農產品派送的時候存在盲目性問題。派送員在農產品出倉后不按照規(guī)劃好的路徑排列農產品，而是隨便裝入車中。邊走邊按照運單上的客戶地址進行派發(fā)農產品。繞路或者派送路徑重復的情況頻頻出現(xiàn)，不僅浪費派送時間并且增加了派送成本。

2 模型建立與假設

2.1 蟻群算法原理

螞蟻總能找到一條往返于食物源和巢穴之間的最優(yōu)路徑，這是因為螞蟻在走過的路徑上釋放出一種特殊的信息素，路徑越長，釋放的信息素濃度越低。螞蟻再次選擇路徑的時候，信息素濃度較高的路徑被選中的概率相對較大，因此形成一個正反饋，最優(yōu)路徑上的信息素濃度越來越大，而其他的路徑上信息素濃度卻會隨著時間增加而減少。最終整個蟻群會找出最短路徑。具體情況如圖1 所示:

設E 是螞蟻巢穴，F(xiàn) 是食物源，BD 是一個障礙物。路徑ABC 的距離是路徑ADC 的2 倍。因為在E 到F 的直線距離中間有障礙物的存在。螞蟻必須經過B 或D 往返于E,F 兩點之間。設每個時間單位分別有30 只螞蟻由E 到達A，由F 到達C。為方便說明，設螞蟻走過后留下的信息素在路徑上的停留時間為l。在初始時刻（如圖1a），由于路徑AB、CB、AD、CD 上都沒有信息素，A 和C 兩點所在的螞蟻可以隨機選擇路徑。從統(tǒng)計的角度可以認為它們以相同的概率選擇AB、AD 或者CB、CD。因為信息素與路徑的長短成反比，在經過一個時間單位后，路徑ADC 上的信息素是路徑ABC 上信息素的2 倍。在t=1 時刻（如圖1b），將有20 只螞蟻分別由A 和C到達D，有10 只螞蟻分別由A 和C 到達B。隨著時間的推移，螞蟻選擇路徑ADC 的概率會越來越大，直到所有螞蟻完全選擇路徑ADC，螞蟻便找到了從蟻穴到食物源的最短路徑。

圖1 蟻群算法原理示意圖

2.2 最短路徑模型建立

農產品配送路徑優(yōu)化問題就是找到一條派送員以公司點部為起點，經過每一個有需求的客戶且僅一次，最后返回到起點的最短路徑。本節(jié)將蟻群算法的原理運用到進行農產品配送路徑優(yōu)化問題中。

2.2.1 提出假設

2.2.2 最短路徑模型建立

2.2.3 基本蟻群算法模型

式（6） 中，Q3是常量，Lk表示第k 只螞蟻在一次循環(huán)后路徑的長度。即如果螞蟻經過ij，則信息素增量為一個常量除以螞蟻k 的一次循環(huán)路線長。這里信息素增量只與螞蟻的循環(huán)路線和Q3有關系，而和具體的dij無關。

蟻量模型和蟻密模型利用的是局部信息，螞蟻在完成一步（從一個客戶到達另外一個客戶） 便更新所有路徑上的信息素。而蟻周模型利用的是整體信息，螞蟻在一個循環(huán)（對所有n 個客戶的訪問） 以后，才更新所有路徑上的信息素。因此在求解農產品配送路徑優(yōu)化問題時，蟻周模型比前面兩種模型好。

當所有螞蟻在一次循環(huán)結束后。所有m 只螞蟻從同一點部M 出發(fā)隨機的前往n 個客戶處，重復上述步驟直到所有螞蟻都選擇一條相同路徑的時候或者到達最大循環(huán)次數(shù)Nmax選出最短路徑。蟻群算法的步驟為：將m 只螞蟻隨機放入n 個客戶處，m只螞蟻分別從n 個客戶處出發(fā)，由式（2） 選擇下一次經過的客戶，Tabuk 為放入的已去過的客戶，一次循環(huán)后，根據(jù)式（3）、式（6） 更新每條路徑上的信息素，反復重復以上步驟，直到終止條件成立，求出目標函數(shù)最優(yōu)值為止。

2.3 實例計算

為方便計算，本文選取蘇州車坊鎮(zhèn)SF 速運獨墅湖點部M 中的收派員A 的區(qū)域B 中的10 個客戶為例（以K0,K1,…,K9，命名）。運用蟻群算法對此10 個客戶的農產品配送路徑進行規(guī)劃來說明蟻群算法在農產品配送路徑優(yōu)化問題中的實用性。

2.3.1 實例說明

（1） 某鄉(xiāng)村的客觀條件

采用10 個客戶為研究對象，標記為1,…,10 分別代表K0,K1,…,K910 個客戶。在派送農產品的時候不是取兩地之間的直線距離，而是沿道路距離，通過測量建立點部到各個客戶的距離以及客戶與客戶之間的距離表如表1 所示。

表1 點部到每個客戶的距離以及客戶之間的距離 單位：米

（2） 參數(shù)設置

為方便計算，提出以下假設條件：①10 個客戶都需要有簽收。②所有螞蟻每次都由點部出發(fā)，走完所有客戶后又回到點部。③每只螞蟻在一次循環(huán)過程中經過每一個客戶且僅一次。④每個客戶到點部M 以及客戶與客戶之間的路徑長度已知。

本文用100 000 次循環(huán)作為計算終止條件（這里一次循環(huán)是指所有螞蟻完成一次遍歷所有客戶且僅一次后回到出發(fā)點部）。螞蟻總數(shù)目設置為客戶的總數(shù)目(m=n=1)0 。即10 只螞蟻同時從點部M 出發(fā)開始循環(huán)，直到所有螞蟻都返回點部則完成一次循環(huán)。具體參數(shù)設置如表2 所示。

在表2 中，Lk表示的是第k 只螞蟻的一次循環(huán)路線的長度，如果第k 只螞蟻經過的路線為：M→K0→K1→K7→K8→K2→K5→K4→K3→K6→K9→M。

表2 實例中所用參數(shù)設置

即第k 只螞蟻本次循環(huán)的路徑總長度為2 575 米。本文就是運用蟻群算法計算出一只螞蟻從點部出發(fā)經過每個客戶且只經過一次最后回到點部的最短路徑。從而縮短農產品配送路徑，節(jié)省運輸成本。

2.3.2 運用蟻群算法對農產品配送路徑進行編程計算

結合蟻群算法的原理，對農產品配送路徑進行優(yōu)化設計，并運用C++對設計好的最短路徑模型進行編程計算。運用蟻群算法優(yōu)化農產品配送路徑的步驟為：10 只螞蟻從同一點部M同時出發(fā)，將參數(shù)代入式（2） 選擇下一次經過的客戶，Tabuk 為放入的已去過的客戶，一次循環(huán)后，將參數(shù)代入式（3）、式（6） 更新每條路徑上的信息素，反復重復以上步驟，直到終止條件成立，求出式（1） 最短路徑模型的最優(yōu)值為止。按照上述步驟編輯好的程序如附錄所示。附錄在VC 上運行結果如圖2 所示：

圖2 附錄在VC 上的運行結果

2.3.3 結果分析

由圖2 可知螞蟻從獨墅湖點部M 出發(fā)經過10 個客戶且每個客戶只經過一次的排列順序為：M 9 7 8 6 5 4 3 2 1 0 M。因此派送員A 在為10 個客戶派送農產品的時候，從點部M 出發(fā)后，首先應去客戶K9處，最后到達客戶K0處。其走過的路徑即為此次農產品配送過程中走過的最短路徑。最短路徑L 的排列順序為：M→K9→K7→K8→K6→K5→K4→K3→K2→K1→K0→M。

即是派送員由獨墅湖點部M出發(fā)，分別經過10 個客戶且僅一次派送完農產品直接返回點部的最短路程為1 475 米。

如果第k 只螞蟻的循環(huán)路徑為：M→K1→K3→K6→K8→K9→K4→K0→K2→K5→K7→M。k

通過多次對10 個客戶的排列順序隨機組合，沒有找到路徑Lk的長度比1 475 米更小的值。說明派送員A 為10 個客戶派送農產品的最短路徑為1 475 米。

在沒有進行路徑優(yōu)化的時候，農產品員隨機選擇路徑進行農產品配送，剛好選擇到最短路徑L 的幾率非常小，但是在運用蟻群算法進行路徑規(guī)劃后，派送員每次都可以按照規(guī)劃好的路徑進行農產品配送。為每一個農產品派送員規(guī)劃自己區(qū)域內的客戶帶來很大的方便，由此可見蟻群算法在農產品配送路徑優(yōu)化中具有非常大的實用性。

3 結束語

3.1 主要研究工作

本文首先針對農產品配送路徑的現(xiàn)狀進行分析，然后提出派送員選擇農產品配送路徑的時候，存在選擇隨機性問題和路徑重復問題。最后針對這兩個問題引入蟻群算法對農產品配送路徑進行優(yōu)化，尋找一條從農產品公司點部M 出發(fā)經過每一個需求點且僅一次最后回到點部M 的最短路徑，實現(xiàn)節(jié)約農產品公司的配送成本、提高派送效率、增強客戶滿意度的目標。通過本文的研究說明蟻群算法在農產品配送路徑優(yōu)化問題中應用，有助于農產品公司降低運輸成本，提高客戶滿意度。

3.2 進一步研究問題

本文雖取得了一些有意義的成果，但是還有許多需要進一步進行研究的方向。

（1） 在論文的實例中假設每個客戶都有農產品需要簽收，但實際派送過程中派送員負責的客戶中有的客戶在派送沒有簽收。改進蟻群算法突破局部最優(yōu)的計算，把客戶變動的因素設為變量的同時也能找到農產品配送的最短路徑。

（2） 本文假設派送員在一次農產品配送過程中經過每一個客戶且僅一次。沒有考慮到突發(fā)狀況和特殊快件的出現(xiàn)，例如實際生活中有的派送員因為一時大意而沒有把同一客戶處的農產品配送完畢，需要重復派送。或者有的農產品收件人需要提供優(yōu)先派送服務，下一步可以通過進一步改進蟻群算法使其在加入突發(fā)狀況后依然能找到最短路徑。