基于貪心蟻群算法的生鮮配送全局路徑規(guī)劃

楊瑞琪，馬巧玲，連天嬌，郭丹陽(yáng)，許曙博

（廣州城市理工學(xué)院,廣東廣州，510800）

0 引言

隨著經(jīng)濟(jì)的發(fā)展和社會(huì)生活水平的提高，各個(gè)城市出現(xiàn)交通擁堵現(xiàn)象，給生鮮產(chǎn)品配送帶來(lái)挑戰(zhàn)。生鮮配送的速度會(huì)影響到人們健康生活，然而當(dāng)前社會(huì)在生鮮配送上的發(fā)展水平較低，需要提高生鮮配送的技術(shù)。

對(duì)于生鮮配送路徑優(yōu)化問(wèn)題的研究，許多國(guó)內(nèi)學(xué)者進(jìn)行了大量的研究，并取得一定的成果。文慧君[1]研究了上層為冷鏈物流優(yōu)化總成本，下層為優(yōu)化客戶滿意度的雙層規(guī)劃模型，使用遺傳算法對(duì)雙層規(guī)劃模型進(jìn)行求解。楊雅琪[2]在生鮮連鎖店配送路徑問(wèn)題的研究中，考慮到各地區(qū)交通擁堵的因素，為有效減少生鮮配送成本，并且提高生鮮配送的準(zhǔn)時(shí)性。因此為M生鮮連鎖店構(gòu)建出，由蟻群算法和侵入雜草算法相結(jié)合的新混合蟻群算法—生鮮連鎖店配送促進(jìn)優(yōu)化模型。明小菊等[3]以最小化成本為目標(biāo)創(chuàng)建了冷鏈配送優(yōu)化模型，采用萊維飛行和反向?qū)W習(xí)優(yōu)化的粒子群算法對(duì)粒子群算法進(jìn)行優(yōu)化用于模型求解。王永鋒[4]針對(duì)生鮮產(chǎn)品易腐敗的特性，提出建立帶時(shí)間窗的配送車輛路徑優(yōu)化數(shù)學(xué)模型，選擇混沌遺傳算法對(duì)模型求解，縮短了運(yùn)輸距離，降低了運(yùn)輸成本。

我國(guó)對(duì)生鮮產(chǎn)品配送的需求不斷增加，為了降低生鮮產(chǎn)品的配送成本，解決路徑優(yōu)化問(wèn)題，本文采用蟻群算法尋找最優(yōu)路徑，但該算法收斂速度慢、運(yùn)行時(shí)間長(zhǎng)、區(qū)域搜索能力差。為了彌補(bǔ)蟻群算法的缺點(diǎn)，引入貪心算法提高了蟻群算法的局部搜索能力。考慮到實(shí)際生鮮產(chǎn)品配送需求的特點(diǎn)和相關(guān)條件的制約，設(shè)計(jì)了貪心蟻群算法，實(shí)施了全球路徑規(guī)劃，達(dá)到了配送路徑的最佳目的。

1 算法

1.1 蟻群算法

蟻群算法是模仿螞蟻覓食的行為，是一種仿生算法。螞蟻在尋找食物的過(guò)程中，產(chǎn)生螞蟻和螞蟻之間交換信息的機(jī)制，即信息素，從而獲得食物和當(dāng)前位置的最佳路徑[5]。

傳統(tǒng)的蟻群算法是由1991 年由 Marco Dorigo等提出的。在研究過(guò)程中發(fā)現(xiàn)，螞蟻覓食的過(guò)程中，會(huì)在路上釋放信息素，而且信息素會(huì)隨著時(shí)間的流逝而揮發(fā)，螞蟻?zhàn)哌^(guò)的路線越長(zhǎng)，留下的信息素?fù)]發(fā)多濃度則低，相反越短的路徑上面的信息素發(fā)揮的時(shí)間越短，導(dǎo)致該路徑上的信息素濃度高，更容易引導(dǎo)后來(lái)的螞蟻來(lái)走這條最短的路徑[6]。蟻群算法就是模擬自然界蟻群尋找從蟻巢到食物源間最短路徑過(guò)程的一種隨機(jī)搜索算法[7]。但是蟻群算法存在收斂速度慢，容易陷入局部最優(yōu)解的問(wèn)題。蟻群算法的執(zhí)行步驟如圖2所示。

圖1 螞蟻的覓食過(guò)程

圖2 蟻群算法流程

螞蟻在覓食過(guò)程中會(huì)在路徑上留下信息素，其他螞蟻則傾向于沿著不同路徑上信息素濃度較高的路徑走，如果距離相同，則傾向于走濃度較高的路徑，經(jīng)過(guò)一段時(shí)間后，可以以最短的路徑到達(dá)目的地。螞蟻k從選擇下一節(jié)點(diǎn)的概率公式如式（1）所示 ：

每個(gè)螞蟻個(gè)體在通過(guò)特定路徑時(shí)釋放信息素，通過(guò)所有路徑節(jié)點(diǎn)后，根據(jù)信息素的疊加和揮發(fā)機(jī)制更新路徑中的信息素，更新策略如公式（3）所示：

式中：ρ為信息素?fù)]發(fā)系數(shù)，（1-ρ）為信息素的殘留系數(shù)，如果ρ值過(guò)小，會(huì)導(dǎo)致殘留的信息素裹多，則會(huì)無(wú)法區(qū)別路徑的長(zhǎng)短，?τij為節(jié)點(diǎn)i到節(jié)點(diǎn)j信息素的增量，其計(jì)算值如式（4）所示 ：

式中：Q為蟻群算法的信息素強(qiáng)度系數(shù)。

1.2 貪心算法

貪心算法是一種能夠得到某種度量意義下的最優(yōu)解的分級(jí)處理方法，它總是做出在當(dāng)前看來(lái)是最優(yōu)的選擇，也就是說(shuō)貪心策略并不是從整體上加以考慮它所做出的選擇只是在某種意義上的局部最優(yōu)解算法[8]。貪心算法在路徑規(guī)劃方面，每次僅會(huì)選擇離當(dāng)前節(jié)點(diǎn)最近的節(jié)點(diǎn)，直到所有的節(jié)點(diǎn)都選取完畢，就完成路徑規(guī)劃。由于貪心策略總是采用從全局看來(lái)是最優(yōu)的選擇，因此并不從整體上加以考慮，不能保證求得的最后解是最佳的。

當(dāng)貪心算法經(jīng)常被用于解決優(yōu)化問(wèn)題時(shí)，為了獲得目標(biāo)函數(shù)最優(yōu)解，將會(huì)不斷地進(jìn)行搜索選擇。采用循環(huán)的動(dòng)態(tài)方式縮小問(wèn)題、解決問(wèn)題，不斷得出子問(wèn)題的最優(yōu)解。例如，在活動(dòng)選擇問(wèn)題中，我們總是根據(jù)一個(gè)問(wèn)題選擇結(jié)束時(shí)間最早的活動(dòng)，然后根據(jù)其余活動(dòng)選擇結(jié)束時(shí)間最早的活動(dòng)，直到?jīng)]有活動(dòng)以這種方式選擇為止。綜上所述，將總問(wèn)題劃分成子問(wèn)題，依次求解子問(wèn)題的最優(yōu)解，最后將子問(wèn)題的最優(yōu)解整合成總問(wèn)題的解[9]。

1.3 貪心蟻群算法

針對(duì)貪心算法和蟻群算法各自的缺點(diǎn)，把兩種算法結(jié)合起來(lái)，在傳統(tǒng)蟻群算法的操作步驟中接入貪心策略，提高算法的局部搜索能力和收斂速度。算法步驟如下：首先進(jìn)行初始化參數(shù)，包括蟻群初始化數(shù)量、最迭代次數(shù)、啟發(fā)函數(shù)因子、揮發(fā)因子、信息素等，其中開(kāi)始的時(shí)候每條邊的信息素量都相等。將各只螞蟻分別放在各個(gè)的頂點(diǎn)，禁忌表為對(duì)應(yīng)的頂點(diǎn)。其次選取一只螞蟻，引入貪心策略修改初始路線。傳統(tǒng)的蟻群算法，螞蟻的初始路線是隨機(jī)生成的，當(dāng)遇見(jiàn)帶有信息素的路線時(shí)，根據(jù)概率決絕是否要更改路線。蟻群即使當(dāng)下時(shí)刻選擇了走帶有信息素的路線，下一時(shí)刻也不一定會(huì)繼續(xù)走帶有信息素的路線，反而是繼續(xù)走隨機(jī)路線。由于隨機(jī)路線是隨機(jī)生成的，當(dāng)參數(shù)設(shè)置不當(dāng)時(shí)，算法搜索路徑的時(shí)候會(huì)延長(zhǎng)，收斂速度極慢，因此引入貪心策略，設(shè)置蟻群的初始路線，減少算法迭代的時(shí)間。計(jì)算一只螞蟻額的轉(zhuǎn)移概率，選擇下一個(gè)頂點(diǎn)，更新禁忌表，再計(jì)算概率，再選取頂點(diǎn)，循環(huán)往復(fù)，直至這只螞蟻遍歷了所有頂點(diǎn)。計(jì)算當(dāng)前這只螞蟻留在各條邊上的信息素增量，然后該螞蟻完成使命死去。所有螞蟻都重復(fù)一樣的步驟。直到所有螞蟻都完成使命。計(jì)算各條邊的信息素增量 ?τij和信息素量τij(t+n)。最后，記錄本次迭代的路徑，更新當(dāng)前的最優(yōu)路徑，清空禁忌表。判斷是否達(dá)到預(yù)定的迭代步數(shù)，若是則輸出當(dāng)前的最優(yōu)路徑，結(jié)束程序，若為否，則繼續(xù)迭代。

2 實(shí)驗(yàn)

2.1 參數(shù)設(shè)置

蟻群作為一種啟發(fā)式搜索算法，蟻群算法具有良好的魯棒性，且易于融合其他算法應(yīng)用到實(shí)際問(wèn)題中[5]。貪心蟻群算法的實(shí)驗(yàn)參數(shù)設(shè)置如下表所示，參數(shù)的設(shè)置都是在經(jīng)驗(yàn)值的基礎(chǔ)上，結(jié)合實(shí)驗(yàn)效果進(jìn)行修改的，具有一定的適用性。

表1 相關(guān)參數(shù)設(shè)置

2.2 實(shí)驗(yàn)數(shù)據(jù)介紹

為了驗(yàn)證算法改進(jìn)的有效性，使用32個(gè)信息節(jié)點(diǎn)來(lái)模擬一位生鮮配送員的配送情況，并利用Matlab軟件編寫算法實(shí)現(xiàn)。節(jié)點(diǎn)的部分信息如下所示。其中節(jié)點(diǎn)1表示起點(diǎn)，節(jié)點(diǎn)2-32表示顧客，如表2所示。假定生鮮配送員以勻速行駛，沒(méi)有突發(fā)狀況發(fā)生。

表2 部分節(jié)點(diǎn)信息

2.3 結(jié)果分析

分別對(duì)貪心算法、傳統(tǒng)的蟻群算法和改進(jìn)后的貪心蟻群算法進(jìn)行10次實(shí)驗(yàn)，得到的結(jié)果如下表所示。從尋優(yōu)的結(jié)果可以看出，在求解該問(wèn)題的最優(yōu)路線時(shí)，貪心算法只基于當(dāng)前節(jié)點(diǎn)考慮下一個(gè)最優(yōu)節(jié)點(diǎn)，導(dǎo)致前期的路線為最優(yōu)路線，后期的路線為剩余節(jié)點(diǎn)的湊合，路線很長(zhǎng)，達(dá)不到全局優(yōu)化的目的。而蟻群算法和貪心蟻群算法從圖中可以看出，規(guī)劃的路線節(jié)點(diǎn)之間的長(zhǎng)度較均勻合理。但是貪心蟻群算法所求得的路徑的距離是三種中最短的、算法運(yùn)行的時(shí)間也較傳統(tǒng)的蟻群算法少得多。如圖可知，貪心蟻群最優(yōu)解的配送路線為：1-15-9-8-4-25-21-32-16-6-12-22-11-10-13-19-5-7-14-27-2-23-28-17- 29-24-3-18-31-30-20-26，計(jì)算得到總距離約114.9294km。

表3 算法運(yùn)行結(jié)果

圖3 貪心算法路徑規(guī)劃圖

圖4 蟻群算法路徑規(guī)劃圖

圖5 貪心蟻群路徑規(guī)劃圖

螞蟻種群算法和貪心蟻群算法的最佳距離和算法迭代次數(shù)如下圖所示，通過(guò)貪心算法改善局部搜索能力后，可以用較少的迭代次數(shù)找到最佳路徑，算法的改進(jìn)具有良好的效果。

圖6 蟻群算法適應(yīng)度曲線

圖7 貪心蟻群算法適應(yīng)度曲線

3 結(jié)論

本文基于生鮮配送問(wèn)題，使用貪心算法、蟻群算法和改進(jìn)后的貪心蟻群算法進(jìn)行求解，通過(guò)對(duì)比實(shí)驗(yàn)可知，貪心蟻群算法能加快算法的收斂，并進(jìn)行路徑的優(yōu)化。