路徑規(guī)劃典型算法精選(九篇)

前言：一篇好文章的誕生，需要你不斷地搜集資料、整理思路，本站小編為你收集了豐富的路徑規(guī)劃典型算法主題范文，僅供參考，歡迎閱讀并收藏。

第1篇：路徑規(guī)劃典型算法范文

（吉林工程技術師范學院信息工程學院，吉林 長春 130052）

【摘　要】本文通過對比求解最短路徑問題的Dijkstra算法和Floyd算法的設計思想、求解過程和應用實例，討論了兩種算法的特點及適用領域。

關鍵詞 最短路徑問題；Dijkstra算法；Floyd算法

作者簡介：高嵐（1979—），女，吉林長春人，碩士，吉林工程技術師范學院信息工程學院，講師，主要從事軟件工程教學研究。

0　引言

最短路徑問題是網(wǎng)絡分析中最基本的組合優(yōu)化問題之一，在公交路線網(wǎng)絡規(guī)劃中應用廣泛。因此，實際公交線網(wǎng)優(yōu)化設計中，路徑選擇算法成為一個重要研究課題，它直接關系到交通網(wǎng)絡效率、傳輸延遲和吞吐量等主要技術性能指標。

早在20世紀初，最短路徑這一重要問題就已得到人們的高度重視，當時有許多科學家研究這一問題的求解方法，但直到1959年荷蘭計算機科學家Dijkstra（迪加斯特拉）才給出這一問題求解的基本思想，成為一代經(jīng)典。當時的Dijkstra提出的這一算法主要解決的是從固定的一點到其他各點的最短路徑問題。但實際生活中要求解的可能是任意兩點間的最短距離，可采用Floyd（弗洛伊德）算法。本文通過將兩種算法進行一些對比討論，得出關于兩種算法效率和適用問題的一些結論。

1　最短路徑問題

最短路徑問題是圖論中的基本問題。在賦權圖中，找出兩點間總權和最小的路徑就是最短路徑問題。最短路徑算法包括指定頂點對之間的最短路徑算法和所有頂點間的最短路徑算法，前者對于運輸?shù)暮侠砘哂兄匾碚撘饬x，而后者的意義在于選擇合理的中轉中心，使得總費用最少。在圖論中最典型的兩種求最短路徑算法分別是Dijkstra算法和Floyd算法。

2　Dijkstra算法

2.1　算法基本思想

每次新擴展一個距離最短的點，更新與其相鄰點間距離。當所有邊的權都為正時，由于不會存在一個距離更短的沒有擴展過的點，所以這個點的距離不會再被改變，因而保證了算法的正確性。根據(jù)這個原理，采用Dijkstra算法求解最短路的圖不能有負權邊，因為擴展到負權邊的時候會產(chǎn)生更短的距離，有可能破壞已經(jīng)更新的點距離不會改變的性質(zhì)。

2.2　Dijkstra算法思想在物流配送中的應用

采用圖論中的最短路徑算法Dijkstra算法來建立物流配送路徑選擇模型，主要思想是從代表兩個頂點的距離開始，每次插入一個頂點比較任意兩點之間的已知最短路徑和插入頂點作為中間頂點時兩點間的最短路徑，得到的最終的權矩陣就反映了所有頂點間的最短距離信息。最短距離者作為費用最小者，即最佳的物流配送選址位置。

3　Floyd算法

3.1　算法基本思想

通過一個圖的權值矩陣求出它的每兩點間的最短路徑矩陣。

從圖的帶權鄰接矩陣A=[a(i,j)] n×n開始，遞歸地進行n次更新，即由矩陣D(0)=A，按一個公式，構造出矩陣D(1)；又用同樣地公式由D(1)構造出D(2)；……；最后又用同樣的公式由D(n-1)構造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點矩陣path來記錄兩點間的最短路徑。

3.2　Floyd算法在選址問題中的應用

某城市考慮建立區(qū)域內(nèi)二次供水中轉站。在選址問題中，點表示可供選址，其間連線表示運輸費用，其需求點之間運費如圖1所示。在選址中，要求該中轉站到其他站點的距離最短，即運輸費用最少，通過運用求解最短路徑的Floyd算法可求出該網(wǎng)點布局的最佳中轉站。

由計算可知，a到其他點的費用和為C(a)=33，同理C(b)=27，C(c)=18，C(d)=21，C(e)=33，比較可知c到其他各點的費用最小。因此本例從經(jīng)濟性考慮，選c點為中轉站最優(yōu)。

4　討論

典型的最短路徑求解算法Dijkstra算法和Floyd算法各有所長。Dijkstra算法可為任一源節(jié)點找出與其它所有節(jié)點的最短路徑，是目前公認的較好的最短路徑算法，但由于它遍歷計算的節(jié)點很多，所以效率低。Floyd算法是一種用于尋找給定的加權圖中頂點間最短路徑的算法，是一種動態(tài)規(guī)劃算法，可以算出任意兩個節(jié)點之間的最短距離，代碼編寫簡單，但是Floyd算法計算最短路徑時時間復雜比較高，不適合計算大量數(shù)據(jù)。

綜上，求解單源點無負權邊最短路徑可采用Dijkstra算法，而求所有點最短路徑應用Floyd算法。對于稀疏圖，采用n次Dijkstra算法比較出色，對于稠密圖，適用Floyd算法。

5　結束語

本文通過對比兩種求解最短路徑算法的設計思想、求解過程、應用實例，討論了算法的特點及適用領域。了解算法求解問題的差異，針對不同類型問題采取對應的求解算法，將大大提升解決問題的效率，對實際生產(chǎn)生活起到重要作用。

參考文獻

［1］辛建亭,胡萍.圖論在通訊網(wǎng)中的應用[J].2009,3.

［2］凡金偉,呂康.基于Dijkstra算法在物流配送中的應用[J].電腦編程技巧與維護,2009(4):39-45.

［3］鄧春燕.兩種最短路徑算法的比較[J].電腦知識與技術,2008(12):511-512.

［4］徐鳳生.求最短路徑的新算法[J].計算機工程與科學,2006,2.

［5］殷劍宏,吳開亞.圖論及其算法[M].合肥:中國科學技術大學出版社,2005.

［6］陳玉華.淺談圖論在現(xiàn)實生活中的應用[J].云南省教育學院學報,2004.

［7］王燕,蔣笑梅.配送中心全程規(guī)劃[M].北京:機械工業(yè)出版社,2004.

第2篇：路徑規(guī)劃典型算法范文

單個機器人的路徑規(guī)劃是找出從起始點至終點的一條最短無碰路徑。多個機器人的路徑規(guī)劃側重考慮整個系統(tǒng)的最優(yōu)路徑，如系統(tǒng)的總耗時間最少路徑或是系統(tǒng)總路徑最短等。從目前國內(nèi)外的研究來看，在規(guī)劃多機器人路徑時，更多考慮的是多機器人之間的協(xié)調(diào)和合作式的路徑規(guī)劃。

目前國內(nèi)外多機器人路徑規(guī)劃研究方法分為傳統(tǒng)方法、智能優(yōu)化方法和其他方法三大類。其中傳統(tǒng)方法主要有基于圖論的方法（如可視圖法、自由空間法、柵格法、Voronoi圖法以及人工勢場方法等）；智能優(yōu)化方法主要有遺傳算法、蟻群算法、免疫算法、神經(jīng)網(wǎng)絡、強化學習等；其他方法主要有動態(tài)規(guī)劃、最優(yōu)控制算法、模糊控制等。它們中的大部分都是從單個機器人路徑規(guī)劃方法擴展而來的。

1）傳統(tǒng)方法多機器人路徑規(guī)劃傳統(tǒng)方法的特點主要體現(xiàn)在基于圖論的基礎上。方法一般都是先將環(huán)境構建成一個圖，然后再從圖中尋找最優(yōu)的路徑。其優(yōu)點是比較簡單，比較容易實現(xiàn)；缺點是得到的路徑有可能不是最優(yōu)路徑，而是次優(yōu)路徑。薄喜柱等人[4]提出的一種新路徑規(guī)劃方法的基本思想就是基于柵格類的環(huán)境表示和障礙地圖的。而人工勢場方法的基本思想是將移動機器人在環(huán)境中的運動視為一種虛擬人工受力場中的運動。障礙物對移動機器人產(chǎn)生斥力，目標點產(chǎn)生引力，引力和斥力周圍由一定的算法產(chǎn)生相應的勢，機器人在勢場中受到抽象力作用,抽象力使得機器人繞過障礙物。其優(yōu)點是適合未知環(huán)境下的規(guī)劃，不會出現(xiàn)維數(shù)爆炸問題；但是人工勢場法也容易陷入局部最小，并且存在丟失解的部分有用信息的可能。顧國昌等人[5]提出了引用總體勢減小的動態(tài)調(diào)度技術的多機器人路徑規(guī)劃，較好地解決了這個問題。

2）智能優(yōu)化方法多機器人路徑規(guī)劃的智能優(yōu)化方（算）法是隨著近年來智能計算發(fā)展而產(chǎn)生的一些新方法。其相對于傳統(tǒng)方法更加智能化，且日益成為國內(nèi)外研究的重點。

遺傳算法是近年來計算智能研究的熱點，作為一種基于群體進化的概率優(yōu)化方法，適用于處理傳統(tǒng)搜索算法難以解決的復雜和非線性問題，如多機器的路徑規(guī)劃問題。在路徑規(guī)劃中，其基本思想是先用鏈接圖法把環(huán)境地圖構建成一個路徑節(jié)點鏈接網(wǎng)，將路徑個體表達為路徑中一系列中途節(jié)點，并轉換為二進制串；然后進行遺傳操作（如選擇、交叉、復制、變異），經(jīng)過N次進化，輸出當前的最優(yōu)個體即機器人的最優(yōu)路徑。遺傳算法的缺點是運算速度不快，進化眾多的規(guī)劃要占據(jù)很大的存儲空間和運算時間；優(yōu)點是有效避免了局部極小值問題，且計算量較小。

孫樹棟等人[6，7]在這方面較早地展開了研究，提出的基于集中協(xié)調(diào)思想的一種混合遺傳算法來規(guī)劃多機器人路徑方法較好地解決了避障問題。但不足的是該方法必須建立環(huán)境地圖，在環(huán)境未知情況下的規(guī)劃沒有得到很好的解決；且規(guī)劃只能保證找到一個比較滿意的解，在求解全局最優(yōu)解時仍有局限。

文獻[8]中提出的一種基于定長十進編碼方法有效降低了遺傳算法的編碼難度，克服了已有的變長編碼機制及定長二進制編碼機制需特殊遺傳操作算子和特殊解碼的缺陷,使得算法更加簡單有效。

智能計算的另一種常見的方法——蟻群算法屬于隨機搜索的仿生算法。其基本思想是模擬螞蟻群體的覓食運動過程來實現(xiàn)尋優(yōu)，通過螞蟻群體中各個體之間的相互作用，分布、并行地解決組合優(yōu)化問題。該算法同樣比較適合解決多機器人的路徑規(guī)劃問題。

朱慶保[9]提出了在全局未知環(huán)境下多機器人運動螞蟻導航算法。該方法將全局目標點映射到機器人視野域邊界附近作為局部導航子目標，再由兩組螞蟻相互協(xié)作完成機器人視野域內(nèi)局部最優(yōu)路徑的搜索，然后在此基礎上進行與其他機器人的碰撞預測與避碰規(guī)劃。因此，機器人的前進路徑不斷被動態(tài)修改，從而在每條局部優(yōu)化路徑引導下，使機器人沿一條全局優(yōu)化的路徑到達目標點。但其不足是在動態(tài)不確定的環(huán)境中路徑規(guī)劃時間開銷劇增，而且機器人缺乏必要的學習，以至于整個機器人系統(tǒng)路徑難以是最優(yōu)路徑。

強化學習[10，11](又稱再激勵學習)是一種重要的機器學習方法。它是一種智能體從環(huán)境狀態(tài)到行為映射的學習，使得行為從環(huán)境中獲得積累獎賞值最大。其原理如圖1所示。

強化學習算法一般包含了兩個步驟：a）從當前學習循環(huán)的值函數(shù)確定新的行為策略；b）在新的行為策略指導下，通過所獲得的瞬時獎懲值對該策略進行評估。學習循環(huán)過程如下所示，直到值函數(shù)和策略收斂:

v0π1v1π2…v*π*v*

目前比較常見的強化學習方法有：MonteCarlo方法、動態(tài)規(guī)劃方法、TD（時間差分）方法。其中TD算法包含Sarsa算法、Q學習算法以及Dyna-Q算法等。其Q值函數(shù)迭代公式分別為

TD（0）策略：V(si)V(si)+α[γi+1+γV(si+1)-V(si)]

Sarsa算法：Q(st,at)Q(st,at)+α[γt+1+γQ(st+1,at.+1)-Q(st,at)]Qs′學習算法：Qπ(s,a)=∑Pαss′[Rass′+γVπ(s′)]

近年來，基于強化學習的路徑規(guī)劃日益成為國內(nèi)外學者研究的熱點。M.J.Mataric[12]首次把強化學習引入到多機器人環(huán)境中。而基于強化學習的多機器人路徑規(guī)劃的優(yōu)點主要體現(xiàn)在：無須建立精確的環(huán)境模型，簡化了智能體的編程；無須構建環(huán)境地圖；強化學習可以把路徑規(guī)劃、避碰、避障、協(xié)作等問題統(tǒng)一解決。

張芳等人[13]提出了基于再激勵協(xié)調(diào)避障路徑規(guī)劃方法，把再勵函數(shù)設計為基于行為分解的無模型非均勻結構，新的再勵函數(shù)結構使得學習速度得以提高且有較好的魯棒性。同時，證明了在路徑規(guī)劃中，機器人的趨向目標和避障行為密切相關，對反映各基本行為的再勵函數(shù)取加權和來表示總的再勵函數(shù)要優(yōu)于取直接和的表示方式，也反映了再勵函數(shù)設計得合理與否及其確切程度將影響再勵學習的收斂速度。王醒策等人[14]在動態(tài)編隊的強化學習算法方面展開了研究。宋一然[15]則提出了分段再勵函數(shù)的強化學習方法進行路徑規(guī)劃。其缺點是學習次數(shù)較多、效率不高，當機器人數(shù)目增加時，它有可能面臨維數(shù)災難的困難。所以，基于強化學習的路徑規(guī)劃在多機器人環(huán)境下的學習將變得比較困難，需要對傳統(tǒng)的強化學習加以優(yōu)化，如基于人工神經(jīng)網(wǎng)絡的強化學習[16]等。

3)其他方法除了以上國內(nèi)外幾種比較常見且研究較多的方法外，還有唐振民等人[17]提出的基于動態(tài)規(guī)劃思想的多機器人路徑規(guī)劃，把運籌學中的動態(tài)規(guī)劃思想與Dijkstra算法引入到多機器人的路徑規(guī)劃中，用動態(tài)規(guī)劃的基本思想來解決圖論中的費用流問題和路徑規(guī)劃中的層級動態(tài)聯(lián)盟問題。其選擇距離鄰近法作為聯(lián)盟參考依據(jù)。一個機器人的鄰居是指在地理位置上分布在這個機器人周圍的其他機器人；與該機器人最近鄰的機器人為第一層鄰居,第一層鄰居的鄰居為該機器人的第二層鄰居,依此類推。那么層級越高（即越近)的鄰居,它滿足協(xié)作要求的可能性越大。動態(tài)規(guī)劃算法實質(zhì)上是一種以空間換時間的技術，它在實現(xiàn)的過程中，必須存儲產(chǎn)生過程中的各種狀態(tài)，其空間復雜度要大于其他算法，故動態(tài)規(guī)劃方法比較適合多機器人的全局路徑規(guī)劃。

孫茂相等人[18]提出了最優(yōu)控制與智能決策相結合的多移動機器人路徑規(guī)劃方法。其首先構造一個以各機器人最優(yōu)運動狀態(tài)數(shù)據(jù)庫為核心的實時專家系統(tǒng),在離線狀態(tài)下完成;然后各機器人在此專家系統(tǒng)的支持下,以最優(yōu)規(guī)劃策略為基礎,采用速度遷移算法,自主決定其控制。該方法擁有較好的穩(wěn)定性與復雜度。焦立男等人[19]提出的基于局部傳感和通信的多機器人運動規(guī)劃框架較好地解決了多機器人路徑規(guī)劃在局部在線規(guī)劃的系統(tǒng)框架問題。沈捷等人[20]提出了保持隊形的多移動機器人路徑規(guī)劃。以基于行為的導航算法為基礎,把機器人隊列的運動過程劃分為正常運動、避障和恢復隊形三個階段。在避障階段,引入虛擬機器人使隊形保持部分完整;當隊形被嚴重打亂時,規(guī)劃機器人的局部目標位姿使隊列快速恢復隊形。其算法重點為避障機器人進入避障狀態(tài),暫時脫離隊列,并以虛擬機器人代替避障機器人。

2多機器人避碰和避障

避障和避碰是多機器人路徑規(guī)劃研究中需要考慮的重點問題之一。避障和避碰主要討論的內(nèi)容有防止碰撞；沖突消解、避免擁塞；如何避免死鎖。在路徑規(guī)劃中常見的多機器人避障方法[21]有主從控制法、動態(tài)優(yōu)先法（建立在機器人之間的通信協(xié)商上）、交通規(guī)則法、速率調(diào)整法，以及障礙物膨脹法、基于人工勢場的方法等。

目前國內(nèi)外對于多機器人避障展開的研究還不是很多，比較典型的有徐潼等人[22]以Th.Fraichard的思想為基礎，擴充并完善了路徑/速度分解方案來協(xié)調(diào)多機器人,設立集中管理agent進行整體規(guī)劃，為每個機器人規(guī)劃路徑；并根據(jù)優(yōu)先級規(guī)則對運動特征進行分布式規(guī)劃以避免機器人間的沖突。周明等人[23]提出分布式智能避撞規(guī)劃系統(tǒng)，將原來比較復雜的大系統(tǒng)轉換為相對簡單的子系統(tǒng)問題,由各智能機器人依據(jù)任務要求和環(huán)境變化,獨立調(diào)整自身運動狀態(tài),完成任務的分布式智能決策體系結構。任炏等人[24]提出了基于過程獎賞和優(yōu)先掃除的強化學習多機器人系統(tǒng)的沖突消解方法。該算法能夠顯著減少沖突,避免死鎖,提高了系統(tǒng)整體性能。歐錦軍等人[25]提出了通過調(diào)整機器人的運動速度實現(xiàn)多機器人避碰，將避碰問題轉換為高維線性空間的優(yōu)化問題,并進一步將其轉換為線性方程的求解。該方法的缺點是系統(tǒng)的復雜度較高、計算量太大。

人工勢場方法的特點是計算簡潔、實時性強、便于數(shù)學描述，且適合于多自由度機器人環(huán)境，但容易產(chǎn)生抖動和陷入局部極小。為了克服其缺點，景興建等人[26]提出了人工協(xié)調(diào)場的方法，在傳統(tǒng)排斥力場中增加一個協(xié)調(diào)力,并將吸引力、排斥力和協(xié)調(diào)力與局部環(huán)境下機器人的運動狀態(tài)和運動要求結合起來，有效地保證機器人的安全性，提高機器人在復雜動態(tài)環(huán)境下行為決策的準確性和魯棒性。

3多機器人協(xié)作和協(xié)調(diào)機制

多機器人間的運動協(xié)調(diào)[27~31]是多機器人路徑規(guī)劃的關鍵，也是多機器人與單機器人路徑規(guī)劃相區(qū)別的根本所在。多機器人系統(tǒng)在復雜動態(tài)實時環(huán)境下，由于受到時間、資源及任務要求的約束，需要在有限時間、資源的情況下進行資源分配、任務調(diào)配、沖突解決等協(xié)調(diào)合作問題，而機器人間的協(xié)調(diào)與協(xié)作，能夠大大地提高整個系統(tǒng)的效率和魯棒性，成為系統(tǒng)完成控制或解決任務的關鍵。

目前已有的協(xié)調(diào)方式分為集中式、分布式和混合式三種。在集中式協(xié)調(diào)中，集中規(guī)劃器詳細地規(guī)劃出每個機器人的動作，通常的做法是將多個機器人看做一個多自由度的機器人進行規(guī)劃；而分布式協(xié)調(diào)規(guī)劃中，機器人之間進行合作，將一個任務分成多個子任務，根據(jù)各自的特點完成不同的子任務，從而共同完成總任務；混合式協(xié)調(diào)是集中式和分布式混合在一起的形式。

摘要：在查閱大量文獻的基礎上對多機器人路徑規(guī)劃的主要研究內(nèi)容和研究現(xiàn)狀進行了分析和總結，討論了多機器人路徑規(guī)劃方法的評判標準，并闡述了研究遇到的瓶頸問題，展望了多機器人路徑規(guī)劃方法的發(fā)展趨勢。

關鍵詞：多機器人；路徑規(guī)劃；強化學習；評判準則

Abstract:Thispaperanalyzedandconcludedthemainmethodandcurrentresearchofthepathplanningresearchformultirobot.Thendiscussedthecriterionofpathplanningresearchformultirobotbasedlargeofliterature.Meanwhile,itexpoundedthebottleneckofthepathplanningresearchformultirobot，forecastedthefuturedevelopmentofmultirobotpathplanning.

Keywords:multirobot；pathplanning;reinforcementlearning;evaluatingcriteria

近年來，分布式人工智能(DAI)成為人工智能研究的一個重要分支。DAI研究大致可以分為DPS（distributedproblemsolving）和MAS（multiagentsystem）兩個方面。一些從事機器人學的研究人員受多智能體系統(tǒng)研究的啟發(fā)，將智能體概念應用于多機器人系統(tǒng)的研究中，將單個機器人視做一個能獨立執(zhí)行特定任務的智能體，并把這種多機器人系統(tǒng)稱為多智能體機器人系統(tǒng)（MARS）。因此，本文中多機器人系統(tǒng)等同于多智能體機器人系統(tǒng)。目前，多機器人系統(tǒng)已經(jīng)成為學術界研究的熱點,而路徑規(guī)劃研究又是其核心部分。

機器人路徑規(guī)劃問題可以建模為一個帶約束的優(yōu)化問題，其包括地理環(huán)境信息建模、路徑規(guī)劃、定位和避障等任務，它是移動機器人導航與控制的基礎。單個移動機器人路徑規(guī)劃研究一直是機器人研究的重點，且已經(jīng)有許多成果[1~3]，例如在靜態(tài)環(huán)境中常見的有連接圖法、可視圖法、切線圖法、Voronoi圖法、自由空間法、柵格法、拓撲法、鏈接圖法、DempsterShafer證據(jù)理論建圖等；動態(tài)環(huán)境中常見的有粒子群算法、免疫算法、遺傳算法、神經(jīng)網(wǎng)絡、蟻群算法、模擬退火算法、人工勢場法等。然而，多機器人路徑規(guī)劃研究比單個機器人路徑規(guī)劃要復雜得多，必須考慮多機器人系統(tǒng)中機器人之間的避碰機制、機器人之間的相互協(xié)作機制、通信機制等問題。

1多機器人路徑規(guī)劃方法

單個機器人的路徑規(guī)劃是找出從起始點至終點的一條最短無碰路徑。多個機器人的路徑規(guī)劃側重考慮整個系統(tǒng)的最優(yōu)路徑，如系統(tǒng)的總耗時間最少路徑或是系統(tǒng)總路徑最短等。從目前國內(nèi)外的研究來看，在規(guī)劃多機器人路徑時，更多考慮的是多機器人之間的協(xié)調(diào)和合作式的路徑規(guī)劃。

目前國內(nèi)外多機器人路徑規(guī)劃研究方法分為傳統(tǒng)方法、智能優(yōu)化方法和其他方法三大類。其中傳統(tǒng)方法主要有基于圖論的方法（如可視圖法、自由空間法、柵格法、Voronoi圖法以及人工勢場方法等）；智能優(yōu)化方法主要有遺傳算法、蟻群算法、免疫算法、神經(jīng)網(wǎng)絡、強化學習等；其他方法主要有動態(tài)規(guī)劃、最優(yōu)控制算法、模糊控制等。它們中的大部分都是從單個機器人路徑規(guī)劃方法擴展而來的。

1）傳統(tǒng)方法多機器人路徑規(guī)劃傳統(tǒng)方法的特點主要體現(xiàn)在基于圖論的基礎上。方法一般都是先將環(huán)境構建成一個圖，然后再從圖中尋找最優(yōu)的路徑。其優(yōu)點是比較簡單，比較容易實現(xiàn)；缺點是得到的路徑有可能不是最優(yōu)路徑，而是次優(yōu)路徑。薄喜柱等人[4]提出的一種新路徑規(guī)劃方法的基本思想就是基于柵格類的環(huán)境表示和障礙地圖的。而人工勢場方法的基本思想是將移動機器人在環(huán)境中的運動視為一種虛擬人工受力場中的運動。障礙物對移動機器人產(chǎn)生斥力，目標點產(chǎn)生引力，引力和斥力周圍由一定的算法產(chǎn)生相應的勢，機器人在勢場中受到抽象力作用,抽象力使得機器人繞過障礙物。其優(yōu)點是適合未知環(huán)境下的規(guī)劃，不會出現(xiàn)維數(shù)爆炸問題；但是人工勢場法也容易陷入局部最小，并且存在丟失解的部分有用信息的可能。顧國昌等人[5]提出了引用總體勢減小的動態(tài)調(diào)度技術的多機器人路徑規(guī)劃，較好地解決了這個問題。

2）智能優(yōu)化方法多機器人路徑規(guī)劃的智能優(yōu)化方（算）法是隨著近年來智能計算發(fā)展而產(chǎn)生的一些新方法。其相對于傳統(tǒng)方法更加智能化，且日益成為國內(nèi)外研究的重點。

遺傳算法是近年來計算智能研究的熱點，作為一種基于群體進化的概率優(yōu)化方法，適用于處理傳統(tǒng)搜索算法難以解決的復雜和非線性問題，如多機器的路徑規(guī)劃問題。在路徑規(guī)劃中，其基本思想是先用鏈接圖法把環(huán)境地圖構建成一個路徑節(jié)點鏈接網(wǎng)，將路徑個體表達為路徑中一系列中途節(jié)點，并轉換為二進制串；然后進行遺傳操作（如選擇、交叉、復制、變異），經(jīng)過N次進化，輸出當前的最優(yōu)個體即機器人的最優(yōu)路徑。遺傳算法的缺點是運算速度不快，進化眾多的規(guī)劃要占據(jù)很大的存儲空間和運算時間；優(yōu)點是有效避免了局部極小值問題，且計算量較小。

孫樹棟等人[6，7]在這方面較早地展開了研究，提出的基于集中協(xié)調(diào)思想的一種混合遺傳算法來規(guī)劃多機器人路徑方法較好地解決了避障問題。但不足的是該方法必須建立環(huán)境地圖，在環(huán)境未知情況下的規(guī)劃沒有得到很好的解決；且規(guī)劃只能保證找到一個比較滿意的解，在求解全局最優(yōu)解時仍有局限。

文獻[8]中提出的一種基于定長十進編碼方法有效降低了遺傳算法的編碼難度，克服了已有的變長編碼機制及定長二進制編碼機制需特殊遺傳操作算子和特殊解碼的缺陷,使得算法更加簡單有效。

智能計算的另一種常見的方法——蟻群算法屬于隨機搜索的仿生算法。其基本思想是模擬螞蟻群體的覓食運動過程來實現(xiàn)尋優(yōu)，通過螞蟻群體中各個體之間的相互作用，分布、并行地解決組合優(yōu)化問題。該算法同樣比較適合解決多機器人的路徑規(guī)劃問題。

朱慶保[9]提出了在全局未知環(huán)境下多機器人運動螞蟻導航算法。該方法將全局目標點映射到機器人視野域邊界附近作為局部導航子目標，再由兩組螞蟻相互協(xié)作完成機器人視野域內(nèi)局部最優(yōu)路徑的搜索，然后在此基礎上進行與其他機器人的碰撞預測與避碰規(guī)劃。因此，機器人的前進路徑不斷被動態(tài)修改，從而在每條局部優(yōu)化路徑引導下，使機器人沿一條全局優(yōu)化的路徑到達目標點。但其不足是在動態(tài)不確定的環(huán)境中路徑規(guī)劃時間開銷劇增，而且機器人缺乏必要的學習，以至于整個機器人系統(tǒng)路徑難以是最優(yōu)路徑。

強化學習[10，11](又稱再激勵學習)是一種重要的機器學習方法。它是一種智能體從環(huán)境狀態(tài)到行為映射的學習，使得行為從環(huán)境中獲得積累獎賞值最大。其原理如圖1所示。

強化學習算法一般包含了兩個步驟：a）從當前學習循環(huán)的值函數(shù)確定新的行為策略；b）在新的行為策略指導下，通過所獲得的瞬時獎懲值對該策略進行評估。學習循環(huán)過程如下所示，直到值函數(shù)和策略收斂:

v0π1v1π2…v*π*v*

目前比較常見的強化學習方法有：MonteCarlo方法、動態(tài)規(guī)劃方法、TD（時間差分）方法。其中TD算法包含Sarsa算法、Q學習算法以及Dyna-Q算法等。其Q值函數(shù)迭代公式分別為

TD（0）策略：V(si)V(si)+α[γi+1+γV(si+1)-V(si)]

Sarsa算法：Q(st,at)Q(st,at)+α[γt+1+γQ(st+1,at.+1)-Q(st,at)]Qs′學習算法：Qπ(s,a)=∑Pαss′[Rass′+γVπ(s′)]

近年來，基于強化學習的路徑規(guī)劃日益成為國內(nèi)外學者研究的熱點。M.J.Mataric[12]首次把強化學習引入到多機器人環(huán)境中。而基于強化學習的多機器人路徑規(guī)劃的優(yōu)點主要體現(xiàn)在：無須建立精確的環(huán)境模型，簡化了智能體的編程；無須構建環(huán)境地圖；強化學習可以把路徑規(guī)劃、避碰、避障、協(xié)作等問題統(tǒng)一解決。

張芳等人[13]提出了基于再激勵協(xié)調(diào)避障路徑規(guī)劃方法，把再勵函數(shù)設計為基于行為分解的無模型非均勻結構，新的再勵函數(shù)結構使得學習速度得以提高且有較好的魯棒性。同時，證明了在路徑規(guī)劃中，機器人的趨向目標和避障行為密切相關，對反映各基本行為的再勵函數(shù)取加權和來表示總的再勵函數(shù)要優(yōu)于取直接和的表示方式，也反映了再勵函數(shù)設計得合理與否及其確切程度將影響再勵學習的收斂速度。王醒策等人[14]在動態(tài)編隊的強化學習算法方面展開了研究。宋一然[15]則提出了分段再勵函數(shù)的強化學習方法進行路徑規(guī)劃。其缺點是學習次數(shù)較多、效率不高，當機器人數(shù)目增加時，它有可能面臨維數(shù)災難的困難。所以，基于強化學習的路徑規(guī)劃在多機器人環(huán)境下的學習將變得比較困難，需要對傳統(tǒng)的強化學習加以優(yōu)化，如基于人工神經(jīng)網(wǎng)絡的強化學習[16]等。

3)其他方法除了以上國內(nèi)外幾種比較常見且研究較多的方法外，還有唐振民等人[17]提出的基于動態(tài)規(guī)劃思想的多機器人路徑規(guī)劃，把運籌學中的動態(tài)規(guī)劃思想與Dijkstra算法引入到多機器人的路徑規(guī)劃中，用動態(tài)規(guī)劃的基本思想來解決圖論中的費用流問題和路徑規(guī)劃中的層級動態(tài)聯(lián)盟問題。其選擇距離鄰近法作為聯(lián)盟參考依據(jù)。一個機器人的鄰居是指在地理位置上分布在這個機器人周圍的其他機器人；與該機器人最近鄰的機器人為第一層鄰居,第一層鄰居的鄰居為該機器人的第二層鄰居,依此類推。那么層級越高（即越近)的鄰居,它滿足協(xié)作要求的可能性越大。動態(tài)規(guī)劃算法實質(zhì)上是一種以空間換時間的技術，它在實現(xiàn)的過程中，必須存儲產(chǎn)生過程中的各種狀態(tài)，其空間復雜度要大于其他算法，故動態(tài)規(guī)劃方法比較適合多機器人的全局路徑規(guī)劃。

孫茂相等人[18]提出了最優(yōu)控制與智能決策相結合的多移動機器人路徑規(guī)劃方法。其首先構造一個以各機器人最優(yōu)運動狀態(tài)數(shù)據(jù)庫為核心的實時專家系統(tǒng),在離線狀態(tài)下完成;然后各機器人在此專家系統(tǒng)的支持下,以最優(yōu)規(guī)劃策略為基礎,采用速度遷移算法,自主決定其控制。該方法擁有較好的穩(wěn)定性與復雜度。焦立男等人[19]提出的基于局部傳感和通信的多機器人運動規(guī)劃框架較好地解決了多機器人路徑規(guī)劃在局部在線規(guī)劃的系統(tǒng)框架問題。沈捷等人[20]提出了保持隊形的多移動機器人路徑規(guī)劃。以基于行為的導航算法為基礎,把機器人隊列的運動過程劃分為正常運動、避障和恢復隊形三個階段。在避障階段,引入虛擬機器人使隊形保持部分完整;當隊形被嚴重打亂時,規(guī)劃機器人的局部目標位姿使隊列快速恢復隊形。其算法重點為避障機器人進入避障狀態(tài),暫時脫離隊列,并以虛擬機器人代替避障機器人。

2多機器人避碰和避障

避障和避碰是多機器人路徑規(guī)劃研究中需要考慮的重點問題之一。避障和避碰主要討論的內(nèi)容有防止碰撞；沖突消解、避免擁塞；如何避免死鎖。在路徑規(guī)劃中常見的多機器人避障方法[21]有主從控制法、動態(tài)優(yōu)先法（建立在機器人之間的通信協(xié)商上）、交通規(guī)則法、速率調(diào)整法，以及障礙物膨脹法、基于人工勢場的方法等。

目前國內(nèi)外對于多機器人避障展開的研究還不是很多，比較典型的有徐潼等人[22]以Th.Fraichard的思想為基礎，擴充并完善了路徑/速度分解方案來協(xié)調(diào)多機器人,設立集中管理agent進行整體規(guī)劃，為每個機器人規(guī)劃路徑；并根據(jù)優(yōu)先級規(guī)則對運動特征進行分布式規(guī)劃以避免機器人間的沖突。周明等人[23]提出分布式智能避撞規(guī)劃系統(tǒng)，將原來比較復雜的大系統(tǒng)轉換為相對簡單的子系統(tǒng)問題,由各智能機器人依據(jù)任務要求和環(huán)境變化,獨立調(diào)整自身運動狀態(tài),完成任務的分布式智能決策體系結構。任炏等人[24]提出了基于過程獎賞和優(yōu)先掃除的強化學習多機器人系統(tǒng)的沖突消解方法。該算法能夠顯著減少沖突,避免死鎖,提高了系統(tǒng)整體性能。歐錦軍等人[25]提出了通過調(diào)整機器人的運動速度實現(xiàn)多機器人避碰，將避碰問題轉換為高維線性空間的優(yōu)化問題,并進一步將其轉換為線性方程的求解。該方法的缺點是系統(tǒng)的復雜度較高、計算量太大。

人工勢場方法的特點是計算簡潔、實時性強、便于數(shù)學描述，且適合于多自由度機器人環(huán)境，但容易產(chǎn)生抖動和陷入局部極小。為了克服其缺點，景興建等人[26]提出了人工協(xié)調(diào)場的方法，在傳統(tǒng)排斥力場中增加一個協(xié)調(diào)力,并將吸引力、排斥力和協(xié)調(diào)力與局部環(huán)境下機器人的運動狀態(tài)和運動要求結合起來，有效地保證機器人的安全性，提高機器人在復雜動態(tài)環(huán)境下行為決策的準確性和魯棒性。

3多機器人協(xié)作和協(xié)調(diào)機制

多機器人間的運動協(xié)調(diào)[27~31]是多機器人路徑規(guī)劃的關鍵，也是多機器人與單機器人路徑規(guī)劃相區(qū)別的根本所在。多機器人系統(tǒng)在復雜動態(tài)實時環(huán)境下，由于受到時間、資源及任務要求的約束，需要在有限時間、資源的情況下進行資源分配、任務調(diào)配、沖突解決等協(xié)調(diào)合作問題，而機器人間的協(xié)調(diào)與協(xié)作，能夠大大地提高整個系統(tǒng)的效率和魯棒性，成為系統(tǒng)完成控制或解決任務的關鍵。

目前已有的協(xié)調(diào)方式分為集中式、分布式和混合式三種。在集中式協(xié)調(diào)中，集中規(guī)劃器詳細地規(guī)劃出每個機器人的動作，通常的做法是將多個機器人看做一個多自由度的機器人進行規(guī)劃；而分布式協(xié)調(diào)規(guī)劃中，機器人之間進行合作，將一個任務分成多個子任務，根據(jù)各自的特點完成不同的子任務，從而共同完成總任務；混合式協(xié)調(diào)是集中式和分布式混合在一起的形式。

多機器人間典型的協(xié)調(diào)方法[32]有合同網(wǎng)協(xié)議[33]、黑板模型、結果共享的協(xié)同方法、市場機制。近年來強化學習在多機器人協(xié)作方面也得到很好的應用，陳雪江[32]在基于強化學習的多機器人協(xié)作方面展開了研究，提出了多智能體協(xié)作的兩層強化學習方法來求解在多智能體完全協(xié)作、有通信情況下的協(xié)作問題。其主要通過在單個智能體中構筑兩層強化學習單元來實現(xiàn)：第一層強化學習單元負責學習智能體的聯(lián)合任務協(xié)作策略；第二層強化學習單元負責學習在本智能體看來是最有效的行動策略。陳偉等人[34]提出基于多目標決策理論的多機器人協(xié)調(diào)方法；通過對環(huán)境的拓撲建模,從基于行為的機器人學角度出發(fā),對任務進行分解并設計目標行為,以多目標行為決策理論作為決策支持,從而達到多機器人運動協(xié)調(diào)的目的。

4多機器人路徑規(guī)劃方(算)法的判優(yōu)準則

通常評價機器人路徑規(guī)劃方(算)法的標準文獻[35]有正確性、時間/空間復雜度、并行性、可靠性、擴展性、魯棒性和學習。而多機器人的路徑規(guī)劃除了以上一些衡量標準之外，還需要考慮整個系統(tǒng)的最優(yōu)化以及機器人間的協(xié)調(diào)性。

1)正確性是分析算法的最基本的原則之一。一般來說算法的正確性是指:在給定有效的輸入數(shù)據(jù)后，算法經(jīng)過有窮時間的計算能給出正確的答案。但在多機器人路徑規(guī)劃算法中，正確性主要指:路徑規(guī)劃算法要生成多個機器人協(xié)調(diào)運動的無碰安全路徑;這條路徑是優(yōu)化的。

2)安全性一般指多機器人所生成的各路徑中節(jié)點與障礙物有一定的距離。但在實際的應用背景下，有人認為安全性可以從兩個方面來理解：a）狹義地講，它就是機器人在行走過程中所做的功。在一定的條件下，它與路徑長度準則是一致的。b）廣義地講，它是各種優(yōu)化條件加權綜合而得到的結果。

3)復雜度一個算法的復雜性高低體現(xiàn)在該算法所需要的計算機資源的多少上面。所需要的資源越多，該算法的復雜性越高；反之，所需要的資源越少，該算法的復雜性就越低。算法的復雜性包括時間復雜度和空間復雜度。

在多機器人的路徑規(guī)劃算法中，算法的復雜度分析顯得尤為重要。一般地，單機器人路徑規(guī)劃算法的時空復雜度已經(jīng)頗高，它們的數(shù)量級至少是O(n2)；多機器人的路徑規(guī)劃算法不僅是m-O(n2)(即m個機器人路徑規(guī)劃簡單地疊加)，它們之間還存在著對運動空間競爭的沖突，面對不斷變化的沖突的協(xié)調(diào)需要花費大量的時間和空間。通常多機器人的路徑規(guī)劃算法與機器人的個數(shù)呈指數(shù)關系O(km×n2)（k為常數(shù)）。這對多機器人路徑規(guī)劃算法的時間/空間復雜度控制是一個很嚴峻的考驗。

4)并行性算法的并行性從算法設計、編寫程序、編譯和運行等多個不同的層次來體現(xiàn)。路徑規(guī)劃過程需要大量的計算，當處理的環(huán)境比較復雜，機器人工作的環(huán)境過于緊湊，尤其是機器人數(shù)量很多時，算法的時間/空間復雜度勢必會成為算法效率的關鍵。因此，在算法設計和運行上的并行性是通?？紤]的方法。對多個機器人的路徑規(guī)劃盡量采用分布式多進程的規(guī)劃機制，以實現(xiàn)每個機器人路徑規(guī)劃的并行性。

5)可靠性把多個機器人及其工作環(huán)境看成是一個系統(tǒng)，多機器人處于它們各自的起始點時，稱該系統(tǒng)處于初始狀態(tài)；當它們處于各自的目標點時，稱該系統(tǒng)處于目標狀態(tài)。多機器人的路徑規(guī)劃就是在該系統(tǒng)的這兩個狀態(tài)間建立一串合理的狀態(tài)變遷。這一狀態(tài)變遷過程可能會歷經(jīng)許多狀態(tài)，如果在狀態(tài)變遷過程中，路徑規(guī)劃算法控制不好各狀態(tài)間的轉移關系，就會導致系統(tǒng)紊亂，出現(xiàn)機器人間的碰撞、找不到路徑等惡性后果，使任務失敗。所以這就對算法的可靠性和完備性提出了挑戰(zhàn)。為了很好地克服這一困難，需要對系統(tǒng)的各種可能狀態(tài)建模，分析它們相互間的關系，建立有限狀態(tài)自動機模型或Petri網(wǎng)模型，并以此為指導，按照軟件工程的思想，構造恰當?shù)乃惴ㄝ斎雭韺λ惴ǖ目煽啃赃M行檢驗。

6)可擴展性在多機器人的路徑規(guī)劃算法中，可擴展性主要是指一種路徑規(guī)劃算法在邏輯上，或者說在實現(xiàn)上能否容易地從2D空間擴展到3D空間，從低自由度擴展到高自由度，從較少的機器人數(shù)到更多的機器人數(shù)。可擴展性在各種路徑規(guī)劃算法之間沒有一種量的比較標準，只能從實際的具體情況出發(fā)、從對環(huán)境描述的適宜程度出發(fā)、從算法解決這一問題的復雜度出發(fā)、從算法本身的自適應出發(fā)等來考慮。

7)魯棒性和學習魯棒性對于多機器人系統(tǒng)非常重要。因為許多應用，如路徑規(guī)劃要求連續(xù)的作業(yè)、系統(tǒng)中的單個機器人出現(xiàn)故障或被破壞，要求機器人利用剩余的資源仍然能夠完成任務。學習是在線適應特定的任務。雖然通用的系統(tǒng)非常有用，但將它用于特定應用上時，通常需要調(diào)整一些參數(shù)。具有在線調(diào)整相關參數(shù)的能力是非常吸引人的，這在將體系結構轉移到其他應用時可以節(jié)省許多工作。尤其是多機器人系統(tǒng)中機器人的自身學習和相互間的學習能夠大大提高整個系統(tǒng)的效率和系統(tǒng)的穩(wěn)定性。

8）最優(yōu)化對動態(tài)環(huán)境有優(yōu)化反應。由于有些應用領域涉及的是動態(tài)的環(huán)境條件，具有根據(jù)條件優(yōu)化系統(tǒng)的反應能力成為能否成功的關鍵。

5結束語

綜上所述，國內(nèi)外研究者在多機器人路徑規(guī)劃取得了一些成果，但是在協(xié)作、學習、通信機制等方面仍面臨很大的困難和不足。如何進一步提高機器人間的協(xié)調(diào)性，增強機器人自身以及相互間的學習以提高多機器人系統(tǒng)的效率和魯棒性都有待深入研究。近年來無線通信技術得到長足發(fā)展,但在目前的技術條件下，在多機器人系統(tǒng)中實現(xiàn)所有機器人之間的點對點實時通信還有較大困難，這也是大多數(shù)多機器人系統(tǒng)仍然采用集中通信方式的主要原因。因此，如何降低多機器人系統(tǒng)對通信速度的依賴程度也是一個非常重要的問題。

總之,多機器人路徑規(guī)劃設計和實現(xiàn)是一項極其復雜的系統(tǒng)工程,展望其能在結合計算智能方法，如差分進化、遺傳算法、粒子群算法、免疫算法、模糊邏輯算法、BP網(wǎng)絡、人工勢場的改進、模擬退火和環(huán)境建模方法等方面取得新的突破。

參考文獻：

［1］WEISSG.Multiagentsystems:amodernapproachtodistributedmodernapproachtoartificialintelligence[M].Cambridge,Massachusetts：MITPress，1999：121-161.

[2]蔡自興，徐光祐.人工智能及其應用:研究生用書[M].3版.北京：清華大學出版社，2004：124-198.

[3]譚民,王碩,曹志強.多機器人系統(tǒng)[M].北京：清華大學出版社，2005：6-81.

[4]薄喜柱,洪炳熔.動態(tài)環(huán)境下多移動機器人路徑規(guī)劃的一種新方法[J].機器人，2001,23（5）：407-410.

[5]顧國昌,李亞波.基于總體勢減小的動態(tài)調(diào)度技術解決多機器人的路徑規(guī)劃[J].機器人，2001,23（2）：171-174.

[6]孫樹棟,林茂.基于遺傳算法的多移動機器人協(xié)調(diào)路徑規(guī)劃[J].自動化學報，2000,26（5）：672-676.

[7]周明,孫樹棟,彭炎午.基于遺傳算法的多機器人系統(tǒng)集中協(xié)調(diào)式路徑規(guī)劃[J].航空學報，2000,21（2）：146-149.

[8]CAIZixing,PENGZhihong.Cooperativecoevolutionaryadaptivegeneticalgorithminpathplanningofcooperativemultimobilerobotsystems[J].JournalofIntelligentandRoboticSystems:TheoryandApplications,2002,33(1):61-71.

[9]朱慶保.全局未知環(huán)境下多機器人運動螞蟻導航算法[J].軟件學報，2006,17（9）：1890-1898.

[10]SANDHOLMTW，CRITESRH.Multiagentreinforcementlearningintheiteratedprisoner’sdilemma[J].BioSystems，1996，37(1):147-166.

[11]高陽，陳世福，陸鑫.強化學習研究綜述[J].自動化學報，2004,30（1）：

86-100.

[12]MATARICMJ.Interactionandintelligentbehavior[D].Massachusetls:DepartmentofElectricalEngineeringandComputerScience,MIT,1994.

[13]張芳,顏國正,林良明.基于再勵學習的多移動機器人協(xié)調(diào)避障路徑規(guī)劃方法[J].計算機工程與應用，2003，39（3）：80-83.

[14]王醒策,張汝波,顧國昌.多機器人動態(tài)編隊的強化學習算法研究[J].計算機研究與發(fā)展，2003,40（10）：1444-1450.

[15]宋一然.基于強化學習的多機器人路徑規(guī)劃方法[J].莆田學院學報，2006,13（2）：38-41.

[16]韓學東,洪炳熔.基于人工神經(jīng)網(wǎng)絡的多機器人協(xié)作學習研究[J].計算機工程與設計，2002,23（6）：1-3.

[17]唐振民,趙春霞,楊靜宇，等.基于動態(tài)規(guī)劃思想的多機器人路徑規(guī)劃[J].南京理工大學學報，2003,27（5）：610-615.

[18]孫茂相,周明,王艷紅,等.多移動機器人實時最優(yōu)運動規(guī)劃[J].控制與決策，1998,

13（2）：125-130.

[19]焦立男,唐振民.基于局部傳感和通訊的多機器人運動規(guī)劃框架[J].計算機工程與應用，2007,43(17)：89-93.

[20]沈捷,費樹岷，鄭波.多移動機器人保持隊形路徑規(guī)劃[J].東南大學學報，2005,35(3):391-395.

[21]MANSORMA，MORRISAS.Pathplanninginunknownenvironmentwithobstaclesusingvirtualwindow[J].JournalofIntelligentandRoboticSystems，1999，24(3):235-251.

[22]徐潼，唐振民.多機器人系統(tǒng)中的動態(tài)避碰規(guī)劃[J].計算機工程，2003,29(17):

79-81,104.

[23]周明,孫茂相,尹朝萬，等.多移動機器人分布式智能避撞規(guī)劃系統(tǒng)[J].機器人，1999,21（2）：139-143.

[24]任炏,陳宗海.基于強化學習算法的多機器人系統(tǒng)的沖突消解的方法[J].控制與決策，2006,21(4):430-434,439.

[25]歐錦軍,朱楓.一種多移動機器人避碰規(guī)劃方法[J].機器人，2000,22(6):474-481.

[26]景興建,王越超,談大龍.基于人工協(xié)調(diào)場的多移動機器人實時協(xié)調(diào)避碰規(guī)劃[J].控制理論與應用，2004,21(5):757-764.

[27]PANAITL,LUKES.Cooperativemultiagentlearning:thestateoftheart[J].AutonomousAgentsandMultiAgentSystems,2005,11(3):387-434.

[28]TZAFESTASCS,PROKOPIOUPA,TZAFESTASSG.Pathplanningandcontrolofacooperativethreerobotsystemmanipulatinglargeobjects[J].JournalofIntelligentandRoboticSystems，1998,22(2):99-116.

[29]薛宏濤,葉媛媛,沈林成，等.多智能體系統(tǒng)體系結構及協(xié)調(diào)機制研究綜述[J].機器人，2001,23（1）：85-90.

[30]周風余,李貽斌,宋銳，等.基于混合式多智能體系統(tǒng)的協(xié)作多機器人系統(tǒng)研究[J].山東大學學報:工學版，2005,35(1):82-87.

[31]夏冰,張佐,張毅,等.基于多智能體系統(tǒng)的動態(tài)路徑選擇算法研究[J].公路交通科技，2003,20（1）：93-96.

[32]陳雪江.基于強化學習的多機器人協(xié)作機制研究[D].杭州：浙江工業(yè)大學，2004.

[33]SMITHR.Thecontractnetprotocol:highlevelcommunicationandcontrolinadistributedproblemsolver[J].IEEETransonComputer,1980，C-29(12):1104-1113.

[34]陳偉,張銘鈞,孟憲松.基于多目標決策理論的多機器人協(xié)調(diào)方法[J].哈爾濱工程大學學報，2003,24（3）：308-312.

[35]李亞波.多機器人的路徑規(guī)劃與協(xié)調(diào)[D].哈爾濱：哈爾濱工程大學，2000.

摘要：在查閱大量文獻的基礎上對多機器人路徑規(guī)劃的主要研究內(nèi)容和研究現(xiàn)狀進行了分析和總結，討論了多機器人路徑規(guī)劃方法的評判標準，并闡述了研究遇到的瓶頸問題，展望了多機器人路徑規(guī)劃方法的發(fā)展趨勢。

第3篇：路徑規(guī)劃典型算法范文

【關鍵詞】 圖論；貪心算法；應用

在求解一些問題中，貪心算法作為一種優(yōu)解的有效算法，能夠快速地、有效地解決很多實際存在的問題，被廣泛運用在圖論領域中.雖然貪心算法也有不足之處，如應用范疇比較狹窄，但對于圖論有些問題，貪心算法既可以正確求解，也有著很高的應用價值.

一、概述貪心算法

貪心算法是一種分級處理方法，在決策中，貪心算法總會對當前情況進行最好的選擇.與動態(tài)規(guī)劃算法不同的是，貪心算法并不考慮問題的整體最優(yōu)，而只是考慮某種意義上的局部最優(yōu).因此，貪心算法并未結合所有問題求得整體最優(yōu)解，但對于一些問題來講，它可以求得整體最優(yōu)解.在一些狀況下，雖然貪心算法并未得到整體最優(yōu)解，但是能夠得到與最優(yōu)解的近似，所以，貪心算法有著很高的應用價值.

二、貪心算法的求解步驟

1.基本要素.對于一個切實存在的問題，怎樣才能知道是否能夠用貪心算法求解并得到最優(yōu)解，在具體應用過程中，人們研究和總結出兩個重要性質(zhì)：一是，貪心選擇的性質(zhì)；二是，最優(yōu)子結構的性質(zhì).很多使用貪心方法求解問題中都會具有這兩個性質(zhì).

2.步驟的求解.貪心算法的求解先要明確出一個貪心準則，每步都按照此準則進行方案優(yōu)化.排序各個問題，排一次輸一個量.假若這個輸入與已構成的量最優(yōu)解加在一起后很難出現(xiàn)可行解，這樣就不能將輸入值與這部分解相融合.

三、使用貪心算法對單源點最短路徑求解的可行性

在圖論中存在一個很典型的問題：單源點最短路徑這一問題.對問題的描述如下：對于有向帶權圖G=（V，E），其每條邊上的權重都是非負實數(shù).選定在V中某個頂點，稱為源點.此問題求解的是從源點到圖G中其各個頂點的最短路徑長度.在這里所講的長度就是指通過各個邊的權值總和.Dijkstra正是運用貪心算法求解這個問題，用所有路徑長度之和作為最小貪心準則，所以，每個單獨路徑都要有最小長度.實現(xiàn)此算法步驟是：將頂點集合分為兩個子集，即：S，V-S.在子集S中將所有最短路徑頂點都已求得.在初始時，集合S中有源點，然后，將其做貪心來擴充此集合.選取在G中頂點V，從源點到V點并通過S中頂點的路徑稱之為源點到頂點V的特殊路徑，設置數(shù)組Dirt記錄各個頂點對應的最短特殊路徑長度.

四、應用貪心算法求解最小生成樹的可行性

（一）Kruskal算法的應用

對于最小生成樹圖論的討論是非常有價值和有意義的，具體描述包括如下幾點：已知無項連通帶權圖 G=（V，E）.E中每條邊（u，v）的權值設為c[u][v].求圖G的生成樹G′，使G′上各邊權值的總和是所有生成樹中各邊權值中總和最小.此問題被稱為最小生成樹問題.求解最小生成樹問題有很 多種方法，其中Kruskal、Prim等算法應用最為廣泛.

Kruskal算法與Prim算法相比，在生成最小生成樹中，前者比后者更加簡潔明了.一是將無向連通帶權圖 G的n個頂點視為n個 獨立的分支，但這幾個分支間是互相連通的.并根據(jù)權值給各個邊從小至大展_排序.將第一條邊與連通分支進行相連，之后按照權值遞增順序檢查剩下的各個邊，若加入此邊就構成回路，就拋棄此邊，然后，考察余下每條邊；反之，加入此邊并不會構成回路，就將此邊加入.

（二）Prim算法的應用

Prim算法思想是：一是在圖中選取一個頂點u，將u置于頂點集合子集S里.若S是頂點集合V的真子集，就應該將頂點加入子集S中，但要滿足iI ^ S，jI ^ V-S條件，并且C[i][j]是權值最小的一個邊.根據(jù)同樣的步驟進行貪心選擇，直至子集S=V結束.在這時，已被選取的邊就構成了在圖G中的一顆小生成樹.

在對比上文兩種方法后才發(fā)現(xiàn)，這兩種方法雖然都是使用貪心算法解決問題，但由于貪心準則不同的影響，最小生成樹選邊與求解步驟也是不同的，所以，在實際應用貪心算法中，需要因地制宜地應用，盲目、一味地應用貪心算法，很容易引發(fā)其他方面的問題，但相對而言，貪心算法還是值得大范圍地應用的.

第4篇：路徑規(guī)劃典型算法范文

關鍵詞：配送區(qū)域劃分;配送路徑優(yōu)化;算法

中圖分類號：F252.14 文獻標識碼：A

Abstract： The demand of logistics industry and the competitive landscape have changed. The development way of logistics enterprise is from quantity expansion to connotation construction. More and more enterprise study to enhance the competitiveness from three aspects： system， management， and technology. It can make direct economic sense to optimize logistics system. It will be the focus of enterprise development and promotion. It has prevalent meaning of guidance. In this paper， from the angle of enterprise application， I try to use the cluster analysis method determine the distribution region， then use the improved ant colony algorithm to optimize vehicle routing so that we can reduce the cost， and improve the benefits.

Key words： distribution regional division; distribution vehicle routing optimization; algorithm

0 引 言

流通領域中，許多物流配送企業(yè)借助外部經(jīng)濟的發(fā)展，實現(xiàn)了規(guī)模擴張與快速發(fā)展，但對如何控制成本，提高運營效率的迫切性并不強?，F(xiàn)在隨著經(jīng)營環(huán)境的變化，物流需求量更大，客戶、網(wǎng)絡更復雜，對服務的要求更多樣化。但面臨的競爭更加激烈，不管是從事跨區(qū)域配送還是城市配送，首先需要考慮顧客服務水平，贏得客戶的認可，然后考慮配送運營的成本問題，因而如何創(chuàng)新物流服務，提高運營效率和控制日常運營成本成為每個配送企業(yè)需要時刻思考的問題。

傳統(tǒng)的基于經(jīng)驗的方法，在企業(yè)規(guī)模有限，客戶數(shù)量不是非常多，配送網(wǎng)絡相對簡單的情況下，只要員工和管理者技能過關，執(zhí)行力好，都應該能夠較好地完成配送任務，獲得企業(yè)的發(fā)展。但是隨著銷售區(qū)域擴大，客戶數(shù)量的不斷增加，客戶需求持續(xù)增長，配送業(yè)務量大增，配送周期縮短，配送線路更復雜，并且需求的隨機性、變動性加大，光憑經(jīng)驗和手工安排，已無法做到配送計劃的優(yōu)化，必須借助于統(tǒng)計分析、利用數(shù)學模型和智能算法，才能獲得較好的配送計劃，節(jié)省時間，提高效率。本文就是針對這些問題，從企業(yè)應用的角度，提出先合理劃分配送區(qū)域，再優(yōu)化配送路線的方法，從而達到降低成本，提高競爭力的目標。

1 論文總體思路綜述

排單和車輛調(diào)度是整個配送計劃和作業(yè)實施的核心，是配送任務和客戶服務按時完成的有力保證。

傳統(tǒng)的訂單排單和車輛調(diào)度、路線安排都是由公司里業(yè)務能手來完成，送貨區(qū)域大了，客戶多了，這項工作的效率和完成工作的成本控制都會不理想，現(xiàn)在常用的智能優(yōu)化方法，把它作為一個典型的VSP問題，建立數(shù)學模型，利用智能化的算法，求解可行的配送路徑規(guī)劃，作為理論研究，這樣的做法是有意義的。但是有兩個問題：（1）這個模型數(shù)據(jù)的收集整理工作量特別大，計算過程也較長，因而成本不會低。（2）模型本身一定要適合實際的作業(yè)過程，這就需要有一個不斷測試和優(yōu)化的過程，并且還要適應每天的動態(tài)變化，否則反而會影響到日常的作業(yè)過程。許多研究理論完備、精深，但是在適應產(chǎn)業(yè)化運營時，工程上的可實現(xiàn)性還有待提高和完善。因而影響了這些很有價值的研究在企業(yè)實際中的運用。

本文的研究并不針對配送路徑規(guī)劃做理論上的深究，而是立足實際應用，在可接受的范圍內(nèi)，利用較簡易實用的智能優(yōu)化方法，在較短的時間內(nèi)，以較低的成本獲得相對優(yōu)化的配送路徑規(guī)劃方案。不求最佳，但求有效。為今后電子排單和送貨線路優(yōu)化軟件的開發(fā)和應用作必要的鋪墊。

具體設想：第一步，利用聚類分析法對配送區(qū)域進行合理分區(qū)，先把復雜問題簡單化。第二步，每個分區(qū)內(nèi)就是個典型的TSP問題，有很成熟的解決辦法。在平衡好各分區(qū)工作時間安排后，就能很快獲得較理想的配送方案。

重點是第一步，分區(qū)時一定要考慮到客戶位置、需求量、車輛載重、作業(yè)時間均衡限制等因素，需要花費好多功夫。

2 配送區(qū)域動態(tài)優(yōu)化及其方法

2.1 配送區(qū)域的初始劃分方法。配送區(qū)域優(yōu)化方法對最終優(yōu)化的結果有很大的影響，因而合理的劃分方法的選擇十分重要，目前常用的劃分方法有掃描法和聚類算法，在配送客戶有限、區(qū)域較小時運用掃描法就可以了，但是當客戶數(shù)量很多，區(qū)域較大，又要考慮約束條件時，聚類算法就是我們必然的選擇了，聚類算法中K-means比較成熟，操作簡單，原理是：把大量d維（二維）數(shù)據(jù)對象n個聚集成k個聚類k

在運用聚類分析法時有幾個問題要注意：第一，k的選擇，以一天送貨總量/單車載重量，也可以放寬一些，到：一天送貨總量/單車載重量+1。第二，k個聚類內(nèi)的密度，分區(qū)密度大，效率高，成本低。第三，每個分區(qū)內(nèi)工作時間大體相當，這樣便于運行的穩(wěn)定，進行成本控制和人員、車輛的考核。第四，每個聚類間不重合。做到這樣分區(qū)效果會比較好。

傳統(tǒng)的K-means聚類法，k個聚類區(qū)內(nèi)，初始點是隨機產(chǎn)生的，運行時間長，收斂效果差。基于均衡化考慮，在配送對象分布不均勻時，用密度法效果較好，初始中心點以密度來定義，運用兩點間歐氏距離方法，求解所有對象間的相互距離，并求平均數(shù)，用meanD表示，確定領域半徑R=■，n是對象數(shù)目，coefR是半徑調(diào)節(jié)系數(shù)，0

coefR=0.13時，效果最好。如果使用平均歐氏距離還不理想，可增加距離長度，甚至用最大距離選擇法，收斂速度比較快。

在配送對象分布較均勻時，可考慮用網(wǎng)格法，效果較好，整個配送區(qū)域劃分用k=Q/q，k為初始點個數(shù)，假設k=mn，將地圖劃分成m行n列，以每格中心點為初始點，通過網(wǎng)格內(nèi)的反復聚類運算，達到收斂，獲得網(wǎng)格穩(wěn)定的聚類中心。

2.2 分區(qū)內(nèi)配送工作量的均衡。這樣就完成了配送區(qū)域的初步劃分，但是沒有考慮各個分區(qū)內(nèi)工作量的均衡問題，如果工作量不均衡，對于客戶服務水平的保證，成本的控制，作業(yè)的安排，人員、車輛的考核都存在問題。

在實際的物流企業(yè)配送作業(yè)過程中，一般一輛車一天也就送貨10多家或20來家，多余的時間要用于收款，與公司財務部門交賬，核算出車相關費用，所以不考慮同一車同一天出車多次的情況，多次出車待以后深入探討。那么就意味著每個分區(qū)就是一輛車一條線路，把問題大大簡化了，需要說明的是：這種方法對于配送規(guī)模不是特別大的單個城市配送是適用的，也具有廣泛性。

各分區(qū)內(nèi)的每日配送工作量是以配送作業(yè)耗用時間來衡量的，耗用時間有兩部分構成：（1）車輛行駛時間;（2）客戶服務時間。由于配送分區(qū)有限，每個分區(qū)內(nèi)的客戶數(shù)量不是很多，可以采用實地測時的方式，把每條線路的配送時間統(tǒng)計出來，這是一種手工辦法，但比較符合實際，各線路時間分別為T■，T■，T■，T■，…，T■，從中選出最大值T■，最小值T■，用經(jīng)驗法確定允許的差值，然后來調(diào)整超過差值的分區(qū)內(nèi)的客戶，從而使得各區(qū)作業(yè)時間基本均衡。

如果客戶數(shù)量眾多，分區(qū)也較復雜，就需要借助統(tǒng)計學方法，通過對樣本線路車輛行駛時間以及服務時間，擬合出分區(qū)作業(yè)時間函數(shù)，然后，計算出所有線路作業(yè)時間，即使分區(qū)重新調(diào)整，線路重新組合，仍可以很快計算出線路作業(yè)時間。本文不在這個方面進行深入探討。

2.3 重新組合客戶，確定最終區(qū)域劃分。觀察各線路作業(yè)時間超過允許差值的部分，由大到小來調(diào)整，將離聚類中心最遠的數(shù)據(jù)點彈出，使本區(qū)T值下降，直至在差值以內(nèi)，將彈出點加入到臨近的不足均衡作業(yè)時間的分區(qū)內(nèi)，如果臨近分區(qū)作業(yè)時間超過允許差值，這個點就不能彈出，只能彈出另外的次遠數(shù)據(jù)點，以此類推，任何一個數(shù)據(jù)點只能彈出一次，直到所有數(shù)據(jù)點和分區(qū)調(diào)整完畢。

這樣最終確定的分區(qū)，既能做到區(qū)域劃分緊密，效率、成本更低，又能做到各區(qū)作業(yè)時間均衡，便于工作指派，車輛、人員核算。

以上是本文的第一部分工作，也是最有意義的工作，確定好合理的區(qū)域劃分，不僅是配送作業(yè)合理化的重要步驟，也是業(yè)務人員訪銷工作和客戶服務的重要依據(jù)。

3 基于改進蟻群算法的分區(qū)線路優(yōu)化方法

分區(qū)內(nèi)線路安排，就是一輛送貨車由DC出發(fā)，依次經(jīng)過分區(qū)內(nèi)每一個客戶點，完成送貨后返回DC，求出近似最優(yōu)的行車順序，這是個典型的旅行商問題（Traveling Salesman Problem，TSP），TSP是NP完全問題，解法很多，有精確算法，也有啟發(fā)式算法，目前許多智能算法就屬于啟發(fā)式算法，可以解決較復雜的線路優(yōu)化問題，對于一般線路優(yōu)化也能做得更準確，這里介紹蟻群算法解決實際問題。原因是蟻群算法與其他啟發(fā)式算法相比，在求解性能上，具有較強的魯棒性和搜索較好解的能力，是一種分布式的并行算法，一種正反饋算法，易于與其它方法結合。克服基本算法缺點，改善算法性能。

3.1 蟻群算法簡介。蟻群算法（Ant Colony Algorithm， ACA）是由意大利學者M.Dorigo等人于20世紀90年代初提出的一種新的模擬進化算法，其真實地模擬了自然界螞蟻群體的覓食行為。M.Dorigo等人將其用于解決旅行商問題TSP，并取得了較好的實驗結果。

蟻群算法用于解決優(yōu)化問題的基本思路是：用螞蟻的行走路徑表示待優(yōu)化問題的可行解，整個螞蟻群體的所有路徑構成待優(yōu)化問題的解空間。路徑較短的螞蟻釋放的信息素數(shù)量較多，隨時間推移，較短路徑上積累的信息素濃度逐步增高，選擇該路線的螞蟻數(shù)量也越來越多，最終整個螞蟻會在正反饋的作用下集中到最佳線路上，這個路線就是最有解。

3.2 用蟻群算法解決分區(qū)線路優(yōu)化問題。以下用數(shù)學語言描述蟻群算法的整個過程：設螞蟻數(shù)量為m，分區(qū)內(nèi)客戶數(shù)量為n，m≤n，客戶點i與客戶點j之間距離用d■i，j=1，2，3，…，n表示，t時刻i與j連接路徑上的信息素濃度為τ■t。初始時刻各路徑上的信息素濃度相同。

位于客戶點i的第k只螞蟻選擇客戶點j的概率為：

P■i，j=■ （1）

其中：

τi，j表示邊i，j上的信息素濃度;

ηi，j是啟發(fā)信息，d是客戶點i和j之間的距離;α和β反映了信息素與啟發(fā)信息的相對重要性;

tabu■表示螞蟻k已經(jīng)訪問過的城市列表。

當所有螞蟻完成周游后，按以下公式進行信息素更新。

τ■t+n=ρ?τ■t+Δτ■

Δτ■=■Δτ■■

其中：ρ為小于1的常數(shù)，表示信息的持久性。

Δτ■■=■ （3）

其中：Q為常數(shù);l■表示第k只螞蟻在本次迭代中走過的路徑，L■為路徑長度。

蟻群算法解決TSP問題具體步驟：（1）基本參數(shù)設置：包括螞蟻數(shù)m，信息素重要程度因子0≤α≤5，啟發(fā)函數(shù)重要因子1≤β≤5，信息素消逝參數(shù)0.1≤ρ≤0.99，信息素釋放總量10≤Q≤10 000，最大迭代次數(shù)iter_max，迭代次數(shù)初值iter=1。用試驗方法確定α、β、ρ、Q值，以獲得較優(yōu)的組合，有助于改進基本蟻群算法，提高整體優(yōu)化效果，并縮短運算時間。（2）初始解的求解：利用最近鄰算法，以縮短算法運算時間，并以此算法產(chǎn)生初始解的路徑長度作為產(chǎn)生初始信息素的基礎。（3）構建解空間：將各個螞蟻隨機地置于不同出發(fā)點，對每個螞蟻，按公式（1）計算其下一個待訪問的網(wǎng)點，直到所有螞蟻訪問完區(qū)域內(nèi)所有網(wǎng)點。（4）更新信息素：計算各個螞蟻經(jīng)過的路徑長度L■k=1，2，…，m，記錄當前迭代次數(shù)中的最優(yōu)解。同時，根據(jù)（2）式和（3）式對各個網(wǎng)點連接路徑上的信息素濃度進行更新。（5）判斷是否終止：若iter

蟻群算法如結合其他啟發(fā)式算法，建立混合算法，能夠解決許多現(xiàn)實問題，達到較好運算效果，結合具體問題，可以深入研究。

4 本文的局限與進一步研究的方向

本文的研究更多地從實際運用和操作的便利角度出發(fā)，因而力求方法簡便，運算效率較高，然而實際問題遠比設想復雜，物流系統(tǒng)的優(yōu)化應該是整體性的優(yōu)化。本文只是做了配送區(qū)域的合理劃分，在此基礎上，對區(qū)域內(nèi)配送路徑進行優(yōu)化，只是送貨過程的優(yōu)化，完整的過程還包括客戶服務水平，合理的庫存水平，以及配送中心選址，服務地點（卸貨點）的設置等，只有這些因素都考慮到了，才能真正實現(xiàn)配送系統(tǒng)的優(yōu)化。另外，還有靜態(tài)分析和動態(tài)分析的區(qū)別，大區(qū)域劃分保持相對靜態(tài)，區(qū)域間根據(jù)每日具體的業(yè)務需求做必要的動態(tài)調(diào)整，這部分可借助人工安排，也可參考軟件，保持一定的靈活性。整個配送系統(tǒng)的研究千頭萬緒，在進一步的研究中，首先需要把銷售系統(tǒng)的優(yōu)化結合進來，客戶前端的需求和庫存決定著后面的訂單以及配送，業(yè)務員對零售網(wǎng)點的訪銷，一方面對接客戶服務，體現(xiàn)公司的客戶服務水平，另一方面，對接訂單的處理以及最終的配送工作，業(yè)務人員訪銷作業(yè)的系統(tǒng)性安排，以及客戶、配送中心信息的一體化都有賴于業(yè)務訪銷與配送作業(yè)的綜合優(yōu)化。

因而，配送區(qū)域合理劃分、送貨線路優(yōu)化以至于整個物流系統(tǒng)，銷售系統(tǒng)、供應系統(tǒng)的不斷優(yōu)化，對于物流企業(yè)、社會物流以及整個經(jīng)濟運行系統(tǒng)是非常有意義的，對于眾多轉型中，缺乏專業(yè)知識和技術的中小物流企業(yè)，有著普遍意義，值得重視。

參考文獻：

[1] 陳子俠，等. 杭煙物流與送貨路線優(yōu)化[J]. 物流技術，2003（8）：38-40.

[2] 王勇，池吉. 物流配送路線及配送時間的優(yōu)化分析[J]. 重慶交通大學學報，2008（4）：647-650.

第5篇：路徑規(guī)劃典型算法范文

[關鍵詞]成品油配送；路徑優(yōu)化；時間窗；數(shù)學模型

[DOI]1013939/jcnkizgsc201718184

1引言

庫存和運輸是物流系統(tǒng)最重要的功能要素，是物流獲得“時間價值”和“空間價值”的兩大主要環(huán)節(jié)，它們的耗費約占物流總成本的2/3。[1]庫存路徑問題主要是研究一個供應商向多個顧客提供配送服務時，在滿足顧客的需求量、配送時間窗以及庫存容量限制等約束條件的情況下，使總成本達到最小。BirgerRaa[2-3]等人于2007年在研究庫存路徑問題（Inventory Routing Problem）時，假設顧客的需求率是恒定的，在不引起缺貨的情況下，以平均配送和庫存成本最小化為目標得出周期性補貨策略，并運用粒子群算法對該模型進行了求解。2008年又在模型中加入了車輛使用成本，同時運用插入遺傳算法對模型分步進行求解。Kunpeng Li[4]等人在解決成品油配送問題時，考慮車輛容載量、加油站齏嬡萘俊⒊盜臼量等因素的情況下以最大路徑遍歷時間的最小化為目標函數(shù)建立數(shù)學模型，并設計了禁忌搜索算法。趙達[5]等人在2006年以零售商系統(tǒng)下隨機需求的IRP為研究對象，提出了一種基于馬爾科夫決策過程與修正的C-W節(jié)約算法的啟發(fā)式分解算法。我們在2016年以工作量均衡為目標，研究了帶硬時間窗約束的成品油二次配送路徑優(yōu)化問題，建立了整數(shù)規(guī)劃模型并設計了求解模型的算法。[6]

成品油配送問題是一種典型的庫存路徑問題，由于各個加油站的成品油均儲存在容量有限的油罐中，為加油站配送成品油的車輛也是特定的油罐車，為了滿足加油站的日常銷售，油庫需要每天向加油站配送成品油，才能保證銷售過程中不出現(xiàn)斷貨。在研究成品油庫存路徑問題時，如果加油站的銷售速率為常數(shù)，則可以根據(jù)加油站當前的存儲量確定出一段時間內(nèi)的需求量，進一步根據(jù)配送車輛的容量以及油罐的容量限制，確定出配送時間窗。這種條件下成品油配送庫存路徑問題就簡化成了帶容量和時間窗限制的車輛路徑問題。本文主要研究簡化以后的成品油配送車輛路徑優(yōu)化問題，建立該問題的數(shù)學模型并設計求解模型的蟻群算法。

2問題描述

成品油的配送路徑優(yōu)化問題可以描述為：有一個油庫，同時向多個加油站提供某一種型號的成品油；已知加油站在某一時間段內(nèi)對成品油的需求量；每個加油站有對應的硬時間窗，成品油配送車輛不能早于也不能晚于加油站時間窗進行供油；配送車輛在每個加油站卸油均需要消耗一定的時間；為加油站配送成品油的油罐車為單艙車，且油罐車的數(shù)量充足；每輛油罐車的容載量、固定使用成本、單位距離行駛成本均不相同；每輛車可以同時向多個加油站供油，每個加油站只能接受一輛油罐車為其供油；每輛油罐車的平均行駛速度相同，均為50km/h。系統(tǒng)的目標就是在已知各個加油站的需求量以及相互之間的距離的情況下，求使得系統(tǒng)總運行成本最小的配送方案。

在成品油配送過程中，假設配送車輛從油庫出發(fā)為若干個加油站配送成品油，完成配送任務后返回油庫。同一輛配送車服務的若干個加油站的總需求量不能超過車輛的容載量。由于每個加油站只能接受一輛油罐車為其供油，因此為加油站供油的油罐車在該加油站的卸油量與加油站的需求量相等。油罐車在到達加油站時開始卸油，開始卸油的時刻應處于該加油站的時間窗內(nèi)。每輛車在卸油時會耗費一定的時間，卸油耗費的時間與卸油量成正比，且當車輛在一個加油站完成卸油時會立即駛往下一個加油站。

由于油庫的車輛數(shù)量充足以及每輛車的容量、固定成本及可變成本不同，因此，需要從可用車輛中選擇一部分為加油站送油，并進一步確定出每一輛油罐車服務的加油站集合及配送路徑，使得總配送成本最低。每輛選中的油罐車的配送路徑可以用油庫及加油站的序號按照配送順序依次表示。如0-1-5-3-0表示一輛配送車輛從油庫0點出發(fā)，依次為加油站1、5、3配送成品油，配送結束后返回油庫。

5結論

成品油配送路徑優(yōu)化問題是成品油二次配送過程中的關鍵的問題。當制訂成品油配送計劃時，在保證加油站不斷油的情況下，降低配送成本是最主要的考慮因素之一。本文研究了各個加油站的需求量確定的情況下，在滿足各個加油站需求量及服務時間窗限制的前提下，使系統(tǒng)的運行成本最低的成品油配送路徑優(yōu)化問題。建立了以系統(tǒng)總運行成本最低為目標的整數(shù)規(guī)劃模型，最后通過算例對模型進行了驗證。

本文只考慮了確定需求下單一品種成品油的配送問題，未考慮車輛的分艙及滿載約束限制。在實際的成品油配送中，各個加油站的需求量往往是一個隨機變量，并且不同品種的成品油需求量服從的隨機變量分布不同，油罐車的容量和隔艙數(shù)也不同，而且要求滿載運輸。另外，在本文為了簡化問題，假設一個加油站只能被一輛車服務，實際中一個加油站可以被多輛車服務。在后續(xù)的研究中，我們將逐漸加入這些約束條件，建立更加符合實際情況的成品油配送路徑優(yōu)化模型，為解決實際問題提供理論依據(jù)。

參考文獻：

[1]Herer Y，Levy RThe Metered Inventory Routing Problem，an Integrative Heuristic Algorithm[J].International Journal of Production Economics，1997，51（1）：69-81

[2]BirgerRaa，El-HoussaineAghezzafA Practical Solution Approach for the Cyclic Inventory Routing Problem[J].European Journal of Operational Research，2007，1922：429-441

[3]BirgerRaaNew Models and Algorithms forthe Cyclic Inventory Routing Problem[J].4OR，2008，61∶97-100

[4]Kunpeng Li，Bin Chen，AppaIyer Sivakumar，Yong WuAn InventoryCrouting Problem with the Objective of Travel Time Minimization[J].European Journal of Operational Research，2014：936-945

第6篇：路徑規(guī)劃典型算法范文

關鍵詞：最短路徑；神經(jīng)網(wǎng)絡；多層前向反饋網(wǎng)絡（MLFN）；激活函數(shù)

中圖分類號：TP18 文獻標識碼：A

1 引言（Introduction）

現(xiàn)代通信網(wǎng)絡廣泛使用TCP/IP網(wǎng)絡體系結構，在TCP/IP網(wǎng)絡體系結構中，網(wǎng)際層是很重要的網(wǎng)絡層次，網(wǎng)際層的主要功能就是為數(shù)據(jù)包（網(wǎng)際層的數(shù)據(jù)信息單元）尋找路徑并轉發(fā)數(shù)據(jù)包，這個過程稱為路由選擇，路由選擇是網(wǎng)際層最重要的功能，特別是在包交換網(wǎng)絡中。路由選擇技術對網(wǎng)絡性能有很大的影響，最理想的路由算法就是為源節(jié)點與目標節(jié)點尋找最短路徑并高速轉發(fā)數(shù)據(jù)，并且能夠避免數(shù)據(jù)包的丟失。不過要尋找兩個節(jié)點之間的最短路徑是眾所周知的難題，目前廣泛研究的最短路徑算法都具有許多約束條件[1]。

在包交換網(wǎng)絡中，兩個主機之間的數(shù)據(jù)包通信一般通過如下方式：發(fā)送主機將數(shù)據(jù)組織成數(shù)據(jù)塊，一般稱為包，包中封裝有目標主機的網(wǎng)絡地址（一般稱為IP地址），網(wǎng)絡中的路由設備根據(jù)包中攜帶的目標地址為數(shù)據(jù)包尋找路徑并轉發(fā)，最終到達目標主機。一個路由策略的主要目標就是盡量減少IP數(shù)據(jù)包的傳輸延遲，盡最大可能傳輸數(shù)據(jù)包。影響數(shù)據(jù)包平均傳輸延遲時間的主要因素有網(wǎng)絡的可靠性以及網(wǎng)絡帶寬容量和網(wǎng)絡路由等因素的影響，其中路由對網(wǎng)絡性能影響非常重大。因此一個理想的路由算法[2]應該盡量在規(guī)定的時間內(nèi)找到最優(yōu)路徑來滿足網(wǎng)絡的服務質(zhì)量（QoS）。

目前的最短路徑搜索算法主要有：

（1）Bellman-Ford的動態(tài)規(guī)劃算法，這種算法主要用于求含負權值的單源點最短路徑算法。

（2）與Bellman算法類似的Dijkstra標記算法（也稱迪杰斯特拉算法），其按路徑長度遞增依次產(chǎn)生最短路徑。

當前在大多數(shù)的包交換網(wǎng)絡中，最短路徑計算都應用于網(wǎng)際層路由算法中，特別是網(wǎng)絡連接的鏈路具有權值，權值反映的是每條傳輸鏈路的傳輸代價，包括傳輸容量、網(wǎng)絡擁塞、傳輸狀態(tài)（如包隊列頭分組延遲以及網(wǎng)絡故障等）。最短路徑問題可以歸結為在源節(jié)點和目標節(jié)點之間尋找成本最小路徑問題，換句話說，最短路徑路由問題其實是在許多設計和規(guī)劃中都需要的經(jīng)典組合優(yōu)化問題，神經(jīng)網(wǎng)絡技術[3]就可以解決這個復雜的問題。

2 多層前向反饋網(wǎng)絡（MultiLayer forward feedback

network）

多層次網(wǎng)絡，顧名思義由多個功能層次組成的網(wǎng)絡，這種結構的網(wǎng)絡，除了數(shù)據(jù)輸出層和數(shù)據(jù)輸入層意外，還包括隱藏層（或者隱藏單元），每個層次各司其職。多層前向反饋網(wǎng)絡是神經(jīng)網(wǎng)絡中一種典型的分層結構，輸入層神經(jīng)元信息從輸入層進入隱藏層神經(jīng)元網(wǎng)絡后逐層向前傳遞直至輸出層，神經(jīng)元與神經(jīng)元之間的連接的權值稱為鏈接權值?，F(xiàn)代網(wǎng)絡一般都是分層次的結構網(wǎng)絡，其中最著名的有ISO七層體系結構與Internet實際使用的TCP/IP體系結構，網(wǎng)絡的體系結構都是分層次的，都是多層次的網(wǎng)絡結構。通信網(wǎng)絡中的網(wǎng)絡節(jié)點對應神經(jīng)網(wǎng)絡的神經(jīng)元，節(jié)點與節(jié)點之間有鏈接鏈路，每條鏈路具有相應的鏈路權重，對應神經(jīng)元節(jié)點與輸出節(jié)點之間的鏈接鏈路也具有鏈接權重值，兩者之間關系如圖1所示。

圖1 多層前向反饋網(wǎng)圖

Fig.1 Multilayer forward feedback

3 反向傳輸網(wǎng)絡（Back propagation network）

反向傳輸是訓練多層人工神經(jīng)網(wǎng)絡的一種系統(tǒng)方法，它需要具有很好的數(shù)學基礎，并具有廣泛的應用潛力。

與生物神經(jīng)元類似，人工神經(jīng)元接收代表其他神經(jīng)元輸出的大量數(shù)據(jù)，每個輸入都乘以鏈路鏈接權值，類似于生物神經(jīng)中的突觸強度，匯總后的輸入加權值通過激活函數(shù)處理最后確定神經(jīng)元的輸出圖，如圖2所示。

圖2 反向傳輸多層訓練網(wǎng)圖

Fig.2 Back propagation training network

其中的凈值輸入：

考慮到線值，相應的神經(jīng)元輸入由下面的公式給出：

=

相應的輸出（激活值）使用非線性變換函數(shù)f給出。

4 激活函數(shù)（Activation function）

最后的數(shù)據(jù)輸出是通過稱為激活函數(shù)的非線性過濾函數(shù)產(chǎn)生的（有時稱為變換函數(shù)），常見的選擇是S函數(shù)或邏輯函數(shù)。如圖3所示，其中α是斜率參數(shù)，當函數(shù)的改變在兩個漸進值之間變化時，用于調(diào)整函數(shù)突發(fā)。

圖3 邏輯函數(shù)

Fig.3 Logistic function

多個激活函數(shù)稱為階躍函數(shù)，或Heaviside函數(shù)，如圖4所示。

圖4 Heaviside函數(shù)

Fig.4 Heaviside function

5 學習速率（Learning rate）

大多數(shù)網(wǎng)絡結構在學習過程中都要對權值w和v進行調(diào)整。學習速率系數(shù)的選擇決定了權重調(diào)整的大小，從而影響每次迭代的收斂速度，差的系數(shù)選擇可能導致收斂失敗。如果學習速率系數(shù)過大，搜索路徑將發(fā)生振蕩，導致后面的收斂速度更慢。而如果系數(shù)過小，后面的過程將以很小的步驟進行，也會導致收斂速度減慢。

6 問題陳述（Statements）

考慮一個加權有向圖G=（V；E），V是有n個頂點的集合，E是一組有序的m條邊。固定成本Cij與圖G中頂點i到頂點j的邊相關聯(lián)。在運輸系統(tǒng)或機器人系統(tǒng)中，物理成本可能就是兩個頂點間的距離，從一個頂點到另一個頂點也需要時間和精力。在一個通信系統(tǒng)中，成本可以由傳輸時間，節(jié)點到節(jié)點間鏈路容量來確定。一般來說，成本系數(shù)矩陣【Cij】不一定是對稱的，比如，從頂點i到頂點j的成本不一定與從頂點j到頂點i的成本一樣。此外，一些頂點間的邊可能也不存在，也就是m可能小于n2（也就是m

學習算法如下：

如果輸出是正確的，那就不用做權重調(diào)整了。

Wij（k+1）=Wijk

如果輸出是1，但是結果本來應該為0，那么在活動輸入鏈路中將降低權重值。

Wij（k+1）=Wijk-α.xi，其中α是學習速率（因子）。

如果輸出是0，但是結果本來應該為1，那么在活動輸入鏈路中將增加權重值。

Wij（k+1）=Wijk+α.xi

Wij（k+1）是調(diào)整后的權重值，而Wijk是調(diào)整前的權重值。

Rosenblatts算法如下：

（1）用（n+1）個輸入神經(jīng)元X0，X1，X2，…，Xn創(chuàng)建感知器，其中X=1是偏置輸入，O是輸出神經(jīng)元。

（2）初始化隨機權重W=（W0，W1…Wn）。

（3）遍歷訓練輸入模式X集合，使用權值為每個輸入模式j計算輸入加權后的總和。

（4）使用階梯函數(shù)計算輸出Y。

Y=f（netj）=1 netj>0

=0 其他

（5）對每個輸入模式j，用目標輸出Yj與計算得到的Yj進行比較，是否對所有的輸入模式都正確分類并都存在且輸出了權重值。

如果計算的輸出Yj是1，而結果本來為0，用下面給出的公式修改權值。

Wi=Wi-α.xi

如果計算的輸出Yj是0，而結果本來應該為1，就使用如下公式修改權值。

Wi=Wi+α.xi其中，α是學習因子。

（7）回到第（3）步。

7 結論（Conclusion）

神經(jīng)網(wǎng)絡被證明是優(yōu)化分組交換多層網(wǎng)絡的一種簡單方法，Rosenblatts算法的初步完成為優(yōu)化神經(jīng)網(wǎng)絡完成最短路徑奠定了基礎，經(jīng)過幾次迭代網(wǎng)絡可以得到優(yōu)化后的路由。

參考文獻（References）

[1] 孫俊逸，雷建鋒.基于神經(jīng)網(wǎng)絡下的最短路徑問題求解[J].中 國科技論文在線，1-7.

[2] 李望超.神經(jīng)網(wǎng)絡中的最短路徑問題[J].電子科學學刊，1996， S1期.

[3] 朱大銘，馬紹漢.神經(jīng)網(wǎng)絡求解圖最短路徑問題的一種新方法 [J].軟件學報，1996，A00：191-198.

第7篇：路徑規(guī)劃典型算法范文

關鍵詞：蟻群算法；TSP；改進

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)22-724-02

Research on Ant Colony Algorithm for TSP

ZHU Jie

(Scool of Software,Tongji University,Shanghai 201804,China)

Abstract:Ant colony algorithm was a novel simulated ecosystem evolutionary algorithm. After introducing the essence of the ant colony algorithm.this paper its application in the complicated combinatorial opitimization problem such as TSP.Then suggested a improved ant colony algorithm to solve TSP problems more effiently.

Key words:ant colony algorithm;TSP; improved

1 引言

現(xiàn)實生產(chǎn)生活中有很多組合優(yōu)化問題，這類問題隨著規(guī)模的擴大，問題空間呈現(xiàn)組合爆炸的特征，大多數(shù)這類問題在多項式時間內(nèi)無法求解，對這類問題的處理目前多用啟發(fā)式算法來求解。

旅行商(TSP)問題就是典型的組合優(yōu)化問題, 直觀地說，TSP問題就是指一位商人從自己的家鄉(xiāng)出發(fā)。希望能找到一條最短的路徑，途經(jīng)給定的城市集合中的所有城市，最后返回家鄉(xiāng)。并且每個城市都被訪問一次且僅一次。上世紀50年代中期創(chuàng)立仿生學以來，人們不斷地從生物進化的機理中得到啟發(fā)，提出了許多用于解決復雜組合優(yōu)化問題的新方法，比如神經(jīng)網(wǎng)絡、遺傳算法、模擬退火算法、進化規(guī)劃算法等，并成功應用于解決實際問題。但由于TSP屬于Np-難問題，在最差情況下精確性算法需要指數(shù)級的時間來尋找最優(yōu)解。時間代價太大了。近似算法就是尋求在相對較低的計算成本下．找到好的或接近最優(yōu)解的解答，但是算法不一定保證能夠找到最優(yōu)解。由意大利學者M.Dorigo,V.Maniezzo, A.Colomi于1992年首先提出的蟻群系統(tǒng)(AntColonySystem, ACS)是一種新生的仿生進化算法，適用于求解復雜組合優(yōu)化問題，在解決TSP問題方面取得了較為理想的效果。

2 螞群算法概述

蟻群算法是一種元啟發(fā)式算法，蟻群算法是一種受自然啟發(fā)的基于群體智能的算法。算法模型源于真實螞蟻群體搜尋食物的過程：智能螞蟻(算法中的人工螞蟻)模擬真實螞蟻從巢穴到食物所在地之間搜索最短路徑，在問題的解空間中搜索。螞蟻在覓食過程中通過釋放一種稱為信息素的物質(zhì)相互傳遞信息。信息素痕跡參數(shù)是對這種行為的模擬。一般來說，信息素痕跡參數(shù)可以賦予點或邊(TSP中信息素值賦給點)。螞蟻們傾向于朝著信息素濃度高的方向前進，因此由大量螞蟻組成的蟻群的行為便表現(xiàn)出一種信息的正反饋現(xiàn)象，某一路徑上走過的螞蟻越多，則信息素濃度越高，后來者選擇該路徑的概率就越大。

3 基于蟻群算法的TSP求解

給定一個有n個城市的TSP問題，人工螞蟻的數(shù)量為m，每個人工螞蟻的行為符合下列規(guī)律：（1）根據(jù)路徑上的信息素濃度，以相應的概率來選取下一步路徑；（2）不再選取自己本次循環(huán)已經(jīng)走過的路徑為下一步路徑，用一個數(shù)據(jù)結構來控制這一點；（3）當完成了一次循環(huán)后，根據(jù)整個路徑長度來釋放相應濃度的信息素，并更新走過的路徑上的信息素濃度。

3.1 蟻群算法的基本模型：

■ (1)

■表示螞蟻下一步允許選擇的城市。α表示外激素的相對重要性（α≥0 ），β表示啟發(fā)信息的相對重要性(β≥0 )。

隨著時間的推移，可能會出現(xiàn)兩種情況：1)先前留下的外激素逐漸消失；2)殘留的外激素過多，從而淹沒了啟發(fā)信息。為了避免這兩種情況，在每一只螞蟻從起點到達終點后，必須對殘留的外激素進行更新。用參數(shù)ρ(0≤ρ≤1)來表示外激素物質(zhì)的保留率，則1-ρ就表示外激素的揮發(fā)率，經(jīng)過m個時間單位后，螞蟻完成一次循環(huán)，各路徑上的信息量要根據(jù)以下式子作調(diào)整:

■

■

■表示在本次循環(huán)中留在路徑ij上的信息量，■表示螞蟻k在路段ij上留下的殘留外激素濃度。

■式中為dij為表示相鄰兩個城市間的距離。

3.2 蟻群算法的實現(xiàn)步驟如下

步驟1：初始化相關參數(shù)，如螞蟻的數(shù)目。

步驟2：將螞蟻隨機或均勻分布到各個城市。

步驟3：每只螞蟻通過訪問各個城市而形成一個解，并在訪問的過程中，將已訪問到的城市保留在i中。在城市i中每只螞蟻要從沒有訪問的城市中選擇訪問下一個城市j時須根據(jù)概率公式(1)進行選擇，如此循環(huán)，直到所有的螞蟻訪問完所有的城市。

步驟4：計算每只螞蟻行走的總路徑長度Lk，并保存最優(yōu)解。

3.3 算法設計思想

蟻群算法實現(xiàn)的關鍵是信息素的釋放和更新。以及螞蟻個體依據(jù)信息素進行路徑選擇的策略，在分析蟻群算法在后期容易陷入局部最優(yōu)解的原因后，不難發(fā)現(xiàn)這是由正反饋現(xiàn)象所引起的。在每次循環(huán)結束時，對信息素進行全局更新，從而增強了目前最優(yōu)路徑對螞蟻的”吸引力”。在TSP問題中應用蟻群算法進行求解最短路徑，在城市數(shù)量不多時，得出的結果是令人滿意的。在前期，這“吸引力”對算法起到了很好的加速作用。然而，它也會導致算法過早停滯。若單純地調(diào)低信息素的權重。會削弱正反饋的機制的作用，很難使信息素集中分布。螞蟻也就失去了選路的參照，退化為簡單的以路徑為參照的搜索。本算法改進的地方是對局部信息素和全局信息素進行了區(qū)分。采用不同的更新策略，根據(jù)發(fā)現(xiàn)解的情況動態(tài)地調(diào)整選擇概率．在加速收斂發(fā)現(xiàn)最優(yōu)和防止停滯之間找到平衡。在每次循環(huán)結束時，進行全局更新的信息素與螞蟻自己釋放的局部信息素不同。每次循環(huán)結束時，只有最優(yōu)螞蟻(找到目前最優(yōu)路徑的的螞蟻)才更新全局信息素，全局信息素用表示。而局部信息素是每只螞蟻在每移動一步后，都進行局部信息素的更新，螞蟻k從城市i移動到城市j的概率公式變?yōu)椋?/p>

■

τij(t)表示t時刻在城市i和城市j連線上的局部更新的信息素濃度，λij(t)表示t時刻在城市i和城市j連線上的全局更新的信息素濃度。α表示局部信息素τij的重要性，δ表示全局信息素λij的重要性， ρ是τ和λ的權重。

■

權重p是可變的，在[0,1]間取值。用于控制兩種信息素的比重。當發(fā)現(xiàn)更優(yōu)的解時，減少p的值以增加全局信息索的權重，從而有利于更快的發(fā)現(xiàn)其附近的解；若迭代多次而沒有發(fā)現(xiàn)新解，則增加P的值削弱全局信息素的權重，從而擴大搜索的范圍。

局部信息素的更新:■

Δτ為常數(shù)，信息素初始值。

全局信息素的更新：■

■，Cbs表示最優(yōu)螞蟻所走過的路徑長度。

4 結論

自蟻群算法提出來后，已經(jīng)吸引了眾多研究者對該算法進行研究，并成功地將其運用在解決組合優(yōu)化問題上，如TSP，QAP(quadratic assignment problem)，JSP(job―shop scheduling problem)等。對于許多組合優(yōu)化問題，能夠用一個圖來闡述將要解決的問題；能定義一種正反饋過程如問題中的殘留信息；問題結構本身能夠提供解題用的啟發(fā)式信息；能夠建立約束機制：這些使用蟻群算法就能夠得到解決。由于蟻群算法具有信息正反饋和并行計算的特點，其求解能力要在一定程度上好于其它一些啟發(fā)式算法。但是蟻群算法也有一些不足之處，容易陷入局部最優(yōu)從而出現(xiàn)過早停滯是該算法的主要缺點。

最后,本文提出了一種改進的蟻群優(yōu)化算法，大膽引入了全局和局部信息素概念，采用了不同的更新策略和動態(tài)的路徑選擇概率．使得在搜索的中后期能更有效地發(fā)現(xiàn)全局最優(yōu)解。在前期加強全局信息素的作用，從而加速收斂；在中后期，逐漸削弱全局信息素在路徑選擇中的作用，達到擴大搜索區(qū)域的目的。

參考文獻：

[1] 陳宏建,陳峻,徐曉華,等.改進的增強型蟻群算法田[J].計算機工程,2005,31(2):176-178.

[2] Gutjahr W J.A graph-based An t System and its convergence[J].Future Generation Computer System,2000,16(8),873-888.

[3] Liang G S,Chou,17 U,HAN T C.Cluster analysis based on fuzzy equivalence relation[J].European Journal of Operational Re?search,2005,166(1):160-171．

[4] Ai exy U,Verena S P,Wolfgang S H.,et a1.Cluster analysis of individuals with similar trends of fat intake during childhood and adolescence:a new approach to analyzing dietary data[J].Nutrition Research,2005,25(3):251,260．

[5] Arulampalam S., Maskell S., Gordon N., et al. A tutorial on particle filters for on-linenon-linear/non-gaussian bayesian tracking[J].IEEE Transactions on Signal Processing, 2002,50(2):174-188.

[6] Mutapi F., Mduluza T.,RODDAM A W．Cluster analysis of schistosome-specific an tibody responses artitions the population into distinct epidemiological groups[J].Immunology Letters,2005，96(2):231,240．

（上接第725頁）

[7] 段海濱．蟻群算法原理及其應用[M].北京:科學出版社，2005．

[8] 秦玲.蟻群算法的改進與應用[D].揚州:揚州大學,2004.

[9] Gendron B．Parallel computing in combinatorial optimization[M]．Pisa：[s.n]，2005．[10] D. Haehnel, W. Burgard, D. Fox, K.P. Fishkin, and M. Philipose, "Mapping and localization with RFID technology," IEEE Int. Conf. Robotics and Automation, pp.1015C1020, 2004.

[10] Yuan H，Parrill A．Cluster analysis and three．Dimensional QSAR studies of HIV-1 integrase inhibitors[J]．Journal Of Molecu?lar Graphics and Modelling，2005，23(4):317,328．

[11] 胡小兵,黃席樾.對一類帶聚類特征TSP問題的蟻群算法求解[J].系統(tǒng)仿真學報,2004(9):2683-2686.

[12] 張宗永,孫靜,譚家華.蟻群算法的改進及其應用[J].上海交通大學報,2002,56(11):1 564-1 566．

[13] 馬良,項培軍.螞蟻算法在組合優(yōu)化中的應用[J].管理科學學報,2001,4(2):52-57.

第8篇：路徑規(guī)劃典型算法范文

[關鍵詞]電視制導 視覺顯著性 地標選擇 航跡規(guī)劃

[中圖分類號]TP[文獻標識碼]A[文章編號]1007-9416(2010)02-0115-03

引言

電視制導導彈作為一種空地精確制導武器,具有命中精度高、威力大和射程遠等優(yōu)點,已成為現(xiàn)代空戰(zhàn)中打擊敵方縱深戰(zhàn)略目標的重要手段之一,人工參與的電視末制導方式是其中主要方法之一。完成精確打擊的關鍵在于兩個核心環(huán)節(jié):一是在確定了目標點的情況下,綜合考慮導彈機動性能、地形高程、障礙、威脅以及飛行任務約束條件等多種因素,選擇合理的起始點;二是在起始點到目標點的飛行路徑中,盡可能設計若干有效的地標點,以滿足飛行員視覺判斷需要,合理判斷和調(diào)整導彈飛行方向,以提高打擊精度。

目前公開的飛行器航跡規(guī)劃方法中,大多假定起始點和目標點已事先給出,其間路徑的地標點為已知,但如何在明確目標點的前提下,獲取有效的攻擊通道和典型的地標點序列,尚有許多問題亟待解決。鑒于視覺主觀判斷在前述工作流程中的重要性,引入視覺顯著性計算,在視頻序列中間斷地提取顯著地物(對應為地標點、對應幀為顯著幀)作為候選地標序列是一種可行的分析思路。目前主流的顯著區(qū)域檢測算法,文獻[1]將其分為三大類:第一類方法從候選區(qū)域內(nèi)部提取顯著特征,如Kadirt[2]方法。第二類方法從候選區(qū)域與外界的比較中提取顯著性特征,以Itti[3]的中心-周邊算子為代表。第三類從候選區(qū)域內(nèi)部和外部提取顯著性特征,這類方法將上述兩種特征結合起來作為候選區(qū)域的顯著性特征,如Priviterat[4]方法。

本文嘗試以高分辨率遙感圖像數(shù)據(jù)為分析數(shù)據(jù)源,提出了一種簡單的基于視覺顯著性度量篩選地標序列的方法,在一定幾何約束關系下以目標點為中心,導彈飛行航跡距離為半徑的限定扇區(qū)中,自動檢測候選地標點,通過顯著性綜合度量函數(shù),評估攻擊路徑的有效性,實現(xiàn)在有效扇區(qū)內(nèi)選擇有效攻擊起始點并確定攻擊通道,并給出地標序列的功能。典型實驗驗證了方法的有效性。本方法可作為人工選擇攻擊通道和地標點的輔助工具,縮小候選范圍,提高工作效率。

1 地標顯著性度量方法

1.1 視覺顯著性

注視(Attention)機制的研究表明,人類視覺在描述場景時往往將注意力集中在某些明顯與眾不同、視覺效果突兀的區(qū)域,這種特性稱為視覺顯著性[5]。例如,在圖1中,A要比其他部分更加突出,能夠迅速引起觀察者的注意。這種突出性就是視覺顯著性,突出性較強的A部分就是該圖像的顯著區(qū)域。

1.2 遙感圖像定義地標顯著性

研究表明,位于圖像中心位置且與周邊亮度差異較大的區(qū)域容易引起觀察者的注意。基于這一特性,考慮遙感圖像的特點及計算復雜度和實時性的要求,我們把位于圖像中心、與周邊視覺反差大、容易識別的地物作為候選地標點。根據(jù)上述思想,鑒于視頻序列圖像數(shù)據(jù)量大的特點,為減少計算量,選取灰度值作為其特征,通過地物顯著性度量參數(shù)進行度量,M值越大顯著性越強,反之顯著性就越弱。相關公式如下:

(1)

;

式中:表示第幀圖像的顯著性度量值,表示第個窗口內(nèi)的平均灰度值,表示第個窗口外的平均灰度值。

1.3 給定路徑的綜合顯著性

對給定路徑(明確始點、終點的前提下),在提取了序列地標后,可通過設計綜合顯著性度量函數(shù)評估該打擊路徑的有效性,這樣可為在限定扇區(qū)中找到最優(yōu)攻擊路徑提供客觀判斷依據(jù)。

首先生成給定路徑遍歷幀,幀圖像的顯著性度量值由(1)式計算得到,形成該路徑視頻序列顯著值曲線圖,再由2.3節(jié)地標篩選算法,找到該路徑上的地標點,地標點始終處于曲線圖的峰值位置。給定路徑的綜合顯著性體現(xiàn)在兩個方面:一是該路徑的平均顯著性度量值;二是地標點所在幀的顯著性度量值(圖中圓圈所處的峰值點)與其前后顯著性谷值(黑點所處位置)的差值的平均值。綜合以上兩個因素,可得到如下計算公式:

(2)

式中:表示通道綜合顯著性度量值,表示地標點個數(shù),表示當前地標點的顯著性峰值,表示前一顯著性谷值,表示后一顯著性谷值,表示視頻幀數(shù),表示顯著性度量值。

2 攻擊通道自動篩選方法

2.1 成像幾何參數(shù)

導彈飛行過程中,彈載攝像機不斷拍攝戰(zhàn)場視頻圖像,攝像機拍攝到的戰(zhàn)場范圍是由其成像幾何[6]決定的,它對于地標選取具有非常重要的作用。假設導彈飛行高度為,攝像機此刻所處位置的俯仰角為。

又已知相機可視角度為,則可根據(jù)幾何關系計算得到前沿寬度分別為,視場縱深L。計算公式如下:

(3)

(4)

2.2 候選攻擊通道劃分

以可行攻擊候選扇區(qū)為研究對象,導彈從弧線上的任意點出發(fā)飛向目標點都是安全的,沿攝像機主光軸方向?qū)⑸葏^(qū)劃分成N條候選攻擊通道(CH(1)、CH(2)… CH(N))。候選攻擊通道劃分得越密,相互交叉的部分越多,劃分數(shù)量也就越多,找到的地標點也會越多,但計算量越會很大;劃分得越疏,候選通道就越少,找到的地點標也就會越少,計算量也會越小。因此,基于以上問題,我們按照下列方式進行劃分:從扇區(qū)的某一邊開始,把該邊作為導彈的飛行路線,根據(jù)(2)式計算得到的后沿寬度D1為范圍劃分導彈飛行通道,再間隔/2的寬度作為飛行路線依次劃分,這樣相鄰兩條通道相交部分為后沿寬度的1/4,目標始終處于各通道的中心位置。

將條通道分別生成視頻幀圖像,生成的視頻幀數(shù)根據(jù)導彈的飛行速度、導彈起始點到目標的距離、每秒采集幀數(shù)確定,則:

(5)

同時,可以計算得到視場縱深L所包含幀數(shù)為:

=(/)*m(6)

2.3 地標篩選

地標的篩選必須滿足以下三個條件:

(1)為保證地標在視頻中穩(wěn)定可見,必須要求含地標視頻幀的幀數(shù)在一秒所采集幀數(shù)中超過一定比例,則:

即:視場中至少要保證存在一個地標且要持續(xù)數(shù)幀,且當臨界狀態(tài)出現(xiàn),一個地標即將消失時,下一個地標要出現(xiàn),這樣才能避免地標丟失。

(2)要突出地標顯著性,便于人眼識別,即顯著值要大。

(3)地標點數(shù)目要合適,不能選得太多,選得太多,相鄰地標點之間距離太近,沒有實際意義,選得太少,地標點距離遠,就會導致有些幀丟失地標,不利于視覺連續(xù)性跟蹤和判斷。

為了滿足以上條件,我們采用以下四個步驟進行:

根據(jù)(1)式對各個通道的視頻幀圖像進行顯著性度量,計算每幀圖像的顯著性度量值。

將每個通道幀圖像的顯著性度量值形成顯著性曲線圖,橫坐標表示幀數(shù),縱坐標表示顯著性度量值,這樣就形成了條顯著性曲線圖。

找到曲線上的各個峰值點和谷值點,把峰值點作為候選地標。

從第一幀開始,先在幀內(nèi)找到一個峰值最大的點作為第一個地標點,為了減少不必要的地標,與前一個地標點間隔/2幀,在+/2至+幀內(nèi)找一個峰值最大的點作為下一個地標點,通過同樣的方法依次找出后面所有的地標點。

2.4 攻擊通道選擇

由1.3節(jié)計算得到各條路徑的綜合顯著性度量值后,找到綜合顯著性度量值最大的一條路徑作

為最終的攻擊通道,公式如下:

(8)

本文為全文原貌 未安裝PDF瀏覽器用戶請先下載安裝 原版全文

3 實驗結果及分析

假設導彈飛行高度=600m,飛行速度=250/,視頻采集幀頻=5幀/,攝像機俯角=18o,攝像機可視角度為γ=17.5o。實驗用地圖為Google Earth下載的某地區(qū)高分辨率全色數(shù)據(jù),限定某候選扇區(qū)在40o度范圍內(nèi),選取10條候選通道,按照成像幾何關系仿真生成視頻序列圖,每條通道生成180幀灰度圖像。按照上述方法,通過仿真,下面是其中3組典型地標篩選結果對比分析,圖中x坐標表示視頻幀數(shù),y坐標表示顯著性度量值,d圈住的峰值點為地標點所在幀。

由圖7、8、9和表1可以看出,第一候選通道篩選了11個地標,但160-180幀之間沒有地標,存在地標丟失現(xiàn)象;第二候選通道篩選了11個地標,但其第2、6、7、10、11個地標點的峰值不夠明顯,顯著性不強;第三候選通道選擇了13個地標點,峰值明顯的點全部被選中。通過(2)式計算得到三幅圖像的綜合顯著度值分別為:1.1179、1.0991和1.1305,根據(jù)(8)式得出CH(3)選擇的地標點顯著性程度更高。同時,通過三個候選通道的地標幀圖像對比也可以發(fā)現(xiàn),第三候選通道優(yōu)于第一、二候選通道。圖10是第三候選通道找到的地標視頻幀圖像,位于幀圖像中心位置的地物(即地標點)亮度與周邊差異較大,易于人眼識別,因此選擇第三候選通道為最終的攻擊通道。

4 結語

本文提出了一種基于視覺顯著性的空地電視制導導彈攻擊通道地標選擇算法。該算法在地標篩選,攻擊通道選擇方面得到了較為滿意的結果。本文算法在復雜背景和較強噪聲干擾的情況下,還有待進一步改進。

[參考文獻]

[1] 張鵬,王潤生,靜態(tài)圖像中的感興趣區(qū)域檢測技術[J].中國圖像圖形學報,2005;10(2):142～148

[2] Kadir T.Brady M.Saliency,scale and image description[J].International Journal of Computer Vision,2001;45(2):83-105.

[3] Itti L,Koch putational modeling of visual attention[J].Nature Reviews Neuroscience,2001:2(3):194～230

[4] Privitera C M.Stark L W.Algorithms for defining visual regions-of-interest:comparison with eye fixations[J].IEEE Transactions on Pattern Analysis and Machine Intelligenc,2000;22(9):970～982.

[5] 王璐,蔡自興,未知環(huán)境中基于視覺顯著性的自然路標檢測[J].模式識別與人工智能,2006,19(1):100～105.

[6] 李永賓,黃長強,郝曉輝,對電視制導空地導彈巡航飛行高度的分析[J].導彈學報,2001:13(4):82-87.

第9篇：路徑規(guī)劃典型算法范文

關鍵詞：動態(tài)路由協(xié)議；鏈路狀態(tài)路由協(xié)議；OSPF；router-id沖突；自治系統(tǒng)；CE；RFC2328

1 OSPFv2協(xié)議研究

1.1 OSPF協(xié)議概述

IETF為了滿足建造越來越大基于IP網(wǎng)絡的需要，形成了一個工作組，專門用于開發(fā)開放式的、鏈路狀態(tài)路由協(xié)議，以便用在大型、異構的IP網(wǎng)絡中。新的路由協(xié)議已經(jīng)取得一些成功的一系列私人的、和生產(chǎn)商相關的、最短路徑優(yōu)先（SPF）路由協(xié)議為基礎，在市場上廣泛使用。包括OSPF在內(nèi)，所有的SPF路由協(xié)議基于一個數(shù)學算法Dijkstra算法。這個算法能使路由選擇基于鏈路狀態(tài)，而不是距離向量。

OSPF由IETF在20世紀80年代末期開發(fā)，OSPF是SPF類路由協(xié)議中的開放式版本。最初的OSPF規(guī)范體現(xiàn)在RFC1131中，第1版（OSPF版本1）很快被進行重大改進的版本所代替，新版本體現(xiàn)在RFC1247文檔中，RFC1247OSPF稱為OSPF版本2是為了明確指出其在穩(wěn)定性和功能性方面的實質(zhì)性改進。OSPF版本2中有許多更新文檔，每一個更新都是對開放標準的精心改進，后續(xù)的規(guī)范出現(xiàn)在RFC 1583、2178和2328中。

鏈路是路由器接口的另一種說法，因此OSPF也稱為接口狀態(tài)路由協(xié)議。OSPF通過路由器之間通告網(wǎng)絡接口的狀態(tài)來建立鏈路狀態(tài)數(shù)據(jù)庫，生成最短路徑樹，每個OSPF路由器使用這些最短路徑構造路由表。

OSPF路由協(xié)議是一種典型的鏈路狀態(tài)（Link-state）的路由協(xié)議，一般用于同一個路由域內(nèi)。在這里，路由域是指一個自治系統(tǒng)（Autonomous System），即AS，它是指一組通過統(tǒng)一的路由政策或路由協(xié)議互相交換路由信息的網(wǎng)絡。在這個AS中，所有的OSPF路由器都維護一個相同的描述這個AS結構的數(shù)據(jù)庫，該數(shù)據(jù)庫中存放的是路由域中相應鏈路的狀態(tài)信息，OSPF路由器正是通過這個數(shù)據(jù)庫計算出其OSPF路由表的。作為一種鏈路狀態(tài)的路由協(xié)議，OSPF將鏈路狀態(tài)廣播數(shù)據(jù)LSA（Link State Advertisement）傳送給在某一區(qū)域內(nèi)的所有路由器，這一點與距離矢量路由協(xié)議不同，運行距離矢量路由協(xié)議的路由器是將部分或全部的路由表傳遞給與其相鄰的路由器。

1.2 OSPFv2協(xié)議研究

RFC2328中明確OSPF僅通過在IP包頭中的目標地址來轉發(fā)IP包，IP包在AS中被轉發(fā)，而沒有被其他協(xié)議再次封裝。OSPF是一種動態(tài)路由協(xié)議，它可以快速地探知AS中拓撲的改變（例如路由器接口的失效），并在一段時間的收斂后計算出無環(huán)路的新路徑，收斂的時間很短且只使用很小的路由流量。

在連接狀態(tài)路由協(xié)議中，每臺路由器都維持著一個數(shù)據(jù)庫以描述AS的拓撲結構，這個數(shù)據(jù)庫被稱為連接狀態(tài)數(shù)據(jù)庫，所有參與的路由器都有著同樣的數(shù)據(jù)庫，數(shù)據(jù)庫中的各項說明特定路由器自身的狀態(tài)（如該路由器的可用接口和可以到達的鄰居）。該路由器通過洪泛將其自身的狀態(tài)傳送到整個AS中。所有的路由器同步地運行完全相同的算法。根據(jù)連接狀態(tài)數(shù)據(jù)庫，每臺路由器構建出一棵以其自身為樹根的最短路徑樹，最短路徑樹給出了到達AS中各個目標的路徑，路由信息的起源在樹中表現(xiàn)為樹葉。當有多條等值的路徑到達同一目標時，數(shù)據(jù)流量將在這些路徑上平均分攤，路徑的距離值表現(xiàn)為一個無量綱數(shù)。

OSPF允許將一些網(wǎng)絡組合到一起。這樣的組被稱為區(qū)域area。區(qū)域?qū)S中的其他部分隱藏其內(nèi)部的拓撲結構，信息的隱藏極大地減少了路由流量；同時，區(qū)域內(nèi)的路由僅由區(qū)域自身的拓撲來決定，這可使區(qū)域抵御錯誤的路由信息，區(qū)域通常是一個子網(wǎng)化的IP網(wǎng)絡。OSPF允許靈活的配置IP子網(wǎng)，由OSPF的每條路徑都包含目標和掩碼，同一個IP網(wǎng)絡的兩個子網(wǎng)可以有不同的大?。床煌难诖a），這常被稱為變長子網(wǎng)variable length subnetting，數(shù)據(jù)包按照最佳匹配（最長匹配）來轉發(fā)，主機路徑被看作掩碼為“全1”（0xffffffff）的子網(wǎng)來處理。

OSPF協(xié)議中所有的信息交換都經(jīng)過驗證。這意味著，在AS中只有被信任的路由器才能參與路由，有多種驗證方法可以被選擇；事實上，可以為每個IP子網(wǎng)選用不同的驗證方法。來源于外部的路由信息（如路由器從諸如BGP的外部網(wǎng)關協(xié)議中得到的路徑）向整個AS內(nèi)部宣告，外部數(shù)據(jù)與OSPF協(xié)議的連接狀態(tài)數(shù)據(jù)相對獨立，每條外部路徑可以由所宣告的路由器作出標記，在自制系統(tǒng)邊界路由器（ASBR）之間傳遞額外的信息。

2 OSPF域router-id沖突研究

兩臺路由器R1與R2之間建立域內(nèi)OSPF，當R1和R2出現(xiàn)router-id 10.1.1.1重復時，通過查看OSPF數(shù)據(jù)庫可以得到以下信息，詳情請查閱下圖3、圖4。

我們從以上數(shù)據(jù)分析得出，每種LSA的age數(shù)值都非常的小，每種LSA的seq數(shù)值都非常的大，這也說明當出現(xiàn)router-id重復，那么LSDB中的LSA表現(xiàn)得非常不穩(wěn)定，最終將導致SPF算法不停的工作、路由表不穩(wěn)定、路由條目丟失。通過查看路由器日志告警文件可以見一旦出現(xiàn)router-id重復，那么日志信息表現(xiàn)為下圖5的形式，其中adv-rtr為重復的router-id。

綜上所述，從router-id沖突分析后得出以下結論：

（1）整個ospf域內(nèi)會泛洪錯誤LSA，database不斷更新（seq很大，age很?。W(wǎng)絡極其不穩(wěn)定；

（2）由于整個ospf域database不斷更新，導致整個ospf域中routing-table抖動（route flapping），丟失路由條目。

3 結束語

移動通信網(wǎng)絡IP承載網(wǎng)工程建設中涉及IP地址分配，工程建設過程中使用分配的IP地址開啟建立動態(tài)路由協(xié)議OSPF的router-id，需重視并嚴格按照設計規(guī)范及要求，加強IP地址的分配及使用，杜絕分配IP地址沖突導致OSPF域router-id的重復使用，避免因router-id沖突影響OSPF協(xié)議的正常工作，避免因router-id沖突導致的網(wǎng)絡事故影響用戶業(yè)務的發(fā)生。

[參考文獻]