中國農業(yè)大學碩士學位論文STYLEREF"標題1"錯誤！文檔中沒有指定樣式的文字?；谙伻核惴ǖ闹悄苘囕v路徑優(yōu)化研究國內外文獻綜述目錄TOC\o"1-3"\h\u6421基于蟻群算法的智能車輛路徑優(yōu)化研究國內外文獻綜述 1260931.1研究背景及意義 177401.2智能車輛的研究現狀 2289181.3路徑規(guī)劃的研究現狀和方法 4156841.3.1研究現狀 493711.3.2路徑問題的研究方法 5319421.4蟻群算法的研究現狀 10125151.5蟻群算法在路徑規(guī)劃中的研究現狀 111.1研究背景及意義隨著全球經濟化的時代潮流，我國的經濟快速發(fā)展，科技支持下的城市面貌日新月異地變化著。人們的出行方式從傳統(tǒng)的步行和自行車到如今各式各樣的機動車，迅猛地將自己的腳步印在更遙遠的土地上。機動車保有量的快速增長，一方面方便了人們的出行，另一方面對城市交通提出了嚴峻挑戰(zhàn)，不可避免地造成了交通擁堵。交通擁堵現象不僅浪費了大量的道路資源，還增加了城市在道路建設上的投資成本，與此同時汽車尾氣的大量排放，對環(huán)境造成了污染，影響了人們的身體健康，比如近幾十年來出現的霧霾天氣，而汽車尾氣的排放和霧霾天氣的出現難逃干系，在霧霾天氣出現時，駕駛汽車的能見度降低，行駛速度變慢，道路再次擁堵，也增大了交通運輸的壓力。為了經濟發(fā)展和促進社會產生，創(chuàng)造一個良好的交通運輸環(huán)境顯得十分必要，于是學者們提出了一個智能交通系統(tǒng)（IntelligentTrafficSystem,簡稱ITS）的理念。它傳達的主要思想是：運用先進的信息技術、通信傳輸技術以及計算機技術，建立一個實時、安全、高效地運輸系統(tǒng)。自從車輛路徑問題[3]在1959年被提及之后，越來越多的學者把它與智能交通系統(tǒng)相結合，而路徑規(guī)劃作為車輛路徑問題的解決方法之一，更是被廣泛應用于物流管理中的車輛問題與城市道路網規(guī)劃導航上，因此如何規(guī)劃路徑時，尋找一條從起點到終點可以供車輛走得又好又快的路徑，在ITS中成為一個核心問題。蟻群算法[8]（AntColonyAlgorithm,簡稱ACA）作為一種智能仿生啟發(fā)式算法，具有自適應性好、強穩(wěn)定性和正反饋等優(yōu)點，因此常被用來解決路徑尋優(yōu)問題。但蟻群算法也存在著極易陷入局部最優(yōu)解、搜索效率低下等問題。本文針對蟻群算法的現有缺點，探究問題產生的原因，提出相應的策略提高算法性能，使得算法在實際行駛中更好地輔助智能車行駛，增強乘客出行體驗，同時緩解道路擁堵狀況，節(jié)省道路資源和減少事故發(fā)。1.2智能車輛的研究現狀智能車的智能二字表明智能車比普通車擁有更多更強的能力和功能，在普通車輛上增加了傳感器、控制機構和執(zhí)行機構，主動對行駛環(huán)境中出現的人車路進行信息識別，自行將車輛的行駛狀態(tài)與復雜多變的路況相匹配，又好又快地到達乘客期望的目的地。若科技不斷進步發(fā)展，對于智能車的最理想目標是可以免去人們干預而自動駕駛車輛。正如背景所述，經濟和科技的高速發(fā)展讓越來越多的車輛進入我們的日常生產、休閑活動中，成了出行時必不可少的交通工具。但是由于人的身心狀態(tài)的不穩(wěn)定性和狀態(tài)的突發(fā)性，如今的交通事故頻發(fā)成了危害人類生命安全的殺手。在數不勝數的交通事故中，經調查發(fā)現，最主要原因是駕駛員的注意力分散。據統(tǒng)計追尾造成的事故在百分之三十，車輛路徑跑偏導致的事故占百分之二十，因此，智能車輛的研究與開發(fā)輔助駕駛員實時監(jiān)測、穩(wěn)定車輛狀態(tài)迫在眉睫，勢在必行。目前，智能車輛技術正以高智能化和高集成度的趨勢快速發(fā)展，已經成為未來車輛發(fā)展的新浪潮和新趨勢，國內外許多著名的研究機構和大學投入了大量的精力研究和開發(fā)智能車輛。人工智能車輛具有安全、節(jié)能、舒適的優(yōu)勢，在滿足了人們對車輛的基本需求之外，智能車輛的控制器技術也在不斷的完善，其廣泛的應用于自動泊車功能、穩(wěn)速下自動巡航系統(tǒng)以及緊急防撞系統(tǒng)等，既能使車輛在行駛中更安全、又能達到提高乘坐人員的舒適化程度的目的，同時也考慮了駕駛員的舒適程度和操作簡便性，解放了駕駛員的部分精力，不必長時間集中精神，造成疲勞駕駛。從發(fā)展的角度，智能車輛有兩個進程，分別是輔助駕駛進程和無人駕駛進程。根據智能化的程度不同，智能汽車可以分為5個層次：(1)無智能。車輛的構成為純機械，由駕駛員駕駛控制。(2)具有單一功能的智能車。這一類汽車一般具有某些特定的自動控制功能，例如倒車預警，用于警告周圍車輛。(3)具有多項功能的智能化。這一類車輛具有至少兩個的功能的自動控制功能，一般稱之為半自動駕駛車輛。(4)有條件的無人駕駛。這一類汽車可以在路況良好，速度保持穩(wěn)定的安全交通環(huán)境下自動駕駛，完全不需要駕駛員駕駛車輛。當駕駛情況發(fā)生變化時，車輛可以自行判斷切換回駕駛模式，為高度自動駕駛階段。(5)無人駕駛。這一類汽車可以所有時刻檢測周圍駕駛環(huán)境和路況變化，并且及時切換汽車工況保證將乘客安全快捷地帶到目的地，在過程中完全不需要人員對車輛進行操作稱之無人駕駛階段。20世紀中葉，國外的研究機構和高校己經發(fā)現了智能車輛潛在的前景，并著手對其進行深入研究，并應用于軍事方面。隨著對電動汽車的不斷研究，智能車輛技術與電動汽車的研發(fā)具有緊密的聯(lián)系，智能車輛利用控制技術以及使用傳感器檢測車輛運行信息等多種方法，為智能車輛的發(fā)展帶來新的可能和新的啟發(fā)。因此，隨著研究的不斷投入，國外在智能車輛方面已經取得部分成果。美國將智能車輛分為5個等級，分別為:無智能化駕駛、部分輔助駕駛、高度自動駕駛、完全自動駕駛以及無人駕駛，這5個等級也是智能車輛的發(fā)展趨勢美國交通部也正在不斷的研發(fā)智能車輛的產品，如賽格威兩輪平衡車,如圖1-1賽格威兩輪平衡車Fig.1-1Segwaytwo-wheelbalancingcar圖1-1，其理論時速:10-20km/h，理論續(xù)航:10-20km，具有方便、快捷、環(huán)保的優(yōu)點。德國汽車制造商研發(fā)了Klaus駕駛機器人，該車具有精細的控制系圖1-2Klaus駕駛機器人Fig.1-2Klausdriverrobot統(tǒng)和傳感機構。同時，日本各大汽車研發(fā)機構不斷的擴展實用的技術和方法，如豐田AHS智能汽車系統(tǒng)的設計，由此可看出，世界各強國都想在高端汽車領域占有一席之地。中國在智能車輛方面的研究起步較國外晚一些，但發(fā)展速度很快。由于各種條件的限制，我國與國外的智能車輛技術還存在一定的距離，還需要深入研發(fā)。2017年12月2日，深圳福田保稅區(qū)4輛全電動公交車在開放道路上首發(fā)試運行，這是中國乃至世界首次在開放道路上進行的“無人駕駛公交車”試運行，這些公交車裝有先進的雷達系統(tǒng)，能夠實時對路況信息進行反饋，它具有工作條件適應性強、反應速度快、控制精度高等優(yōu)點且自主避障能力強。在此基礎上，我國還不斷的對車輛控制器深入研究，并應用在各個領域中，為我國能更好的開發(fā)智能車輛奠定了堅實的基礎?！?】目前對于無人駕駛的開發(fā)和研究只是剛起步，取得初步成效。真正的無人駕駛應該是算法自己學會如何開車。從這個程度來看，無論是美國的無人駕駛還是中國的無人駕駛，都還處于幼兒階段，大放異彩，未來可期。而蟻群算法就是實現智能車無人駕駛前的規(guī)劃路徑任務。改進蟻群算法，選擇一條更優(yōu)質的路徑是體現智能車“智能”的第一步。1.3路徑規(guī)劃的研究現狀和方法1.3.1研究現狀路徑規(guī)劃的目的是降低交通參與者出行的時間成本和經濟成本，在最短的時間內到達目的地。這一領域內已經積攢了相當的研究成果，應用的范圍也早已不局限于手機導航、車載導航，在移動機器人、無人機的使用中，路徑規(guī)劃也有著舉足輕重的地位，因此如何短時間內選出最優(yōu)路徑具備重要的研究價值。路徑規(guī)劃的常見解決方法有：Dijkstra算法、啟發(fā)式搜索算法A*、模擬退火算法、遺傳算法以及蟻群算法等。【2】1993年，楊建剛【3】博士用人工神經網絡方法來建立自主運動系統(tǒng)AMS的動態(tài)路徑規(guī)劃集成系統(tǒng)。2000年，謝秉磊[9]等人將目標約束確定為貨運量的約束與時間窗的約束，設計了一類可以將帶軟、硬時間窗的貨運問題一起同步處理的遺傳算法，提高了算法的效率和實際應用性。2001年，李嘉[10]等人將禁忌搜索算法與遺傳算法相結合，兩種算法各司其職，對混合車隊規(guī)劃車輛路徑的問題進行了求解。2003年，崔雪麗[11]等人通過對蟻群優(yōu)化算法加以改進，結合實際背景，在經典VRP的基礎上對有缺貨情況下的車輛路徑問題進行了求解，并獲得較好的結果。2004年，閻慶和鮑遠律[12]將模擬退火算法與遺傳算法相結合，并加入了記憶裝置，設計了一種擁有記憶功能的遺傳模擬退火算法。實驗結果表明，該方法在一定程度上可以解決物流配送的問題，獲得高質量的解。2008年，殷志鋒[13]等人提出一種基于進化規(guī)劃與MMAS算法相融合的混合算法，并通過對車輛路徑問題的求解體現出算法的優(yōu)良性能。2009年，葉偉[14]將模擬退火算法所具有的局部尋優(yōu)能力以及量子粒子群算法所具有的全局尋優(yōu)能力相結合，提出了一種新型混合算法并應用于求解車輛路徑問題，實驗結果體現了改進后算法收斂速度快、解的質量高的優(yōu)點。2011年，劉曉勇[15]等人針對蟻群算法在求解車輛路徑問題時所體現出來的求解速度慢，解的質量差的缺點，提出了一類基于啟發(fā)式信息的蟻群算法并應用于求解有限制的車輛路徑問題。實驗結果表明，在收斂速度以及解的質量方面，該算法要優(yōu)于基本蟻群算法。2021年，李文振，李富康等人通過改進轉移概率來優(yōu)化螞蟻轉移規(guī)則，從而讓螞蟻對最佳柵格信息進行精準定位，還采用新啟發(fā)式信息來擴展視野和加快搜索，仿真結果表明，該改進方法在路徑搜索效率和收斂速度方面有著優(yōu)秀的表現。1.3.2路徑問題的研究方法車輛路徑規(guī)劃問題是一類經典的NP問題，VRP同時也屬于組合優(yōu)化問題，并且擁有廣泛的應用背景。從提出問題到現在，就受到了各個領域專業(yè)人士的廣泛關注，如運籌學、物流科學、計算機科學。因此許多針對性的算法也被提出，算法分類如圖1-1所示，圖1-1算法分類Fig1-1Algorithmclassificationdiagram主要的求解算法有下列幾種：1.精確算法能夠求出最優(yōu)解的方法就是精確算法。在面對路徑規(guī)劃問題時，主要有分支定界法、割平面法、動態(tài)規(guī)劃法、網絡流算法等，其中分支定界法和動態(tài)規(guī)劃法在運籌學中都有所涉及，解決一些相對較簡單的問題。顯而易見，當用精確算法解決規(guī)模擴大后的問題時，求解用時將大幅增長，局限性明顯。分支定界法在求解整數規(guī)劃和混合整數規(guī)劃問題喜歡常用分支定界法，它通過選擇不同的分支變量和子問題來搜索迭代。它的基本思想在于每次分支后，先判斷解時候可行，若為不可行解則不再進行分支，到此為止，縮小搜索范圍。在保證可行解的情況下，繼續(xù)分支，反復進行這一過程直到無法繼續(xù)分支并得到最優(yōu)解。動態(tài)規(guī)劃法二十世紀五十年代初，美國數學家貝爾曼等人在研究多階段決策過程的優(yōu)化問題時，提出了著名的最優(yōu)化原理，創(chuàng)立了動態(tài)規(guī)劃法。利用了遞歸思想，把多階段問題轉換為多個單一階段問題，從而求解。2.啟發(fā)式算法啟發(fā)式算法（heuristicalgorithm)是相對于最優(yōu)化算法提出的。一個問題的最優(yōu)算法求得該問題每個實例的最優(yōu)解。啟發(fā)式算法可以這樣定義：一個基于直觀或經驗構造的算法，在可接受的花費（指計算時間和空間）下給出待解決組合優(yōu)化問題每一個實例的一個可行解，該可行解與最優(yōu)解的偏離程度一般不能被預計【】。啟發(fā)式算法的分類一般為兩種：傳統(tǒng)式啟發(fā)式算法和現代智能啟發(fā)算法。傳統(tǒng)啟發(fā)式算法相較于現代智能啟發(fā)算法來說比較簡單，易于實現。解決規(guī)模較大的路徑規(guī)劃問題時，通常可以求得局部最優(yōu)解或是滿意解。而現代啟發(fā)式算法可以全面搜索解空間，超越了局部最優(yōu)解。下面對常見的啟發(fā)式算法進行簡單介紹。(1)傳統(tǒng)啟發(fā)式算法①構造法構造法的基本思想是:按照一定的準則，將不在線路上的點逐個增加進線路中，直到所有的點都被加入到路線中為止。目前的構造法主要有Gendreau提出的GENI插入法、Solomon插入法、Gavish等人提出的并行節(jié)約法等。該類方法最早用于求解旅行商問題，后來被運用于求解車輛路徑問題。其使用起來簡單方便，但是獲得的解的質量有時候可能會比較差。②兩階段法大M法與兩階段法是在LP原問題缺少初始可行基的情況下添加人工變量，獲得單位矩陣和初始可行基，從而繼續(xù)求解。用大M法在手工計算時不會碰到麻煩，但是用計算機求解時，M的取值被計算機的最高位數限制。并且M通常要和線性規(guī)劃問題中的參數差距大，若兩者數值相近則有可能計算結果并非時原問題的真正最優(yōu)解。為了避免以上的麻煩，就將需要進入人工變量的問題采用兩個階段進行解決，避免使用M。兩階段法的基本思想是:在第一階段求解目標函數的只包含人工變量的輔助問題，獲得一個可行解;第二階段在保持解可行的基礎上，在原問題上去除人工變量，繼續(xù)尋找最優(yōu)解，直到無法改進。目前的兩階段法主要有Miller和Gillett提出的Sweep算法、Fisher和Jaikumar提出的算法以及Renaud提出的Petal算法等。（2）現代啟發(fā)式算法①遺傳算法(GA)遺傳算法是由JOHNHolland于1975年提出的一類優(yōu)化算法。該算法主要以孟德爾的遺傳變異理論以及達爾文生物進化論中“適者生存、優(yōu)勝劣汰”的思想為基礎，通過對最初的解(“先代”)不斷進行交叉、變異、選擇等操作以產生新的解(“后代”)。這類算法具有快速的全局搜索能力，通常得到的解的質量也比較好。遺傳算法的運算過程如下:步驟1:參數初始化。需要設置的參數有：種群數量M、最大迭代次數、交叉概率、變異概率。令時間t=0，并隨機生成M個初始群體。步驟2:個體評價。計算每個個體的適應度值。步驟3:選擇。根據適應度值的大小進行選擇能夠進入下一代的個體。步驟4:交叉。按交叉概率對個體進行交叉操作。步驟5:變異。按變異概率對交叉過后的個體進行變異，從而得到下一代群體。步驟6:若沒有達到算法的停止條件，則轉步驟2繼續(xù)進行以上步驟，若達到停止條件，則轉步驟7。步驟7:輸出具有最大適應度的個體。得解。遺傳算法的運算對象一般為決策變量的編碼，可以直接對結構對象進行操作，一般用于模擬生物的遺傳和進化，當然在生產調度、自動控制、數據挖掘等領域也有廣泛應用。遺傳算法和本文研究的蟻群算法一樣具有群體搜索的特性，大量個體同時搜索可以在開始時試錯，避免后期的浪費。遺傳算法具有很強的可擴展性和融合性，常與其他技術混合使用。但它同時也有明顯缺點：效率通常低于其他的優(yōu)化方法，不如蟻群算法有先天優(yōu)勢，因此在選擇單純算法改進時，并沒有選擇遺傳算法。圖1-2GA流程圖Fig1-2theflowchartoftheGA②粒子群算法(PSO)粒子群算法是由Kenney和Eberhart于1995年共同提出的，與遺傳算法類似，粒子群算法也是一類需要通過不斷迭代才能進行優(yōu)化的算法。算法的思想來源于鳥類的捕食行為，目前己廣泛用于數據挖掘、模糊神經網絡、函數優(yōu)化等各個領域。粒子群算法的運算過程如下：步驟1:初始化所有粒子，設置粒子數量M，隨機生成M個初始解及M個初始速度。步驟2:根據粒子當前所在位置和速度產生新的位置。步驟3:判斷所有粒子的適應值。更新個體極值pbest，找出全局極值gbest。步驟4:更新粒子的速度及位置。步驟5:判斷是否達到了之前設定的最大迭代次數，若是則轉步驟6，否則轉步驟2。步驟6:輸出全局極值。粒子群算法和遺傳算法都是通過初始化種群，使用適應值來評價體系，不同點在于，遺傳算法的染色體之間是共享信息的，而PSO中是由全局最值單向向其他粒子發(fā)出信號，比遺傳算法更快收斂于最優(yōu)值。但粒子群算法在網絡權重的編碼和遺傳算子的選擇有些麻煩，因此也沒有選擇粒子群算法。③蟻群算法（ACA）蟻群算法是從螞蟻覓食的過程中獲得靈感，屬于仿生學算法，最早應用于求解TSP問題并取得成功。在其他方面的應用也獲得不錯的效果，例如日常生產調度問題、指派問題等。蟻群算法廣泛應用于車輛路徑規(guī)劃問題，而本文也正是需要改進蟻群算法在智能車路徑規(guī)劃問題上應用，因此在下文繼續(xù)討論蟻群算法的發(fā)展現狀。圖1-3ACA流程圖Fig1-3theflowchartoftheACA1.4蟻群算法的研究現狀蟻群算法是MacroDorigo首先在他的博士論文中提出的[16],是一種應用于組合優(yōu)化問題的啟發(fā)式算法。蟻群算法是基于螞蟻覓食的行為提出的，螞蟻在尋找食物的過程中，會在其爬行過的路徑上釋放信息素，并通過路徑上信息素濃度的高低來標記路徑的好壞，信息素濃度高的路徑質量好，更容易被后續(xù)螞蟻選擇，而信息素濃度低的會被其他螞蟻所忽視，整個過程體現了覓食過程的正反饋特性，并且能夠根據環(huán)境的變化做出相應的改變，所以其不僅應用于TSP問題上，也常被用于其他方面，例如電網規(guī)劃，醫(yī)學圖像分割以及云計算調度等。蟻群算法由于其強魯棒性和高并行性的優(yōu)點，使得它在路徑規(guī)劃問題上被大量應用，但它也存在著過早收斂和易陷入停滯等缺點。針對這些缺點，國內外研究者提出了多種方案來改進蟻群算法。李擎[17]融合粒子群和蟻群算法，結合精英策略和全局異步策略來更新其信息素，成功減少了蟻群算法的耗時。Wei[18]把蟻群算法與禁忌搜索算法相結合，利用兩種算法的優(yōu)點，通過二次優(yōu)化蟻群算法的初始解來提高蟻群算法的求解性能。DonggeQin[19]還提出了一種基于鄰域搜索的蟻群算法，降低了一群算法的時間復雜度。夏亞梅[20]等通過多信息素動態(tài)更新這一更新策略來優(yōu)化遺傳算法，并成功應用于QoS路,提高了算法的收斂速度。為了提高最優(yōu)解的質量，也有研究利用路徑權值矩陣來改進以權的轉移規(guī)則[21]。Bullnheimer[22]等人提出了排序蟻群系統(tǒng)通過對每只螞蟻走過的路徑長度進行排序，再根據不同路徑得到的排序結果設置不同的信息素揮發(fā)系數。T.Stutzle等人[23]結合Dorigo提出的帶精英蟻群算法的特點，提出了最大最小蟻群系統(tǒng)。在對信息素的上下限進行設置的同時，只對全局最優(yōu)螞蟻行走的路徑進行加強，在防止陷入局部最優(yōu)的同時，有效提高了算法的收斂速度。Gambardella和Dorigo[24]提出了一群系統(tǒng)通過采用偽隨機概率轉移的方式，有效避免了算法在初期容易陷入盲目搜索的問題，加快了算法的收斂速度，同時對于螞蟻未走過的路徑保持信息素不變，擴大了算法的搜索范圍，避免陷入局部最優(yōu)。在上述經典改進算法中，蟻群系統(tǒng)和最大最小蟻群系統(tǒng)在性能上有著更加優(yōu)異的表現[25]。在以上文獻中，國內外學者對蟻群算法的研究主要集中在以下三個方面:（1）針對蟻群算法數學模型的理論分析和研究，主要表現為對算法模型的改進和參數取值的分析;（2）針對傳統(tǒng)蟻群算法中收斂速度慢，容易陷入局部最優(yōu)的缺點，進行性能上的改進，常見的改進包括啟發(fā)函數的改進，信息素更新方式的改進和與其他算法相融合;（3）最后是結合蟻群算法本身的特性，將其應用到不同的實際領域中，例如路徑規(guī)劃、物流配送和網絡分析等領域。1.5蟻群算法在路徑規(guī)劃中的研究現狀關于蟻群算法在路徑規(guī)劃中的研究都是圍繞著如何提高法的收斂速度和避免局部最優(yōu)的問題展開。在文獻[26]中充分結合蟻群算法和神經網絡算法各自的優(yōu)點將改進的混合算法應用到路徑規(guī)劃中，針對離群算法容易陷入局部最優(yōu)的缺點,利用時間網絡算法的并行性保證算法的全局選優(yōu)能力，同時利用蟻群算法對神經網絡進行進一步的訓練，克服了原始算法中收斂速度慢的問題。在文獻[27]中王小燕等人結合人工市場法和蟻群算法各自的優(yōu)點，將改進的蟻群算法應用到路徑規(guī)劃中，通過引入初始路徑和改進啟發(fā)函數的方式，保證路徑質量的同時，有效提高了算法的收斂速度。在文獻[28]中將遺傳算法融入到蟻群算法中，通過蟻群算法中使用復制，交叉變異等操作，有效避免了算法容易陷入局部最優(yōu)的問題，同時克服了大多數路徑規(guī)劃結果中存在的尖峰問題.以上文獻在使用蟻群算法進行路徑規(guī)劃時，主要克服蟻群算法本身存在