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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

42、越多，“信息素”也越來越多，后來者選擇此路徑的可能性也更大（因為殘留的信息濃度較大的緣故）。這樣，在單位時間內(nèi)此路徑持續(xù)被更多的螞蟻選擇訪問，信息素積累增多，直到最后，幾乎所有的螞蟻都選擇這條最短的路徑。</p><p>　　4.5.2 算法實現(xiàn)</p><p>　　我們用人工螞蟻代替車輛對需求點點進行“配送”，螞蟻在i需求點選擇的下一個需求點j時，主要考慮兩方面因素，一是i，j兩需求點之

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

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

45、 AS 算法中，ηij 通常取需求點 i 與需求點j 之間距離的倒數(shù)。α和β分別表示信息素和啟發(fā)式因子的相對重要程度。當所有螞蟻完成一次循環(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 沒有經(jīng)過邊 ij，則△τkij的值為零?！鳓觡ij表示為：</p><p><b>　　(2. 4)</b></p><p>　　其中，Q 為正常數(shù)，Lk 表示第 k 只螞蟻在

47、本次周游中所走過路徑的長度。</p><p>　　M. Dorigo 提出了 3 種 AS 算法的模型 ，式(2.4)稱為 ant-cycle，另外兩個模型分別稱為 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算法實際上是正反饋原理和啟發(fā)式算法相結(jié)合的一種算法。在選擇路徑時，螞蟻不僅利用了路徑上的信息素，而且用到了城市間距離的倒數(shù)作為啟發(fā)式因子。</p><p>　　AS 算法的時間復雜度為Ο(NC*n2*m) &l

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

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

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

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

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

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

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

56、更新。蟻群算法之所以優(yōu)于其他算法，是因為每一次迭代中，信息素的期望值往往會低于其初始值，其計算公式如下：</p><p>　　式中，m表示螞蟻數(shù)量，Cnm代表路徑長度。選擇該初始值的初衷是因為，一旦信息素初始值過小，搜索區(qū)域往往受到限制，大多搜索會過于集中在初始有限的路徑中，即我們所說的陷入局部搜索中，很難找到最優(yōu)解。相反地，如果讓信息素的初始值過大，就會無法發(fā)揮蟻群算法初始的多次迭代優(yōu)勢，這種效果會一直持續(xù)到信

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

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

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

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

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

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

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

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

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

66、t;<p>　　實際情況中需要考慮的約束條件如下：</p><p>　　限制容量?？蛻舻囊蠡蛘哒f需求量有大有小，有時候受到車輛本身的條件所限，是沒有辦法一次性全部裝載的，也就是說，車輛的要求負重不能大于車輛本身的最大載重。這種限制稱為CVRP。</p><p>　　路長限制。車輛不可能無限制的一直跑下去，其行駛總路長受到油耗和油量的限制，即車輛的行駛路長需要設定為一個合適的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

84、 </p><p>　?。脩艨梢栽谲浖缑嫔想S機標注倉庫與客戶的地址(不少于10個客戶)；</p><p>　　＊客戶的地址表示采用Window設備坐標系。客戶地址間的距離采用設備坐標像素間距模擬，坐標之間行駛速度采用隨機算法生成。</p><p><b>　?。?）動態(tài)路線規(guī)劃</b></p><p>　　＊軟件可根

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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