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

篇(1)

關(guān)鍵詞 路徑規(guī)劃;全局規(guī)劃;局部規(guī)劃

中圖分類號 TP242 文獻(xiàn)標(biāo)識碼 A 文章編號 1674-6708(2009)10-0067-02

路徑規(guī)劃是指機器人從起始點到目標(biāo)點之間找到一條安全無碰的路徑,是機器人領(lǐng)域的重要課題。移動機器人技術(shù)研究中的一個重要領(lǐng)域是路徑規(guī)劃技術(shù),它分為基于模型的環(huán)境已知的全局路徑規(guī)劃和基于傳感器的環(huán)境未知的局部路徑規(guī)劃。本文綜述了移動機器人路徑規(guī)劃的發(fā)展?fàn)顩r,對移動機器人路徑規(guī)劃技術(shù)的發(fā)展趨勢進行了展望。

根據(jù)機器人工作環(huán)境路徑規(guī)劃模型可分為兩種:基于模型的全局路徑規(guī)劃,這種情況的作業(yè)環(huán)境的全部信息為已知;基于傳感器的局部路徑規(guī)劃,作業(yè)環(huán)境信息全部未知或部分未知,又稱動態(tài)或在線路徑規(guī)劃。

1 全局路徑規(guī)劃

全局路徑規(guī)劃主要方法有:可視圖法、自由空間法、柵格法、拓?fù)浞ā⑸窠?jīng)網(wǎng)絡(luò)法等。

1.1 可視圖法

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

1.2 拓?fù)浞?/p>

拓?fù)浞▽⒁?guī)劃空間分割成具有拓?fù)涮卣鞯淖涌臻g,根據(jù)彼此連通性建立拓?fù)渚W(wǎng)絡(luò),在網(wǎng)絡(luò)上尋找起始點到目標(biāo)點的拓?fù)渎窂?最終由拓?fù)渎窂角蟪鰩缀温窂健Ｍ負(fù)浞ɑ舅枷胧墙稻S法,即將在高維幾何空間中求路徑的問題轉(zhuǎn)化為低維拓?fù)淇臻g中判別連通性的問題。

1.3 柵格法

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

1.4 自由空間法

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

1.5 神經(jīng)網(wǎng)絡(luò)法

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

2 局部路徑規(guī)劃

局部路徑規(guī)劃包括人工勢場法、模糊邏輯算法、神經(jīng)網(wǎng)絡(luò)法、遺傳算法等。

2.1 人工勢場法

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

2.2 模糊邏輯算法

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

2.3 神經(jīng)網(wǎng)絡(luò)法

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

2.4 遺傳算法

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

3 移動機器人路徑規(guī)劃技術(shù)的發(fā)展展望

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

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

參考文獻(xiàn)

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

篇(2)

關(guān)鍵詞：移動機器人；路徑規(guī)劃；A*算法；柵格法

中圖分類號：TP391.4 文獻(xiàn)標(biāo)志碼：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

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

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

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

1 環(huán)境模型描述

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

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

2 A*全局路徑規(guī)劃算法

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

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

xd是目標(biāo)點的橫坐標(biāo)，yd是目標(biāo)點的縱坐標(biāo)，xn是節(jié)點n的橫坐標(biāo)，yn是節(jié)點n的縱坐標(biāo).

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

Step1 把起始節(jié)點放入開啟列表.

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

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

Step4 將當(dāng)前擴展節(jié)點放入關(guān)閉列表中，并檢查終點是否在開啟列表中.如果不在開啟列表中，則跳回Step2繼續(xù)搜索；否則，最優(yōu)路徑已經(jīng)找到，結(jié)束搜索.

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

3 改進的A*算法

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

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

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

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

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開始重復(fù)上述過程，分割直線段L2和L3直到將終點作為路徑點a20時，分割過程結(jié)束.

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

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

路徑3的總轉(zhuǎn)折角度：

其中α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*算法，本文方法縮短了總路徑長度，減小了總轉(zhuǎn)折角度.

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

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

4 實 驗

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

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

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

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

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

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

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

5 結(jié) 論

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

參考文獻(xiàn)

[1] 席裕庚，張純剛.一類動態(tài)不確定環(huán)境下機器人的滾動路徑規(guī)劃[J].自動化學(xué)報，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] 張捍東，鄭睿，岑豫皖.移動機器人路徑規(guī)劃技術(shù)的現(xiàn)狀與展望[J].系統(tǒng)仿真學(xué)報，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] 朱大奇，顏明重.移動機器人路徑規(guī)劃技術(shù)綜述[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] 吳乙萬，黃智.基于動態(tài)虛擬障礙物的智能車輛局部路徑規(guī)劃方法[J].湖南大學(xué)學(xué)報：自然科學(xué)版，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] 楊淮清，肖興貴，姚棟.一種基于可視圖法的機器人全局路徑規(guī)劃算法[J].沈陽工業(yè)大學(xué)學(xué)報，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īng)網(wǎng)絡(luò)在移動機器人路徑規(guī)劃中的應(yīng)用[J].系統(tǒng)仿真學(xué)報，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] 郝冬，劉斌.基于模糊邏輯行為融合路徑規(guī)劃方法[J].計算機工程與設(shè)計，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]鄧高峰，張雪萍，劉彥萍.一種障礙環(huán)境下機器人路徑規(guī)劃的蟻群粒子群算法[J].控制理論與應(yīng)用，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]吳憲祥，郭寶龍，王娟.基于粒子群三次樣條優(yōu)化的移動機器人路徑規(guī)劃算法[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]王雪松，高，程玉虎，等.知識引導(dǎo)遺傳算法實現(xiàn)機器人路徑規(guī)劃[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*算法的室內(nèi)移動機器人路徑規(guī)劃[J].清華大學(xué)學(xué)報：自然科學(xué)版，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]王紅衛(wèi)，馬勇，謝勇，等.基于平滑A*算法的移動機器人路徑規(guī)劃[J].同濟大學(xué)學(xué)報：自然科學(xué)版，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)

關(guān)鍵詞：儲位分配；訂單分批；揀選路徑；仿真技術(shù)

中圖分類號：F715.6 文獻(xiàn)標(biāo)識碼：A 文章編號：1001-828X（2014）010-00-01

引言

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

一、儲位分配問題

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

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

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

二、訂單分批問題

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

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

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

此外，國內(nèi)外學(xué)者也提出采用遺傳算法、啟發(fā)式算法等來求解訂單分批問題。

三、揀選路徑問題

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

四、揀選作業(yè)系統(tǒng)仿真技術(shù)

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

參考文獻(xiàn)：

[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]陳璐，陸志強.自動化立體倉庫中的儲位分配及存取路徑優(yōu)化[J].管理工程學(xué)報，2012，26（1）：42-47.

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

篇(4)

關(guān)鍵詞：庫存配送系統(tǒng)；聯(lián)合優(yōu)化；遺傳算法；C-W算法

一、庫存與配送系統(tǒng)聯(lián)合優(yōu)化研究分類

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

一類研究基于供應(yīng)鏈整體成本，構(gòu)建模型求得整體的訂貨量與配送策略。此類研究綜合考慮了供應(yīng)鏈各節(jié)點企業(yè)的三大成本“庫存、采購與運輸”，基于各方需求統(tǒng)一確定，互相了解需求，并且不允許缺貨情況的發(fā)生，運輸服務(wù)統(tǒng)一由第三方提供，構(gòu)建的目標(biāo)優(yōu)化模型以生產(chǎn)商的生產(chǎn)成本、零售商的采購、庫存成本，以及運輸服務(wù)提供方的運輸成本，以此求得最優(yōu)解。但是該類研究沒有考慮供應(yīng)鏈參與各方的合作情況，各方對于利益的分配、成本的分?jǐn)倷C制沒有考慮，容易造成分配不均而產(chǎn)生摩擦。

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

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

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

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

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

二、庫存與配送系統(tǒng)聯(lián)合優(yōu)化模型構(gòu)建

庫存與配送系統(tǒng)聯(lián)合優(yōu)化是促進供應(yīng)鏈一體化的有效手段，本文基于供應(yīng)商統(tǒng)一管理庫存構(gòu)建一個供應(yīng)商對多個零售商配送的簡單兩級供應(yīng)鏈模型。

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

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

篇(5)

關(guān)鍵詞：迷宮問題，機器人，深度優(yōu)先

 

0 引言

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

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

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

1迷宮機器人結(jié)構(gòu)描述

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

1.1機械結(jié)構(gòu)描述

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

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

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

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

1.2傳感器系統(tǒng)

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

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

1.3 控制系統(tǒng)

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

2 迷宮問題描述

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

3算法仿真試驗

3.1算法描述如下：

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

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

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

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

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

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

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

：輸出可行路徑。

3.2實驗結(jié)果過程及結(jié)果：

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

4 物理系統(tǒng)實現(xiàn)：

圖 3 深度優(yōu)先算法找到的路徑示意圖

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

5結(jié)論：

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

 

參考文獻(xiàn)：

[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].電路與系統(tǒng)學(xué)報.2005,10(3)： 72-75.

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

篇(6)

關(guān)鍵詞TSP問題 0-1規(guī)劃 智能算法

中圖分類號：O158 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2014）05-0139-02

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

1 TSP問題描述

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

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

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

2.1 貪婪算法

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

2.2 模擬退火算法

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

2.3 遺傳算法

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

2.4 粒子群算法

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

2.5 蟻群算法

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

3 實例計算

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

圖1為四種智能算法的收斂狀態(tài)。

4 各種求解算法的比較

根據(jù)本文的實例計算和相關(guān)文獻(xiàn)[7]，可以給出各算法的比較。

5 結(jié)語

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

參考文獻(xiàn)

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

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

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

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

[5]嚴(yán)露.粒子群算法研究與應(yīng)用[D].電子科技大學(xué)碩士論文，2013.

篇(7)

交通信息采集技術(shù)研究現(xiàn)狀

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

交通信息處理技術(shù)研究現(xiàn)狀

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

交通信息技術(shù)發(fā)展現(xiàn)狀

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

交通信息服務(wù)質(zhì)量評價研究現(xiàn)狀

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