序論：寫作是一種深度的自我表達。它要求我們深入探索自己的思想和情感，挖掘那些隱藏在內心深處的真相，好投稿為您帶來了七篇路徑規劃典型算法范文，愿它們成為您寫作過程中的靈感催化劑，助力您的創作。

篇(1)

關鍵詞 路徑規劃;全局規劃;局部規劃

中圖分類號 TP242 文獻標識碼 A 文章編號 1674-6708(2009)10-0067-02

路徑規劃是指機器人從起始點到目標點之間找到一條安全無碰的路徑,是機器人領域的重要課題。移動機器人技術研究中的一個重要領域是路徑規劃技術,它分為基于模型的環境已知的全局路徑規劃和基于傳感器的環境未知的局部路徑規劃。本文綜述了移動機器人路徑規劃的發展狀況,對移動機器人路徑規劃技術的發展趨勢進行了展望。

根據機器人工作環境路徑規劃模型可分為兩種:基于模型的全局路徑規劃,這種情況的作業環境的全部信息為已知;基于傳感器的局部路徑規劃,作業環境信息全部未知或部分未知,又稱動態或在線路徑規劃。

1 全局路徑規劃

全局路徑規劃主要方法有:可視圖法、自由空間法、柵格法、拓撲法、神經網絡法等。

1.1 可視圖法

可視圖法視移動機器人為一點,將機器人、目標點和多邊形障礙物的各頂點進行組合連接,并保證這些直線均不與障礙物相交,這就形成了一張圖,稱為可視圖。由于任意兩直線的頂點都是可見的,從起點沿著這些直線到達目標點的所有路徑均是運動物體的無碰路徑。搜索最優路徑的問題就轉化為從起點到目標點經過這些可視直線的最短距離問題。

1.2 拓撲法

拓撲法將規劃空間分割成具有拓撲特征的子空間,根據彼此連通性建立拓撲網絡,在網絡上尋找起始點到目標點的拓撲路徑,最終由拓撲路徑求出幾何路徑。拓撲法基本思想是降維法,即將在高維幾何空間中求路徑的問題轉化為低維拓撲空間中判別連通性的問題。

1.3 柵格法

柵格法將移動機器人工作環境分解成一系列具有二值信息的網格單元,多采用四叉樹或八叉樹表示,并通過優化算法完成路徑搜索,該法以柵格為單位記錄環境信息,有障礙物的地方累積值比較高,移動機器人就會采用優化算法避開。對柵格的改進采用以障礙物為單位記錄的信息量大大減少,克服了柵格法中環境存儲量大的問題。

1.4 自由空間法

自由空間法應用于移動機器人路徑規劃,采用預先定義的如廣義錐形和凸多邊形等基本形狀構造自由空間,并將自由空間表示為連通圖,通過搜索連通圖來進行路徑規劃。自由空間的構造方法是從障礙物的一個頂點開始,依次作其它頂點的鏈接線,刪除不必要的鏈接線,使得鏈接線與障礙物邊界所圍成的每一個自由空間都是面積最大的凸多邊形。連接各鏈接線的中點形成的網絡圖即為機器人可自由運動的路線。

1.5 神經網絡法

可視圖法缺乏靈活性,且不適用于圓形障礙物的路徑規劃問題。神經網絡法用于全局路徑規劃可以解決以上問題。算法定義了整條路徑的總能量函數,相應于路徑長度部分的能量和相應于碰撞函數部分的能量。由于整個能量是各個路徑點函數,因此通過移動每個路徑點,使其朝著能量減少的方向運動,最終便能獲得總能量最小的路徑。

2 局部路徑規劃

局部路徑規劃包括人工勢場法、模糊邏輯算法、神經網絡法、遺傳算法等。

2.1 人工勢場法

人工勢場法基本思想是將移動機器人在環境中的運動視為一種虛擬人工受力場中的運動。障礙物對移動機器人產生斥力,目標點產生引力,引力和斥力周圍由一定的算法產生相應的勢,機器人在勢場中受到抽象力作用,抽象力使得機器人繞過障礙物。

2.2 模糊邏輯算法

模糊邏輯算法基于對駕駛員的工作過程觀察研究得出。駕駛員避碰動作并非對環境信息精確計算完成的,而是根據模糊的環境信息,通過查表得到規劃出的信息,完成局部路徑規劃。模糊邏輯算法的優點是克服了勢場法易產生的局部極小問題,對處理未知環境下的規劃問題顯示出很大優越性,對于解決用通常的定量方法來說是很復雜的問題或當外界只能提供定性近似的、不確定信息數據時非常有效。

2.3 神經網絡法

模糊控制算法有諸多優點,但也有固有缺陷:人的經驗不一定完備;輸入量增多時,推理規則或模糊表會急劇膨脹。神經網絡法則另辟蹊徑。路徑規劃是感知空間行為空間的一種映射,映射關系可用不同方法實現,很難用精確數學方程表示,但采用神經網絡易于表示,將傳感器數據作為網絡輸入,由人給定相應場合下期望運動方向角增量作為網絡輸出,由多個選定位姿下的一組數據構成原始樣本集,經過剔除重復或沖突樣本等加工處理,得到最終樣本集。

2.4 遺傳算法

遺傳算法以自然遺傳機制和自然選擇等生物進化理論為基礎,構造了一類隨機化搜索算法。利用選擇、交叉和變異編制控制機構的計算程序,在某種程度上對生物進化過程作數學方式的模擬,只要求適應度函數為正,不要求可導或連續,同時作為并行算法,其隱并行性適用于全局搜索。多數優化算法都是單點搜索,易于陷入局部最優,而遺傳算法卻是一種多點搜索算法,故更有可能搜索到全局最優解。

3 移動機器人路徑規劃技術的發展展望

隨著計算機、傳感器及控制技術的發展,特別是各種新算法不斷涌現,移動機器人路徑規劃技術已經取得了豐碩研究成果。從研究成果看,有以下趨勢:首先,移動機器人路徑規劃的性能指標要求不斷提高,這些性能指標包括實時性、安全性和可達性等;其次,多移動機器人系統的路徑規劃。協調路徑規劃已成為新的研究熱點。隨著應用不斷擴大,移動機器人工作環境復雜度和任務的加重,對其要求不再局限于單臺移動機器人。在動態環境中多移動機器人的合作與單個機器人路徑規劃要很好地統一;再次,多傳感器信息融合用于路徑規劃。移動機器人在動態環境中進行路徑規劃所需信息都是從傳感器得來。單傳感器難以保證輸入信息準確與可靠。此外基于功能/行為的移動機器人路徑規劃,這是研究的新動向之一。

總之,移動機器人的路徑規劃技術已經取得了豐碩成果,但各種方法各有優缺點,也沒有一種方法能適用于任何場合。在研究這一領域時,要結合以前的研究成果,把握發展趨勢,以實用性作為最終目的,這樣就能不斷推動其向前發展。

參考文獻

[1]陳陳.優化方法與最優控制[M].北京:機械工業出版社,1993.

篇(2)

關鍵詞：移動機器人；路徑規劃；A*算法；柵格法

中圖分類號：TP391.4 文獻標志碼：A

Mobile Robot Path Planning Based on an Improved A* Algorithm SUN Wei1， LV Yunfeng1， TANG Hongwei1，2， XUE Min1

（1. College of Electrical and Information Engineering， Hunan University， Changsha 410082， China；

2. Department of Electrical Engineering， Shaoyang University， Shaoyang 422000， China）

Abstract：An improved A* algorithm was presented for global path planning of mobile robot. Firstly， the environment model was described using the grid method， and the preliminary path was obtained by traditional A* algorithm. Secondly， the path planned by A* method was flaw with much redundant points， large path length， and turning angle. The original path was partitioned by tiny step to obtain a series of path point. The finish point from the start point was connected by using straight line in sequence. To decrease the path length and turning angle， the path node can be removed if there are no obstacles on the line. The analysis and comparison between the proposed algorithm， traditional A* algorithm and another improved A* method were then given in the simulation experiment and physical experiments. Additionally， the merits of the proposed algorithm and other algorithms were compared when the obstacle rate， amount of task point， and step length were different. The experiment results show that the proposed algorithm effectively reduces the path length and turning angle.

Key words：mobile robot； path planning； A* algorithm； grid method

路徑規劃問題一直是智能機器人領域的一個研究岬.移動機器人路徑規劃是指機器人基于機載傳感器獲得的環境信息規劃出一條從起點到終點的無碰、安全的可行路徑，并在此基礎上盡可能地優化路徑[1].移動機器人路徑規劃主要解決以下三個問題：第一是規劃出的路徑能使機器人從起點運動到終點；第二是采用相應的算法使得機器人能夠避開環境中的障礙物；第三是在滿足前面兩點要求的基礎上，盡可能地優化機器人的運動軌跡，通常是以規劃出的路徑最短作為優化目標[2].根據機器人對環境信息的感知程度，路徑規劃問題分為全局路徑規劃和局部路徑規劃.前者是指機器人在擁有全部環境信息的基礎上進行的路徑規劃，又稱為離線路徑規劃；后者是指機器人在只有部分環境信息的基礎上進行的路徑規劃，又稱為在線路徑規劃[3].本文主要討論全局路徑規劃.

移動機器人路徑規劃的研究起始于20世紀70年代，到目前為止，已有大量的研究成果.針對全局路徑規劃，主要方法有可視圖法、拓撲學法、人工智能算法和柵格法[4].文獻[5]針對自由空間法當環境發生變化時，需要重新建立網絡連接模型，因而導致路徑規劃算法的環境適應性差和實時性不高的缺陷，提出了一種基于可視圖的全局路徑規劃算法，該方法是直接在環境地圖上進行路徑規劃，從而提高了算法的環境適應能力和實時性.神經網絡作為人工智能中一種重要的算法也被應用到了移動機器人路徑規劃領域，如文獻[6]，首先建立了一個障礙物罰函數的神經網絡模型，并得到了整條路徑的能量函數；然后求得該函數的極小值點，且應用了模擬退火算法避免陷入局部最優；最終對得到的路徑進行了優化，使得路徑更加平滑和安全.除此之外，學者們還采用其它的智能算法來解決移動機器人路徑規劃問題，如模糊邏輯[7-9]，蟻群算法[10]，粒子群優化[11]，遺傳算法[12-13]等.

柵格法是將機器人運動環境建立成一系列具有二值信息的網格模型，再用搜索算法獲取最優路徑.文獻[14]提出了一種改進的A*算法，解決了傳統A*算法得到的路徑包含過多冗余點問題，并得到機器人在拐點處的最小轉折角度.但該算法并沒有減小機器人的路徑長度和轉折角度.文獻[15]針對傳統A*算法得到的路徑折線多、累計轉折角度大的問題，提出了一種平滑A*算法，減少了不必要的路徑點并減小了路徑長度和轉折角度.但只是在原有的路徑點上進行處理，路徑長度和轉折角度的減少量有限.本文提出了另一種改進的A*算法，將進一步地減少移動機器人的總路徑長度和總轉折角度.

1 環境模型描述

眾所周知，移動機器人工作環境地圖建立是路徑規劃中十分重要的一步.地圖建立是指將各種傳感器獲得的環境信息進行融合并抽象成地圖模型[16].采用柵格單位描述二維環境信息非常簡單有效，應用廣泛.所以，本文也使用柵格法來建立移動機器人工作環境模型.如圖1所示，柵格法將機器人工作環境分割成一系列具有相同尺寸的柵格，并將這些柵格分成兩類：可通過柵格和不可通過柵格.圖1中，空白柵格表示可通過柵格，即移動機器人能自由通過的地方，黑色柵格表示不可通過柵格，即該柵格有靜態的障礙物.

為了方便研究又不失一般性，本出以下3點合理的假設：1）障礙物邊界是在實際邊界的基礎上加一個移動機器人安全距離得到的，這樣就可以將移動機器人看作是環境中的一個質點；2）在這有限的二維空間中，機器人的移動方向可以是任意的，并且不考慮高度的影響；3）在整個路徑規劃過程中，環境信息是不變的.圖1是一個10*10的移動機器人工作環境，S是機器人起點，D是終點.本文的工作就是找到一條從起點到終點的無碰的最優路徑.

2 A*全局路徑規劃算法

A*算法是一種典型的啟發式搜索方法.通過估價函數來引導和決定它的搜索方向.從起點開始搜索周圍的節點，由估價函數得到每個節點的價值，選擇價值最低的作為下一個擴展節點，循環重復這一過程直到搜索到終點，則停止搜索，獲得最終路徑.由于每一次都是以估價值最低的節點作為擴展節點，所以最終的路徑代價是最低的.估價函數由式（1）給出：

式中：g（n）是狀態空間中從起始節點到節點n的實際代價，h（n）是從節點n到終點的啟發式估計代價函數，本文采用曼哈頓距離作為啟發式函數[14].

xd是目標點的橫坐標，yd是目標點的縱坐標，xn是節點n的橫坐標，yn是節點n的縱坐標.

在A*算法搜索路徑的過程中，需要不斷地更新兩個列表，一個是開啟列表，另一個是關閉列表.開啟列表存儲的是所有的周圍節點.A*算法從開啟列表中選擇具有最小估價值的節點作為下一個擴展節點.關閉列表存儲的是所有經過的節點和環境中的障礙節點.應用A*算法進行路徑搜索的具體流程如下所述：

Step1 把起始節點放入開啟列表.

Step2 檢查開啟列表是否為空，如果為空，則表示搜索失敗；不為空，則執行Step3.

Step3 選取開啟列表中具有最低f（?）的節點作為當前擴展節點，對擴展節點的每個周圍節點作如下處理：①當該節點的周圍節點是障礙點或者是關閉列表中的節點，則沒有任何動作；②當該節點的周圍點不在開啟列表中，則把該節點的周圍節點添加進開啟列表中，并將當前擴展節點作為該節點的周圍節點的父節點，計算該節點的周圍節點的f（?）和g（?）；③當該節點的周圍節點在開啟列表中，如果以當前擴展節點作為父節點，該節點的周圍節點的g（?）比原來更低，則把當前擴展節點作為父節點，并重新計算該節點的周圍節點的f（?）和g（?）.否則，不作任何改變.

Step4 將當前擴展節點放入關閉列表中，并檢查終點是否在開啟列表中.如果不在開啟列表中，則跳回Step2繼續搜索；否則，最優路徑已經找到，結束搜索.

Step5 從終點開始，沿著每一個父節點移動，回到起始點，這就是最終的路徑.

3 改進的A*算法

采用A*算法進行移動機器人路徑規劃雖然能獲得一條安全無碰的路徑，但路徑點較多，折線多，導致路徑的總長度和總轉折角度較大.這在移動機器人實際應用中將消耗更多的能量和花費更多的r間.本文提出了一種改進的A*算法，能有效地減少路徑長度和轉折角度.

圖2的實線是在一個任意環境中A*算法規劃出的路徑，本文方法是在原路徑的基礎上，從起點開始以較小的步長分割原路徑，得到更多路徑點，如圖2的路徑點a1到a20.按照一定的規則剔除冗余路徑點，將剩余的路徑點按順序連接，最終獲得更加優化的路徑.

圖3是本文算法的流程圖，圖中符號的定義如下：

k為分割路徑的步長；c，m，i分別是當前路徑點下標、待連接路徑點下標和新路徑點下標；A為以步長k分割原始路徑得到的路徑點集合A={a1，a2，…，aN}，其中a1是起始點，aN是終點；ac為當前路徑點；am為當前待連接點；

lcm為連接ac與am的直線；lc，c+1為連接ac與ac+1的直線；B為新的路徑點集合，B={b1，b2，…，bs }.

注意，以步長k分割路徑是在原路徑的直線段進行的.例如，對圖4中A*算法得到的路徑進行分割，先進行直線段L1的分割，從起點開始依次得到路徑點a1，a2，…，a7，此時a8與原路徑點的距離小于步長k，則將原路徑點作為a8，并從路徑點a8開始重復上述過程，分割直線段L2和L3直到將終點作為路徑點a20時，分割過程結束.

圖4中的實線是在任意環境中A*算法規劃出的路徑1，由直線段L1 ，L2 和L3組成，本文方

法規劃出的路徑3由直線段La1a6，La6a9，La9a10和La10a20組成，其中Laiaj是指起點為ai，終點為aj的直線段.由圖4可以直觀地看出：路徑1的路徑長度明顯大于路徑3的路徑長度.另外，路徑1的總轉折角度：

路徑3的總轉折角度：

其中α2=∠ba6a9 ， β2=∠da9a10，γ1=∠ca10a20.而α1=α2+β2，β1=γ1+γ2，γ2=∠a15a20a10，則θ1=α1+β1=α2+β2+γ1+γ2=θ3+γ2.所以，θ1>θ3.相對于A*算法，本文方法縮短了總路徑長度，減小了總轉折角度.

文獻[15]提出的平滑A*算法直接地剔除A*算法規劃出的路徑點，使得路徑更加平滑.而本文方法是先進行分割，再剔除冗余的路徑點.圖4中直線段La1a8，La8a11和La11a20是文獻[15]中平滑A*算法得到的路徑2.顯然，路徑2的長度大于路徑3的長度.另外，路徑2的轉折角度：

其中α1=∠ba8a9，β3=∠a15a20a10，而α1=α2+β2，β3=γ1+γ3，γ3=∠a11a20a10，則θ2=α1+β3=α2+β2+γ1+γ3=θ3+γ3，所以θ2>θ3.相對于文獻[15]提出的平滑A*算法，本文方法得到的路徑也更加優化.

4 實 驗

為了驗證本文算法的可行性和有效性，進行了計算機仿真實驗和實物實驗.考察了不同情形下算法的性能，以下將從4個方面進行仿真實驗： 1）探究同樣的條件下本文算法與A*算法以及文獻[15]的平滑A*算法的性能；2）環境障礙率p對各算法的影響；3）不同目標點數n下算法的優劣；4）本文算法在不同的分割步長k下的效果.以下的4種情形都是在邊長為200個單位的正方形環境下進行實驗，將實驗環境分割成20*20個柵格元素，每個元素是邊長為10個單位的正方形柵格.將實驗環境分割成20*20個柵格元素，每個元素是邊長為10個單位的正方形柵格.

情形1 環境障礙率（障礙柵格數量占總柵格數量的比例）p=30%，取本文算法的分割步長k=0.1，目標數n=1即只有一個終點，起點是（4，4），終點是（198，198），機器人在起點的角度為90°.進行了50次實驗，圖5和圖6是不同算法規劃出的路徑長度和轉折角度，表1是3種算法50次實驗的各項平均值比較.從實驗結果中可以看出，本文提出的改進A*算法相對于A* 算法和文獻[15]的平滑A* 算法，有效地減少了路徑長度和轉折角度.注意，雖然環境障礙率都是30%，但障礙柵格是隨機分布的，這就導致了不同的環境復雜度，所以同樣的算法和實驗條件在不同的實驗次數下卻有不同的實驗結果.

情形2 考察在不同的環境障礙率下，各個算法的性能.令分割步長k=0.1，目標數n為1，起點（4，4）、終點（198，198），機器人在起點的角度為90°.分別在環境障礙率為10%，20%，30%，40%，50%時，進行了50次實驗，并求得不同障礙率下路徑長度的均值和轉折角度的均值，實驗結果如圖7、圖8所示.可以看出，一方面當環境障礙率增大時，各個算法得到的路徑長度和轉折角度也在不斷增大.這是因為環境障礙率一定程度上代表了環境的復雜度，當環境越復雜時，那么規劃的路徑長度和轉折角度也就越大；另一方面，在圖7和圖8中，方框內的數據是本文算法相對于A*算法路徑長度和轉折角度的減少量.當環境障礙率越大時，路徑長度和轉折角度的減少量也不斷增大，這說明相對于A*算法，本文方法更加適合在障礙物較多的環境中使用.

情形3 在移動機器人的工作空間中可能存在多個任務點，這就意味著環境中會有多個不同的終點.這里將研究當機器人有多個任務點時，各個路徑規劃算法的優劣性.這里做以下兩點規定：1）對環境中的任務點進行了編號，任務點1，（198，198）；任務點2，（4，198）；任務點3，（95，95）；任務點4，（198，4）.2）當機器人有n個任務需要執行時，它的執行順序是由任務點1遞增至任務點n.取障礙率p=30%，分割步長k=0.1，分別在n等于1，2，3，4時，進行了50次實驗，并求得路徑長度和轉折角度的均值，實驗結果如圖9和圖10所示，圖中方框內的數據是本文算法相對于A*算法路徑長度和轉折角度的減少量.顯而易見，當機器人的任務點越多，本文算法相對于A*算法規劃的路徑長度和轉折角度的減少量越大.

情形4 本文算法中存在一個分割步長k，這里將考察參數k對算法效果的影響.令環境障礙率p=30%，僅有一個任務點（198，198），起點是（4，4），機器人在起點的角度為90°.在不同的分割步長下進行了50實驗，并求出相應的均值，驗結果如圖11和圖12所示.可以得出這樣的結論：當分割步長越小時，本文算法得到的路徑長度和轉折角度也越小.顯然，這是因為分割步長越小，路徑分割得越精細，路徑長度和轉折角度也就相應減小.

在實物實驗中，本文采用的移動機器人是Turtlebot2，移動底座的最大移動速度：0.7 m/s，最大角速度：180°/s.采用ThinkPad E450C筆記本電腦作為移動機器人的控制器.移動機器人的實際運動空間如圖13所示，是3.6 m×6.6 m的矩形環境.起點（0.9 m，0.9 m），終點（2.7 m，6.3 m），機器人在起點的角度為90°.為了使用本文改進的A*算法進行路徑規劃，需要先建立環境的柵格模型，設置柵格元素為0.6 m×0.6 m的正方形，對實際障礙物進行膨化處理，映射成圖14的黑色柵格.分別采用A*算法、文獻[15]的平滑A*算法和本文算法進行移動機器人的路徑規劃.圖14的直線段La1a5，La5a11，La11a21，La21a27，La27a32，La32a44 和

La44a53是A*算法規劃出的路徑；文獻[15]中平滑A*算法得到的路徑是直線段La1a5，La5a11，La11a21，La21a27，La27a32和La32a53；直線段La1a8，La8a24，La24a25，La25a35和La35a53是本文算法得到的結果.由于移動機器人的運動總是存在外界干擾和運動精度等因素，其運動的實際路徑長度與轉折角度總是比規劃的路徑長度和轉折角度要稍稍大一些，如表2所示.但無論是規劃的路徑長度和轉折角度，還是移動機器人實際運動的路徑長度和轉折角度，本文算法得到的實驗結果都比A*算法和文獻[15]平滑A*算法更加優化.

5 結 論

采用A*算法進行移動機器人路徑規劃，可以得到一條從起點連接終點的無碰安全路徑，但路徑的冗余點較多，路徑長度和轉折角度較大.針對這些問題，本文提出了一種改進A*算法，能有效地減少路徑冗余點和減小路徑長度及轉折角度.并且，分析比較了不同的環境障礙率、任務點數量、分割步長對算法性能的影響.一方面，相對于A*算法，本文方法更加適合多任務點，高障礙率環境下的移踴器人路徑規劃；另一方面，采用較小的分割步長可使得規劃出的路徑更加優化.

參考文獻

[1] 席裕庚，張純剛.一類動態不確定環境下機器人的滾動路徑規劃[J].自動化學報，2002，28（2）： 161-175.

XI Yugeng， ZHANG Chungang.Rolling path planning of mobile robot in a kind of dynamic uncertain environment[J]. Acta Automatica Sinica， 2002，28（2）：161-175.（In Chinese）

[2] 張捍東，鄭睿，岑豫皖.移動機器人路徑規劃技術的現狀與展望[J].系統仿真學報，2005， 17（2）： 439-443.

ZHANG Handong， ZHENG Rui， CEN Yuwan. Present situation and future development of mobile robot path planning technology[J]. Journal of System Simulation， 2005，17（2）：439-443.（In Chinese）

[3] 朱大奇，顏明重.移動機器人路徑規劃技術綜述[J].控制與決策，2010， 25（7）： 961-967.

ZHU Daqi， YAN Mingzhong. Survey on technology of mobile robot path planning[J]. Control and Decision， 2010，25（7）：961-967.（In Chinese）

[4] 吳乙萬，黃智.基于動態虛擬障礙物的智能車輛局部路徑規劃方法[J].湖南大學學報：自然科學版，2013，40（1）： 33-37.

WU Yiwan， HUANG Zhi. Dynamic virtual obstacle based local path planning for intelligent vehicle[J]. Journal of Hunan University：Natural Sciences， 2013，40（1）：33-37.（In Chinese）

[5] 楊淮清，肖興貴，姚棟.一種基于可視圖法的機器人全局路徑規劃算法[J].沈陽工業大學學報，2009，31（2）： 225-229.

YANG Huaiqing， XIAO Xinggui， YAO Dong. A V-graph based global path planning algorithm for mobile robot[J]. Journal of Shenyang University of Technology， 2009，31（2）：225-229.（In Chinese）

[6] 梁瑾，宋科璞.神經網絡在移動機器人路徑規劃中的應用[J].系統仿真學報，2010，22（增刊1）： 269-272.

LIANG Jin， SONG Kepu. The application of neural network in mobile robot path planning[J]. Journal of System Simulation， 2010，22（s1）：269-272.（In Chinese）

[7] 郝冬，劉斌.基于模糊邏輯行為融合路徑規劃方法[J].計算機工程與設計，2009，30（3）： 660-663.

HAO Dong， LIU Bin. Behavior fusion path planning method for mobile robot based on fuzzy logic[J]. Computer Engineering and Design， 2010，30（3）：660-663.（In Chinese）

[8] ARPINO C P， MELENDEZ W M， GUZMAN J， et al. Fuzzylogic based speed planning for autonomous navigationunder velocity field control[C]//2009 IEEE Int Conf on Mechatronics. Malaga， 2009： 201-212.

[9] ZOUMPONOS G T， ASPRAGATHOS N A. Fuzzy logic pathplanning for the robotic placement of fabrics on a worktable[J]. Robotics and Computer Integrated Manufacturing， 2008， 24 （2）： 174-186.

[10]鄧高峰，張雪萍，劉彥萍.一種障礙環境下機器人路徑規劃的蟻群粒子群算法[J].控制理論與應用，2009，26（8）： 879-883.

DENG Gaofeng， ZHANG Xueping， LIU Yanping. Ant colony optimization and particle swarm optimization for robot-path planning in obstacle environment[J]. Control Theory & Applications， 2009，26（8）：879-883.（In Chinese）

[11]吳憲祥，郭寶龍，王娟.基于粒子群三次樣條優化的移動機器人路徑規劃算法[J].機器人，2009，31（6）： 556-560.

WU Xianxiang， GUO Baolong， WANG Juan. Mobile robot path planning algorithm based on particle swarm optimization of cubic splines[J]. ROBOT， 2009，31（6）：556-560.（In Chinese）

[12]王雪松，高，程玉虎，等.知識引導遺傳算法實現機器人路徑規劃[J].控制與決策，2009，24（7）： 1043-1049.

WANG Xuesong， GAO Yang， CHENG Yuhu， et al. Knowledge-guided genetic algorithm for path planning of robot[J]. Control and Decision， 2009，24（7）：1043-1049.（In Chinese）

[13]THEODORE M， KAVEH A， ROGER L W. Genetic algorithms for autonomous robot navigation[J]. IEEE In Strumentation and Measurement Magazine， 2007，12（1）： 26-31.

[14]王殿君.基于改進A*算法的室內移動機器人路徑規劃[J].清華大學學報：自然科學版，2012， 52（8）： 1085-1089.

WANG Dianjun. Indoor mobile-robot path planning based on an improved A* algorithm[J]. Journal of Tsinghua University：Science and Technology，2012，52（8）：1085-1089.（In Chinese）

[15]王紅衛，馬勇，謝勇，等.基于平滑A*算法的移動機器人路徑規劃[J].同濟大學學報：自然科學版，2010，38（11）： 1647-1651.

WANG Hongwei， MA Yong， XIE Yong， et al. Mobile robot optimal path planning based on smoothing A* algorithm[J]. Journal of Tongji University：Natural Science， 2010，38（11）：1647-1651.（In Chinese）

篇(3)

關鍵詞：儲位分配；訂單分批；揀選路徑；仿真技術

中圖分類號：F715.6 文獻標識碼：A 文章編號：1001-828X（2014）010-00-01

引言

對于B2C企業配送中心而言，揀選作業占配送中心作業總量的60%[1]。鑒于B2C企業多品種、小批量、多頻次、快速響應的客戶需求，如何提高配送中心的作業效率，從揀選作業入手效果更佳。縱觀揀選作業的研究大多集中于以下幾個方面：一是儲位分配問題；二是訂單分批問題；三是揀選路徑優化問題。

一、儲位分配問題

貨物儲位分配是指按照節約揀貨時間、減少揀貨路徑、提高空間利用率等目標，將商品合理放置在合適的儲位。合理的儲位分配是提高配送中心出入庫作業效率和降低搬運成本的有效途經。

1.確立貨位分配目標，建立貨位分配模型、使用算法進行優化研究。Ene Seval等人使用改進的數學模型和隨機進化優化算法，并分兩階段來設計儲位分配和揀選系統[1]。Park Changkyu等人聚焦于平面儲位分配問題，采用改進的遺傳算法，并建立數學模型進行了實證研究[2]。陳璐等人提出了一個混合整數規劃模型對該問題進行優化建模，設計開發了一個基于有向連接圖的優化算法對儲位分配問題求初始解，并用禁忌搜索算法進行改進[3]。吳迪等人以最小化系統總成本及最大化時間滿意度為目標建立雙目標非線性整數約束規劃模型，并提出了基于精英重組的混合多目標進化算法，在此基礎上進行關鍵參數敏感度分析，得出雙目標比單目標模型得出的儲位分配結果更優[4]。

2.基于研究數據的關聯性，解決儲位分配問題。Glock Christoph 等人根據比較數據研究，提出不同的存儲位置分配策略，并提出容易在實踐中使用的啟發式算法[5]。Chiang David等人提出一種數據挖掘的基礎存儲分配方法，在有空貨架時為新產品找到最優存儲分配，對未賦值的存儲位置通過應用關聯規則挖掘來解決存儲分配問題[6]。王成林等人基于區域關聯度的儲位規劃方法，對儲位管理的關聯度進行了定義和分析[7]。張志勇等人討論了利用Apriori算法對倉儲管理系統的大規模業務數據進行強關聯挖掘，并結合IQ分析來分配貨物的儲位[8]。

二、訂單分批問題

訂單分批是指將多張客戶訂單合并生成一個批次揀貨單，并對該批次揀貨單進行揀貨作業，貨物揀選完成后，再將揀選品按照原始訂單進行分揀。其目的在于減少揀貨人員尋找儲位時間、縮短揀貨人員的行走距離、提高揀貨效率。國內學者李詩珍通過仿真發現訂單分批策略對減少作業總時間影響最大。訂單分批問題，作為NP難題，針對配送中心訂單分批問題的研究可以分為以下兩類。

1.基于訂單相似度分批，指訂單是按照待揀品項所在的儲存位置相似或者相近進行分批。伍經緯[9]通過對比訂單分批的MAA，FIFS，GSM，COG，GS等五種算法，得出在S型路徑下，MAA算法更有效。李詩珍[10]以最小化訂單揀選行走距離為目標建立了訂單分批模型，并通過以計算訂單相似度為核心步驟的種籽算法以及其他與其原理相類似的節約算法、包絡算法、基于聚類分析的啟發式算法等對模型進行求解與實證分析，并分別對不分批、先到先服務分批、聚類分批下的行走距離進行計算與比較。國外的眾多學者對于不同的揀貨系統分別提出了不同的種子算法、節約算法等，但本質上都是種子算法。De Koster[11]在多貨架矩形系統中結合揀選路徑與分批數量，通過仿真模擬得出最簡單的分批方法都比先進先出分批方法好，S型路徑下揀選設備能與種子算法高效率結合。

2.基于時間窗分批，指在考慮客戶的等待時間以及訂單處理時間的同時，以最小化訂單總時間為目標來決定時間窗大小，也就是將確定或不定的某一時間段的訂單作為一個批次進行揀選，總作業時間除以時窗值，即得到分批次數。馬士華 在解決配送中心揀貨作業中問題中引入延遲制造思想，提出基于時間延遲的動態時窗分批策略，該策略可以消除目前揀貨系統存在的等待時間和閑忙不均的現象，實現揀貨作業的高效率。對于隨即訂單到達的情況，很多學者將可變時間窗固定分批批量問題處理為隨機服務隊列模型。De Koster[11]提出輪換檢測動態模型，將分批、揀選、分類看作串聯隊列，從而實現優化平均揀選作業時間的目的。Won在處理基于客戶響應時間的訂單分批問題時，以最優化顧客響應時間為目標，提出SBJ和JBP算法以降低訂單揀選時間來提高效率。

此外，國內外學者也提出采用遺傳算法、啟發式算法等來求解訂單分批問題。

三、揀選路徑問題

揀選作業路徑優化的目的是為了減少行走距離與縮短揀貨時間，以實現揀選效率的最大化。目前，大多數B2C企業采用固定矩形貨架的人工揀貨或自動化倉庫。路徑優化問題屬于一類特殊的旅行商問題（TSP），對于揀選路徑問題的優化算法主要有啟發式算法、神經網絡算法、彈性算法，以及近年發展迅速的遺傳算法、模擬退貨算法、禁忌搜索算法等智能算法。人工揀貨作業常采用啟發式揀貨策略，即穿越策略、中點策略、最大間隙策略、混合策略等。對于B2C企業而言，特別是訂單數量多，訂購數量少的電商而言，通常采用最簡單的S型路徑，揀貨人員從貨架巷道的一端進入，從兩邊貨架上揀取貨品，然后轉彎進入下一巷道，直至貨品揀取完成。

四、揀選作業系統仿真技術

揀貨作業問題不僅包括以上三個問題，還包括人員配置、設備選擇、流程優化等很多問題，揀貨作業系統作為配送中心的核心子系統，它的優化與改進對配送中心效率的提高意義重大。配送中心是典型的現代機械電子相結合的系統，也是典型的隨機型離散事件系統，其復雜性與系統性可通過仿真的方法進行設計與優化。目前，物流系統仿真技術已經越來越多的被運用到決策中去，物流系統仿真軟件也有了更多的選擇性。二維平面式動畫表現形式（2D）的有ARENA、Em-Plant、WITNESS、EXTEND，三維立體（3D）的有Flexsim、Automod、RalC、WITNESS等。本質上，物流仿真軟件的建模大同小異，都是通過實體的組合來建模，參數的控制來調節，目標的設定來實現，并通過對結果的分析發現瓶頸和做進一步的優化調整。

參考文獻：

[1]Ene Seval，Ozturk Nursel. Storage location assignment and order picking optimization in the automotive industry[J]. International Journal of Advanced Manufacturing Technology，2012，60：787-797.

[2]Park Changkyu，Seo Junyong.Mathematical modeling and solving procedure of the planar storage location assignment problem[J]. Computers & Industrial Engineering，2009，57（3）：1062-1071.

[3]陳璐，陸志強.自動化立體倉庫中的儲位分配及存取路徑優化[J].管理工程學報，2012，26（1）：42-47.

[4]吳迪，李蘇劍，李海濤.基于時間滿意度的混合渠道庫存及分配策略[J].山東大學（理學版），2013，48（6）：51-60

篇(4)

關鍵詞：庫存配送系統；聯合優化；遺傳算法；C-W算法

一、庫存與配送系統聯合優化研究分類

1.聯合優化思路。在庫存與配送聯合優化研究提出之前，大多學者都是單獨對企業庫存與配送進行研究的，比如考慮輸入輸出對動態庫存進行研究，單獨進行配送線路規劃，動態庫存管理研究中輸入輸出是已知的，沒有考慮輸入輸出受企業采購過程中供應商配送的影響，而單獨的運輸線路規劃問題則沒有考慮庫存內部動態管理，因此，對庫存與配送系統聯合優化研究很有必要，目前該類研究大致可以分為以下類型：

一類研究基于供應鏈整體成本，構建模型求得整體的訂貨量與配送策略。此類研究綜合考慮了供應鏈各節點企業的三大成本“庫存、采購與運輸”，基于各方需求統一確定，互相了解需求，并且不允許缺貨情況的發生，運輸服務統一由第三方提供，構建的目標優化模型以生產商的生產成本、零售商的采購、庫存成本，以及運輸服務提供方的運輸成本，以此求得最優解。但是該類研究沒有考慮供應鏈參與各方的合作情況，各方對于利益的分配、成本的分攤機制沒有考慮，容易造成分配不均而產生摩擦。

另外一類研究則是是由供應商主導庫存配送，考慮一個供應商對多個零售商的庫存-配送進行管理，構建模型對各獨立零售商的庫存進行管理，基于各地庫存對時間、數量的需求，以自身成本最小為目標，進行路線規劃，及時給零售商補貨。供應商管理庫存與前一類研究不同，兩類研究均從總體成本最優角度出發，但是前一類研究沒有厘清供應鏈中各企業角色，及相應的職責，此類研究確定了供應商管理庫存，則明確了研究的類型，對于成本分配問題有了較好的解決。通過建立合理的數學算法可以對基于庫存考慮的線路規劃問題求得最優解，通過供應鏈各節點的協同配合促進運作效率，各方均獲得最大收益，為實際供應鏈運作提供參考。

2.算法研究分類。庫存-配送系統可以視為庫存-路徑問題的升級版，但是本質考慮的重點仍然是供應鏈各方庫存保有量、采購量、采購周期，與運輸路徑選擇之間的合理調節。對于庫存-路徑問題的算法研究較多，我們可以借鑒其相關算法應用于庫存-配送系統研究。

（1）啟發式算法。運用啟發式算法對庫存-路徑問題進行求解的研究比較普遍，如蟻群算法、鄰域搜索算法、禁忌搜索算法、模擬退火算法、遺傳算法及人工神經網絡等智能算法都或多或少有應用于庫存-路徑研究領域，其中遺傳算法有較好的收斂性，能較快地達到全局最優解，并且有優勝劣汰的算法規則，最多地被運用或改進后運用于庫存-路徑求解。

（2）C-W節約算法。C-W算法是解決旅行商提出的，基于節約的理念，適用于物流單元間流量較為穩定，變化不大的問題，是一種較為簡潔實用的算法。由供應商主導庫存，為多個零售商供貨可以解決信息不對稱造成的庫存過度配置，配送次數多配送量過大的情形，可以達到配送次數最少，配送量最經濟（供應商、零售商采用最佳采購量）的效果，此時配送路線上配送較為穩定，配送變化不會太大，不會因為市場需求變動過大而引起配送問題，因為供應商對零售商的庫存需求情況十分了解。因此C-W算法比較適合研究庫存-路徑問題，多數學者采用遺傳算法或其他優化算法是都會結合C-W算法特點進行研究。

（3）其他算法。除運籌學領域優化算法、智能算法與C-W算法這幾類典型的庫存-路徑求解算法之外，一些學者還采用概率論領域的馬爾科夫決策過程研究隨機需求下的庫存-路徑算法，也有學者采用分散決策算法（DDA decentralized decision algorithm）以求解分散決策情形下的庫存與運輸問題）。

二、庫存與配送系統聯合優化模型構建

庫存與配送系統聯合優化是促進供應鏈一體化的有效手段，本文基于供應商統一管理庫存構建一個供應商對多個零售商配送的簡單兩級供應鏈模型。

1.模型假設。（1）各零售商需求確定，且均與供應商形成直接連接網絡；（2）零售商不允許缺貨，不考慮提前期；（3）運輸費用與距離成正比；（4）一個運輸車輛一天只做一次配送，在不超過運輸車輛的滿載負荷前提下可以為多個零售商配送；（5）多個零售商的不同貨物可以拼車運貨，這一點由供應商統一管理庫存，統一配送可以比較好地解決。

2.符號表示。本文考慮的是由供應商管理庫存，由單供應商與多個零售商構成的一對多的簡單二級供應鏈，用數字序號下標表示供應商與零售商，i∈（0，1，2，...，N），0表示供應商，1至N表示零售商。貨物由供應商負責配送，共有M輛運輸車，每輛車的載重相等為Q，供應商的補貨周期為T，eij表示供應商及各零售商之間的距離，di表示零售商的需求率，A0，Ai表示供應商與零售商的補貨成本，h0與hi表示供應商與零售商的庫存成本，C表示車輛的運輸成本，在供應商的補貨周期內，ni表示零售商的訂貨次數，ti表示零售商的訂貨周期，則T=niti，令Xijkt表示車輛k在時間t從點i開往j進行配送，是則值為1，否則為0，令Qjkr表示車輛k在時間r為點j配送的貨物量。

篇(5)

關鍵詞：迷宮問題，機器人，深度優先

 

0 引言

迷宮最短路徑問題是一個典型的搜索、遍歷問題，目前很多學者提出了一些新的迷宮路徑求解算法如如遺傳算法[1]、脈沖耦合神經網絡[2] 、蟻群算法[3]、反應擴散搜索[4]等，在迷宮最優路徑仿真搜索方面做出了一定的成績，但上述算法需要進行大規模的運算，對處理器的要求很高，因此只能應用于仿真層次，對于實際的物理系統來說實現起來是有困難的。

迷宮問題經典的算法是深度優先算法和廣度優先算法，深度優先算法是從迷宮的入口出發，順著某一方向向前探索，若能走通，則繼續前進，否則沿原路退回（回溯)，換一個方向再繼續探索，直到所有可能的通路都探索到為止，深度優先算法可以在未知迷宮中找到一條可行但不一定是最優的通路。廣度優先搜索是從入口出發，離開入口后依次搜索與當前位置相鄰的單元格，然后分別從這些相鄰單元格出發依次訪問它們的鄰接格，依次類推直到找到迷宮出口，算法可以找到迷宮的最優路徑，但探索點會隨著探索的深入急劇增加，需要大量的內存空間用來保存探索過程的記錄。

考慮到實際物理系統內存容量和運算速度的限制以及以上算法的優缺點，帶回溯的深度優先算法具有占用內存空間少，對處理器的速度要求不高，不需要知道迷宮內部的具體結構的特點，因此適合于機器人在未知迷宮中進行路徑搜索。免費論文參考網。

1迷宮機器人結構描述

智能移動機器人技術是機器人研究領域的一個重要分支，智能移動機器人是指機器人在完全未知的環境中，實時自主運動，是集環境感知、動態決策與規劃、行為控制與執行等功能于一體的具有高度自動化程度的智能化裝置。因此走迷宮機器人是在沒有人工干預的情況下，通過機器人自身的傳感器系統感知迷宮環境，并根據不同的迷宮環境做出不同的決策并驅動執行裝置執行相應的動作來完成走迷宮的過程的一種機器人。免費論文參考網。

1.1機械結構描述

機器人的移動方式有很多種，但大致可分為車輪式

和足步式兩種，車輪移動方式的大部分技術比較成熟，

控制也比較容易，而足步行走方式的控制要困難得多，

因此本文的迷宮機器人采用輪式移動機構，其機械結構如圖1所示：它有三個車輪，其中前輪為從動輪，為萬向自由輪，后兩輪為相互獨立的驅動輪，固定不可轉向，并且每個輪子都有獨立的電氣驅動模塊和變速機構，車身的方向和速度依靠改變兩輪的速度來實現。

1.2傳感器系統

環境感知能力是移動機器人除了移動之外最為基本的一種能力，感知能力的高低直接決定了一個機器人的智能性高低，它的作用是建立合理的機器人感覺系統，以便機器人能夠建立起完整的信息獲取渠道。機器人要具備智能行為就必需依靠傳感器不斷感知外界環境，從而做出相應的決策行為。目前傳感器的種類繁多，功能越來越豐富，像超聲波傳感器、紅外傳感器、光電傳感等。傳感器系統是機器人很重要的

部分，選擇機器人傳感器完全取決于機器人的工作需要和應用特點，因此迷宮機器人具有如下傳感器系統：其傳感器系統包括3個紅外傳感器和2兩個光電傳感器，3三個紅外傳感器位于機器人的左前右方（如圖1中箭頭3所示），探測距離是6cm，分別對機器人左前右三個方向的迷宮墻壁進行探測，以便機器人建立起迷宮障礙物的完整信息，光電傳感器1用來檢測是否進入一個新的迷宮格中，而傳感器2主要用來和1配合以識別機器人是否到達終點。

1.3 控制系統

控制系統主要包括單片機及其外圍電路以及電機驅動模塊、串行通訊模塊等，單片機采用了ATMEL公司的ATmega16微控制器，在16MHZ頻率下速度為16MIPS的8位RISC結構單片機，其內含硬件乘法器和16K的flash，支持ISP編程，運算速度比普通的單片機要快的多，因此可以滿足系統的需要。

2 迷宮問題描述

迷宮問題是圖形學、圖論和數據結構等領域中廣為人知的一個經典問題，我們把迷宮簡化成如右圖2所示：圖中‘1’表示障礙物，‘0’表示通路，機器人從入口處進入，從出口出來就算成功的走出迷宮。

3算法仿真試驗

3.1算法描述如下：

：初始化，隨機生成符合要求的m行n列的迷宮maze（m，n），通過調整迷宮數組中0和1的個數比調節迷

宮的可行通路數量，0越多，則迷宮的可行路徑就越多，就越容

易找到出口。設定方向數組dir：規定搜索迷宮只能向上下左右四個方向搜索，對于正方形迷宮，設邊長為1個單位，因此可以設定方向數組dir（4，2）=[1 0;0 1;0 -1;-1 0]。行進經過結點記錄數組jiedian（i，j）用來記錄機器人探索過的每個結點，如果機器人走過結點（i，j），則jiedian（i，j）=1，否則為0。走過路徑記錄數組way用來記錄機器人行走過程的可行路徑信息。

：機器人開始行走，從當前結點開始向三個方向搜索，如果沒有障礙物（即該方向的迷宮壁為0）且不是終點并且沒有走過（即jiedian（i，j）=0），則把該結點記錄到jiedian中。

：如果只有一個結點符合要求，則以該結點為起點繼續過程，同時把該結點記錄到way中，如果有兩個或兩個以上的結點，則從中隨機選擇一個結點為起點繼續過程，并把該結點記錄到way中。免費論文參考網。

：如果三個方向都有障礙物，則機器人進行回溯，退回上一個結點，選擇排除已經探索方向的其它方向繼續搜索，如果沒有可通路徑則繼續回溯直到回到起點，轉到，否則轉到繼續搜索直到找到終點，轉。

：給出沒有可行路徑信息。

：輸出可行路徑。

3.2實驗結果過程及結果：

為了驗證算法的有效性，我們隨機生成一個22*22規模的迷宮，應用深度優先算法進行迷宮路徑搜索，其仿真結果如3圖所示：圖中‘o’表示迷宮的‘0’，‘’表示迷宮中的1，左上角為迷宮的入口，右下角為迷宮的出口，深色部分表示算法找到的可行迷宮路徑，從圖3中可以看到：深度優先算法可以在迷宮中找到一條可行路徑。

4 物理系統實現：

圖 3 深度優先算法找到的路徑示意圖

機器人路徑規劃問題可以分為兩種，一種是基于環境先驗完全信息的全局路徑規劃，另一種是基于傳感器信息的局部路徑規劃，后者環境是未知或者部分未知的。基于實際物理系統的特點，我們把該算法應用到我們研制的迷宮機器人上，在不影響算法正確性的情況下，我們采用圖4所示的簡化迷宮進行實驗：帶箭頭的白線是機器人實際所走路線圖，可以看到機器人從入口出發，按照帶回溯的深度優先算法行走，經過一定的時間后能夠順利的找到出口，完成了在未知迷宮中的行走過程，實驗證明了算法的有效性。

5結論：

迷宮問題是一個經典的遍歷問題，求解算法很多，但對于實際的物理系統，考慮到其運算速度和內存大小的局限，運用深度優先算法進行迷宮路徑的搜索是可行的，從仿真實驗和物理實驗都可以看出，深度優先算法是有效的。

 

參考文獻：

[1] SU S,Tsuchiya K. Learning of a maze using a genetic algorithm[c]. IndustrialElectronics, Control and Instrumentation 1993, Proceedings of the IECON’93International Conference On, 1993, 1: 376-379.

[2] 宋寅卯，袁端磊.基于PCNN的迷宮最短路徑求解算法[J].電路與系統學報.2005,10(3)： 72-75.

[3] 胡小兵，黃席樾. 蟻群算法在迷宮最優路徑問題中的應用[J].計算機仿真.2005，22（4）：115-116.

篇(6)

關鍵詞TSP問題 0-1規劃 智能算法

中圖分類號：O158 文獻標識碼：A 文章編號：1007-9416（2014）05-0139-02

旅行商問題（Traveling Salesman Problem， TSP）是典型的組合優化問題，很多優化問題都可以直接或間接的轉為為TSP問題，而且TSP問題已被證明具有NPC計算復雜性，有很大的求解難度，因此研究TSP問題的求解方法有著很大的實際意義。本文旨在介紹求解TSP的幾種常用解法，并結合實例比較這些算法的性能，為TSP的求解提供一些參考。

1 TSP問題描述

TSP問題的數學表述為：一個有窮的城市集合C={C1，C2，…，Cm}，對于每一對城市Ci，Cj∈C有距離d（Ci，Cj）∈R+。問：經過C中所有城市的旅行路線，記為序列，是否存在最小的正數B，對所有可能的序列都有

2 TSP問題幾種常用求解方法

TSP問題有著很多求解算法，主要有。

2.1 貪婪算法

貪婪算法[2]（Greedy algorithm）是求解大規模TSP問題的常用算法之一，是一種求解優化問題的簡單、迅速的求解辦法。貪婪法有限考慮當前情況下最優的優化測度，自頂向下，逐步迭代，具有算法簡單，耗時短的特點。但貪婪算法的求解結果往往不是最優的，甚至可能與全局最優解間有不小的差距。

2.2 模擬退火算法

模擬退火（Simulated Annealing，SA）算法是求解TSP問題的有效方法之一，容易編程實現，求解速度快。模擬退火是一種全局優化算法，加入了隨機狀態模型，使算法以概率選擇的方式逼近最優狀態，其收斂性可以得到嚴格的理論證明。模擬退火算法具有一整套完整的退火搜索計劃，包括足夠高的初始溫度、緩慢的退火速度、大量的迭代次數及足夠的概率擾動[3]。

2.3 遺傳算法

遺傳算法（Genetic Algorithm，GA）是一種常用的智能算法，具有全局搜索能力，對TSP問題有良好的效果。遺傳算法是由Michigan大學的J.Holland教授于1975年提出，算法通常由編碼、個體適應度評估和遺傳運算三部分構成，其中遺傳運算包括染色體復制、交叉、變異和倒位等[4]。

2.4 粒子群算法

粒子群算法（Particle Swarm Optimization，PSO）是依據鳥類覓食的群體性模型而發明的新型智能算法，是由美國電氣工程師Eberhart和社會心理學家Kennedy于1995年提出，具有通用性強，參數少，容易實現，收斂速度快等優點，也是解決TSP問題的有效算法之一[5]。

2.5 蟻群算法

蟻群算法（Ant Colony Optimization，ACO）是根據螞蟻發現路徑的行為的而發明的用于尋求優化路徑的機率型算法，由Marco Dorigo于1992年在他的博士論文中提出。蟻群算法是一種模擬進化算法，具有包括較強的魯棒性在內的許多優良性質，在本質上是一種并行的分布式算法，容易實現，可以較好地求解TSP問題[6]。

3 實例計算

選取我國北京、天津、武漢、深圳、長沙、成都、杭州、西安、拉薩、南昌等十個城市，分別使用1-10對十個城市進行編號，獲取十個城市的距離矩陣，使用上節所述算法進行求解。已知路徑最小長度為12055，最優路徑為2-1-8-9-6-3-5-4-10-7-2，求解結果如表1所示。

圖1為四種智能算法的收斂狀態。

4 各種求解算法的比較

根據本文的實例計算和相關文獻[7]，可以給出各算法的比較。

5 結語

TSP問題有著很大的求解難度，但并不意味著無法進行有效的求解，使用一些比較成熟的智能化算法進行求解，可以獲得較好的解答。當然各種近似求解算法還有著一些固有的缺陷，在不同情況下有著不同的性能表現，需要在使用時加以選擇。

參考文獻

[1]謝金星，薛毅.優化建模與Lindo/Lingo軟件.北京：清華大學出版社，2005.

[2]黃輝，梁國宏等.求解一類線性規劃問題的原始貪婪算法和對偶貪婪算法及其相互關系[J].蘭州交通大學學報，2007，26（1）：149-152.

[3]田澎，王浣塵等.旅行商問題（TSP）的模擬退火求解[J].上海交通大學學報，1995，S1：111-116.

[4]胡玉蘭.基于遺傳算法的旅行商問題仿真實現[J].控制工程，2002，6：79-81.

[5]嚴露.粒子群算法研究與應用[D].電子科技大學碩士論文，2013.

篇(7)

交通信息采集技術研究現狀

目前，交通信息采集手段可以分為2類:(1)通過人工采集獲取，如:交通調查數據、交通事件信息等;(2)通過各類交通信息檢測系統實時自動采集，自動采集技術包括移動型交通采集技術和固定型交通采集技術。固定型采集技術固定型采集技術是運用安裝在固定地點的檢測設備對道路進行交通參數檢測的方法，能夠提供交通流量、地點平均速度、車頭時距、車型分類和車道占有率等參數。目前，常用的固定檢測器有:環形線圈檢測器、微波檢測器、視頻檢測器、紅外檢測器、超聲波檢測器等。各種檢測技術都有不同的優缺點(見表1)，在工程建設時，需根據環境條件和具體需求進行選擇，也可在同一系統中采用多種檢測方式，通過對多源交通數據的融合處理提高檢測精度。移動型采集技術移動型采集技術是運用安裝有GPS定位設備的移動車輛(浮動車)檢測道路上的固定標識物來采集交通參數的方法。移動型采集技術主要有:電子標簽、GPS、蜂窩網絡和汽車牌照自動識別［8］。其中基于GPS的動態交通數據采集技術是當前最主要的移動型采集技術。目前，對該技術的理論研究重點主要包括提高采集數據質量的方法和計算樣本量的方法等。目前市場上的車載終端硬件都有一些數據校正算法對數據進行預處理，剔除或修正異常數據，以保證數據質量。樣本量計算，即根據信息檢測要求或估計精度要求計算所需的浮動車數量，以求在滿足應用精度要求和信息采集成本二者之間尋找平衡點，目前，相關計算方法研究已比較成熟。

交通信息處理技術研究現狀

浮動車信息處理技術浮動車信息處理是實現對浮動車GPS數據的格式轉換、預處理、統計分析、地圖匹配、浮動車最小樣本量估計、從而得到各路段的速度趨勢、旅行時間、路況等交通信息。其中重點研究內容在地圖匹配和行程速度估計2方面。在地圖匹配問題研究方面，國內學者提出了很多算法，例如基于概率統計的地圖匹配算法、基于曲線擬合的地圖匹配算法、基于權重的地圖匹配算法、基于卡爾曼濾波的地圖匹配算法、基于模糊邏輯的地圖匹配算法等［9－13］。針對浮動車數據大規模、長間隔的特點，其算法與傳統的導航地圖匹配算法有一定區別。劉彥挺提出了一種將基于權值、道路拓撲和最優路徑選擇相結合的綜合地圖匹配算法［14］，章威提出了浮動車地圖匹配模型族的解決方案，設計了浮動車數據地圖匹配算法體系［15］。在行程速度估計研究方面，QuirogaCesarA提出了行程速度積分計算方法［16］，董均宇建立了GPS浮動車路段平均速度估計的數據融合模型［17］，章威在對平均速度和平均通過時間算法誤差分析的基礎上，提出了基于浮動車技術的目標路段行車速度估計算法［18］。行程時間預測目前廣泛應用的行程時間預測模型包括:歷史平均模型、ARIMA模型、卡爾曼濾波模型、神經網絡模型和非參數回歸模型等［19］。例如:動態路徑誘導系統中使用歷史平均模型對行程時間進行預測，文獻［20］中使用ARIMA模型對城市主干道的行程時間進行預測，朱中在文獻［21］中使用卡爾曼濾波理論對行程時間進行預測，楊兆升在文獻［22］中建立了基于BP神經網絡的行程時間預測模型，朱耿先在文獻［23］中使用RBF神經網絡對行程時間進行預測。對于短時交通流預測，根據理論基礎的不同，可以將預測方法分為2大類:統計預測方法和人工智能方法［24］。統計預測方法又可以分為回歸分析預測、時間序列預測以及概率預測等。它們均嘗試把交通流參數看成一個時間變量，從而找到這一時間序列中隱含的統計規律或關系。這些方法比較成熟、算法簡單、速度快，但是過分依賴于用數學模型來刻畫交通流特征或者需要很強的經驗判斷，這將直接影響到這類方法的有效性和預測精度。另外，傳統統計學研究的是樣本數目逼近無窮大的漸進理論，當樣本數目有限時就難以取得理想的效果，因此很難適應目前復雜多變的交通狀況。由于受到這些條件的制約，采用統計預測方法進行短時交通流預測的效果并不理想［25］。人工智能方法中的典型代表就是神經網絡方法。神經網絡憑借其逼近任意非線性函數的能力和所具有的容錯、自學習等優點，已被國內外學者用于建立交通流量預測模型，并取得了不少有效的研究成果［26－28］。雖然神經網絡能夠根據歷史數據進行學習訓練和經驗積累，具有自適應能力的優點，但是它得到的結果是基于經驗風險最小化的，需要有足夠大的樣本數據數量，可能還會出現過學習問題以及求得局部極小解的問題［29］。這些不足，使神經網絡在交通流量預測中的應用效果不如期望的那樣好，對于非平穩的短時交通流，當輸入信號中混有噪聲時，神經網絡預測的精度更差［30］。由Vapnik等提出支持向量機(SupportVectorMachines，SVM)的機器學習算法［31］，與傳統的神經網絡學習方法相比，實現了結構風險最小化原理(StructureRiskMinimization，SRM)，它同時最小化經驗風險和VC維(Vapnik－ChervonenkisDimension)的界，這就取得了較小的實際風險，從而對未來的樣本有較好的泛化性能。SVM能夠有效解決小樣本、非線性等回歸問題，泛化能力強，并能找到全局最優解，克服了神經網絡局部極值的難題［32－33］。路徑規劃最優路徑規劃是交通出行信息服務平臺提供信息服務的重要內容之一。在國內外，有大量的關于路徑規劃算法的研究，常見的路徑規劃算法主要有Dijkstra算法，Bellman－Ford算法、Floyd算法、啟發式搜索算法、A*算法等。還有很多為車輛導航而改進的算法，如K最短路徑算法、遺傳算法、蟻群算法和神經網絡算法等［34－35］。為了改進算法的性能和提高算法的適用性，很多學者對相關問題進行了系統和深入的研究。陸峰從問題類型、網絡類型和實現方法3方面對最短路徑算法進行了系統的分類［36］;張可提出了基于路阻函數模型和信號交叉口延誤模型，標定以出行時間度量的道路權重的方法體系，以及適合車輛導航的路徑優化推薦算法［37］，鄭年波根據對偶圖思想，定義搜索節點結構，處理交叉口轉向限制和延誤，并提出了基于搜索節點的雙向啟發式A*算法［38］。Car＆Frank提出了基于層次空間推理的交通網絡行車最優路徑算法［39］。陸峰、付夢印、李清泉、吳一民等人也對分層路徑規劃算法進行了深入研究，提出了切實可行的推理規則和算法，并開展了相關的實驗驗證［40－43］。目前，還有一種研究趨勢是利用從移動對象軌跡數據中挖掘出的“熱點路徑”來輔助路網分層，從而提高層次路徑規劃的合理性和可用性［44－45］。對于動態路徑規劃，蘇永云和晏克非建立了路段動態行程時間計算模型，并運用到動態最短路徑改進A*算法中［46－47］。

交通信息技術發展現狀

交通信息技術常常被研究者所忽視，國內相關的研究不多，工程實踐中也缺乏可行的標準指導。交通信息技術的研究側重包括信息方式和內容的選擇與設計、信息子系統架構、交通信息協議和用于交通信息的移動通信技術。交通信息方式提供信息服務的方式和載體有:交通信息咨詢服務熱線電話、交通信息服務網站查詢、電子信箱定制、移動通信短信息定制或點播、觸摸屏終端查詢、靜態指示牌、電子情報板、交通信息廣播電臺、車載智能交互顯示終端、路側廣播系統等。通常，由于公眾出行信息服務平臺服務對象的廣泛性和服務內容的多樣性，需要多種信息方式綜合以達到最佳效果。交通信息協議目前，面向移動終端的交通信息協議在國際上主要有3個:TMC、TPEG和VICS。TPEG是TMC未來的替布協議，VICS則是日本VICS系統應用的協議［6］。我國的RDS-TMC標準是在參考國際標準中的ISO14189-1/14189-2/14189-3的基礎上，結合我國特點，于2006年11月正式［48］。但目前沒有配套全國統一的位置表(LocationTable)，因此，使用企業內部信息標準，是各交通信息服務商的現實選擇，如文獻［6］中提出的基于LINK的面向移動終端的交通信息協議。交通信息的無線通信技術對移動終端實時交通信息，必須使用無線數據通道，目前可選擇的無線通信技術主要包括:調頻多工數據系統(RDS、DARC)、數字廣播(DAB、CMMB)、蜂窩網絡(2G、2.75G、3G)、專用短程通信(DSRC)。目前國內已建成的WiFi/WLAN和WiMAX網絡由于城市覆蓋范圍小、沒有規模商用、建成該網絡的城市不多等因素，還難以使用于交通信息［6］。(1)RDS廣播數據系統(RDS)由歐洲廣播聯盟組織開發，數據傳輸速率為1.2kbps左右。RDS數據內容可以包括電臺類型、節目類型、交通公告、廣告信息、標準時間、天氣預報等，同時提供了開放式數據接口，為特殊要求用戶提供數據文本應用通道。(2)DARC日本廣播協會(NHK)開發的DARC數據傳輸速率為16kbps，能夠和RDS兼容。VICS系統就是采用DARC完成中心向車載移動接收設備的信息傳輸。RDS和DARC成本低廉、技術成熟、覆蓋范圍廣，且不干擾音頻廣播，目前國內部分城市利用RDS和DARC技術路況信息，終端設備通過嵌入式的FM副載波接收芯片獲取路況信息并實現動態導航過程。(3)DAB數字音頻廣播(DAB)是繼調幅、調頻廣播之后的第3代廣播，具有接收質量高、抗干擾性能強、發射功率小、覆蓋面積大、頻譜利用率高、適合高速移動接收等特點，其數據帶寬為1.2Mbps。DAB目前已在國內部分城市投入商用，路況、新聞、電視與數字廣播等地方性信息服務，相關導航產品也已面世。(4)CMMB中國移動多媒體廣播CMMB是國內自主研發的第一套面向多種移動終端的數據廣播系統，速率范圍在2.7～12Mbps，可以通過無線廣播電視覆蓋網，向各種小屏幕便攜終端提供數字廣播電視節目和信息服務，在2008北京奧運會前開始提供服務，目前已覆蓋全國大部分主要城市和地級市。早在2006年，國家廣電總局就已對CMMB和DAB進行了區別定位和明確劃分:CMMB通過衛星實現全國統一覆蓋，由單一運營商運營;DAB側重本地多媒體業務，由地方不同的運營商分別運營。(5)蜂窩網絡蜂窩網絡是目前最常用的交通信息的通信通道，常用技術包括2.5、2.75G和3G。2.5G是在GSM基礎上添加了GPRS(傳輸速率115.2kbps);2.75G是在GSM基礎上添加了EDGE(傳輸速率384Kbps)，可以說是從2G到3G的最后過渡階段，在CDMA基礎上發展起來的CDMA1X(傳輸速率153.6kbps)也稱為2.75G技術;3G就是TD－SCDMA(傳輸速率2.8Mbps)、CDMA2000EVDO(傳輸速率3.1Mbps)、WCDMA(傳輸速率14.4Mbps)這些更加高速的網絡。2011年，我國移動通信用戶已經超過8.6億，3大運營商2011年凈利潤突破1200億。作為移動通信增值服務的出行信息服務具有巨大的市場發展潛力。(6)DSRC專用短程通信(DSRC)技術是ITS的基礎之一，傳輸速率為250～500kbps，能夠提供高速的數據傳輸，是專門用于車輛通信的技術，它負責在車－路以及車－車之間建立信息雙向傳輸。

交通信息服務質量評價研究現狀

科學的交通出行信息質量評價是評估交通出行信息是否滿足公眾需求的重要手段。目前我國對交通信息質量的評價體系的研究還很少。美國ITS協會于1999年召開了一個關于ATIS數據質量的研討會，并了一份報告，該報告提出了關于檢測器數據、交通事件、圖像和氣象檢測器數據的質量評估準則。美國聯邦公路管理局于2003年了一份關于ATIS系統中的行程時間質量評估報告，在該報告中定義了行程時間的評估內容及評估方法。2004年，美國聯邦公路管理局了“交通數據質量評估報告”，在該報告中，介紹了交通信息質量的評估框架和準則，這些準則針對不同信息使用用戶和使用環境。但在這些文獻有一些缺陷，評價要素(交通參數)不全面或評價指標不全面，而且也沒有多指標的綜合評價方法，不能對交通信息質量進行綜合評價。我國交通信息質量標準尚未，各服務機構尚未以統一的質量標準提供信息，這在一定程度上影響了人們對交通信息的使用［49］。因此，迫切需要形成一個完整的交通信息質量評價體系，為制定國家交通信息質量標準提供理論依據和數據支撐。