基于校園園區的送貨機器人全局路徑規劃

李亞正，王 豐

(華北理工大學 機械工程學院，河北 唐山 063210)

0 引言

近年來物流行業發展迅速，由于客戶需求的多樣性，網購商品的種類越來越多，并且購買者的收貨地點往往不集中，這對快遞配送的效率要求很高。自主送貨機器人作為高度智能化產品，可有效解決電子商務“最后一公里”面臨的困境。路徑規劃技術是實現機器人自主行駛的基礎，研究自主送貨機器人路徑規劃技術可有效解決當前電子商務面臨的配送難的問題，因此，開展對自主送貨機器人的研究符合物流行業當下的實際需求，具有重要的意義。

1 全局路徑規劃流程

在所建立的園區電子地圖上進行全局路徑規劃主要包括兩個方面：建立電子地圖和全局路徑規劃[1]。

建立電子地圖分為園區地圖的抽象、路阻的標定及園區電子地圖的存儲三個步驟。地圖抽象是將道路交叉口抽象為拓撲圖中的頂點，道路抽象為邊，這樣就將園區地圖抽象為頂點和邊的集合；路阻標定也就是對車道抽象成的邊進行賦值；電子地圖的存儲是將拓撲圖的信息進行存儲。

全局路徑規劃分為路徑搜索及道路還原兩步。路徑搜索是在電子地圖建立好之后，根據機器人配送的要求在地圖中選擇起點和目標點，然后利用路徑規劃算法規劃出起點和終點之中總路阻最小的路徑;道路還原是將規劃出的路徑還原成真實路徑。

2 全局路徑規劃

2.1 路網抽象

以某大學校園作為全局路徑規劃的環境，通過對路網的結構進行分析，采用圖論中的拓撲圖來表示路網，根據校園地圖中的道路拓撲關系進行圖的頂點和邊的抽象，將標定的點抽象為拓撲圖中的點，道路節點間路段抽象成拓撲圖中的邊，完成地圖的抽象。將路網抽象成的拓撲地圖如圖1所示，在校園區域內標定了81個節點?？紤]到送貨機器人在快遞站點裝取貨物，對多個目標點進行配送，將點1(三角形地標)設定為機器人配送站，即機器人配送的起點與終點，并在校園區域內選定了16個配送點，對應的節點為點2～點17(方形地標)。

圖1 拓撲結構效果圖

2.2 路阻標定

對于路阻的評價，實際上就是出行費用的計算過程[2]。路阻有多種含義，如果要求規劃出的路徑長度最短，則將路阻設置為道路的長度；如果要求機器人行駛的時間最短，則路阻設置為道路的行駛時間。研究對象為校園園區，道路較規范并且不擁堵，因此以道路長度作為路阻最合理。

使用BIGEMAP坐標采集系統中的谷歌地球無偏移地圖，采集校園道路交叉口的大地坐標。在實際的采集系統使用過程中，直接采集的坐標通常是以WGS-84坐標系為基準坐標系測得的大地坐標，由于大地坐標無法直接用于電子地圖的建立，因此還需要對所測得的大地坐標進行高斯-克呂格投影，將所提取的大地坐標轉換為平面坐標。

已知橢球面上的大地坐標緯度B、經度L，求平面坐標X、Y的問題稱為高斯投影正算[3]，也就是將基于WGS-84坐標系采集的道路交叉口的大地坐標根據高斯-克呂格投影正算法轉換為平面坐標。

如圖2所示，高斯-克呂格投影的幾何概念是：假定有一個橢圓柱與地球橢球體上某一經線相切，其橢圓柱的中心軸位于赤道平面上，而后按等角投影的條件將中央子午線兩側各一定經差范圍內的地區投影到橢圓柱面上，再將此柱面展開即成為投影面[4]。

圖2 高斯-克呂格投影

圖2中陰影部分的投影面展開如圖3所示，中央子午線的投影是縱坐標軸X，赤道的投影是橫坐標軸Y。

圖3 高斯-克呂格平面直角坐標系

高斯-克呂格平面直角坐標系中每帶以中央經線投影后的直線為X軸，以赤道投影后的直線為Y軸，兩軸交點為每個投影帶的坐標原點。我國地處北半球，X值都為正值，而在每個投影帶中央經線左邊坐標值為負，規定使縱坐標軸向左平移500 km，避免Y坐標出現負值[5]。

高斯投影的思想是通過經差對地球球面劃分投影帶來限制長度方向的變形。為減少投影變形，分帶的經差通常為6°或3°，即六度帶投影和三度帶投影[6]，本文采用六度帶投影。要想獲得互通的兩節點間道路長度，就需要知道各節點的平面坐標，使用BIGEMAP坐標采集系統采集圖1拓撲結構效果圖中的道路節點的大地坐標。以節點1～節點5為例，WGS-84坐標系下這些節點的大地坐標(B，L)和經過投影后的平面坐標(X，Y)如表1所示。

表1 BIGEMAP采集的部分數據及轉換值

獲取了各節點的平面坐標便可得到兩互通節點間的道路長度，以道路長度作為路阻。部分節點間的路阻如表2所示。

表2 部分節點間的路阻

2.3 電子地圖存儲

電子地圖的存儲表示方法是多種多樣的，例如鄰接矩陣、十字鏈表和鄰接表等[7]。本文采用鄰接矩陣這種存儲結構，該矩陣可以表示圖中頂點間的相鄰關系。

鄰接矩陣的存儲“是通過一維數組來存儲圖中節點的信息，再由二維數組即矩陣來表示各節點之間的鄰接關系”。通過校園地圖的抽象及路阻的標定，在此基礎上運用MATLAB編寫鄰接矩陣。鄰接矩陣的創建過程如下：

(1) 將全局地圖抽象為拓撲圖之后，確定每條邊的路阻。

(2) 初始化鄰接矩陣，Inf代表兩個頂點之間無通路，表示不互通。

(3) 將兩節點間道路的權值放入鄰接矩陣中，同一節點間路阻為0。

本文在校園地圖內選取了81個節點，通過計算各節點間的距離得到了各鄰接點的距離矩陣。本文所建立的電子地圖的部分鄰接矩陣如表3所示。

表3 部分校園地圖鄰接矩陣 m

2.4 路徑搜索及道路還原

在全局路徑規劃中，基于圖形學的路徑規劃算法要與建模中的地圖構建集成使用，所以校園電子地圖建立好之后，需要采用路徑規劃算法進行搜索來完成機器人對多個目標點的配送任務。

模擬退火算法適用于計算多目標點的最短路徑問題，可以計算出圖中某一節點到所需要經過的多個節點間的最短路徑，相比其他算法具有原理簡單、運算速度快的優點。

由建立的電子地圖鄰接矩陣，通過MATLAB編寫適用于鄰接矩陣的模擬退火算法程序。對基于校園區域建立的電子地圖進行最短路徑規劃，首先將鄰接矩陣導入MATLAB，機器人需要在點1裝取貨物，設定點1為起始點，途中要經過2、3、12這三個配送點，配送完畢后，回到點1。所規劃的全局最短路徑由以下道路節點構成：1-19-34-4-36-29-81-80-54-55-11-61-12-64-79-78-18-3-39-1，該最短路徑長度為2 455.34 m。最后將規劃出的道路節點還原成實際交通地圖中的真實路徑，如圖4所示，箭頭所指引的路徑為規劃的最短路徑。

圖4 路徑規劃結果圖

3 結論

本文通過對某校園地圖進行抽象，并在建立電子地圖的基礎上完成了全局路徑規劃，并將抽象的路線還原成實際交通地圖中的真實路徑。本文通過多次仿真，調整參數，在一定程度上克服了算法本身的缺點。在實際生活中，路徑規劃算法在機器人配送問題上仍有提高空間。本文將模擬退火算法應用于自主送貨機器人路徑規劃中，旨在為電子商務物流配送問題的創新提供參考。