基于蟻群算法的送餐最短路徑問題求解研究

文/原丕業張明王岐昌劉曉偉

1.引言

隨著人們生活水平提高，外賣點餐越來越受歡迎。對于送餐員來說，短時間內接到的多個訂單，配送地點有所差異，且需要較短時間內將外賣送達。因此，送餐員需要考慮如何在最短時間內走完既定的路程并且路程最短。20世紀90年代意大利學者DorigoM 從仿生學的角度出發，最早提出了蟻群算法。蟻群算法（Ant Colony Optimization ACO） 是一種新型的模擬進化的算法，靈感來源于螞蟻覓食時釋放出一種信息素來發現路徑的行為[1]。它應用于組合優化的啟發式搜索方法，結合其它算法的優點，提出后被廣泛應用并深入研究。目前蟻群算法被應用于許多組合優化的問題中，例如旅行商問題（Traveling Salesmen Problem）、網絡路徑最優化問題等。楊從平（2014）用蟻群算法對快遞路徑網絡優化，降低配送車輛數和路程[2]。邵長旭（2018）等利用蟻群算法解決無人機航點數量較多的多種飛行軌跡問題，使飛行器以最短路徑完成任務，減少控制系統的時間損耗，提高任務執行效率[3]。本文以外賣送餐問題為例，采用蟻群算法，對蟻群算法在餐飲行業的應用進行探究，以便解決生活中的實際問題。

送餐問題對時間要求較為嚴格，送餐員在越短的時間內完成訂單，越能夠獲得消費者滿意度。主要是針對送餐員配送多個訂單，如何在路線網絡中選擇最優配送路線快速送餐配送。送餐問題是TSP問題的實際應用。TSP問題是一個局部最優解問題[4]。此問題可描述為：一個旅行商人從某個城市出發依次遍歷n個城市，每個城市只能拜訪一次，最后回到原出發城市，選擇最短的巡回路線[5]。旅行商問題是經典NP問題，在實際應用中，行走路徑多含障礙物，故蟻群算法有更加良好契合度。

2.基于蟻群算法的送餐路徑優化算法

2.1 蟻群算法基本原理

自然界中螞蟻的覓食行為不依賴于視覺，靠的是體內分泌的信息素和螞蟻種群的集體合作，尋找從蟻巢到食物的最短路徑。螞蟻在外出覓食時初始時會進行探索，并釋放一種稱為信息素（Pheromoe）的化學物質，螞蟻間借助信息素作為溝通媒介互傳遞消息[6]。螞蟻覓食，在行進路徑遺留信息素，較短路徑較高信息素濃度，其后螞蟻在路徑選擇時會優先順著信息素濃度高的路徑行走，最終經若干個螞蟻的選擇，趨向同一條路徑[7]。

螞蟻出巢覓食時一旦找到食物就會馬上返巢；若兩只以上螞蟻找到同一食物，行走的不同行徑，則過長路徑會導致信息素強度比較低，其后的螞蟻群體會選擇信息素濃度較高的路徑，最后篩選出一條最短路徑。如此以來，螞蟻種群的這樣一種選擇方式造成了一種螞蟻選擇路徑概率的大小與此路徑上信息素濃度大小的正反饋現象，即信息素濃度越大，其后螞蟻對該路徑選擇的可能性越大[8]。

2.2 蟻群算法模型構建

Dorigo提出以人工螞蟻代替真實螞蟻來模擬覓食。人工螞蟻與真實螞蟻既有區別又有聯系。兩者共同之處：（1）兩者都是相互合作的群體；（2）前者也是由信息素來獲得群體相互間的信息傳遞。簡單螞蟻具有以下特征：（1）通過城市間的信息素濃度來選擇下一個訪問城市時；（2）選擇訪問一個城市后，將城市計入到禁忌表tabu（k）中，螞蟻選擇的合法路線，不得選擇已訪問城市。一次循環之后，禁忌表中存放的是螞蟻群體所產生的巡回路線即螞蟻的行徑路線，隨后禁忌表會被清空，螞蟻進行下一步的自由選擇。

初始時刻（t=0時），城市間的信息量相等τij=C(C為常數)。t時刻時，螞蟻k選擇下一個將要訪問的城市時的概率由該條路徑上的信息素濃度決定：

經過一段時間，螞蟻行徑路線上信息素會產生變化，信息素的更新可以用（2）式來表示：

ρ 為信息素揮發系數，1-ρ 為信息素持久性；τij（t+a）表示在（t+a）時刻，城市i到j路徑的信息素濃度；Δτijk為第k只螞蟻在a時間段內在城市i到j間產生的信息素濃度，Δτijk為m只螞蟻在a時間段內在該條路徑釋放的總信息素濃度。確定Δτij可以用式（3）來表示：

Q為常數，表示信息素強度；Lk為螞蟻k所走路徑長度。

2.3 蟻群算法求解步驟

（1）參數初始化：初始化τij；（2）m 只螞蟻隨機分布到n個城市；（3）將螞蟻已訪城市放入禁忌表（tabu）中；（4）依據公式（1）計算螞蟻下一步將要選擇轉移的城市；（5）每迭代一次都將m只螞蟻走過的路徑長度進行計算，得出路徑長度數值。（6）在當前迭代次數的條件下，計算螞蟻行進路線的平均長度和最短距離。（7）根據公式（2）更新信息素。（8）迭代次數加1。nc=nc+1。（nc表示為迭代次數）（9）若迭代次數大于等于預定的迭代次數，則輸出計算結果；否，返回步驟（2）。流程圖如圖1所示：

圖1 計算流程圖

3.實例驗證及結果分析

3.1 實例求解驗證

調查選取15個距離坐標，建立城市坐標系，對距離坐標進行檢驗。參數設置如下：螞蟻數量m=30，信息素啟發因子α=1，期望啟發因子β=5，信息素揮發系數ρ=0.1，最大迭代次數NC-max=200，信息數初始化值=100。

坐標為C= （1321，616；4578，1415；3417，1230；5346，1109；1684，2035；4681，1578；2662，679；6110，2132；761，519；5713，1716；4399，2351；2963，1928；2857，3281；4965，3157；2336，2753）

然后對15個坐標進行數據分析，得數據迭代200次后的理論最短路徑與迭代收斂圖：（見圖3、圖4）

可以看出在迭代次數進行到10次左右時，該曲線已經收斂趨向于所得出最短路徑S=1.5174*104，接近于1.5174*104。說明在本模型中，進行200次迭代運行出的結果具有合理性。

探究螞蟻數量是否對模型的最優解產生影響，將螞蟻數量進行分別賦值5、10、15……50，而后分別環運行20次，尋找其中最短路徑的最大值、最小值以及平均值。具體數值見表1：

圖3 最短路徑圖

圖4 曲線收斂圖

表1 螞蟻數量對路徑長度的影響

3.2 運行結果分析

本文假設30只螞蟻通過15個訂餐點，經200次迭代，調試運行20次，求得最短路徑，并得最短路徑圖與曲線收斂圖，曲線收斂圖表示隨著迭代次數的增加，最短路徑距離會逐漸收斂于某個值。隨后改變螞蟻的數量來測算螞蟻數量對平均最短距離的影響，將螞蟻數量與平均最短距離用折線圖進行表示，對螞蟻數量分別賦值5、10、15……50，由圖4可以看出隨著螞蟻數量的增加，平均最短距離也逐漸趨向穩定。

送餐員送餐的過程中可以按照以上仿真結果進行路線行走，經過軟件計算出來的行走路線符合送餐過程的要求即：不重復地經過所有送餐點且最終回到原出發點。且經過重復測試，螞蟻數量增多最終數值越接近優化后的結果，所以仿真的結果是具有說服力的。

4、結論

上述過程可以看作是送餐員不重復的經過15個送餐點，完成外賣配送任務的過程。蟻群算法作為眾多智能算法之一，用于解決旅行商問題有較好的計算成果。

TSP問題在，旅游問題、配送送貨、推銷問題等具有廣泛應用，在實際問題中的求解中具有現實研究意義。本文采用蟻群算法，用來求解組合優化問題中的外賣送餐路徑規劃問題，對巡回路徑進行測算，并畫出最短路徑圖和曲線收斂圖來驗證結果的準確性和可信性。

在對送餐問題和蟻群算法的深層次理解的基礎上，建立模型并進行多次、多數值循環調試。得出問題的最優解，實現最初的目標，規劃出最短路徑，提高送餐效率。但是本文問題研究較淺，無論是理論還是實踐方面都還需要進一步的加深研究。