基于改進(jìn)蟻群算法的物流配送路徑優(yōu)化畢業(yè)論文

1、<p>　　摘要：本文所要探討的物流配送路徑優(yōu)化問(wèn)題，是基于改進(jìn)蟻群算法的物流最優(yōu)路徑選擇系統(tǒng)，算法實(shí)際上是正反饋原理和啟發(fā)式算法相結(jié)合的一種算法。該軟件采用C++語(yǔ)言編寫，用Qt做界面，可在Win7下運(yùn)行。在選擇路徑時(shí)，螞蟻利用了路徑上的信息素，不斷疊加，最終產(chǎn)生最優(yōu)路徑。本系統(tǒng)提供給合乎用戶需求的優(yōu)化路徑策略，如路徑最短、時(shí)間最短等進(jìn)行配送路線規(guī)劃方案。結(jié)合網(wǎng)上已有資源及多次實(shí)驗(yàn)計(jì)算，從而證明合理的使用蟻群算法進(jìn)行路徑線路

2、，能夠高效、快速的得到問(wèn)題的最優(yōu)解或接近最優(yōu)解。</p><p>　　關(guān)鍵詞：基本蟻群算法；最大最小蟻群算法；物流配送；蟻群系統(tǒng)；路徑優(yōu)化； </p><p><b>　　第一章 緒論</b></p><p><b>　　1.1研究背景</b></p><p>　　在美國(guó)，物流產(chǎn)業(yè)鏈被人們形象地比作

3、“尚未開(kāi)發(fā)的價(jià)值400億美元的金礦"。數(shù)據(jù)顯示，僅在每年物流成本上的支出，美國(guó)工業(yè)界就需要支付達(dá)到4000億美元。如此龐大的數(shù)字，我們?nèi)绻麅H僅將它降低10％，一年就可以節(jié)約近400億美元。在我國(guó)，2004年后，隨著網(wǎng)絡(luò)時(shí)代的極速發(fā)展，帶動(dòng)了網(wǎng)購(gòu)即電子商務(wù)的發(fā)展，相應(yīng)地我國(guó)對(duì)物流的需求也愈發(fā)增大。商務(wù)部公布的數(shù)據(jù)顯示，去年我國(guó)物流總額將近38．4億元，僅僅過(guò)了一年，增幅較往年就到到了2．9個(gè)百分點(diǎn)，物流業(yè)的經(jīng)濟(jì)產(chǎn)出可見(jiàn)一斑。然而

4、，就目前物流業(yè)發(fā)展可見(jiàn)，其發(fā)展己經(jīng)成為經(jīng)濟(jì)發(fā)展過(guò)程中必須有效管理的問(wèn)題。數(shù)據(jù)顯示我國(guó)GDP中物流所占比持續(xù)偏高，甚至高于發(fā)達(dá)國(guó)家。如此可見(jiàn)，物流業(yè)經(jīng)濟(jì)的迅猛增長(zhǎng)已經(jīng)是勢(shì)不可擋。</p><p>　　然而通過(guò)觀察以往的研究可以發(fā)現(xiàn)，我國(guó)現(xiàn)階段物流配送的發(fā)展依舊十分落后，只配不送的尷尬現(xiàn)狀造成物流配送中出現(xiàn)低效率、高成本、服務(wù)差等諸多問(wèn)題，這已經(jīng)嚴(yán)重影響到了電子商務(wù)在未來(lái)市場(chǎng)的長(zhǎng)足發(fā)展，要知道，電子商務(wù)在網(wǎng)絡(luò)時(shí)代中占

5、據(jù)著極其重要的經(jīng)濟(jì)地位。高成本、低效率的物流配送使得在網(wǎng)上瞬間完成的電子商務(wù)所節(jié)約的時(shí)間、費(fèi)用已變得毫無(wú)意義。試想一下，用戶花費(fèi)較少的支出買了商品，卻需要在商品配送上另花費(fèi)更多的時(shí)間和金錢，這本身就是一個(gè)不合理的現(xiàn)象。因此該如何實(shí)現(xiàn)高效、迅捷的配送是企業(yè)經(jīng)營(yíng)急需解決的問(wèn)題。鑒于此，研究運(yùn)用科學(xué)方法，合理建立一個(gè)高效率、低成本的物流配送系統(tǒng)來(lái)支持電子商務(wù)在物流業(yè)的發(fā)展己成為當(dāng)務(wù)之急。</p><p>　　1.2 本

6、文研究目的和意義</p><p>　　1.2.1本文研究目的</p><p>　　物流配送網(wǎng)絡(luò)是指物流過(guò)程中相互聯(lián)系的設(shè)施及組織的集合。多種不同的物流節(jié)點(diǎn)和聯(lián)結(jié)各點(diǎn)的線路構(gòu)成了整個(gè)物流網(wǎng)絡(luò)。其中節(jié)點(diǎn)包括倉(cāng)庫(kù)以及配送中心等，按規(guī)定進(jìn)行物流配送運(yùn)營(yíng)的路線和航線則構(gòu)成了物流線路。物流配送路徑優(yōu)化需要解決的根本問(wèn)題就是從生產(chǎn)區(qū)域到消費(fèi)區(qū)域的空間轉(zhuǎn)移過(guò)程中對(duì)實(shí)現(xiàn)物品移動(dòng)(運(yùn)輸)途徑的優(yōu)化。由于配送路

7、徑問(wèn)題求解演算是屬于NP．Hard（非確定性多項(xiàng)式）的問(wèn)題，問(wèn)題往往復(fù)雜性較高。此類問(wèn)題的解決方法有不少，傳統(tǒng)方法包括啟發(fā)式算法和精確算法。實(shí)際解決中采用精確算法確實(shí)可得最優(yōu)解，弊端則是求解時(shí)間會(huì)隨著問(wèn)題規(guī)模的增大而指數(shù)增長(zhǎng)。一旦需要解決的節(jié)點(diǎn)過(guò)多往往需要花費(fèi)很多時(shí)間，因此在大數(shù)據(jù)的問(wèn)題解決中運(yùn)用很少。相比之下，啟發(fā)式算法就要合適的多，它通?？梢愿鶕?jù)問(wèn)題的特性而將其化為多個(gè)小問(wèn)題，以較為直觀的方式來(lái)求解各個(gè)支問(wèn)題。這是該方法的優(yōu)勢(shì)所在。

8、可是以往的研究成果表明，盡管運(yùn)用啟發(fā)式算法可以針對(duì)VRP（車輛路線問(wèn)題）問(wèn)題獲得比較滿意的解，但是同樣的，當(dāng)問(wèn)題規(guī)模變大時(shí)，最優(yōu)解的產(chǎn)生往往會(huì)超出計(jì)劃計(jì)算時(shí)間，收斂速度極其緩慢，甚至算法會(huì)直接進(jìn)入停滯狀態(tài)。</p><p>　　因此，本文研究的目的是：</p><p>　　1、通過(guò)對(duì)各種智能算法的介紹比較，找出它們的區(qū)別和優(yōu)缺點(diǎn)，以及實(shí)際應(yīng)用中的可行度，討論出較為合適的算法。在此基礎(chǔ)上引出

9、蟻群算法，將會(huì)重點(diǎn)闡述該算法的可行性和實(shí)用性，并作出改進(jìn)，使得算法能有在全局搜索和收斂速度上更具優(yōu)勢(shì)。</p><p>　　2、在以往研究的基礎(chǔ)上，建立適合實(shí)際物流配送網(wǎng)絡(luò)路徑優(yōu)化的模型，并選擇使用有效的算法，為物流配送網(wǎng)絡(luò)路徑優(yōu)化問(wèn)題的研究和實(shí)踐提供理論依據(jù)和實(shí)際方法。</p><p>　　3、根據(jù)論文選題要求，結(jié)合論文中選擇的優(yōu)化算法，開(kāi)發(fā)出物流配送路徑優(yōu)化系統(tǒng)，要求該系統(tǒng)要嚴(yán)格遵守選

10、題要求，可適當(dāng)做出改進(jìn)和拓展，作為論文的實(shí)踐研究。</p><p>　　本論文最終要求開(kāi)發(fā)出滿足實(shí)際應(yīng)用的軟件，能夠在windows系統(tǒng)上運(yùn)行，隨機(jī)數(shù)據(jù)生成后（位置坐標(biāo)），可以在符合約束條件的情況下，付出較小代價(jià)給出合理的路徑優(yōu)化解——時(shí)間最短路徑、距離最短路徑。該解可允許有誤差，但誤差必須在可以接受的范圍內(nèi)。</p><p>　　1.2.2本文研究的意義</p><p

11、>　　根據(jù)Ronald H．Ballo的觀點(diǎn)，運(yùn)輸決策包括四種：運(yùn)輸方式的選擇、對(duì)運(yùn)輸路線的規(guī)劃、車輛調(diào)度以及集中運(yùn)輸?shù)?。運(yùn)輸成本降低的重點(diǎn)在于對(duì)運(yùn)輸路徑進(jìn)行合理規(guī)劃，即優(yōu)化運(yùn)輸路徑。這就需要考慮到時(shí)間、財(cái)務(wù)、環(huán)境三方面的因素，即時(shí)間上的準(zhǔn)時(shí)性以及快速響應(yīng)；財(cái)務(wù)上則是各種運(yùn)輸費(fèi)用的節(jié)省；環(huán)境上要考慮行駛時(shí)間、交通問(wèn)題以及各種環(huán)境污染問(wèn)題。這些問(wèn)題往往可以通過(guò)改進(jìn)運(yùn)輸方式、優(yōu)化線路規(guī)劃等加以改善。其中，運(yùn)輸問(wèn)題不屬于本文探討的范圍。

12、而運(yùn)輸?shù)木€路規(guī)劃主要是利用各種技術(shù)以最低的運(yùn)營(yíng)成本、最快捷的響應(yīng)速度、最短的配送運(yùn)輸時(shí)間，把貨物運(yùn)至用戶手中，達(dá)到節(jié)約費(fèi)用和節(jié)省客戶時(shí)間雙贏的目的。實(shí)際中的物流配送尤其是從事城市配送的汽車貨運(yùn)工作往往需要考慮的問(wèn)題更復(fù)雜，比如貨運(yùn)節(jié)點(diǎn)的多寡、物品種類是否繁雜、當(dāng)?shù)亟煌ňW(wǎng)絡(luò)是否暢通等等，甚至運(yùn)輸服務(wù)地區(qū)內(nèi)運(yùn)輸網(wǎng)點(diǎn)分布不均勻都會(huì)直接影響配送工作的進(jìn)行。因此，實(shí)際應(yīng)用中需要考慮的是如何設(shè)計(jì)合理、高效的配送方案以及減少車輛數(shù)量和配送里程數(shù)。高效

13、率的物流中心配送作業(yè)具體而言就是：從配送中心使用多輛車向多個(gè)目的地送貨，假設(shè)每個(gè)需求點(diǎn)的位置和供量確定，車輛載重一定，需要解決的就是</p><p>　　1.3本論文的主要工作</p><p>　　物流配送路徑優(yōu)化問(wèn)題簡(jiǎn)稱VRP，本論文將重點(diǎn)就城市車輛路徑優(yōu)化問(wèn)題作為研究對(duì)象，針對(duì)目前路徑優(yōu)化研究的復(fù)雜性以及各類算法的使用，著重以蟻群算法為主要算法，在蟻群算法基礎(chǔ)上結(jié)合最大最小蟻群算法對(duì)其

14、進(jìn)行改進(jìn)，從而是整個(gè)系統(tǒng)的尋優(yōu)速度更快、結(jié)果更準(zhǔn)確。</p><p>　　本論文的研究工作主要包括：</p><p>　　第一章緒論部分主要以論文研究背景和目的方面為主，闡述了由國(guó)內(nèi)國(guó)際實(shí)際物流發(fā)展而產(chǎn)生的問(wèn)題，引出本論文研究的必要性和重要性。</p><p>　　第二章會(huì)就路徑優(yōu)化研究的國(guó)內(nèi)外現(xiàn)狀為例展開(kāi)分析，指出現(xiàn)階段路徑優(yōu)化問(wèn)題的主要研究方法，由此引出下章針對(duì)

15、這些研究方法的詳細(xì)討論。</p><p>　　第三章是幾種智能優(yōu)化算法的簡(jiǎn)單介紹，主要包括禁忌搜索算法、遺傳算法、模擬退火算法、粒子群優(yōu)化算法和人工神經(jīng)網(wǎng)絡(luò)算法。針對(duì)五中算法的基本思路、優(yōu)缺點(diǎn)、以及實(shí)際應(yīng)用中產(chǎn)生的問(wèn)題與思考。</p><p>　　第四章基于蟻群算法—系統(tǒng)開(kāi)發(fā)基本思想，主要對(duì)研究的數(shù)學(xué)模型、約束條件以及基本蟻群算法的的原理、實(shí)現(xiàn)方式展開(kāi)論述。</p><

16、p>　　第五章主要是針對(duì)基本蟻群算法，結(jié)合最大最小蟻群算法進(jìn)行改進(jìn)，提高算法的收斂速度，以及全局搜索能力。后面也會(huì)給出蟻群算法的其他改進(jìn)方式，以減少最優(yōu)解的誤差。</p><p>　　第六章屬于對(duì)路徑優(yōu)化系統(tǒng)的描述，主要有總體設(shè)計(jì)、功能要求以及界面的相關(guān)方面。此章的所述以及最后的軟件部分都將作為論文的實(shí)物支持。</p><p>　　最后一章是對(duì)本論文的總結(jié)和展望，重點(diǎn)對(duì)本論文中的優(yōu)點(diǎn)

17、和功能做出總結(jié)，同時(shí)就論文的不足結(jié)合現(xiàn)實(shí)技術(shù)做出進(jìn)一步的展望。</p><p>　　第二章 路徑優(yōu)化研究現(xiàn)狀與分析</p><p><b>　　2.1研究現(xiàn)狀</b></p><p>　　物流配送路徑規(guī)劃問(wèn)題的研究現(xiàn)狀：車輛優(yōu)化調(diào)度問(wèn)題及物流配送路徑選擇是整個(gè)物流配送體系優(yōu)化中很重要的環(huán)節(jié)，也是電子商務(wù)活動(dòng)不可或缺的內(nèi)容。由于這一問(wèn)題的理論涉

18、及多學(xué)科，而且應(yīng)用前景可觀，所以很快引起了應(yīng)用數(shù)學(xué)、物流學(xué)、運(yùn)籌學(xué)、計(jì)算機(jī)應(yīng)用圖論與網(wǎng)絡(luò)分析、交通運(yùn)輸工程、管理科學(xué)與工程等學(xué)科的專家、工程技術(shù)人員的極大關(guān)注。因此一度成為組合優(yōu)化領(lǐng)域和運(yùn)籌學(xué)的前沿研究熱點(diǎn)，各學(xué)科專家針對(duì)此類問(wèn)題進(jìn)行了大量的學(xué)術(shù)探討和試驗(yàn)分析，并取得了很大進(jìn)展。近二十年來(lái)國(guó)內(nèi)外對(duì)物流配送路徑優(yōu)化問(wèn)題的研究給予了極大的關(guān)注。</p><p>　　隨著市場(chǎng)經(jīng)濟(jì)的進(jìn)步和物流技術(shù)專業(yè)化水平的不斷提高，物

19、流配送業(yè)得到了快速發(fā)展。配送路徑的選擇是否合理，直接決定了配送速度是否迅捷、服務(wù)質(zhì)量能否有所提高、配送成本能否減少以及整個(gè)經(jīng)濟(jì)塊的利益能否最大化。配送路徑的優(yōu)化問(wèn)題是物流配送體系的一個(gè)重要問(wèn)題，物流配送路徑的優(yōu)化根本在于以最短的配送運(yùn)輸時(shí)間、最低的運(yùn)輸成本、最迅速的響應(yīng)把貨物運(yùn)至客戶手中，最短時(shí)間和最快速度兩者本身與最低運(yùn)輸成本相制約，嚴(yán)格地來(lái)說(shuō)這一個(gè)多目標(biāo)的優(yōu)化問(wèn)題。</p><p><b>　　2.

20、2研究方法</b></p><p>　　路徑優(yōu)化的方法很多，常用的有分區(qū)配送算法、旅行商法、掃描法、動(dòng)態(tài)規(guī)劃法、節(jié)約法等。但這些方法往往存在各種問(wèn)題，例如節(jié)約法很難做到組合點(diǎn)整齊、組合邊緣點(diǎn)的問(wèn)題，且掃描法無(wú)法做到漸進(jìn)優(yōu)化等。如何針對(duì)物流配送路徑優(yōu)化問(wèn)題的特點(diǎn)，建立運(yùn)算復(fù)雜度低、尋優(yōu)性能優(yōu)良的啟發(fā)式算法，也是很多人深入研究的課題。近年來(lái)流行的遺傳算法、禁忌搜索算法等都在這方面取得了不同的成就。但根本性

21、問(wèn)題依舊存在，例如在搜索能力上遺傳算法局部搜索能力很弱，總體上可行解的質(zhì)量也不高，禁忌搜索算法如果沒(méi)有一個(gè)比較合適的初始解其可行性也很低。諸如此類。</p><p>　　第三章 各種智能優(yōu)化算法介紹</p><p>　　3.1 智能優(yōu)化算法</p><p>　　常見(jiàn)的用于解決路徑優(yōu)化問(wèn)題的方法有不少，例如遺傳算法、禁忌搜索算法、模擬退火算法、粒子群優(yōu)化算法等，但往往

22、方法各有不足。蟻群算法的優(yōu)勢(shì)在于它利用并行計(jì)算機(jī)制，可以很好的與其他算法結(jié)合，魯棒性特點(diǎn)尤為突出。本章將會(huì)對(duì)智能優(yōu)化算法做簡(jiǎn)單介紹。為下一章會(huì)針對(duì)蟻群算法概念、算法思想、優(yōu)化步驟和相關(guān)數(shù)學(xué)模型等的進(jìn)一步詳解做鋪墊。</p><p>　　3.1.1禁忌搜索算法 </p><p>　　1986年，由Glover提出的禁忌搜索算法（tabu search，TS）經(jīng)過(guò)后來(lái)學(xué)者的不斷完善，形成了一

23、種比較完整的優(yōu)化算法。禁忌搜索算法的基本工作原理是利用記憶存儲(chǔ)，并對(duì)其系統(tǒng)化使用，從而使搜索過(guò)稱順利進(jìn)行下去。記憶存儲(chǔ)包括短期和長(zhǎng)期記憶存儲(chǔ)。長(zhǎng)期記憶存儲(chǔ)通過(guò)引用其他解進(jìn)行鄰域擴(kuò)充；短期記憶存儲(chǔ)則不同，它是將當(dāng)前解的鄰域限制到一個(gè)子集中來(lái)，子集含于這個(gè)鄰域。</p><p>　　禁忌搜索的過(guò)程實(shí)際上就是一個(gè)局部搜索過(guò)程，將所有的局部最優(yōu)解用一張禁忌表記錄，然后在一周的搜索中，從這些最優(yōu)解中選擇或禁止。出于對(duì)防止算

24、法可能返回重復(fù)解的考慮，TS可以將近期訪問(wèn)過(guò)的最優(yōu)解進(jìn)行顯式保存或者直接禁止這些解。但這就造成了算法很難向著那些未訪問(wèn)過(guò)的解移動(dòng)。為防止這種情況出現(xiàn)，TS提出了新概念“渴望標(biāo)準(zhǔn)”來(lái)覆蓋某些移動(dòng)的禁忌狀態(tài)，使得算法向比目前最優(yōu)解更優(yōu)的解移動(dòng)。</p><p>　　實(shí)際應(yīng)用中，搜索過(guò)程的短期記憶是TS運(yùn)用最廣的特征，稱為“簡(jiǎn)單禁忌搜索”。</p><p>　　3.1.2 模擬退火算法</

25、p><p>　　模擬退火算法的出現(xiàn)最早是由Metropolis在1953年提出的，嚴(yán)格意義上來(lái)說(shuō)，屬于局部算法的延伸，1983年，該算法成功的應(yīng)用于組合優(yōu)化問(wèn)題，尤其在NP-head問(wèn)題中運(yùn)用更多。模擬退化算法的基本原理是基于一般優(yōu)化問(wèn)題與物理中的物質(zhì)退火的相似性，即溫度上升到一定程度的自由運(yùn)動(dòng)粒子，隨著溫度的下降（下降速度保持足夠慢），那么最終整個(gè)系統(tǒng)將會(huì)達(dá)到其自身最低狀態(tài)，稱為基態(tài)狀態(tài)。此時(shí)的基態(tài)可視為函數(shù)的全局

26、最小點(diǎn)。組合問(wèn)題的優(yōu)化過(guò)程類似于此，它的迭代過(guò)程分為三個(gè)步驟——生成新解、判斷該解、是否接受/放棄，并且迭代過(guò)程中遵循隨機(jī)接受準(zhǔn)則，這個(gè)準(zhǔn)則將會(huì)接受所有惡化解，使得得到惡化解的概率降低并無(wú)限接近零，最大程度上使得退火算法跳出局部極值，最終找出最優(yōu)解。</p><p>　　遵循上述準(zhǔn)則的模擬退火算法已經(jīng)脫離了局部搜索算法范疇，成為了一種全局尋找最優(yōu)解算法。此算法的優(yōu)勢(shì)在于，中間解可以一定程度上脫離局部極小點(diǎn)，最終在

27、退火溫度下找到最優(yōu)解。</p><p><b>　　3.1.3遺傳算法</b></p><p>　　遺傳算法是最初是由美國(guó)Michigan大學(xué)的J.Holland教授在1975年提出的，其基本思想是將自然界優(yōu)勝劣汰的自然法則與組合優(yōu)化及其他機(jī)器學(xué)習(xí)等問(wèn)題結(jié)合。六十年代時(shí)這個(gè)算法還處于萌芽狀態(tài)，算法相對(duì)簡(jiǎn)單的多；直到七十年代遺傳算法得到了發(fā)展探索，當(dāng)時(shí)的算法主要用于解決

28、兩類問(wèn)題：（1）建立出一種尋找特定問(wèn)題解的系統(tǒng)；(2)理解如何求解這些問(wèn)題的過(guò)程。發(fā)展到九十年代，遺傳算法的研究運(yùn)用在各方面得到深入。</p><p>　　遺傳算法的原理是基于初始種群的，即在當(dāng)前種群中使用選擇策略選擇個(gè)體，其中該策略的標(biāo)準(zhǔn)是針對(duì)與適應(yīng)值比例的，隨著一代代的雜交和變異，直到最終的期待條件出現(xiàn)為止。對(duì)于旅行商問(wèn)題（TSP），遺傳算法中的雜交方式一般是將染色體標(biāo)記為序列，其中包含所有需求點(diǎn)。這種方式的

29、缺點(diǎn)在于方向的不確定性，最終產(chǎn)生的結(jié)果無(wú)法保證是有意義的。所以需要保證旅行商問(wèn)題雜交算子編碼的有效性。</p><p>　　遺傳算法的主要步驟為：（1）編碼；（2）生成初始群體；（3）檢測(cè)與評(píng)估適應(yīng)值；（4）選擇使用/放棄；（5）交換，即信息交換；（6）變異。變異是新個(gè)體產(chǎn)生的主要方式。</p><p>　　3.1.4 粒子群優(yōu)化算法</p><p>　　粒子群優(yōu)化

30、算法（PSO）是由兩位美國(guó)博士Kennedy（社會(huì)心理學(xué)博士）和Eleberhart（電子工程學(xué)博士）在觀察鳥(niǎo)類覓食過(guò)程中收到啟發(fā)而提出的。例子群優(yōu)化算法同樣是起源于生物社會(huì)系統(tǒng)的模擬。最開(kāi)始的設(shè)想是基于單個(gè)個(gè)體組成的群體與環(huán)境和個(gè)體之間的反饋行為。</p><p>　　與其他算法相似之處在于粒子群優(yōu)化算法同樣是關(guān)于群體的迭代關(guān)系的算法，而不同之處則在于該算法并沒(méi)有設(shè)定交叉、復(fù)制和變異等算子，而是將群體中的個(gè)體微

31、化成無(wú)質(zhì)量無(wú)體積的粒子。值得注意的是，例子算法是一種共生合作的算法。</p><p>　　粒子群算法之所以會(huì)受到各界不同程度的關(guān)注，最重要在于針對(duì)復(fù)雜非線性問(wèn)題，該算法具有比較強(qiáng)的尋優(yōu)能力，且簡(jiǎn)單通用，魯棒性強(qiáng)。在函數(shù)優(yōu)化領(lǐng)域以及車間調(diào)度方面粒子群算法都用應(yīng)用</p><p>　　然而粒子群算法并不是完美的一種算法，它的缺點(diǎn)也是顯而易見(jiàn)，例如該算法的高搜索能力是建立在參數(shù)的合理程度之上的，

32、也就是說(shuō)，沒(méi)有一個(gè)合理的參數(shù)選擇，該算法的搜索性能很低；其次它的局部搜索能力同樣不高，搜索精度很低，這就導(dǎo)致了算法無(wú)法最終尋得全局最優(yōu)解。</p><p>　　3.1.5 神經(jīng)網(wǎng)絡(luò)算法</p><p>　　神經(jīng)網(wǎng)絡(luò)算法（ANN）起源已經(jīng)很難考證了，其基本原理是模擬生物神經(jīng)系統(tǒng)的一種人工智能的簡(jiǎn)化，系統(tǒng)主要由三部分組成：系統(tǒng)功能、組織結(jié)構(gòu)和處理方式。應(yīng)用優(yōu)點(diǎn)在于它可以獲得全局最優(yōu)解，相應(yīng)的算

33、法無(wú)法避免局部極小問(wèn)題，收斂對(duì)初值敏感以及收斂速度慢等問(wèn)題。</p><p>　　第四章 基于蟻群算法—系統(tǒng)開(kāi)發(fā)基本思想</p><p>　　4.1物流配送的問(wèn)題描述</p><p>　　一般配送路徑問(wèn)題可描述如下：</p><p>　　已知條件：需求點(diǎn)（客戶）數(shù)量為L(zhǎng)；</p><p><b>　　需求點(diǎn)數(shù)

34、量和坐標(biāo)；</b></p><p>　　預(yù)計(jì)可出現(xiàn)故障的路段；</p><p>　　要求： a：系統(tǒng)可根據(jù)使用者選擇的路徑規(guī)劃策略，如路徑最短、時(shí)間最少等方式進(jìn)行配送路線規(guī)劃</p><p>　　b：模擬車輛由倉(cāng)庫(kù)出發(fā)，沿著規(guī)劃的配送路線行進(jìn)，最后返回倉(cāng)庫(kù)</p><p>　　c：在配送過(guò)程中可模擬前方行進(jìn)路線堵車事件，系統(tǒng)能夠繞

35、開(kāi)堵車路段動(dòng)態(tài)規(guī)劃配送路線</p><p>　　d：需要滿足的幾個(gè)約束條件：</p><p>　　1) 每條線路上的客戶點(diǎn)需求量之和不超過(guò)汽車載重量；</p><p>　　2) 每條配送路徑的總長(zhǎng)度不超過(guò)汽車一次配送的最大行駛距離；</p><p>　　3) 每個(gè)客戶點(diǎn)的需求必須且只能由一輛汽車來(lái)完成。</p><p>

36、;　　4.2數(shù)學(xué)模型的建立</p><p><b>　　符號(hào)的定義</b></p><p><b>　　L：需求點(diǎn)總數(shù)；</b></p><p>　　qi：需求點(diǎn)i的貨物需求量，其中i=1，2，…，L；</p><p>　　dij：從需求點(diǎn)i到需求點(diǎn)j的距離。注：當(dāng)i=j=0時(shí)，表示起始地， K：車

37、輛數(shù)量</p><p>　　Qk：車輛k的最大載重，其中k=1，2，…，K</p><p>　　Dk：車輛k的最長(zhǎng)行駛距離，其中k=1，2，…，K</p><p>　　nk：車輛k需要配送的需求點(diǎn)總數(shù)，nk=0時(shí)，表示該車沒(méi)有進(jìn)入線路。k=1，2，…，K</p><p>　　Rk：車輛k配送的需求點(diǎn)的集合。當(dāng)nk=0時(shí)，Rk=Φ；當(dāng)nk≠0時(shí)

38、，</p><p><b>　　4.3約束條件</b></p><p>　　根據(jù)前文對(duì)路徑優(yōu)化的描述，需要注意的約束條件如下：</p><p>　　1)線路上的需求點(diǎn)需求量之和不可以超過(guò)汽車載重量：</p><p><b>　　，nk≠0</b></p><p>　　2)每條

39、路徑的總長(zhǎng)度不超過(guò)汽車一次配送的最大行駛距離：</p><p><b>　　， nk≠0</b></p><p>　　3) 每個(gè)需求點(diǎn)的需每次有且只能由一輛汽車來(lái)完成：</p><p><b>　　，k1≠k2</b></p><p>　　4) 配送路徑遍歷所有需求點(diǎn)：</p><

40、;p><b>　　4.4優(yōu)化目標(biāo)</b></p><p>　　根據(jù)需優(yōu)化目標(biāo)，列出所要優(yōu)化目標(biāo)的數(shù)學(xué)形式：</p><p>　　4.5優(yōu)化配送路線的蟻群算法</p><p><b>　　4.5.1基本思想</b></p><p>　　蟻群算法的出現(xiàn)是根據(jù)自然界生物中螞蟻的覓食行為啟發(fā)而產(chǎn)生的“

41、自然”算法。蟻群算法的最顯著的特點(diǎn)在于蟻群中的螞蟻是以“信息素”（pheromone）為介質(zhì)的間接異步聯(lián)系方式。螞蟻的行為（尋找食物或者尋找回巢的路徑），會(huì)在其走過(guò)的途中釋放一些化學(xué)物質(zhì)（即我們所說(shuō)的“信息”）。同一蟻群會(huì)發(fā)現(xiàn)這些信息素，信息素作為一種特有信號(hào)影響蟻群的行動(dòng)（具體表現(xiàn)為后者選擇走這些具有“信息”的路徑的可能性要大于選擇其他路徑的可能性），而后到者會(huì)繼續(xù)在該“信息素”基礎(chǔ)上進(jìn)行加強(qiáng)，如此往復(fù)循環(huán)。這樣，該路徑走過(guò)的螞蟻越來(lái)

42、越多，“信息素”也越來(lái)越多，后來(lái)者選擇此路徑的可能性也更大（因?yàn)闅埩舻男畔舛容^大的緣故）。這樣，在單位時(shí)間內(nèi)此路徑持續(xù)被更多的螞蟻選擇訪問(wèn)，信息素積累增多，直到最后，幾乎所有的螞蟻都選擇這條最短的路徑。</p><p>　　4.5.2 算法實(shí)現(xiàn)</p><p>　　我們用人工螞蟻代替車輛對(duì)需求點(diǎn)點(diǎn)進(jìn)行“配送”，螞蟻在i需求點(diǎn)選擇的下一個(gè)需求點(diǎn)j時(shí)，主要考慮兩方面因素，一是i，j兩需求點(diǎn)之

43、間關(guān)系的親密程度（即可見(jiàn)度），記為ij；另一點(diǎn)則需要考慮由目前的循環(huán)所得路徑優(yōu)化方案體現(xiàn)出來(lái)的由i到j(luò)的可行性（即信息素濃度），記為ij。在算法的初始時(shí)刻，將m只螞蟻隨機(jī)地放到 n 座城市，同時(shí)，將每只螞蟻的禁忌表的第一個(gè)元素設(shè)置為它當(dāng)前所在的城市。此時(shí)各路徑上的信息素量相等，設(shè)τij(0) = C（C 為一較小的常數(shù)）在t時(shí)刻螞蟻k由需求點(diǎn)i轉(zhuǎn)移到需求點(diǎn)j的概率：</p><p><b>　　（2.1

44、）</b></p><p>　　其中，Jk(i)= {1，2，……，n}- tabuk表示螞蟻 k 下一步允許選擇的城市集合。螞蟻 k 當(dāng)前走過(guò)的城市都記錄在列表tabuk。當(dāng)每一座城市都加入到tabuk中時(shí)，螞蟻 k 便完成了一次循環(huán)，此時(shí)螞蟻 k 所走過(guò)的路徑便是 TSP（旅行家問(wèn)題） 的一個(gè)可行解。(2. 1)式中的ηij 表示一個(gè)啟發(fā)式因子，代表螞蟻從需求點(diǎn)i 轉(zhuǎn)移到需求點(diǎn) j 的期望程度。在

45、 AS 算法中，ηij 通常取需求點(diǎn) i 與需求點(diǎn)j 之間距離的倒數(shù)。α和β分別表示信息素和啟發(fā)式因子的相對(duì)重要程度。當(dāng)所有螞蟻完成一次循環(huán)后，信息素根據(jù)式（2. 2）更新。</p><p><b>　　(2. 2)</b></p><p><b>　　(2. 3)</b></p><p>　　其中ρ(0 < ρ &

46、lt;1)是路徑上信息素的蒸發(fā)系數(shù)，1-ρ 表示信息素的持久性系數(shù)；△τij表示本次迭代邊 ij 上信息素的增量。△τkij表示第 k 只螞蟻在本次迭代中留在邊ij 上的信息素量。如果螞蟻 k 沒(méi)有經(jīng)過(guò)邊 ij，則△τkij的值為零?！鳓觡ij表示為：</p><p><b>　　(2. 4)</b></p><p>　　其中，Q 為正常數(shù)，Lk 表示第 k 只螞蟻在

47、本次周游中所走過(guò)路徑的長(zhǎng)度。</p><p>　　M. Dorigo 提出了 3 種 AS 算法的模型 ，式(2.4)稱為 ant-cycle，另外兩個(gè)模型分別稱為 ant-quantity 和 ant-density，其差別主要在 (2. 4) 式，即：在 ant-quantity 模型中為：</p><p><b>　　(2. 5)</b></p>

48、<p>　　在 ant-density 模型中為：</p><p><b>　　(2. 6)</b></p><p>　　AS算法實(shí)際上是正反饋原理和啟發(fā)式算法相結(jié)合的一種算法。在選擇路徑時(shí)，螞蟻不僅利用了路徑上的信息素，而且用到了城市間距離的倒數(shù)作為啟發(fā)式因子。</p><p>　　AS 算法的時(shí)間復(fù)雜度為Ο(NC*n2*m) &l

49、t;/p><p>　　算法的空間復(fù)雜度為S(n)=O(n2)+O(n*m) ，其中 NC 表示迭代的次數(shù)，n 為城市數(shù)，m為螞蟻的數(shù)目。</p><p>　　4.6TSP問(wèn)題概述</p><p>　　TSP問(wèn)題是旅行商問(wèn)題的簡(jiǎn)稱，簡(jiǎn)而言之，說(shuō)的是從前有一個(gè)商人，要從自己家開(kāi)始出發(fā)，途徑一些要求必須經(jīng)過(guò)的城市，最后回到家鄉(xiāng)，而且經(jīng)過(guò)的城市不能有所重復(fù)。旅行商要做的就是找到

50、一條最短路徑達(dá)到目的地。該問(wèn)題在圖論下又叫做哈密頓圈問(wèn)題，最早是由一個(gè)叫Euler研究出其雛形。</p><p>　　4.7基于蟻群算法求解旅行商問(wèn)題（TSP）的基本流程</p><p>　　作為一個(gè)經(jīng)典的路徑尋優(yōu)問(wèn)題，TSP問(wèn)題的理解并不難，但事實(shí)上至今也沒(méi)有準(zhǔn)確地答案。我們用一個(gè)帶權(quán)完全圖G=（N,A）來(lái)闡述，N是所有目標(biāo)城市點(diǎn)的集合，A是所有邊（路徑模型）的集合。首先對(duì)螞蟻數(shù)量、信息

51、素等進(jìn)行初始化，同時(shí)將迭代次數(shù)初始化為零。禁忌表是為了記錄遍歷城市的一個(gè)表，算法開(kāi)始前其值為零，表示未訪問(wèn)任何城市。隨著算法的進(jìn)行，螞蟻會(huì)選擇城市出發(fā)并留下信息素，此時(shí)禁忌表值發(fā)生改變，同時(shí)信息素也會(huì)更新，當(dāng)超出最大迭代次數(shù)時(shí)，程序?qū)?huì)終止，否則迭代繼續(xù)，直至滿足條件。</p><p><b>　　具體流程如下：</b></p><p>　　設(shè)帶權(quán)圖G=（N，A），N

52、=（1，2，3，4，5…,n）表示城市的結(jié)點(diǎn)集合，各點(diǎn)的坐標(biāo)信息和距離dij已知。設(shè)</p><p>　　Xij=1(當(dāng)（i,j）在最優(yōu)回路上時(shí))；</p><p>　　Xij=0（其他條件時(shí)）</p><p>　　因此可得旅行商問(wèn)題的數(shù)學(xué)模型如下：</p><p><b>　　????????</b></p>

53、;<p>　　這里我們規(guī)定丨S丨表示s中G的所有頂點(diǎn)數(shù)量。上述約束條件中，a、b兩個(gè)約束條件的作用就是限制每個(gè)點(diǎn)僅有一條邊進(jìn)和一條邊出；而約束條件c則保證搜索過(guò)程中不會(huì)出現(xiàn)回路解。滿足上述三個(gè)條件的所有解的回路就是哈密頓回路。同時(shí)出現(xiàn)新概念—對(duì)稱型TSP，即滿足條件dij=dji。</p><p>　　總結(jié)其數(shù)學(xué)模型下TSP問(wèn)題的步驟為：</p><p><b>　

54、　Begin</b></p><p><b>　　對(duì)蟻群初始化</b></p><p><b>　　Loop</b></p><p><b>　　構(gòu)造螞蟻路徑；</b></p><p>　　對(duì)某一個(gè)螞蟻進(jìn)行局部搜索法；</p><p><

55、;b>　　信息素更新；</b></p><p>　　未達(dá)到迭代次數(shù)，繼續(xù)轉(zhuǎn)loop；</p><p><b>　　找到最優(yōu)解并輸出；</b></p><p><b>　　End</b></p><p>　　從TSP問(wèn)題的數(shù)學(xué)模型可以看出，需要特別注意兩個(gè)步驟：構(gòu)造螞蟻路徑以及信息素

56、更新。蟻群算法之所以優(yōu)于其他算法，是因?yàn)槊恳淮蔚?，信息素的期望值往往?huì)低于其初始值，其計(jì)算公式如下：</p><p>　　式中，m表示螞蟻數(shù)量，Cnm代表路徑長(zhǎng)度。選擇該初始值的初衷是因?yàn)椋坏┬畔⑺爻跏贾颠^(guò)小，搜索區(qū)域往往受到限制，大多搜索會(huì)過(guò)于集中在初始有限的路徑中，即我們所說(shuō)的陷入局部搜索中，很難找到最優(yōu)解。相反地，如果讓信息素的初始值過(guò)大，就會(huì)無(wú)法發(fā)揮蟻群算法初始的多次迭代優(yōu)勢(shì)，這種效果會(huì)一直持續(xù)到信

57、息素蒸發(fā)到很小的程度，此時(shí)更新的信息素才會(huì)指引搜索偏向性。</p><p>　　我們從構(gòu)建路徑個(gè)信息素更新兩方面剖析該問(wèn)題：</p><p><b>　　1、構(gòu)建路徑</b></p><p>　　在蟻群算法中，我們?cè)O(shè)初始有m只螞蟻參與TSP路徑的構(gòu)建。將所有螞蟻隨機(jī)的選中的需求點(diǎn)中。在構(gòu)建路徑過(guò)程的每一步中，螞蟻會(huì)在規(guī)則概論下選擇其下個(gè)訪問(wèn)需求

58、點(diǎn)，其選擇概論如下：</p><p>　　上式中，是一個(gè)初始的啟發(fā)式信息，α和β在前幾章解釋過(guò)，前者主要是影響信息素的產(chǎn)生，后者為啟發(fā)式信息的重要參數(shù)，allowedk表示螞蟻們未訪問(wèn)過(guò)的需求點(diǎn)，換而言之，就是螞蟻下一個(gè)需要到達(dá)的點(diǎn)。我們分別對(duì)α和β取零值，可以發(fā)現(xiàn)，當(dāng)α為0時(shí)，此時(shí)會(huì)最大概論選出離i點(diǎn)最近需求點(diǎn)，這滿足貪心算法的定義。而當(dāng)β=0時(shí)，此時(shí)對(duì)于概論P(yáng)來(lái)說(shuō)，能夠改變它的只有信息素的放大系數(shù)，換句話說(shuō)，

59、信息素并沒(méi)有發(fā)揮它該發(fā)揮的作用，即信息素沒(méi)有使用任何啟發(fā)式偏向性。此時(shí)的蟻群算法相對(duì)與其他智能算法沒(méi)有任何優(yōu)勢(shì)可言，甚至不如其他算法，尤其是α大于1時(shí)，AS將會(huì)越來(lái)越緩慢，直至停滯運(yùn)行。此時(shí)的算法依舊會(huì)給出一條路徑，也就是多數(shù)螞蟻選擇的路徑，但其實(shí)已經(jīng)沒(méi)有任何研究的意義了，此路徑甚至算不上一個(gè)可行解。</p><p>　　在前幾章我們針對(duì)幾種智能算法做介紹的時(shí)候，提到過(guò)記憶儲(chǔ)存這個(gè)概念，其包括短期儲(chǔ)存和長(zhǎng)期儲(chǔ)存，

60、事實(shí)上，在蟻群算法中，同樣有記憶儲(chǔ)存的概念。我們用Mk來(lái)表示螞蟻們共同維護(hù)的這個(gè)記憶儲(chǔ)存，類似與禁忌表，記憶儲(chǔ)存里面會(huì)給出已經(jīng)被訪問(wèn)過(guò)的需求點(diǎn)集合，并且這些需求點(diǎn)都是嚴(yán)格按照先后順序被存儲(chǔ)。可以發(fā)現(xiàn)，無(wú)論是Mk，還是Nik，都與訪問(wèn)路徑有關(guān)，事實(shí)上后者往往需要以前者M(jìn)k給出的構(gòu)造規(guī)則來(lái)定義概論P(yáng)。。除此之外，在計(jì)算構(gòu)造路徑Tk的總長(zhǎng)度時(shí)，同樣要使用到記憶存儲(chǔ)。</p><p>　　我們用兩種方式可以實(shí)現(xiàn)可行解的構(gòu)

61、建：第一種是并行構(gòu)建，也就是說(shuō)每一只螞蟻都可以隨時(shí)從當(dāng)前需求點(diǎn)出發(fā)向下個(gè)需求點(diǎn)；與之相反的一種方式稱為順序構(gòu)建，我們可以理解為單線程的構(gòu)建，即只有當(dāng)一直螞蟻完成從所在點(diǎn)向下一個(gè)點(diǎn)構(gòu)建完整路徑后，第二只螞蟻才被允許開(kāi)始它的構(gòu)建。兩種方式?jīng)]有特別明確的界限，二者從根本上并沒(méi)有改變蟻群算法的特征。</p><p><b>　　2、信息素的更新</b></p><p>　　信

62、息素的更新會(huì)在全部的螞蟻將路徑構(gòu)建好之后完成。起初，路徑上的信息素會(huì)按照一個(gè)常量減少，也就是信息素蒸發(fā)。當(dāng)減少到某個(gè)值時(shí)，此時(shí)到達(dá)的螞蟻會(huì)重新在走過(guò)的路徑上釋放信息素。信息素的蒸發(fā)滿足下式：</p><p>　　式中，ρ表示信息素蒸發(fā)率，其取值范圍為ρ（0,1]。該參數(shù)的重要性在于可以抑制信息素的無(wú)限積累，而且也可以使算法舍棄已選擇過(guò)的差解。蟻群算法最重要的特點(diǎn)在于螞蟻迭代每一條路徑時(shí)釋放信息素，后面的螞蟻又根據(jù)

63、信息素繼續(xù)選擇該路徑，繼而再次釋放信息素，如此往復(fù)直到所有的螞蟻都選擇信息素最大的那條，也就是我們需要的最優(yōu)路徑。所有螞蟻在其選擇的路徑上釋放信息素為：</p><p>　　根據(jù)上式不難總結(jié)出，在迭代次數(shù)允許的范圍內(nèi)，該路徑的構(gòu)建閱合適，信息素的釋放也越多。</p><p>　　在后一章有關(guān)蟻群算法的改進(jìn)會(huì)提到有關(guān)選取合適參數(shù)以減少可行解誤差的論述，此處給出基本ACO的相關(guān)合理參數(shù)：α=1

64、，β（2，5），ρ=0.5。</p><p>　　4.8 VRP相關(guān)問(wèn)題論述</p><p>　　物流配送優(yōu)化問(wèn)題的研究中，最常用也是最關(guān)鍵的問(wèn)題是車輛路徑問(wèn)題，簡(jiǎn)稱VRP。該問(wèn)題的研究往往不是單一的只針對(duì)某一個(gè)領(lǐng)域的研究，而是結(jié)合許多相關(guān)學(xué)科前沿和熱點(diǎn)，比如計(jì)算機(jī)科學(xué)，物流科學(xué)，數(shù)學(xué)，運(yùn)籌學(xué)等。</p><p>　　該問(wèn)題的具體論述如下：在滿足某些給定條件（約束

65、條件和需求條件）的前提下，從某一確定原點(diǎn)出發(fā)，目的地為多個(gè)需求點(diǎn)組成的集合，需要解決的是在諸多路徑中找出最優(yōu)的那個(gè)解（時(shí)間最短路徑、距離最短了路徑），滿足條件：</p><p>　　每一個(gè)需求點(diǎn)只允許訪問(wèn)一次；</p><p>　　要求每一輛車從原點(diǎn)出發(fā)，最終也必須回到原點(diǎn)；</p><p>　　根據(jù)實(shí)際情況，某些特殊需求點(diǎn)需要接受限制，即約束條件。</p&g

66、t;<p>　　實(shí)際情況中需要考慮的約束條件如下：</p><p>　　限制容量。客戶的要求或者說(shuō)需求量有大有小，有時(shí)候受到車輛本身的條件所限，是沒(méi)有辦法一次性全部裝載的，也就是說(shuō)，車輛的要求負(fù)重不能大于車輛本身的最大載重。這種限制稱為CVRP。</p><p>　　路長(zhǎng)限制。車輛不可能無(wú)限制的一直跑下去，其行駛總路長(zhǎng)受到油耗和油量的限制，即車輛的行駛路長(zhǎng)需要設(shè)定為一個(gè)合適的

67、常數(shù)。這種針對(duì)行駛路程限制或者說(shuō)時(shí)間的限制稱為DVRP。</p><p>　　時(shí)間窗。需求點(diǎn)不可能在車輛為訪問(wèn)的情況下一直等下去，這就需要給車輛一個(gè)時(shí)間限制。我們稱這種限制為VRPTW。</p><p>　　帶回程取貨。有些需求點(diǎn)會(huì)有無(wú)用貨物產(chǎn)生，需要從該點(diǎn)運(yùn)回原點(diǎn)，此時(shí)就可以搭“順風(fēng)車”，減少成本支出。這種限制稱為VRPB。</p><p>　　時(shí)間窗帶回程取貨。

68、也就是結(jié)合了時(shí)間窗和回程取貨限制，需要將無(wú)用貨物在規(guī)定時(shí)間內(nèi)運(yùn)回原點(diǎn)。這種限制稱為VRPBTW。</p><p>　　再次強(qiáng)調(diào)，本文的研究都是基于CVRP的情況下的討論。</p><p>　　第五章 蟻群算法的改進(jìn)</p><p><b>　　5.1問(wèn)題描述</b></p><p>　　我們將具有容量限制的車輛路徑優(yōu)化問(wèn)

69、題（VRP）稱為CVRP，即車輛所負(fù)重的需求量不得超過(guò)其最大容量。以下我們所要研究的問(wèn)題都將以此為前提進(jìn)行。</p><p>　　蟻群算法中，我們往往會(huì)發(fā)現(xiàn)，隨著越來(lái)越多的螞蟻選擇同一條路徑不斷的進(jìn)行下去，這條路上的信息素將會(huì)急劇升高，更多的信息素吸引更多的螞蟻?zhàn)咴撀窂?，愈演愈烈，直到造成堵塞或者停滯。使用第四章所述的基本蟻群算法解決VRP或者CVRP問(wèn)題會(huì)發(fā)現(xiàn)容易出現(xiàn)收斂速度慢、易陷入局部最優(yōu)的問(wèn)題。這個(gè)時(shí)候通

70、常有兩個(gè)方法解決：1、選擇較為合適的α和β值使得最優(yōu)解的誤差控制在可以接受的范圍內(nèi)；2、結(jié)合其他算法來(lái)改進(jìn)蟻群算法。通常情況下第一種方法無(wú)法直接判定選值是否最合適，本章將著重介紹結(jié)合其他算法改進(jìn)后的蟻群算法，選擇算法為最大最小蟻群算法。</p><p>　　5.2最大最小蟻群算法</p><p>　　本算法是在基本蟻群算法上做了如下幾項(xiàng)改進(jìn)。首先，對(duì)最優(yōu)路徑開(kāi)發(fā)做出強(qiáng)化，具體做法為：只有在

71、路徑優(yōu)化中那只最優(yōu)螞蟻，或者是遍歷需求點(diǎn)過(guò)程中構(gòu)建出最優(yōu)路徑的那只螞蟻，才可以被允許釋放信息素，但問(wèn)題就出現(xiàn)了：這樣會(huì)使信息素單一方面的增多最終導(dǎo)致路徑堵塞，也許有人會(huì)說(shuō)：這樣的路徑不正是好的路徑嗎？因?yàn)橛写罅康奈浵佔(zhàn)?。其?shí)不是，這樣的路徑只能稱作較好的路徑而非最優(yōu)路徑。這個(gè)時(shí)候就有了第二個(gè)改進(jìn)方式：將信息素限定在一個(gè)范圍區(qū)間內(nèi)[Imin，Imax]。其次，對(duì)信息素的初始值進(jìn)行設(shè)定，并將其定為范圍區(qū)間的上限值，同時(shí)與較小的那個(gè)信息素蒸發(fā)

72、速率結(jié)合，原因是這樣可以使算法在開(kāi)始的搜索中向著更多的可能最優(yōu)路徑出發(fā)。最后，當(dāng)出現(xiàn)以下條件：系統(tǒng)信息素增多導(dǎo)致系統(tǒng)堵塞，或者在迭代過(guò)程中不再出現(xiàn)優(yōu)化路徑，此時(shí)將會(huì)對(duì)信息素值初始化。</p><p>　　最大最小蟻群算法的具體改進(jìn)如下：</p><p><b>　?。?）更新信息素</b></p><p>　　當(dāng)螞蟻成功的構(gòu)建完成一條路徑時(shí)，根

73、據(jù)信息素蒸發(fā)規(guī)則，最大最小蟻群算法將更新信息素。新的信息素如下：</p><p>　　其中，。信息素釋放的對(duì)象由至今最優(yōu)的螞蟻進(jìn)行釋放，此時(shí)；或者由當(dāng)前迭代最優(yōu)的螞蟻進(jìn)行釋放，此時(shí)。其中Lib指的是目前最優(yōu)路徑的長(zhǎng)度。</p><p><b>　?。?）限制信息素</b></p><p>　　改進(jìn)后的最大最小蟻群算法中規(guī)定，每一條邊的信息素都在

74、區(qū)間[Imin，Imax]中，這樣可以有效的防止停滯狀態(tài)的發(fā)生。最重要的是這種限制可以使得需求點(diǎn)i螞蟻選擇去需求的j的概率保持在區(qū)間[pmin,pmax]內(nèi)。當(dāng)且僅當(dāng)螞蟻只剩下唯一選擇時(shí)才有pmin=pmax=1。</p><p>　　未更新信息素之前，信息素范圍區(qū)間極值定義式如下：</p><p><b>　　I</b></p><p>　　

75、更新信息素后極大值如下：</p><p>　?。?）初始化和重新初始化信息素</p><p>　　算法開(kāi)始前，會(huì)對(duì)信息素進(jìn)行初始化，設(shè)定原則為信息素極大值之上的一個(gè)估算值。由于該方式可以連同一個(gè)信息素蒸發(fā)參數(shù)，導(dǎo)致各邊上的信息素差異的增加相對(duì)緩慢，因此在算法初期，該算法極具探索性。</p><p>　　我們知道，蟻群算法在運(yùn)行中對(duì)某些路徑的探索概論很小，為了解決這個(gè)

76、問(wèn)題，就需要在達(dá)到某些條件時(shí)對(duì)信息素進(jìn)行重新初始化。一般來(lái)說(shuō)，重新初始化的條件有兩個(gè)：算法達(dá)到或接近停滯，或者在達(dá)到迭代次數(shù)上限前依然沒(méi)有找到最優(yōu)路徑。</p><p>　　5.3蟻群算法的其他改進(jìn)策略</p><p>　　在引入最大最小法對(duì)蟻群算法進(jìn)行改進(jìn)后，無(wú)論是算法的收斂速度，還是其全局搜索能力上都有很大的提高。這是從算法本身出發(fā)而做出的改進(jìn)。有時(shí)候我們還可以從算法參數(shù)、需求點(diǎn)選擇策

77、略出發(fā)對(duì)其進(jìn)行改進(jìn)，這樣可以提高算法的自適應(yīng)性。</p><p>　　（1）信息素傳遞參數(shù)的選取</p><p>　　在基本蟻群算法中，是一個(gè)常量，通過(guò)對(duì)其定義式的研究發(fā)現(xiàn)，隨著不但變大，當(dāng)達(dá)到某個(gè)臨界值后，算法對(duì)那些未被搜索過(guò)路徑的選擇概率會(huì)相對(duì)減小，從全局搜索的角度來(lái)說(shuō)，這是有缺陷的。相反，如果選擇的值過(guò)小，收斂速度會(huì)減少。因此如何在算法初期對(duì)進(jìn)行適當(dāng)改進(jìn)調(diào)整，可以幫我忙更快的找到最優(yōu)

78、路徑，達(dá)到目的。在算法初期算法找到都屬于次優(yōu)解，如果值要比較大，需要對(duì)信息濃度進(jìn)行增大調(diào)整，加快收斂速度；如果算法進(jìn)入停滯階段，我們要減小值，進(jìn)而使信息素對(duì)蟻群的影響達(dá)到最小，加大對(duì)全局的搜索以避免局部最優(yōu)。</p><p>　　上式中，r表示連續(xù)沒(méi)有進(jìn)化的循環(huán)的次數(shù)，rmax為常數(shù)，(0,1)也屬于一個(gè)常量，控制衰減速度，min是的最小值，防止過(guò)小影響收斂速度。當(dāng)r達(dá)到預(yù)先設(shè)置的一個(gè)數(shù)值rmax時(shí)，我們就減小，

79、r重新計(jì)數(shù)，如此反復(fù)，直至達(dá)到預(yù)設(shè)最小值min為止。</p><p>　?。?）確定性搜索和探索性搜索的選則</p><p>　　當(dāng)算法在初期找到較優(yōu)解后，需要加快收斂速度，盡快進(jìn)化，從而得到更優(yōu)解。蟻群算法屬于一種啟發(fā)式算法，要想使得算法進(jìn)化就必須不斷進(jìn)行遍歷搜索；但是不斷的搜索又會(huì)限制算法的收斂速度，進(jìn)而反過(guò)來(lái)導(dǎo)致加長(zhǎng)了最優(yōu)解的尋找時(shí)間，甚至忽略了最優(yōu)解。舉個(gè)例子，當(dāng)蟻群算法得到較優(yōu)解

80、時(shí)，且此解有進(jìn)化為最優(yōu)解的可能，此時(shí)算法會(huì)在更大的空間搜索，范圍大了，對(duì)該解對(duì)應(yīng)的路徑選擇概論就會(huì)減少，信息素濃度會(huì)逐漸減少直至此路徑被遺忘。</p><p>　　為此我們引入一個(gè)常量：q0[0,1)，每當(dāng)螞蟻在選擇路徑之前，都會(huì)先產(chǎn)生一個(gè)q[0,1)，k號(hào)螞蟻選擇規(guī)則如下：</p><p>　　由上式可以看出，當(dāng)qq0時(shí)，將會(huì)使用基本蟻群算法進(jìn)行搜索；當(dāng)q<q0時(shí)，是從已經(jīng)得到的結(jié)

81、果中，找出最大概論的路徑作為選擇，屬于確定性搜索。</p><p>　　確定性搜索解決了探索性搜索受限于收斂速度的問(wèn)題，通過(guò)調(diào)整合適的q0，使探索性搜索和確定性搜索合理搭配，從而加快蟻群算法的收斂速度。</p><p>　　通過(guò)對(duì)q0的取值進(jìn)行調(diào)整，我們發(fā)現(xiàn)：當(dāng)q<q0時(shí)，算法會(huì)選擇采用確定性搜索，此時(shí)螞蟻以概率q0選擇最短路徑；而當(dāng)q≥q0時(shí)，算法會(huì)選擇采用探索性搜索，此時(shí)螞蟻以概

82、率l- q0進(jìn)行隨機(jī)路徑選擇。在算法迭代的初期，q0需要選擇較大的初始值，且確定性搜索以較大的概率進(jìn)行，這樣做的目的是為了加快尋找局部較優(yōu)路徑的速度；在算法的中期q0的值會(huì)以較小為準(zhǔn)，增大探索性搜索的概率，繼而加大搜索空間；直到算法的后期，恢復(fù)q0的初始值，加快收斂速度。</p><p>　　結(jié)合最大最小算法改進(jìn)后的蟻群算法，得到的基于改進(jìn)后蟻群算法的物流配送路徑優(yōu)化問(wèn)題的算法流程圖： </p>&

83、lt;p><b>　　圖1 算法流程圖</b></p><p><b>　　第六章 軟件實(shí)現(xiàn)</b></p><p>　　本章就會(huì)展示基于改進(jìn)后蟻群算法的物流配送路徑優(yōu)化系統(tǒng)。</p><p><b>　　6.1 功能要求</b></p><p>　?。?）生成客戶數(shù)據(jù)

84、 </p><p>　?。脩艨梢栽谲浖缑嫔想S機(jī)標(biāo)注倉(cāng)庫(kù)與客戶的地址(不少于10個(gè)客戶)；</p><p>　?。蛻舻牡刂繁硎静捎肳indow設(shè)備坐標(biāo)系?？蛻舻刂烽g的距離采用設(shè)備坐標(biāo)像素間距模擬，坐標(biāo)之間行駛速度采用隨機(jī)算法生成。</p><p><b>　　（2）動(dòng)態(tài)路線規(guī)劃</b></p><p>　?。浖筛?/p>

85、據(jù)用戶選擇的路徑規(guī)劃策略，如最短路徑、最少時(shí)間等進(jìn)行配送路線規(guī)劃。</p><p>　?。M車輛從倉(cāng)庫(kù)出發(fā)，沿著規(guī)劃的配送路線行進(jìn)，最后返回倉(cāng)庫(kù)。在配送過(guò)程中可模擬前方行進(jìn)路線堵車事件，軟件能夠繞開(kāi)堵車路段動(dòng)態(tài)規(guī)劃配送路線。</p><p><b>　　6.2總體設(shè)計(jì)</b></p><p>　　本系統(tǒng)是基于蟻群算法的路徑優(yōu)化設(shè)計(jì)，主要作用是

86、根據(jù)6.1所述的功能要求設(shè)計(jì)，在給出隨機(jī)需求點(diǎn)的坐標(biāo)數(shù)據(jù)后，輸入約束條件（即事故路段），通過(guò)數(shù)據(jù)計(jì)算，最終系統(tǒng)根據(jù)計(jì)算結(jié)果得出優(yōu)化后的路徑（長(zhǎng)度最短、時(shí)間最短）。數(shù)據(jù)圖如下：</p><p><b>　　6.3 軟件架構(gòu)</b></p><p>　　在B2C農(nóng)產(chǎn)品電子商務(wù)物流配送時(shí)，物流車裝載當(dāng)日需要配送的貨品從倉(cāng)庫(kù)出發(fā)，按照事先規(guī)劃好的最優(yōu)配送路徑為每一個(gè)客戶進(jìn)行配

87、送，最后返回倉(cāng)庫(kù)。本軟件可以在配送之前根據(jù)客戶的配送地址間線路間距、經(jīng)驗(yàn)路況做分析計(jì)算出一條最優(yōu)配送路徑。而且，事先通知系統(tǒng)擁擠路段后，系統(tǒng)可以選擇避開(kāi)該路段的最優(yōu)路徑。</p><p>　　軟件界面分為左右兩欄，左欄控制部分有produce data、route shortest、time shortest、Drive、exit五個(gè)按鈕，分別用于產(chǎn)生隨機(jī)數(shù)據(jù)、選擇路線最短的路徑、選擇時(shí)間最短的路徑、模擬汽車行進(jìn)

88、、退出軟件。顯示部分可以顯示最優(yōu)路徑以及相應(yīng)路徑的代價(jià)。具體的，右欄可以顯示倉(cāng)庫(kù)和客戶區(qū)位置（此軟件設(shè)置客戶區(qū)為14個(gè)）并且根據(jù)相應(yīng)的操作描繪出最佳路線并模擬汽車行進(jìn)。</p><p>　　編程實(shí)現(xiàn)上，自定義兩個(gè)類，class WuLiu、class Ant，其中WuLiu類用于實(shí)現(xiàn)軟件的外觀；Ant類用于實(shí)現(xiàn)算法。</p><p><b>　　6.4 測(cè)試文檔</b>

89、;</p><p><b>　　測(cè)試方法：</b></p><p>　　軟件運(yùn)行后，點(diǎn)擊Produce Data按鈕可以生成隨機(jī)測(cè)試數(shù)據(jù)，如果數(shù)據(jù)不理想，可以繼續(xù)點(diǎn)擊該按鈕；點(diǎn)擊Route Shortest按鈕，右側(cè)欄會(huì)描繪最優(yōu)路徑，同時(shí)左欄會(huì)顯示路徑中從倉(cāng)庫(kù)出發(fā)依次經(jīng)過(guò)的客戶區(qū)，同時(shí)顯示此條路徑的代價(jià)；對(duì)于時(shí)間最短的測(cè)試與上面類似；點(diǎn)擊Drive，模擬汽車行進(jìn)；點(diǎn)擊

90、Exit，退出軟件。</p><p>　　測(cè)試中可能出現(xiàn)的問(wèn)題：</p><p>　　對(duì)于同一批數(shù)據(jù)，兩次點(diǎn)擊Route Shortest按鈕生成的最優(yōu)路徑會(huì)有所不同，這是由于算法陷入局部最優(yōu)導(dǎo)致。對(duì)于時(shí)間最短路徑可能會(huì)出現(xiàn)的問(wèn)題也是如此。雖然會(huì)出現(xiàn)陷入局部最優(yōu)的情況，但是，測(cè)試發(fā)現(xiàn)由此造成的誤差會(huì)限制在一定范圍內(nèi)，這中誤差往往是可以接受的，另外可以通過(guò)選擇合適的alpha、beta值使得

91、誤差進(jìn)一步減小。</p><p><b>　　第七章 總結(jié)語(yǔ)</b></p><p>　　本文的核心研究是基于改進(jìn)蟻群算法的物流配送路徑優(yōu)化問(wèn)題。針對(duì)該問(wèn)題，將今年來(lái)市場(chǎng)以及研究中運(yùn)用過(guò)的其他智能算法相應(yīng)做了對(duì)比和簡(jiǎn)述。論文中，通過(guò)結(jié)合最大最小蟻群算法對(duì)基本蟻群算法做出改進(jìn)，解決了基本蟻群算法收斂速度緩慢，優(yōu)化結(jié)果差等問(wèn)題，同時(shí)基于改進(jìn)后的算法本身也可以做到避免陷入局

92、部搜索、算法停滯等問(wèn)題。在信息素方面無(wú)論是信息素初始化更新，還是迭代時(shí)的重新初始化更新方面，改進(jìn)算法都具有優(yōu)勢(shì)，相應(yīng)的提高算法收斂速度和全局尋優(yōu)能力。</p><p>　　本文在驗(yàn)證方面選取的是經(jīng)典問(wèn)題——旅行商問(wèn)題（TSP），為了使得論文研究更具實(shí)際價(jià)值，在車輛路徑問(wèn)題（VRP）的基礎(chǔ)上做出進(jìn)一步擴(kuò)充——在容量方面做出基于現(xiàn)實(shí)的限制，也就是CVRP。本文的所有研究都是基于該前提條件進(jìn)行的研究，實(shí)際應(yīng)用方面更具考

93、究。</p><p>　　在最終的軟件設(shè)計(jì)方面，完全滿足論文選題對(duì)軟件的技術(shù)要求，在隨機(jī)生成需求點(diǎn)坐標(biāo)后，軟件可以快速的做出響應(yīng)，給出滿足條件的優(yōu)化路徑，包括最短時(shí)間優(yōu)化和最短距離優(yōu)化，同時(shí)在軟件中也可以實(shí)現(xiàn)針對(duì)某事故路段而做出路徑的重新優(yōu)化，以及該優(yōu)化結(jié)果相應(yīng)路徑的代價(jià)。并且給出了優(yōu)化路徑的數(shù)字表達(dá)，更直觀也更加滿足在現(xiàn)實(shí)環(huán)境中的路徑解決需要。</p><p>　　本論文主要工作如下：&

94、lt;/p><p>　　開(kāi)題介紹了論文研究的背景、目的、意義，以及對(duì)國(guó)內(nèi)外相關(guān)物流發(fā)展現(xiàn)狀和問(wèn)題展開(kāi)討論。</p><p>　　對(duì)相關(guān)的智能算法做了部分簡(jiǎn)介，包括各種智能算法的演繹基本原理、發(fā)展優(yōu)勢(shì)及實(shí)際應(yīng)用中產(chǎn)生的問(wèn)題和不足。</p><p>　　進(jìn)入本論文重點(diǎn)需要應(yīng)用和介紹的部門——對(duì)基本蟻群算法的基本原理、數(shù)學(xué)模型和約束條件等做了論述，同時(shí)相應(yīng)介紹TSP、CVRP

95、等問(wèn)題，為后面的改進(jìn)蟻群算法章節(jié)做了鋪墊。</p><p>　　主要介紹改進(jìn)后的最大最小蟻群算法，列出在基本蟻群算法改進(jìn)的步驟、注意點(diǎn)，結(jié)合相關(guān)研究得出改進(jìn)后蟻群算法的優(yōu)勢(shì)所在。</p><p>　　針對(duì)以上研究對(duì)基于QT界面制作的軟件部分做出相關(guān)介紹，包括軟件的總體設(shè)計(jì)、制作原理和功能要求。</p><p>　　對(duì)論文中算法的優(yōu)勢(shì)以及軟件部分的優(yōu)缺點(diǎn)進(jìn)行總結(jié)，同時(shí)

96、對(duì)未來(lái)物流的發(fā)展進(jìn)行展望，也提出了針對(duì)本論文可以改進(jìn)的地方。</p><p>　　結(jié)合論文部分做出的基于改進(jìn)蟻群算法的物流配送路徑優(yōu)化系統(tǒng)，在適用性和功能性都較高，能夠在較短時(shí)間、花費(fèi)較小代價(jià)的前提下給出最優(yōu)路徑或者接近最優(yōu)路徑的解，符合論文選題的要求。</p><p><b>　　研究展望</b></p><p>　　如上所說(shuō)，本文能夠在選題

97、的要求下做出較為合適的系統(tǒng)，最終得出最優(yōu)解或者近似最優(yōu)。然而，本論文也是一些不足之處。比如，路徑選擇都是直線行走，而實(shí)際生活中的路線不可能都是直線，當(dāng)然，這是技術(shù)層面上的問(wèn)題，相對(duì)來(lái)說(shuō)，需求點(diǎn)的順序走向是沒(méi)有太大差異。</p><p>　　所以，在時(shí)間和技術(shù)允許的情況下，還可以做出一下幾個(gè)方面的研究拓展：</p><p>　　GPS導(dǎo)航技術(shù)的支持。這會(huì)使得該系統(tǒng)更加完善，配送車輛在某一點(diǎn)時(shí)

98、隨時(shí)可以根據(jù)具體情況改變方案。</p><p>　　在系統(tǒng)中可以加入一個(gè)需求緊急度，即將客戶的需求分類，哪些需要重點(diǎn)、迅速的配送，哪些相對(duì)時(shí)間不急，這樣的安排更具人性化。</p><p>　　建立真實(shí)情況下客戶資源數(shù)據(jù)庫(kù)。</p><p>　　可以細(xì)化軟件模塊，比如添加用戶注冊(cè)模塊、用戶登錄模塊甚至系統(tǒng)管理模塊等等。</p><p>　　動(dòng)態(tài)

99、設(shè)計(jì)更優(yōu)化。本系統(tǒng)是可以避開(kāi)事故路段重新規(guī)劃路徑的，然而這還是不夠的，如果進(jìn)一步對(duì)其動(dòng)態(tài)設(shè)計(jì)，還可以添加在行駛途中遭遇問(wèn)題的規(guī)劃。</p><p>　　技術(shù)革新的腳步從沒(méi)有停止過(guò)，不斷的創(chuàng)新才是發(fā)展的根本。正如論文對(duì)基本蟻群算法的改進(jìn)一樣，今后也一定會(huì)出現(xiàn)更好、更快的算法，我們要做的就是把這些運(yùn)用到實(shí)際中，讓物流業(yè)的發(fā)展更進(jìn)一步。</p><p>　　作者在技術(shù)和經(jīng)驗(yàn)上還有諸多不足，論文中