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

文/原丕業(yè)張明王岐昌劉曉偉

1.引言

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

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

2.基于蟻群算法的送餐路徑優(yōu)化算法

2.1 蟻群算法基本原理

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

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

2.2 蟻群算法模型構(gòu)建

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

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

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

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

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

2.3 蟻群算法求解步驟

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

圖1 計算流程圖

3.實例驗證及結(jié)果分析

3.1 實例求解驗證

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

坐標(biāo)為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個坐標(biāo)進行數(shù)據(jù)分析，得數(shù)據(jù)迭代200次后的理論最短路徑與迭代收斂圖：（見圖3、圖4）

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

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

圖3 最短路徑圖

圖4 曲線收斂圖

表1 螞蟻數(shù)量對路徑長度的影響

3.2 運行結(jié)果分析

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

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

4、結(jié)論

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

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

在對送餐問題和蟻群算法的深層次理解的基礎(chǔ)上，建立模型并進行多次、多數(shù)值循環(huán)調(diào)試。得出問題的最優(yōu)解，實現(xiàn)最初的目標(biāo)，規(guī)劃出最短路徑，提高送餐效率。但是本文問題研究較淺，無論是理論還是實踐方面都還需要進一步的加深研究。