基于柵格模型的運輸路徑規(guī)劃方法

基于網(wǎng)格模型的路徑規(guī)劃方法有很多文獻，但都存在一些缺陷。比如:文獻存在搜索空間大、效率不高和實時性不強等問題;文獻雖能搜索到安全路徑,但不能搜索到最優(yōu)路徑,并且該算法不能處理網(wǎng)絡特征權(quán)值畸形分布的特殊情況,不能完全保證結(jié)果的最佳性。因此,文中在研究調(diào)運路徑規(guī)劃問題的過程中,采用柵格模型表示調(diào)運環(huán)境,通過設定路徑搜索方向權(quán)重,縮小了搜索區(qū)域,使得算法能較快搜索到優(yōu)化的調(diào)運路徑。1問題描述1.1實體的分析和表達根據(jù)實體的幾何特征,提取其特征點,按照一定比例尺進行縮放,將調(diào)運區(qū)域中的所有實體表示成不同形狀的多邊形。1.2維柵格的形成根據(jù)實體在調(diào)運空間中的布列,將調(diào)運空間柵格化,并且按照一定的比例尺建立調(diào)運實體環(huán)境地圖。文中的調(diào)運空間規(guī)定為矩形,記為S。在S中以S的左上角為坐標原點O,以橫向為x軸,縱向為y軸建立系統(tǒng)直角坐標系。將S劃分成m×n個正方形柵格(m行,n列),柵格規(guī)格為1個單位。當被調(diào)運實體的質(zhì)心與劃分的柵格中心重合時,可在該柵格內(nèi)作自由運動。未被調(diào)運的實體視為靜態(tài)障礙物,其占據(jù)的柵格用陰影表示,記為集合B,B={b1,b2,…,bn}。記g∈S為任意柵格,A為g的集合,B?A為靜態(tài)障礙物集。S中所有空白柵格(即自由柵格)對應的編號所組成的集合記為F,顯然F∪B=A。?g∈A在坐標系中都有確定的坐標(x,y),記作g(x,y),其中:x為g所在的列號;y為g所在的行號。采用m×n階的二維數(shù)組為柵格編號(見圖1)。路徑規(guī)劃的目的是使實體由任意柵格gi安全地沿一條較短路徑到達目的柵格gj。其約束條件為gi,gj∈F,i≠j。2路徑規(guī)劃算法2.1單個元素存儲路徑根據(jù)柵格圖結(jié)構(gòu),按照從上至下、從左至右的順序建立升序結(jié)點數(shù)組集合A={a11,a12,…,amn}。集合的每個元素設置輔助存儲路徑結(jié)點搜索數(shù)組pathnodedistance(PND),數(shù)組數(shù)據(jù)項包括結(jié)點本身,其前趨柵格結(jié)點及路徑累積距離為d(aij-ai′j′)。數(shù)組存儲結(jié)構(gòu)如圖2所示,如果是自由柵格,其前趨結(jié)點則置空;如果是障礙物柵格,其前趨結(jié)點則置∞。2.2搜索ai的結(jié)論根據(jù)柵格編號規(guī)律,通過8個鄰接方位的數(shù)組下標與當前柵格數(shù)組下標的關(guān)系,建立其下一步搜索結(jié)點元素集合。記結(jié)點aij的8個鄰接方位數(shù)組集合為Next(aij)={ai,j+1,ai+1,j+1,ai+1,j,ai+1,j?1,ai,j?1,ai?1,j?1,ai?1,j,ai?1,j+1};(1)Νext(aij)={ai,j+1,ai+1,j+1,ai+1,j,ai+1,j-1,ai,j-1,ai-1,j-1,ai-1,j,ai-1,j+1};(1)下一步要搜索記錄的有效結(jié)點集合為search(aij)=Next(aij)?B∩Next(aij)。(2)search(aij)=Νext(aij)-B∩Νext(aij)。(2)其中,結(jié)點元素依次對應于從當前柵格位置右方1開始,沿順時針旋轉(zhuǎn)排列的8個鄰接方向(見圖3)。2.3中心方程的距離方位距離指當前柵格與它的鄰接柵格的距離。定義為兩個柵格中心之間的距離。因此,當前柵格與它相鄰的8個方位的距離值分別為δ(k)=[1,2√,1,2√,1,2√,1,2√],1≤k≤8。(3)δ(k)=,1≤k≤8。(3)2.4鄰接方位的選擇基于兩點之間直線最短的思想,從起始柵格中心與目標柵格中心的連接線所經(jīng)過的柵格作為路徑選擇的概率最大。假設路徑起始位置為圖4中start,目標位置為goal。為了使每次尋優(yōu)都不偏離目標,而盡量向接近目標點的方向運動,當前柵格鄰接方位的位置顯得極為重要。對于8個鄰接方位,按照圖3所示方向,根據(jù)經(jīng)驗值,給出方位選擇的權(quán)重如下:w(k)=[0.18,0.30,0.18,0.09,0.06,0.03,0.06,0.09],1≤k≤8。(4)w(k)=[0.18,0.30,0.18,0.09,0.06,0.03,0.06,0.09],1≤k≤8。(4)可以看出,起始柵格右下方的柵格因為距離目標點最近,其權(quán)重值設定為0.3;而左上方的柵格因為會使得路徑遠離目標柵格,其重要性值最小,為0.03。2.5索方位權(quán)重排序為了保證路徑選擇的多樣性,從起始結(jié)點開始,根據(jù)環(huán)境地圖,將路徑搜索方位權(quán)重排序,設定K的值。K表示選擇的方向結(jié)點數(shù),如果K=3,則從起始結(jié)點開始,選擇權(quán)重排名前三位的3個搜索方向結(jié)點,被選擇的3個結(jié)點再按權(quán)重排序選擇3個搜索方向。依次類推,直至找到目標結(jié)點。2.6搜索符合前趨柵格及其累積路徑距離步驟1初始化環(huán)境地圖。定義A,PND,search(aij),w(k),δ(k),設置參數(shù)K;步驟2確定起點aij和目標點auv,將起點設置為待搜索結(jié)點,其前趨結(jié)點設置為本身,累積路徑距離(以下簡稱距離)為0。步驟3從起始結(jié)點開始,按式(2)(4)及K值確定下一步搜索結(jié)點,將搜索結(jié)點坐標與目標點坐標auv比較,若相同則轉(zhuǎn)步驟4;否則,在PND中記錄其前趨柵格結(jié)點及累積路徑距離。按照search(aij)的搜索方向定位搜索結(jié)點,根據(jù)式(2)(4)及K值決定下一步搜索結(jié)點,對沒有訪問過的結(jié)點,記錄其前趨柵格結(jié)點,并標記其累積路徑距離;對已訪問過的結(jié)點,則比較其累積距離,如果不小于其標記距離,則不更新該結(jié)點,否則更新該結(jié)點及距離。本步驟循環(huán)執(zhí)行,直到找到目標結(jié)點。步驟4從終點結(jié)點開始,搜索其前趨柵格結(jié)點并記錄直至起始結(jié)點,所記錄的結(jié)點的連線即是最短路徑。運算結(jié)束。3試驗結(jié)果與分析按照文中的路徑規(guī)劃算法,在Matlab下進行仿真試驗。假設障礙物柵格數(shù)目為14個。得到的路徑如圖4所示。表1為文中算法與文獻算法在相同的柵格環(huán)境下(柵格規(guī)模為300×400,障礙物采用不同的布列方式)進行多次實驗的統(tǒng)計結(jié)果。由表1可知,本文算法的搜索效率較高。4權(quán)重的方