中國農業大學碩士學位論文STYLEREF"標題1"錯誤！文檔中沒有指定樣式的文字。智能車輛路徑規劃研究現狀文獻綜述1研究現狀路徑規劃的目的是降低交通參與者出行的時間成本和經濟成本，在最短的時間內到達目的地。這一領域內已經積攢了相當的研究成果，應用的范圍也早已不局限于手機導航、車載導航，在移動機器人、無人機的使用中，路徑規劃也有著舉足輕重的地位，因此如何短時間內選出最優路徑具備重要的研究價值。路徑規劃的常見解決方法有：Dijkstra算法、啟發式搜索算法A*、模擬退火算法、遺傳算法以及蟻群算法等。【2】1993年，楊建剛【3】博士用人工神經網絡方法來建立自主運動系統AMS的動態路徑規劃集成系統。2000年，謝秉磊[9]等人將目標約束確定為貨運量的約束與時間窗的約束，設計了一類可以將帶軟、硬時間窗的貨運問題一起同步處理的遺傳算法，提高了算法的效率和實際應用性。2001年，李嘉[10]等人將禁忌搜索算法與遺傳算法相結合，兩種算法各司其職，對混合車隊規劃車輛路徑的問題進行了求解。2003年，崔雪麗[11]等人通過對蟻群優化算法加以改進，結合實際背景，在經典VRP的基礎上對有缺貨情況下的車輛路徑問題進行了求解，并獲得較好的結果。2004年，閻慶和鮑遠律[12]將模擬退火算法與遺傳算法相結合，并加入了記憶裝置，設計了一種擁有記憶功能的遺傳模擬退火算法。實驗結果表明，該方法在一定程度上可以解決物流配送的問題，獲得高質量的解。2008年，殷志鋒[13]等人提出一種基于進化規劃與MMAS算法相融合的混合算法，并通過對車輛路徑問題的求解體現出算法的優良性能。2009年，葉偉[14]將模擬退火算法所具有的局部尋優能力以及量子粒子群算法所具有的全局尋優能力相結合，提出了一種新型混合算法并應用于求解車輛路徑問題，實驗結果體現了改進后算法收斂速度快、解的質量高的優點。2011年，劉曉勇[15]等人針對蟻群算法在求解車輛路徑問題時所體現出來的求解速度慢，解的質量差的缺點，提出了一類基于啟發式信息的蟻群算法并應用于求解有限制的車輛路徑問題。實驗結果表明，在收斂速度以及解的質量方面，該算法要優于基本蟻群算法。2021年，李文振，李富康等人通過改進轉移概率來優化螞蟻轉移規則，從而讓螞蟻對最佳柵格信息進行精準定位，還采用新啟發式信息來擴展視野和加快搜索，仿真結果表明，該改進方法在路徑搜索效率和收斂速度方面有著優秀的表現。2路徑問題的研究方法車輛路徑規劃問題是一類經典的NP問題，VRP同時也屬于組合優化問題，并且擁有廣泛的應用背景。從提出問題到現在，就受到了各個領域專業人士的廣泛關注，如運籌學、物流科學、計算機科學。因此許多針對性的算法也被提出，算法分類如圖1-1所示，圖1-1算法分類Fig1-1Algorithmclassificationdiagram主要的求解算法有下列幾種：1.精確算法能夠求出最優解的方法就是精確算法。在面對路徑規劃問題時，主要有分支定界法、割平面法、動態規劃法、網絡流算法等，其中分支定界法和動態規劃法在運籌學中都有所涉及，解決一些相對較簡單的問題。顯而易見，當用精確算法解決規模擴大后的問題時，求解用時將大幅增長，局限性明顯。分支定界法在求解整數規劃和混合整數規劃問題喜歡常用分支定界法，它通過選擇不同的分支變量和子問題來搜索迭代。它的基本思想在于每次分支后，先判斷解時候可行，若為不可行解則不再進行分支，到此為止，縮小搜索范圍。在保證可行解的情況下，繼續分支，反復進行這一過程直到無法繼續分支并得到最優解。動態規劃法二十世紀五十年代初，美國數學家貝爾曼等人在研究多階段決策過程的優化問題時，提出了著名的最優化原理，創立了動態規劃法。利用了遞歸思想，把多階段問題轉換為多個單一階段問題，從而求解。2.啟發式算法啟發式算法（heuristicalgorithm)是相對于最優化算法提出的。一個問題的最優算法求得該問題每個實例的最優解。啟發式算法可以這樣定義：一個基于直觀或經驗構造的算法，在可接受的花費（指計算時間和空間）下給出待解決組合優化問題每一個實例的一個可行解，該可行解與最優解的偏離程度一般不能被預計【】。啟發式算法的分類一般為兩種：傳統式啟發式算法和現代智能啟發算法。傳統啟發式算法相較于現代智能啟發算法來說比較簡單，易于實現。解決規模較大的路徑規劃問題時，通常可以求得局部最優解或是滿意解。而現代啟發式算法可以全面搜索解空間，超越了局部最優解。下面對常見的啟發式算法進行簡單介紹。(1)傳統啟發式算法①構造法構造法的基本思想是:按照一定的準則，將不在線路上的點逐個增加進線路中，直到所有的點都被加入到路線中為止。目前的構造法主要有Gendreau提出的GENI插入法、Solomon插入法、Gavish等人提出的并行節約法等。該類方法最早用于求解旅行商問題，后來被運用于求解車輛路徑問題。其使用起來簡單方便，但是獲得的解的質量有時候可能會比較差。②兩階段法大M法與兩階段法是在LP原問題缺少初始可行基的情況下添加人工變量，獲得單位矩陣和初始可行基，從而繼續求解。用大M法在手工計算時不會碰到麻煩，但是用計算機求解時，M的取值被計算機的最高位數限制。并且M通常要和線性規劃問題中的參數差距大，若兩者數值相近則有可能計算結果并非時原問題的真正最優解。為了避免以上的麻煩，就將需要進入人工變量的問題采用兩個階段進行解決，避免使用M。兩階段法的基本思想是:在第一階段求解目標函數的只包含人工變量的輔助問題，獲得一個可行解;第二階段在保持解可行的基礎上，在原問題上去除人工變量，繼續尋找最優解，直到無法改進。目前的兩階段法主要有Miller和Gillett提出的Sweep算法、Fisher和Jaikumar提出的算法以及Renaud提出的Petal算法等。（2）現代啟發式算法①遺傳算法(GA)遺傳算法是由JOHNHolland于1975年提出的一類優化算法。該算法主要以孟德爾的遺傳變異理論以及達爾文生物進化論中“適者生存、優勝劣汰”的思想為基礎，通過對最初的解(“先代”)不斷進行交叉、變異、選擇等操作以產生新的解(“后代”)。這類算法具有快速的全局搜索能力，通常得到的解的質量也比較好。遺傳算法的運算過程如下:步驟1:參數初始化。需要設置的參數有：種群數量M、最大迭代次數、交叉概率、變異概率。令時間t=0，并隨機生成M個初始群體。步驟2:個體評價。計算每個個體的適應度值。步驟3:選擇。根據適應度值的大小進行選擇能夠進入下一代的個體。步驟4:交叉。按交叉概率對個體進行交叉操作。步驟5:變異。按變異概率對交叉過后的個體進行變異，從而得到下一代群體。步驟6:若沒有達到算法的停止條件，則轉步驟2繼續進行以上步驟，若達到停止條件，則轉步驟7。步驟7:輸出具有最大適應度的個體。得解。遺傳算法的運算對象一般為決策變量的編碼，可以直接對結構對象進行操作，一般用于模擬生物的遺傳和進化，當然在生產調度、自動控制、數據挖掘等領域也有廣泛應用。遺傳算法和本文研究的蟻群算法一樣具有群體搜索的特性，大量個體同時搜索可以在開始時試錯，避免后期的浪費。遺傳算法具有很強的可擴展性和融合性，常與其他技術混合使用。但它同時也有明顯缺點：效率通常低于其他的優化方法，不如蟻群算法有先天優勢，因此在選擇單純算法改進時，并沒有選擇遺傳算法。圖1-2GA流程圖Fig1-2theflowchartoftheGA②粒子群算法(PSO)粒子群算法是由Kenney和Eberhart于1995年共同提出的，與遺傳算法類似，粒子群算法也是一類需要通過不斷迭代才能進行優化的算法。算法的思想來源于鳥類的捕食行為，目前己廣泛用于數據挖掘、模糊神經網絡、函數優化等各個領域。粒子群算法的運算過程如下：步驟1:初始化所有粒子，設置粒子數量M，隨機生成M個初始解及M個初始速度。步驟2:根據粒子當前所在位置和速度產生新的位置。步驟3:判斷所有粒子的適應值。更新個體極值pbest，找出全局極值gbest。步驟4:更新粒子的速度及位置。步驟5:判斷是否達到了之前設定的最大迭代次數，若是則轉步驟6，否則轉步驟2。步驟6:輸出全局極值。粒子群算法和遺傳算法都是通過初始化種群，使用適應值來評價體系，不同點在于，遺傳算法的染色體之間是共享信息的，而PSO中是由全局最值單向向其他粒子發出信號，比遺傳算法更快收斂于最優值。但粒子群算法在網絡權重的編碼和遺傳算子的選擇有些麻煩，因此也沒有選擇粒子群算法。③蟻群算法（ACA）蟻群算法是從螞蟻覓食的過程中獲得靈感，屬于仿生學算法，最早應用于求解TSP問題并取得成功。在其他方面的應用也獲得不錯的效果，例如日常生產調度問題、指派問題等。蟻群算法廣泛應用于車輛路徑規劃問題，而本文也正是需要改進蟻群算法在智能車路徑規劃問題上應用，因此在下文繼續討論蟻群算法的發展現狀。圖1-3ACA流程圖Fig1-3theflowchartoftheACA參考文獻[1]楊建剛.自主運動系統——人工神經網絡方法在ANN-AMS信息感知與規劃集成系統中的運用[D].浙江大學.1993.[9]謝秉磊.李軍.郭敦煌.有時間窗的非滿載車輛調度問題的遺傳算法[J].系統工程學報,2000,15(3):290-294.[10]李嘉,宋建海一類特殊車輛路徑問題(VRP)[J].東北大學學報:自然科學版,2001,22(3):245-248.[11]崔雪麗,馬良.有缺貨限制的VRP螞蟻算法研究[J].上海理工大學學報,2003,25(1):39-44.[12]閻慶.鮑遠律.新型遺傳模擬退火算法求解物流配送路徑問題[J].計算機應用,2004(S1):261-263.[13]殷志鋒,張巖松等.帶時間窗車輛路徑問題的混合蟻群算法[J].許昌學報,2008(02):88-90.[14]葉偉.帶時間窗車輛路徑問題的混合量子粒子群算法[J].物流科技,2009(6):35-37.[15]劉曉勇,付輝.基于啟發式蟻群算法的VRP問題研究[J].計算機工程與應用,2011,47(32):246-248.[16]李文振.李富康等.基于改進蟻群算法的移動機器人路徑規劃[J].組合機床與自動化加工技術.2021(04):49-52.[17]王曉燕等.基于改進勢場蟻群