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

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

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

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

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

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

6、并引用了其數(shù)學(xué)模型，并介紹了蟻群算法解決VRP問(wèn)題的方法以及現(xiàn)狀面臨的挑戰(zhàn)。并將遺傳算法的復(fù)制、交叉、變異等遺傳算子引入蟻群算法，同時(shí)改進(jìn)信息素的更新方式、客戶點(diǎn)選擇策略，以提高算法的收斂速度和全局搜索能力。</p><p>　　關(guān)鍵詞： 物流配送 車輛路徑問(wè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課題的研究?jī)?nèi)容3</p><p>　　1.3.1基本蟻群算法研究3&

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

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

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

17、/p><p>　　3.2可行解問(wèn)題16</p><p>　　3.3程序的設(shè)計(jì)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)測(cè)試分析26&

18、lt;/p><p>　　4.1單元測(cè)試26</p><p>　　4.1.1 測(cè)試126</p><p>　　4.1.2 測(cè)試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>　　參考文獻(xiàn) 31</b></p><p><b>　　引言</b></p><p>　　物流是以物品從供應(yīng)地向接收地實(shí)體流動(dòng)的過(guò)程

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

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

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

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

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

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

26、題相比有共同點(diǎn)——都是尋找遍歷所有客戶點(diǎn)的最短路徑的問(wèn)題，也有其特性——有更多更復(fù)雜的約束條件和優(yōu)化目標(biāo)。本文針對(duì)這種特點(diǎn)，研究一種基于蟻群算法的優(yōu)化路徑算法，通過(guò)引入遺傳算子，在局部搜索過(guò)程中能夠避免算法早熟、停滯，同時(shí)改進(jìn)信息素的更新方式、客戶點(diǎn)選擇策略，增強(qiáng)蟻群算法的正反饋?zhàn)饔茫瑥亩岣呤諗克俣群腿炙阉髂芰?，使得其在物流配送路徑?yōu)化問(wèn)題中有較好的實(shí)際效果。</p><p><b>　　1.2 研

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

48、客戶點(diǎn)分別用到1到這L個(gè)自然數(shù)標(biāo)識(shí)；第一輛車從配送中心出發(fā)時(shí)用0標(biāo)識(shí)，其他車輛則分別用L+1，L+2，……，L+K-1表示。由于同一輛車可以多次配送，所以，2次以上配送的車輛出發(fā)時(shí)，依次用L+K，L+K+1，……表示。新的一輛車從配送點(diǎn)出發(fā)，或者編碼結(jié)束，就表示前一輛的路線結(jié)束，返回配送中心。這樣就將一次配送表示為一組由0和自然數(shù)組成的編碼。例如，有6個(gè)客戶點(diǎn)，我們分別用1至6表示，3輛車負(fù)責(zé)，那么編碼：</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、可以有效地?cái)U(kuò)大搜索空間，避免算法陷入局部最優(yōu)解。</p><p>　　在蟻群算法每一代搜索完成之后，我們將其中的最優(yōu)解和次優(yōu)解進(jìn)行編碼交叉操作，交叉規(guī)則如下：</p><p>　?、偌僭O(shè)兩組編碼分別是S1和S2，首先隨機(jī)生成交叉段的長(zhǎng)度和交叉段起始位置；</p><p>　?、谡页鯯1和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>　?、芡瑯拥姆椒ㄓ迷赟2上，生成新的編碼S4；</p><p>　?、荼容^S1、S2、S3、S4的結(jié)果，選出最優(yōu)的兩組編碼并保存。</p><p><

52、;b>　　3）變異</b></p><p>　　變異操作也是增加種群多樣性的一種進(jìn)化手段。適度的變異，既能保持種群內(nèi)個(gè)體的多樣化，又能提高算法的效率。</p><p>　　在蟻群算法中，我們?cè)谕瓿山徊娌僮骱?，?duì)種群中最優(yōu)個(gè)體進(jìn)行變異操作，操作方法為：</p><p>　　①隨機(jī)生成變異次數(shù)N；</p><p>　?、陔S機(jī)生成

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

72、逐漸減少。一般地，每只螞蟻?zhàn)咄暌徊交蛘咄瓿蓪?duì)所有n個(gè)節(jié)點(diǎn)遍歷后，應(yīng)該對(duì)信息素進(jìn)行更新處理。這就相當(dāng)于自然界中螞蟻通過(guò)路徑后留下的信息素會(huì)揮發(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ù)]發(fā)因子，τ(t)表示第k只螞蟻在本次循環(huán)中通過(guò)路徑ij，并在這條路上留下信息素τ(t)，也即在ij上增加了信息量τ(t)。</p><p>　　第3章 基于改進(jìn)的蟻群算法解決車輛路徑問(wèn)題</p><p>　　在第二章中系統(tǒng)闡述了蟻群算法的特點(diǎn)和VRP的一些概念，下面將闡述如何應(yīng)用蟻群算法解決VRP問(wèn)題。&

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

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

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

77、分別用到1到這L個(gè)自然數(shù)標(biāo)識(shí)；第一輛車從配送中心出發(fā)時(shí)用0標(biāo)識(shí)，其他車輛則分別用L+1，L+2，……，L+K-1表示。由于同一輛車可以多次配送，所以，2次以上配送的車輛出發(fā)時(shí)，依次用L+K，L+K+1，……表示。新的一輛車從配送點(diǎn)出發(fā)，或者編碼結(jié)束，就表示前一輛的路線結(jié)束，返回配送中心。這樣就將一次配送表示為一組由0和自然數(shù)組成的編碼。例如，有6個(gè)客戶點(diǎn)，我們分別用1至6表示，3輛車負(fù)責(zé)，那么編碼：</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>　?。?）交叉</b></p><p>　　交叉操作是遺傳算法中增加種群多樣性，防止算法早熟、停滯的操作。在蟻群算法中引入交叉操作，可以

79、有效地?cái)U(kuò)大搜索空間，避免算法陷入局部最優(yōu)解。</p><p>　　在蟻群算法每一代搜索完成之后，我們將其中的最優(yōu)解和次優(yōu)解進(jìn)行編碼交叉操作，交叉規(guī)則如下：</p><p>　?、偌僭O(shè)兩組編碼分別是S1和S2，首先隨機(jī)生成交叉段的長(zhǎng)度和交叉段起始位置；</p><p>　?、谡页鯯1和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、>　　（4）變異</b></p><p>　　變異操作也是增加種群多樣性的一種進(jìn)化手段。適度的變異，既能保持種群內(nèi)個(gè)體的多樣化，又能提高算法的效率。</p><p>　　在蟻群算法中，我們?cè)谕瓿山徊娌僮骱?，?duì)種群中最優(yōu)個(gè)體進(jìn)行變異操作，操作方法為：</p><p>　?、匐S機(jī)生成變異次數(shù)N；</p><p>　?、陔S機(jī)生成兩

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

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

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

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

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

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

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

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

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

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

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

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

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

95、p>　　3.3.1 Ant模塊</p><p>　　算法實(shí)現(xiàn)類，定義螞蟻類，保存車輛的發(fā)車順序，車輛數(shù)組，生成隨機(jī)數(shù)，螞蟻去過(guò)和沒(méi)去過(guò)的城市等</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;