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

1.引言

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

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

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

2.1 蟻群算法基本原理

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

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

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

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

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

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

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

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

2.3 蟻群算法求解步驟

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

圖1 計(jì)算流程圖

3.實(shí)例驗(yàn)證及結(jié)果分析

3.1 實(shí)例求解驗(yàn)證

調(diào)查選取15個(gè)距離坐標(biāo)，建立城市坐標(biāo)系，對距離坐標(biāo)進(jìn)行檢驗(yàn)。參數(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個(gè)坐標(biāo)進(jìn)行數(shù)據(jù)分析，得數(shù)據(jù)迭代200次后的理論最短路徑與迭代收斂圖：（見圖3、圖4）

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

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

圖3 最短路徑圖

圖4 曲線收斂圖

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

3.2 運(yùn)行結(jié)果分析

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

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

4、結(jié)論

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

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

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