嵌入式畢業(yè)論文--城區(qū)物流快遞送貨的路徑選擇研究

1、<p>　　本 科 畢 業(yè) 論 文</p><p>　　城區(qū)物流快遞送貨的路徑選擇研究</p><p>　　The Research of path Choice for City Logistics Express </p><p>　　系(院)名稱： 計算機科學(xué)與信息工程學(xué)院 </p><p>　　專業(yè)班級

2、： 11屆計算機科學(xué)與技術(shù)嵌入方向 </p><p>　　學(xué)生姓名： 　　 ＸＸＸ　 　</p><p>　　學(xué)生學(xué)號： </p><p>　　指導(dǎo)教師姓名： XXX　 　 </p><p>　　指導(dǎo)教師職稱： 副 教

3、 授 </p><p>　　2012年 5 月</p><p>　　城區(qū)物流快遞送貨的路徑選擇研究</p><p>　　摘要：物流快遞是現(xiàn)代電子商務(wù)的支撐基礎(chǔ)。我們越來越依賴于物流的同時，也伴隨著很多問題，比如能不能盡快送到目的地，怎樣才能最快送到等。物流快遞送貨的路徑選擇即對于給定的一組訂單，先送什么后送什么的路徑規(guī)劃。對于小規(guī)模的送貨可用

4、最短路徑和動態(tài)規(guī)劃等方法實現(xiàn)，但是隨著問題規(guī)模的擴大，組合優(yōu)化問題常常會呈現(xiàn)組合爆炸的特征，此類問題無法使用常規(guī)方法來求解，屬于NP-Hard問題，車輛路徑問題就是典型的組合優(yōu)化問題。蟻群算法（ACO）是受自然界中螞蟻搜索食物行為啟發(fā)而提出的一種智能優(yōu)化算法。研究發(fā)現(xiàn)，蟻群算法可以較好地求解VRP（Vehicle Routing Problem，車輛路徑優(yōu)化）等組合優(yōu)化問題。蟻群算法發(fā)現(xiàn)較好解的能力很強，具有分布式計算、魯棒性強、易于與

5、其他方法結(jié)合等優(yōu)點，具有十分廣闊的應(yīng)用前景。然而，蟻群算法存在求解速度慢，在規(guī)模擴大后帶來收斂慢等問題。對車輛路徑問題解決上，現(xiàn)有的蟻群算法存在難以回歸原點等問題。這些問題也是我們面臨的巨大挑戰(zhàn)。</p><p>　　本文采用的是面向?qū)ο蟮腣C語言，依據(jù)蟻群算法解決配送路線的優(yōu)化問題，文章從以下幾個方面展開：首先充分概括了當前的蟻群算法在車輛路徑問題上的研究。詳細分析了基本蟻群算法的原理，然后詳細闡述了VRP問題

6、并引用了其數(shù)學(xué)模型，并介紹了蟻群算法解決VRP問題的方法以及現(xiàn)狀面臨的挑戰(zhàn)。并將遺傳算法的復(fù)制、交叉、變異等遺傳算子引入蟻群算法，同時改進信息素的更新方式、客戶點選擇策略，以提高算法的收斂速度和全局搜索能力。</p><p>　　關(guān)鍵詞： 物流配送 車輛路徑問題 蟻群算法 </p><p>　　The Research of path Choice for City Logistics

7、 Express</p><p>　　Abstract: Logistics express is the basis of modern e-business. we are increasingly dependent on logistics. We are increasingly dependent on the logistics with many problems associating wit

8、h it at the same time. For example ,if it is sent to the destination as soon as possible ,how can it be the fastest . The delivery route choice of logistics express is a path planning of what should be put foreword and w

9、hat afterward for a group of given orders .It is can be realized by using the method of the</p><p>　　In this paper ,the system is based on VC technology ,full analyses of the current ant colony algorithm are

10、 listed on the issue .Then we analyze the basic ant colony algorithm in detail ,and then elaborated on the issue VRP and its mathematical model .The increasing scale nodes of the combinatorial optimization problems lead

11、to deal with problem more difficult . Several genetic operators such as crossover and mutation are inducted into the ant colony algorithm , and pheromone updating strategy is</p><p>　　Key words: logistic dis

12、tribution Vehicle Routing Problem ant colony algorithm (ACA)</p><p><b>　　目錄</b></p><p><b>　　引言1</b></p><p><b>　　第1章 緒 論2</b></p><p

13、>　　1.1課題研究的背景和意義2</p><p>　　1.1.1課題研究的背景2</p><p>　　1.1.2課題研究的意義2</p><p><b>　　1.2研究現(xiàn)狀2</b></p><p>　　1.3課題的研究內(nèi)容3</p><p>　　1.3.1基本蟻群算法研究3&

14、lt;/p><p>　　1.3.2蟻群算法解決車輛路徑問題3</p><p>　　第2章 VRP問題的蟻群優(yōu)化算法分析4</p><p>　　2.1蟻群算法應(yīng)用于VRP問題4</p><p>　　2.1.2物流配送問題的描述5</p><p>　　2.1.3利用蟻群算法解決車輛路徑問題5</p>&

15、lt;p>　　2.1.4實際應(yīng)用6</p><p>　　2.1.5確定可行解采用策略7</p><p>　　2.2傳統(tǒng)算法存在的問題8</p><p>　　2.3相關(guān)理論簡介9</p><p>　　2.3.1蟻群算法基本原理9</p><p>　　2.3.2車輛路徑問題9</p><

16、;p>　　2.3.3遺傳算法10</p><p>　　2.3.4蟻群算法信息素11</p><p>　　第3章 基于改進的蟻群算法解決車輛路徑問題13</p><p>　　3.1蟻群算法的改進13</p><p>　　3.1.1改進算法提出的背景13</p><p>　　3.1.2處理策略13<

17、/p><p>　　3.2可行解問題16</p><p>　　3.3程序的設(shè)計19</p><p>　　3.3.1 Ant模塊19</p><p>　　3.3.2 Common模塊21</p><p>　　3.3.3 蟻群和遺傳算法相結(jié)合24</p><p>　　第4章 系統(tǒng)測試分析26&

18、lt;/p><p>　　4.1單元測試26</p><p>　　4.1.1 測試126</p><p>　　4.1.2 測試227</p><p><b>　　第5章 結(jié)論29</b></p><p><b>　　5.1 總結(jié)29</b></p><

19、p><b>　　5.2 展望29</b></p><p><b>　　致謝30</b></p><p><b>　　參考文獻 31</b></p><p><b>　　引言</b></p><p>　　物流是以物品從供應(yīng)地向接收地實體流動的過程

20、。它是一個全新的系統(tǒng)概念，和金融結(jié)算一起構(gòu)成了現(xiàn)代電子商務(wù)的兩大支撐基礎(chǔ)。隨著經(jīng)濟的發(fā)展和經(jīng)濟體制改革的進一步深化，物流業(yè)正成為我國市場經(jīng)濟中競爭最為激烈的行業(yè)之一，其在現(xiàn)代經(jīng)濟發(fā)展中的地位和作用，比任何時期都更加重要?，F(xiàn)階段，物流業(yè)已貫穿于我國生產(chǎn)、分配、流通、和消費的各個領(lǐng)域，社會對物流需求的數(shù)量、質(zhì)量正在不斷提高。</p><p>　　物流配送作為物流體系中最為重要的一環(huán)，對整個物流體系的效率起著關(guān)鍵的作用

21、。先進高效的物流配送系統(tǒng)能為企業(yè)創(chuàng)造出更高的經(jīng)濟效益，是企業(yè)增強自身競爭力的重要手段。當今物流配送的一個重要的研究領(lǐng)域就是系統(tǒng)優(yōu)化。</p><p>　　車輛調(diào)度是物流配送管理最重要的部門。隨著社會的發(fā)展以及消費者對服務(wù)質(zhì)量要求的不斷提高，高效的車輛調(diào)度，以提高物流效率、降低物流成本、提高服務(wù)質(zhì)量對于促進經(jīng)濟健康穩(wěn)定的發(fā)展具有重要意義。所謂的車輛路徑問題，就是車輛和路徑的恰當選取，運輸規(guī)劃的合理制定問題。解決此問

22、題，可用加快對客戶需求的響應(yīng)速度，提高服務(wù)質(zhì)量，增強客戶對物流環(huán)節(jié)的滿意度，降低服務(wù)商運作成本。車輛調(diào)度問題（vehicle route problem , VRP）是物流的一個重要研究方向，是一個典型的車輛調(diào)度問題，也是一個比較重要的組合優(yōu)化問題。</p><p>　　優(yōu)化技術(shù)原本是近代數(shù)學(xué)的一個分支，優(yōu)化是指尋求數(shù)學(xué)上的最優(yōu)解，而優(yōu)化技術(shù)則是以數(shù)學(xué)為基礎(chǔ)尋求最優(yōu)解的技術(shù)。在管理科學(xué)中，優(yōu)化是指在給定條件下如何

23、做出最佳的決策去完成給定的任務(wù)，最好地達到預(yù)期的目標。</p><p>　　對于車輛路徑這種組合優(yōu)化問題，通常隨著問題規(guī)模的擴大，問題空間呈現(xiàn)組合爆炸特征，因此，無法用常規(guī)方法求解，屬于NP-Hard問題。研究聲明：蟻群算法發(fā)現(xiàn)較好解的能力很強，具有分布式計算、魯棒性強、易于與其他方法結(jié)合等優(yōu)點，具有十分廣闊的應(yīng)用前景，也具有很重要的研究價值。通過研究車輛路徑問題，確定最佳的運輸路線，在提高車輛滿載率的同時，使車

24、輛運輸距離達到最小化，完善配送系統(tǒng)，使配送環(huán)節(jié)的總成本降低，提高配送的效率。</p><p><b>　　第1章 緒 論</b></p><p>　　1.1 課題研究的背景和意義</p><p>　　1.1.1 課題研究的背景</p><p>　　物流業(yè)正在成為我國市場經(jīng)濟中競爭最為激烈的行業(yè)之一，在我國國民經(jīng)濟和社會發(fā)

25、展“十一五”計劃中，已將“物流配送”作為重點支持和發(fā)展的服務(wù)產(chǎn)業(yè)。智能物流配送管理系統(tǒng)是完成貨物配送的功能性系統(tǒng)，也是車輛配送中心系統(tǒng)中一個非常重要的組成部分。 而高效的車輛調(diào)度，可以提高物流的效率、降低物流成本、提高物流服務(wù)質(zhì)量、加快對客戶需求的響應(yīng)速度，增強客戶對物流的滿意度。</p><p>　　1.1.2 課題研究的意義</p><p>　　物流配送路徑優(yōu)化和蟻群算法原型所解決的問

26、題相比有共同點——都是尋找遍歷所有客戶點的最短路徑的問題，也有其特性——有更多更復(fù)雜的約束條件和優(yōu)化目標。本文針對這種特點，研究一種基于蟻群算法的優(yōu)化路徑算法，通過引入遺傳算子，在局部搜索過程中能夠避免算法早熟、停滯，同時改進信息素的更新方式、客戶點選擇策略，增強蟻群算法的正反饋作用，從而提高收斂速度和全局搜索能力，使得其在物流配送路徑優(yōu)化問題中有較好的實際效果。</p><p><b>　　1.2 研

27、究現(xiàn)狀</b></p><p>　　蟻群算法是由M.Dorigo和他的同事首先提出來，很好地解決了一些復(fù)雜的組合優(yōu)化問題，如旅行商問題（TSP）和背包問題等等。目前已經(jīng)有很多種基于蟻群算法或其改進算法，應(yīng)用于各種不同的離散優(yōu)化問題，這些研究涉及到了車輛路徑問題（VRP）、網(wǎng)絡(luò)中路由通信問題，等等。</p><p>　　螞蟻們跟蹤信息素路徑的行為確實導(dǎo)致了最短路徑的發(fā)現(xiàn)，即當食物

28、源和巢穴之間存在多條路徑時，一群螞蟻通過跟蹤由個體留下的信息的確找到了優(yōu)化的路徑，這具有實際研究意義。初步的研究結(jié)果表明，蟻群算法在求解復(fù)雜優(yōu)化問題方面有著很大的優(yōu)越性。雖然目前對蟻群算法的研究剛剛起步，一些思想還處于萌芽時期，其嚴格的理論基礎(chǔ)尚未確立，收斂性的證明也不夠成熟，國內(nèi)外的相關(guān)研究仍停留在實驗探索階段，但是從當前的應(yīng)用效果來看，這種模仿自然生物的新型尋優(yōu)算法無疑具有非常光明的前景。</p><p>　

29、　1991年，意大利學(xué)者M.Dorigo等提出了第一個蟻群算法-螞蟻系統(tǒng)并成功應(yīng)用于求解TSP問題。實驗結(jié)果證明蟻群算法具有較強的魯棒性和發(fā)現(xiàn)較好的解的能力但與此同時也存在著一些缺陷，如收斂速度慢、易出現(xiàn)停滯現(xiàn)象等。該算法的問世引起了學(xué)者們的普遍關(guān)注，針對算法的缺點提出了一些改進的蟻群算法。最近國內(nèi)外對蟻群算法的研究日趨火熱，相信隨著更深入的研究，蟻群算法必定會得到更好的發(fā)展。</p><p>　　1.3 課題的

30、研究內(nèi)容</p><p>　　物流配送管理系統(tǒng)是完成貨物配送的功能性系統(tǒng)，也是車輛配送中心系統(tǒng)中一個非常重要的組成部分。正是通過配送管理系統(tǒng)，配送中心才得以最終完成貨物從生產(chǎn)商到用戶的轉(zhuǎn)移，實現(xiàn)商品的使用效用。另外，配送中心配送系統(tǒng)還通過對貨物的集中、合理配送有效的節(jié)約了運力，降低了整個社會的物流總成本。物流配送管理系統(tǒng)，主要是配送車輛優(yōu)化調(diào)度，包括集貨線路優(yōu)化、貨物配裝及配送車輛路徑優(yōu)化。其中的配送車輛路徑優(yōu)化

31、，是物流系統(tǒng)優(yōu)化中關(guān)鍵的一環(huán)。對配送車輛路線進行優(yōu)化，可以提高經(jīng)濟效益、實現(xiàn)物流科學(xué)化。</p><p>　　為解決配送車輛路徑優(yōu)化問題，做了如下工作：</p><p>　　1.3.1 基本蟻群算法研究</p><p>　　首先介紹基本蟻群算法的原理以及相應(yīng)模型的創(chuàng)立，給出了基本蟻群算法的實現(xiàn)步驟，著重介紹了如何利用蟻群算法解決車輛路徑問題。蟻群算法具有采用分布式并

32、行計算機制、易于與其他方法結(jié)合、具有較強的魯棒性等優(yōu)點，但也存在搜索時間長、容易陷入局部最優(yōu)是其最突出的缺點。蟻群算法并不完美，為此本文做出改進措施，通過這種改進，加速了蟻群算法的收斂效果，改進的算法易于實現(xiàn)。</p><p>　　1.3.2 蟻群算法解決車輛路徑問題</p><p>　　通過對相關(guān)文獻的分析和總結(jié)，從物流配送中車輛路徑問題（VRP）的基本理論出發(fā)，闡述了VRP問題，深入分

33、析了VRP問題的數(shù)學(xué)模型。通過利用已有的蟻群算法解決VRP問題，隨后分析了基本蟻群算法解決VRP問題的不足。結(jié)合遺傳算法的優(yōu)點，將復(fù)制、交叉、變異這些遺傳因子引入蟻群算法中，以提高算法收斂速度和全局搜索能力。</p><p>　　第2章 VRP問題的蟻群優(yōu)化算法分析</p><p>　　2.1 蟻群算法應(yīng)用于VRP問題</p><p>　　2.1.1 蟻群算法介紹

34、</p><p>　　蟻群算法是一種由于受自然界生物的行為啟發(fā)而產(chǎn)生的“自然”算法。它是從對蟻群行為的研究中產(chǎn)生的。蟻群的覓食行為實際上是一種分布式的協(xié)同優(yōu)化機制。蟻群中的螞蟻以“信息素”（pheromone）為媒介的間接的異步的聯(lián)系方式是蟻群算法的最大的特點。單只螞蟻雖然能夠找到從蟻穴到食物源的一條路徑，但是找到最短路徑的可能性極小，只有當多只螞蟻組成蟻群時，其集體行為才凸顯出螞蟻的智能發(fā)展最短路徑的能力，這也

35、是蟻群算法的基礎(chǔ)思想：通過螞蟻間的相互合作來搜尋最短路徑。</p><p>　　在尋找最短路徑的過程中，蟻群會在它們經(jīng)過的地方留下一些化學(xué)物質(zhì)（我們稱之為“信息”）。這些物質(zhì)能被同一蟻群中后來的螞蟻感受到，并作為一種信號影響后到者的行動（具體表現(xiàn)在后到的螞蟻選擇這些物質(zhì)的路徑的可能性，比選擇沒有這些物質(zhì)的路徑的可能性大得多），而后到者留下的信息會對原有的信息素進行加強，并且如此循環(huán)下去。這樣，被越多的螞蟻選擇的路

36、徑，在后到螞蟻的選擇中被選擇的可能性就越大（因為殘留的信息濃度較大的緣故）。由于在一定的時間內(nèi)，越短的路徑會被越多的螞蟻訪問，因而積累的信息量也就越多，在下一個時間內(nèi)被其他的螞蟻選中的可能性也就越大。這個過程會一直持續(xù)到所有的螞蟻都走最短的哪一條路徑為止。因此，蟻群算法中另一個重要的機制是自催化機制，也就是正反饋機制，這種正反饋機制將指引蟻群找到高質(zhì)量的問題解。除了正反饋機制外，蟻群算法還有信息素揮發(fā)機制：路徑上的信息素隨著時間不斷揮發(fā)

37、將驅(qū)使螞蟻探索解空間中新的路徑從而避免求解過程中過早的收斂于局部最優(yōu)解。</p><p>　　蟻群算法大概可以概括為：</p><p>　　螞蟻通過的路線會留下信息素，經(jīng)常通過的路徑會造成信息素正反饋。反饋機制能夠擴大解的質(zhì)量對個體選擇路徑的影響，使得算法能夠快速發(fā)現(xiàn)較好的解或最優(yōu)解。</p><p>　　在分岔口，信息素濃度大的路線有更大概率被螞蟻選擇，也即螞蟻僅

38、僅通過信息素相互交流。</p><p>　　路徑越短的路線，選擇的概率越大，這屬于人工干涉的人工蟻群算法，在實際中可以加速找到最短路徑。</p><p>　　信息素會隨著時間而揮發(fā)，使得螞蟻有更多的幾率選擇到不常走的路徑。</p><p>　　2.1.2 物流配送問題的描述</p><p>　　一般配送路徑問題可描述如下：</p>

39、<p>　　有L個客戶點，已知每個客戶點的需求量及位置，至多用K輛汽車從配送中心到達這批需求點，并且在完成配送任務(wù)后，返回物流中心，每輛汽車載重量一定。要求安排車輛行駛路線使得運輸距離最短，且滿足以下幾個約束條件：</p><p>　　1）每條線路上的客戶點需求量之和不超過汽車載重量；</p><p>　　2）每條配送路徑的總長度不超過汽車一次配送的最大行駛距離；</p

40、><p>　　3）每個客戶點的需求必須且只能由一輛汽車來完成。</p><p>　　其目的是使總成本（如距離、時間等）為最小。</p><p>　　2.1.3 利用蟻群算法解決車輛路徑問題</p><p>　　車輛路徑問題，簡單的來說就是在一定約束下遍歷所有節(jié)點，我們用人工螞蟻代替車輛對客戶點進行配送，螞蟻在i客戶點選擇服務(wù)的下一個客戶點j時，主

41、要考慮兩個因素，一是i，j兩顧客點之間的關(guān)系的親密程度，稱為可見度，記為η；另外考慮的是由已完成的循環(huán)所得路徑方案體現(xiàn)出來的有i到j(luò)的可行性，即信息素濃度τ。在t時刻螞蟻k由客戶點i轉(zhuǎn)移到客戶點j的概率： </p><p><b>　　P（t）= </b></p><p>　　if j （公式 2.1）</p&

42、gt;<p>　　式中變量的意義如下：</p><p>　　τ：表示從i節(jié)點到j(luò)節(jié)點路線的信息素濃度，濃度越大螞蟻選擇走這條路的可能性就越大，這就體現(xiàn)了蟻群算法正反饋的特點。</p><p>　　η：與節(jié)點i到節(jié)點j路線長度有關(guān)，這是蟻群算法中人為加上去的一個變量，在自然界中的螞蟻并不知道路線長短，為了更好地達到目標，加上了這個變量。它一般是路徑長度的倒數(shù)，也即η=1/d。但

43、實際情況中，它實際上起的作用是更好地將距離短的路線選擇的概率變大，也即只要是距離的減函數(shù)即可。</p><p>　　α：反應(yīng)螞蟻在搜索路徑中積累的信息量的相對重要程度，α過小，收斂速度慢，而且算法很容易陷入局部最優(yōu)解；如果α過大，相當于信息素的重要性增大，這樣也會很容易陷入局部最優(yōu)而過早的收斂。</p><p>　　β在搜索路線的過程中，一些信息也可以左右螞蟻的選擇，比較典型的就是每條路線

44、的長度。β也即長度信息的加權(quán)因子。β對算法性能也有很大影響，β過大，收斂速度快，過小，則蟻群算法則進入了隨即搜索狀態(tài)。</p><p>　　allow={0,1,…n-1} 表示螞蟻k尚未服務(wù)的客戶點。</p><p>　　當下一個要服務(wù)的客戶點會使運載總量超出汽車載重量，或者使運距超過一次最大行駛距離時，就返回到配送中心 ，人工螞蟻代表下一輛車出發(fā)，繼續(xù)配送。當一次循環(huán)結(jié)束后，螞蟻遍歷了

45、所有客戶點，完成一次配送。當所有螞蟻完成一次循環(huán)后，根據(jù)各螞蟻遍歷的好壞（目標函數(shù)值），計算信息素增量，更新相關(guān)路徑上的信息素，更新規(guī)則：</p><p><b>　?。ü?.2）</b></p><p>　　2.1.4 實際應(yīng)用</p><p>　　實際應(yīng)用中，α和β并不是相對獨立的，彼此間相互影響，這也在很大程度上變成了難以解決的問題，很

46、難確定究竟如何選擇參數(shù)。由以前研究的結(jié)論中，α∈[1.0 ,2.0],β∈[4.0,6.0],ρ∈[0.1,0.5]是蟻群算法中參數(shù)的最優(yōu)設(shè)置。其中ρ是信息素揮發(fā)因子。</p><p>　　在蟻群算法中，每只螞蟻的回路僅僅是可行解的一個部分，我們將一些螞蟻的回路組合起來，如果這些回路包括了所有的節(jié)點，我們稱這個回路的集合為可行解，然而很可能在完成后一個可行解都得不到或者很難確定可行解。</p>&l

47、t;p>　　將復(fù)制、交叉、變異這些遺傳算子引入蟻群算法中，以提高算法的收斂速度。</p><p><b>　　1）編碼</b></p><p>　　遺傳算法中的交叉和變異操作是建立在基因編碼上的，因此在引入交叉和變異操作之前，我們首先對物流配送模型進行編碼。</p><p>　　假設(shè)有L個客戶點，K輛配送車輛，本文采用的編碼方式是將這L個

48、客戶點分別用到1到這L個自然數(shù)標識；第一輛車從配送中心出發(fā)時用0標識，其他車輛則分別用L+1，L+2，……，L+K-1表示。由于同一輛車可以多次配送，所以，2次以上配送的車輛出發(fā)時，依次用L+K，L+K+1，……表示。新的一輛車從配送點出發(fā)，或者編碼結(jié)束，就表示前一輛的路線結(jié)束，返回配送中心。這樣就將一次配送表示為一組由0和自然數(shù)組成的編碼。例如，有6個客戶點，我們分別用1至6表示，3輛車負責，那么編碼：</p><

49、p>　　0，1，2，3，7，4，5，8，6 </p><p>　　表示三輛車的配送路線分別是：車輛1[0→1→2→3→0],車輛3[0→4→5→0]，車輛1第二次配送[0→6→0]。</p><p><b>　　2）交叉</b></p><p>　　交叉操作是遺傳算法中增加種群多樣性，防止算法早熟、停滯的操作。在蟻群算法中引入交叉操作，

50、可以有效地擴大搜索空間，避免算法陷入局部最優(yōu)解。</p><p>　　在蟻群算法每一代搜索完成之后，我們將其中的最優(yōu)解和次優(yōu)解進行編碼交叉操作，交叉規(guī)則如下：</p><p>　　①假設(shè)兩組編碼分別是S1和S2，首先隨機生成交叉段的長度和交叉段起始位置；</p><p>　　②找出S1和S2中的交叉段，假設(shè)S1 ：P|P|P,S2:Q|Q|Q, P和Q分別是S1 和

51、S2的交叉段；將Q插入S1中，位于P前面，這樣形成新的編碼S3：P| Q| P| P；</p><p>　?、墼赟3中，刪除P 、P、P中與Q重復(fù)的編碼。形成交叉編碼S3；</p><p>　　④同樣的方法用在S2上，生成新的編碼S4；</p><p>　?、荼容^S1、S2、S3、S4的結(jié)果，選出最優(yōu)的兩組編碼并保存。</p><p><

52、;b>　　3）變異</b></p><p>　　變異操作也是增加種群多樣性的一種進化手段。適度的變異，既能保持種群內(nèi)個體的多樣化，又能提高算法的效率。</p><p>　　在蟻群算法中，我們在完成交叉操作后，對種群中最優(yōu)個體進行變異操作，操作方法為：</p><p>　?、匐S機生成變異次數(shù)N；</p><p>　　②隨機生成

53、兩個不同的自然數(shù)n，n>1（第一位不變，保證編碼以物流中心為起點）</p><p>　?、墼谧顑?yōu)個體的編碼S中，將第n位和第n位的編碼對調(diào)；</p><p>　?、苤貜?fù)②、③N次，生成新的編碼；</p><p>　?、荼容^S和的結(jié)果，保存較優(yōu)解。</p><p>　　2.1.5 確定可行解采用策略</p><p>

54、;　　根據(jù)已研究出來的結(jié)論可得到以下策略：</p><p>　　1）大螞蟻數(shù)策略：增加螞蟻數(shù)量，擴大范圍，增加可行解產(chǎn)生的可能性。</p><p>　　2）螞蟻初始狀態(tài)均勻分布：在每次迭代前，螞蟻隨機均勻分布于各個節(jié)點，從而發(fā)現(xiàn)可行解的機會增大。</p><p>　　3）近似解策略：當一些情況下無法得到可行解時，或者很難得到可行解時，選擇一些非可行解作為近似，然后按

55、照一些近似化策略得到一些可行解。采用這種策略一般可以得到可行解，但是結(jié)果是否好則很難確定。</p><p>　　關(guān)于可行解的一些策略雖然有理論研究價值，但在實際情況下，很難利用大量時間去測試回路間是否有可行解、回路是否能夠構(gòu)成可行解。</p><p>　　2.2 傳統(tǒng)算法存在的問題</p><p>　　傳統(tǒng)的蟻群算法研究與實際應(yīng)用結(jié)合不足。在實際中，如何讓蟻群算法可

56、以進行企業(yè)級的應(yīng)用，通過蟻群算法來為多客戶進行服務(wù)，同時對算法的安全性、快速性、可行性、有效性提出了挑戰(zhàn)。</p><p>　　單獨運行蟻群算法時，可能對于其速度等因素并不考慮太多，許多研究僅僅停留在理論層面。但當用戶數(shù)量、倉庫規(guī)模變大時，蟻群算法的速度問題將受到越來越多的重視。傳統(tǒng)蟻群算法對TSP問題求解時得到算法復(fù)雜度為O（NC×n×m）：</p><p>　　表2

57、.1基本蟻群算法時間復(fù)雜度</p><p>　　其中NC表示迭代次數(shù)，n表示節(jié)點數(shù)，m表示螞蟻數(shù)量。當n增大時，將影響對服務(wù)器的性能，如何在有限的迭代次數(shù)中得到接近最優(yōu)解成了巨大的挑戰(zhàn)。在可行解的搜索方面，傳統(tǒng)的蟻群算法將得到大量的無用解，耗費大量的資源。</p><p>　　傳統(tǒng)算法的應(yīng)用性研究并不多，沒有針對特殊問題的整體解決方案，也即沒有將理論很好地滲人現(xiàn)代物流項目中。這里包含很多原

58、因，其中一個重要原因是沒有與具體實際相結(jié)合，研究的東西很多偏向理論，導(dǎo)致物流企業(yè)無法直接感觸到算法對物流領(lǐng)域帶來的巨大影響。隨著一系列新的技術(shù)的提出和成熟，蟻群算法漸漸可以和其融合起來，在實際項目中體現(xiàn)出巨大的潛力。</p><p>　　2.3 相關(guān)理論簡介</p><p>　　2.3.1 蟻群算法基本原理</p><p>　　螞蟻在尋找食物過程中，單個螞蟻很難找到

59、食物到蟻穴的最短路徑，但一個蟻群往往可以很輕易地找到最優(yōu)解。尋其原因，單個螞蟻在爬行時留下了具有揮發(fā)性的信息素，螞蟻根據(jù)信息素的大小選擇路徑。隨著時間流逝，信息素會不斷減小，那些相對較短的路線，螞蟻通過的頻率較高，信息素也較高，這將導(dǎo)致越來越多的螞蟻選擇較短路徑，這樣正反饋就產(chǎn)生了。螞蟻也最終找到一條最優(yōu)路線到達目的地。</p><p>　　2.3.2 車輛路徑問題</p><p>　　在

60、物流配送領(lǐng)域中，有一類問題是非常常見的：存在一批客戶，各個客戶的位置和貨物需求是已知的供應(yīng)商具有若干可供派送的車輛，運載能力是一定的，每輛車都從起點出發(fā)，這個起點我們通常稱為配送中心，從這個起點出發(fā)完成若干客戶點的配送任務(wù)后再回到配送中心?，F(xiàn)在 要求的是用最小的車輛總行程類完成貨物的派送，這個問題被稱為車輛路徑問題（vehicle routing problem也即VRP）。</p><p>　　車輛路徑問題是物

61、流的一個重要研究方向，在物流系統(tǒng)中起很大的作用，也是一個比較重要的組合優(yōu)化問題。其研究的是如何使用最短路徑遍歷一個加權(quán)路徑網(wǎng)絡(luò)，這也相似于旅行商問題。但是相對于旅行商問題，車輛路徑問題有更多的約束，這將增大算法的難度。</p><p>　　對車輛路徑問題的描述如下：一個城市里存在一個配送中心，存在多個倉庫，倉庫中有貨物，且貨物是有重量的，且貨物種類不同?，F(xiàn)有n輛車，每輛車的載重是Q。現(xiàn)在利用這n輛車通過所有倉庫，

62、從倉庫里取得貨物，并將貨物送回配送中心。怎樣才能取得最短路徑使得所有車輛的運行軌跡之和最短。車輛路徑問題屬于NP-Hard問題，求解VRP的計算量會隨著倉庫的增加而急劇增加，通常我們在物流方面的應(yīng)用僅僅是找到次優(yōu)解，也即近似最優(yōu)解。</p><p>　　車輛路徑問題的數(shù)學(xué)描述：通常使用有向加權(quán)圖G=｛V，A，d｝來表示VRP問題，其中V=｛v0，v1，…vn｝表示節(jié)點，v0表示配送中心，也是每輛車的起點和終點，A

63、=｛（Vi，Vj）i！=j｝表示連接兩節(jié)點的弧，在實際問題中由于存在單行道的問題，（Vi，Vj）并不等于（Vj，Vi），也即圖所對應(yīng)的矩陣并不是對稱的。</p><p>　　每個倉庫節(jié)點都有一定的需求q，其中q必須為一個大于0的數(shù)。Q為車的載重量，對于路線Rk，路線上面經(jīng)過的所有的節(jié)點的需求之和應(yīng)該小于Q。也即對第j條線路應(yīng)有∑q<Q,因此，VRP問題的目標函數(shù)應(yīng)為：</p><p>

64、;　　MIN distance= （公式2.3）</p><p>　　2.3.3 遺傳算法</p><p>　　遺傳算法是模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優(yōu)的個體，利用遺傳算子（選擇、交叉和變異）對這些個體進行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標為止。</p>

65、<p>　　初始種群：算法采用隨機方法生成若干個個體的集合，該集合稱為初始種群。初始種群中個體的數(shù)量成為種群規(guī)模。</p><p>　　適應(yīng)度函數(shù)：遺傳算法對一個個體（解）的好壞用適應(yīng)度函數(shù)值來評價，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好，適應(yīng)度函數(shù)是遺傳算法進化過程的驅(qū)動力，也是進行自然選擇的唯一標準，它的設(shè)計是結(jié)合求解問題本身的要求而定的。</p><p>　　選擇算子：遺傳算法

66、使用選擇運算來實現(xiàn)對群體中的個體進行優(yōu)勝劣汰操作：適應(yīng)度高的個體被遺傳到下一代群體中的概率大；適應(yīng)度低的個體，被遺傳到下一代群體中的概率小；選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。</p><p>　　交叉算子：所謂交叉運算，是指對兩個相互配對的染色體依據(jù)交叉概率P，按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起

67、關(guān)鍵作用，是產(chǎn)生新個體的主要方法。</p><p>　　變異算子：所謂變異運算，是指依據(jù)變異概率P，將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。遺傳算法中的變異運算是產(chǎn)生新個體的輔助方法，它決定了遺傳算法的局部搜索能力，同時保持種群的多樣性。交叉運算和變異運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。</p><p>　　遺傳算法要實現(xiàn)全局收斂，首先要求任

68、意初始種群經(jīng)有限步都能到達全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。</p><p>　　種群太小則不能提供足夠的采樣點，以致算法性能很差；種群太大，盡管可以增加優(yōu)化信息，組織早熟收斂的發(fā)生，但是會增加計算量，造成收斂時間太長，表現(xiàn)為收斂速度緩慢。選擇操作使高適應(yīng)度個體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。如果在算法

69、中采用最優(yōu)保存策略，即將父代群體中最佳個體保留下來，不參加交叉和變異操作，使之直接進入下一代，最終可使遺傳算法以概率1收斂與全局最優(yōu)解。交叉操作作用于個體對于產(chǎn)生新的個體，實質(zhì)上是在解空間中進行有效搜索。交叉概率太大時，種群中個體更新更快，會造成高適應(yīng)度值的個體很快被破壞掉；概率太小時，交叉操作很少進行，從而會使搜索停滯不前，造成算法的不收斂。變異操作是對種群模式的擾動，有利于增加種群的多樣性。但是，變異概率太小則很難產(chǎn)生新模式，變異概

70、率太大則會使遺傳算法成為隨機搜索算法。</p><p>　　遺傳算法本質(zhì)上是對染色體模式所進行的一系列運算，即通過選擇算子將當前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進行模式重組，利用變異算子進行模式突變。通過這些遺傳操作，模式逐步向較好的方向進化，最終得到問題的最優(yōu)解。</p><p>　　2.3.4 蟻群算法信息素</p><p>　　螞蟻在走過的路線

71、上留下信息素，這樣將對后來通過的螞蟻產(chǎn)生影響，信息素可以直接設(shè)為一個常數(shù)τ，τ的大小直接關(guān)系到蟻群算法的收斂性快慢，過大則使得收斂很快，但很可能停留在局部最優(yōu)而不是全局最優(yōu)，過小則使得收斂速度變得很慢。每個螞蟻在通過路線后在此路線上直接添加τ個信息素。也可以在所有螞蟻通過完成后添加，這種稱作全局更新信息素。</p><p>　　蟻群算法中，螞蟻所留下的信息素，隨著時間的推移，將會被逐漸削弱，走過路線上面的信息素將

72、逐漸減少。一般地，每只螞蟻走完一步或者完成對所有n個節(jié)點遍歷后，應(yīng)該對信息素進行更新處理。這就相當于自然界中螞蟻通過路徑后留下的信息素會揮發(fā)一樣。</p><p>　　在螞蟻算法模型中，采用1-ρ表示信息素的揮發(fā)程度，調(diào)整公式如下:</p><p>　　τ(t+n)=(1-ρ)τ(t)+ ρτ(t) （公式2.4）</p><p>　　τ(t)=

73、 （公式2.5）</p><p>　　式中的ρ是信息素揮發(fā)因子，τ(t)表示第k只螞蟻在本次循環(huán)中通過路徑ij，并在這條路上留下信息素τ(t)，也即在ij上增加了信息量τ(t)。</p><p>　　第3章 基于改進的蟻群算法解決車輛路徑問題</p><p>　　在第二章中系統(tǒng)闡述了蟻群算法的特點和VRP的一些概念，下面將闡述如何應(yīng)用蟻群算法解決VRP問題。&

74、lt;/p><p>　　3.1 蟻群算法的改進</p><p>　　3.1.1 改進算法提出的背景</p><p>　　蟻群算法是從螞蟻群體的覓食行為中受到啟發(fā)，它利用正反饋機理和啟發(fā)式信息來搜尋最優(yōu)解，求解效率較高，但容易出現(xiàn)停滯現(xiàn)象。遺傳算法是一類仿生型優(yōu)化算法，它借鑒了生物界的物競天擇、優(yōu)勝劣汰、適者生存的自然選擇和遺傳機理，全局搜索能力強，但對于系統(tǒng)中的反饋信息

75、沒有利用，往往導(dǎo)致無為的冗余迭代，求解效率低。應(yīng)用蟻群算法和遺傳算法求解VRP，也存在各自的優(yōu)勢和缺陷，將以上兩種算法進行優(yōu)化組合，可以互補優(yōu)缺點，可以更快更好的找到最短路徑。</p><p>　　3.1.2 處理策略</p><p><b>　?。?）復(fù)制</b></p><p>　　蟻群算法中，在每一代所艘完成后，我們將當前父代中最優(yōu)的解復(fù)

76、制到子代中，使得最優(yōu)的個體能在子代中繼續(xù)積累信息素，這樣能加快算法的收斂速度。</p><p><b>　?。?）編碼</b></p><p>　　遺傳算法中的交叉和變異操作是建立在基因編碼上的，因此在引入交叉和變異操作之前，我們首先對物流配送模型進行編碼。</p><p>　　假設(shè)有L個客戶點，K輛配送車輛，本文采用的編碼方式是將這L個客戶點

77、分別用到1到這L個自然數(shù)標識；第一輛車從配送中心出發(fā)時用0標識，其他車輛則分別用L+1，L+2，……，L+K-1表示。由于同一輛車可以多次配送，所以，2次以上配送的車輛出發(fā)時，依次用L+K，L+K+1，……表示。新的一輛車從配送點出發(fā)，或者編碼結(jié)束，就表示前一輛的路線結(jié)束，返回配送中心。這樣就將一次配送表示為一組由0和自然數(shù)組成的編碼。例如，有6個客戶點，我們分別用1至6表示，3輛車負責，那么編碼：</p><p&g

78、t;　　0，1，2，3，7，4，5，8，6 </p><p>　　表示三輛車的配送路線分別是：車輛1[0→1→2→3→0],車輛3[0→4→5→0]，車輛1第二次配送[0→6→0]。</p><p><b>　　（3）交叉</b></p><p>　　交叉操作是遺傳算法中增加種群多樣性，防止算法早熟、停滯的操作。在蟻群算法中引入交叉操作，可以

79、有效地擴大搜索空間，避免算法陷入局部最優(yōu)解。</p><p>　　在蟻群算法每一代搜索完成之后，我們將其中的最優(yōu)解和次優(yōu)解進行編碼交叉操作，交叉規(guī)則如下：</p><p>　?、偌僭O(shè)兩組編碼分別是S1和S2，首先隨機生成交叉段的長度和交叉段起始位置；</p><p>　　②找出S1和S2中的交叉段，假設(shè)S1 ：P|P|P,S2:Q|Q|Q, P和Q分別是S1 和S2

80、的交叉段；將Q插入S1中，位于P前面，這樣形成新的編碼S3：P| Q| P| P；</p><p>　?、墼赟3中，刪除P 、P、P中與Q重復(fù)的編碼。形成交叉編碼S3；</p><p>　?、芡瑯拥姆椒ㄓ迷赟2上，生成新的編碼S4；</p><p>　　⑤比較S1、S2、S3、S4的結(jié)果，選出最優(yōu)的兩組編碼并保存。</p><p><b

81、>　?。?）變異</b></p><p>　　變異操作也是增加種群多樣性的一種進化手段。適度的變異，既能保持種群內(nèi)個體的多樣化，又能提高算法的效率。</p><p>　　在蟻群算法中，我們在完成交叉操作后，對種群中最優(yōu)個體進行變異操作，操作方法為：</p><p>　?、匐S機生成變異次數(shù)N；</p><p>　?、陔S機生成兩

82、個不同的自然數(shù)n，n>1（第一位不變，保證編碼以物流中心為起點）</p><p>　?、墼谧顑?yōu)個體的編碼S中，將第n位和第n位的編碼對調(diào)；</p><p>　?、苤貜?fù)②、③N次，生成新的編碼；</p><p>　?、荼容^S和的結(jié)果，保存較優(yōu)解。</p><p><b>　?。?）其他改進策略</b></p&g

83、t;<p>　　在引入遺傳算法對蟻群算法進行改進后，算法的收斂速度和全局搜索能力得到了提高。我們下面還將從信息素的更新方式、客戶點選擇策略進行改進，以提高蟻群算法的自適應(yīng)性。</p><p>　　①信息素傳遞參數(shù)的選取</p><p>　　按照基本蟻群算法，ρ是一個常量，如果ρ過大，則會使未搜索過的路徑被選擇的概率相對減小，影響全局搜索能力；而如果ρ過小，又會影響算法的收斂速

84、度。因此我們在改進算法中將對ρ作適當調(diào)整。在算法初期，我們希望算法能盡快找到較優(yōu)解，因此ρ要比較大，增大信息濃度的影響，加快算法收斂速度；而當算法停滯不前時，我們要減小ρ，從而減小信息素對蟻群的影響，增大蟻群對解空間的搜索，以脫離局部最優(yōu)解的束縛。 （公式 3.1）</p><p>　　3.1 式中，r 表示連續(xù)沒有進化的循環(huán)的次數(shù)，r 是一個常量，λ∈(0,1)是一個常量，控制ρ衰減速

85、度，ρ是ρ的最小值，防止ρ過小影響收斂速度。當r 達到預(yù)先設(shè)置的一個數(shù)值r 時，我們就減小ρ，r 重新計數(shù)，如此反復(fù)，直至ρ達到預(yù)設(shè)最小值ρ為止。</p><p>　　②確定性搜索和探索性搜索的選擇</p><p>　　加速收斂就是要在已得到的較優(yōu)解的基礎(chǔ)上，盡量快的進化，以得到更優(yōu)解。由于蟻群算法是一種啟發(fā)式算法，不斷地“探索”是蟻群算法進化的必要手段，而正是這種“探索”限制了蟻群算法收

86、斂速度。例如，當算法得到一個較優(yōu)解，而且該解有可能進一步優(yōu)化，但由于“探索”范圍很大，使得螞蟻選擇該路徑的概率相對減小，從而使得路徑上的信息量濃度逐漸衰減，該路徑也逐漸被“遺忘”了。為了解決這一問題，我們引入一個新的常量：q0∈[0,1)，螞蟻k 在每次選擇路徑之前，先隨機產(chǎn)生一個q∈[0,1)，螞蟻k 選擇路徑s 將根據(jù)下式：當q≥q0時,依照概率得到j(luò), 當q<q0 時</p><p>　　j=argm

87、ax (公式3.2)</p><p>　　公式3.2中，當q≥q0 時，是基本蟻群算法中的探索性搜索；當q<q0 時，是從已得的結(jié)果中，找出概率最大的路徑作為選擇，是對已得成果的“利用”，為確定性搜索。確定性搜索彌補了探索性搜索在收斂速度上受限制的缺陷，通過適當調(diào)整q0，能夠使得確定性搜索和探索性搜索合理搭配，加快蟻群算法的收斂速度。我們還要對q0 的取值進行討論。當q<q0 時，算法是

88、采用確定性搜索，此時螞蟻以概率q0 選擇距離最短的路徑；當q≥q0時，算法是采用探索性搜索，此時螞蟻以概率l- q0 隨機選擇路徑。在算法迭代的初期q0 選取較大的初始值，以較大的概率進行確定性搜索，這樣可以加快尋找局部較優(yōu)路徑的速度；在算法的中期q0 選取較小的值，增大探索性搜索的概率，從而擴大搜索空間；在算法的后期，恢復(fù)q0 的初始值，加快收斂的速度。</p><p><b>　　3.2 可行解問題

89、</b></p><p>　　在第二章中看到許多解決方法，但實際上，在真正的開發(fā)中，如何寫出一個好的函數(shù)來解決可行解問題是很困難的，如果一開始把螞蟻隨意灑在節(jié)點上讓其任意爬最后才來整理可行解空間，這是對資源的浪費，而且只有在螞蟻數(shù)量很多時才可能有可行解被發(fā)現(xiàn)，而且可行解的發(fā)現(xiàn)過程牽涉到回路間的相交問題，因此其本身就是一個很復(fù)雜的過程。</p><p>　　在工程中，蟻群算法的應(yīng)

90、用是一個很考驗效率的問題，如果任其亂爬，轉(zhuǎn)換為計算機資源，實際上就是對CPU和內(nèi)存的浪費，因此，我們可不可以在螞蟻爬完的時候可行解就自動出來呢？答案是肯定的，我們可以完全回避可行解問題，將可行解化到整個過程中。</p><p>　　首先，將所有螞蟻都放在配送中心，這相對于螞蟻均勻分布在節(jié)點而首先回到配送中心是一個改變，螞蟻均從配送中心出發(fā)，經(jīng)過一系列節(jié)點后回到配送中心，此時的禁忌表有所變化，已經(jīng)走過的節(jié)點從禁忌表

91、中除去，下一只螞蟻出發(fā)，它可以走的節(jié)點為第一只螞蟻走剩下的節(jié)點。這樣一只只螞蟻從原點出發(fā)，當所有節(jié)點都遍歷一遍時，所有出發(fā)的螞蟻所組成的回路自然就形成了一組可行解。</p><p>　　更新信息素方面，可以根據(jù)排序蟻群算法進行，每次產(chǎn)生一個新的可行解時，對比原來的精英螞蟻所形成的可行解集合，如果發(fā)現(xiàn)比其中某些可行解要更優(yōu)，則替換之，并在路上留下較強信息素，表示此路徑有可能比較優(yōu)越。</p><

92、p>　　下圖為蟻群算法解決VRP問題的整體流程圖，在圖3.1中，具體闡述了整個算法的框架：</p><p>　　其中，tabu表示螞蟻k尚未服務(wù)的客戶點。</p><p>　　圖3.1 用蟻群算法解決VRP問題的整體流程圖</p><p>　　還有一個重要的步驟，就是如何實現(xiàn)螞蟻的路徑選擇。這也是蟻群算法的核心所在。</p><p>

93、　　圖3.2為我們顯示出每只螞蟻構(gòu)造路徑的流程：</p><p>　　圖3.2 每只螞蟻構(gòu)造路徑的流程</p><p>　　為了在螞蟻尋找路線的過程中就確定可行解，我們一開始把所有螞蟻放在配送中心的位置，螞蟻出發(fā)后尋找下一個倉庫節(jié)點，如果在配送中心則下步允許到配送中心。通過計算每條路線的概率后，由計算機隨機生成一個概率值，利用輪盤賭的方法找到一個路線。使用公式計算出是否回到配送中心。這時

94、確定螞蟻的下一步路線，處理禁忌表。當所有節(jié)點均被遍歷并且螞蟻回到配送中心后，這只螞蟻的行程結(jié)束。在它的所有步驟中，我們并不更新信息素，因為這個螞蟻的路線可能是很差的，只針對那些精英螞蟻采用更新信息素的策略。</p><p><b>　　3.3 程序的設(shè)計</b></p><p><b>　　程序的幾個模塊；</b></p><

95、p>　　3.3.1 Ant模塊</p><p>　　算法實現(xiàn)類，定義螞蟻類，保存車輛的發(fā)車順序，車輛數(shù)組，生成隨機數(shù)，螞蟻去過和沒去過的城市等</p><p>　　#include "common.h"</p><p>　　class CAnt</p><p><b>　　{</b></p

96、><p><b>　　public:</b></p><p>　　CAnt(void);</p><p>　　~CAnt(void);</p><p><b>　　public:</b></p><p>　　int m_CarOrderAry[N_MAX_CAR_COUNT];&

97、lt;/p><p>　　ANT_VEHICLE m_CarAry[N_MAX_CAR_COUNT];double m_dbQ; </p><p>　　int m_AllowedCity[N_MAX_CITY_COUNT+1];</p><p>　　int m_nCityCount; </p><p>　　int m_nCurCity; <

98、;/p><p>　　int m_nCurCarIndex; </p><p>　　int m_nPath[N_MAX_PATH];</p><p>　　int m_nPathCount;</p><p>　　double m_dbPathLength; </p><p>　　bool m_blSearchFail; <

99、;/p><p><b>　　private:</b></p><p>　　int ChooseNextCity();</p><p>　　void Move();</p><p><b>　　public:</b></p><p>　　void Init(); </p>

100、;<p>　　void Search();</p><p>　　void CalPathLen();</p><p><b>　　}; </b></p><p>　　#include "StdAfx.h"</p><p>　　#include ".\ant.h"&l

101、t;/p><p>　　CAnt::CAnt(void)</p><p><b>　　{</b></p><p>　　memset(m_nPath,0,sizeof(m_nPath));</p><p>　　m_nPathCount=0; </p><p><b>　　}</b>&

102、lt;/p><p>　　CAnt::~CAnt(void)</p><p><b>　　{</b></p><p><b>　　}</b></p><p>　　void CAnt::Init()</p><p><b>　　{</b></p>

103、<p>　　for (int i=0;i<CAR_COUNT;i++) </p><p><b>　　{</b></p><p>　　m_CarOrderAry[i]=i;</p><p><b>　　……</b></p><p>　　void CAnt::Search()</

104、p><p><b>　　{</b></p><p>　　int nBackCount=0;</p><p>　　while (m_nCityCount < CITY_COUNT)</p><p><b>　　{</b></p><p><b>　　Move();&

105、lt;/b></p><p>　　if (m_nCurCity == 0) </p><p><b>　　{</b></p><p>　　nBackCount++;</p><p>　　if (nBackCount > CAR_COUNT)</p><p><b>　　{&l

106、t;/b></p><p>　　m_blSearchFail=true;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　els

107、e </b></p><p><b>　　{</b></p><p>　　nBackCount=0;</p><p><b>　　}</b></p><p>　　if (m_nPathCount >= N_MAX_PATH)</p><p><b>

108、;　　{</b></p><p>　　m_blSearchFail=true;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if (m_

109、blSearchFail == false)</p><p><b>　　{</b></p><p>　　CalPathLen();</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　3.3.2 Comm

110、on模塊</p><p>　　公共頭文件，定義變量和公用函數(shù)，包括城市結(jié)構(gòu)體，車輛結(jié)構(gòu)體，螞蟻車輛結(jié)構(gòu)體，蟻群算法參數(shù)等。</p><p>　　#pragma once</p><p>　　struct CITY</p><p><b>　　{</b></p><p>　　double dbX;

111、</p><p>　　double dbY; </p><p>　　double dbW; </p><p>　　double dbTB; </p><p>　　double dbTE; </p><p>　　double dbTS; </p><p><b>　　};</b&g

112、t;</p><p>　　struct VEHICLE</p><p><b>　　{</b></p><p>　　double dbMaxLength; </p><p>　　double dbMaxWeight; </p><p>　　double dbSpeed; </p>&

113、lt;p><b>　　};</b></p><p>　　struct ANT_VEHICLE</p><p><b>　　{</b></p><p>　　double dbMovedLength; </p><p>　　double dbMovedWeight; </p><

114、;p>　　double dbMovedTime; </p><p>　　int nSendCount; </p><p><b>　　};</b></p><p>　　const int N_MAX_CITY_COUNT=200;</p><p>　　const int N_MAX_ANT_COUNT=100;