基于校園園區(qū)的送貨機(jī)器人全局路徑規(guī)劃

李亞正，王 豐

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

0 引言

近年來(lái)物流行業(yè)發(fā)展迅速，由于客戶需求的多樣性，網(wǎng)購(gòu)商品的種類越來(lái)越多，并且購(gòu)買者的收貨地點(diǎn)往往不集中，這對(duì)快遞配送的效率要求很高。自主送貨機(jī)器人作為高度智能化產(chǎn)品，可有效解決電子商務(wù)“最后一公里”面臨的困境。路徑規(guī)劃技術(shù)是實(shí)現(xiàn)機(jī)器人自主行駛的基礎(chǔ)，研究自主送貨機(jī)器人路徑規(guī)劃技術(shù)可有效解決當(dāng)前電子商務(wù)面臨的配送難的問題，因此，開展對(duì)自主送貨機(jī)器人的研究符合物流行業(yè)當(dāng)下的實(shí)際需求，具有重要的意義。

1 全局路徑規(guī)劃流程

在所建立的園區(qū)電子地圖上進(jìn)行全局路徑規(guī)劃主要包括兩個(gè)方面：建立電子地圖和全局路徑規(guī)劃[1]。

建立電子地圖分為園區(qū)地圖的抽象、路阻的標(biāo)定及園區(qū)電子地圖的存儲(chǔ)三個(gè)步驟。地圖抽象是將道路交叉口抽象為拓?fù)鋱D中的頂點(diǎn)，道路抽象為邊，這樣就將園區(qū)地圖抽象為頂點(diǎn)和邊的集合；路阻標(biāo)定也就是對(duì)車道抽象成的邊進(jìn)行賦值；電子地圖的存儲(chǔ)是將拓?fù)鋱D的信息進(jìn)行存儲(chǔ)。

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

2 全局路徑規(guī)劃

2.1 路網(wǎng)抽象

以某大學(xué)校園作為全局路徑規(guī)劃的環(huán)境，通過對(duì)路網(wǎng)的結(jié)構(gòu)進(jìn)行分析，采用圖論中的拓?fù)鋱D來(lái)表示路網(wǎng)，根據(jù)校園地圖中的道路拓?fù)潢P(guān)系進(jìn)行圖的頂點(diǎn)和邊的抽象，將標(biāo)定的點(diǎn)抽象為拓?fù)鋱D中的點(diǎn)，道路節(jié)點(diǎn)間路段抽象成拓?fù)鋱D中的邊，完成地圖的抽象。將路網(wǎng)抽象成的拓?fù)涞貓D如圖1所示，在校園區(qū)域內(nèi)標(biāo)定了81個(gè)節(jié)點(diǎn)。考慮到送貨機(jī)器人在快遞站點(diǎn)裝取貨物，對(duì)多個(gè)目標(biāo)點(diǎn)進(jìn)行配送，將點(diǎn)1(三角形地標(biāo))設(shè)定為機(jī)器人配送站，即機(jī)器人配送的起點(diǎn)與終點(diǎn)，并在校園區(qū)域內(nèi)選定了16個(gè)配送點(diǎn)，對(duì)應(yīng)的節(jié)點(diǎn)為點(diǎn)2～點(diǎn)17(方形地標(biāo))。

圖1 拓?fù)浣Y(jié)構(gòu)效果圖

2.2 路阻標(biāo)定

對(duì)于路阻的評(píng)價(jià)，實(shí)際上就是出行費(fèi)用的計(jì)算過程[2]。路阻有多種含義，如果要求規(guī)劃出的路徑長(zhǎng)度最短，則將路阻設(shè)置為道路的長(zhǎng)度；如果要求機(jī)器人行駛的時(shí)間最短，則路阻設(shè)置為道路的行駛時(shí)間。研究對(duì)象為校園園區(qū)，道路較規(guī)范并且不擁堵，因此以道路長(zhǎng)度作為路阻最合理。

使用BIGEMAP坐標(biāo)采集系統(tǒng)中的谷歌地球無(wú)偏移地圖，采集校園道路交叉口的大地坐標(biāo)。在實(shí)際的采集系統(tǒng)使用過程中，直接采集的坐標(biāo)通常是以WGS-84坐標(biāo)系為基準(zhǔn)坐標(biāo)系測(cè)得的大地坐標(biāo)，由于大地坐標(biāo)無(wú)法直接用于電子地圖的建立，因此還需要對(duì)所測(cè)得的大地坐標(biāo)進(jìn)行高斯-克呂格投影，將所提取的大地坐標(biāo)轉(zhuǎn)換為平面坐標(biāo)。

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

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

圖2 高斯-克呂格投影

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

圖3 高斯-克呂格平面直角坐標(biāo)系

高斯-克呂格平面直角坐標(biāo)系中每帶以中央經(jīng)線投影后的直線為X軸，以赤道投影后的直線為Y軸，兩軸交點(diǎn)為每個(gè)投影帶的坐標(biāo)原點(diǎn)。我國(guó)地處北半球，X值都為正值，而在每個(gè)投影帶中央經(jīng)線左邊坐標(biāo)值為負(fù)，規(guī)定使縱坐標(biāo)軸向左平移500 km，避免Y坐標(biāo)出現(xiàn)負(fù)值[5]。

高斯投影的思想是通過經(jīng)差對(duì)地球球面劃分投影帶來(lái)限制長(zhǎng)度方向的變形。為減少投影變形，分帶的經(jīng)差通常為6°或3°，即六度帶投影和三度帶投影[6]，本文采用六度帶投影。要想獲得互通的兩節(jié)點(diǎn)間道路長(zhǎng)度，就需要知道各節(jié)點(diǎn)的平面坐標(biāo)，使用BIGEMAP坐標(biāo)采集系統(tǒng)采集圖1拓?fù)浣Y(jié)構(gòu)效果圖中的道路節(jié)點(diǎn)的大地坐標(biāo)。以節(jié)點(diǎn)1～節(jié)點(diǎn)5為例，WGS-84坐標(biāo)系下這些節(jié)點(diǎn)的大地坐標(biāo)(B，L)和經(jīng)過投影后的平面坐標(biāo)(X，Y)如表1所示。

表1 BIGEMAP采集的部分?jǐn)?shù)據(jù)及轉(zhuǎn)換值

獲取了各節(jié)點(diǎn)的平面坐標(biāo)便可得到兩互通節(jié)點(diǎn)間的道路長(zhǎng)度，以道路長(zhǎng)度作為路阻。部分節(jié)點(diǎn)間的路阻如表2所示。

表2 部分節(jié)點(diǎn)間的路阻

2.3 電子地圖存儲(chǔ)

電子地圖的存儲(chǔ)表示方法是多種多樣的，例如鄰接矩陣、十字鏈表和鄰接表等[7]。本文采用鄰接矩陣這種存儲(chǔ)結(jié)構(gòu)，該矩陣可以表示圖中頂點(diǎn)間的相鄰關(guān)系。

鄰接矩陣的存儲(chǔ)“是通過一維數(shù)組來(lái)存儲(chǔ)圖中節(jié)點(diǎn)的信息，再由二維數(shù)組即矩陣來(lái)表示各節(jié)點(diǎn)之間的鄰接關(guān)系”。通過校園地圖的抽象及路阻的標(biāo)定，在此基礎(chǔ)上運(yùn)用MATLAB編寫鄰接矩陣。鄰接矩陣的創(chuàng)建過程如下：

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

(2) 初始化鄰接矩陣，Inf代表兩個(gè)頂點(diǎn)之間無(wú)通路，表示不互通。

(3) 將兩節(jié)點(diǎn)間道路的權(quán)值放入鄰接矩陣中，同一節(jié)點(diǎn)間路阻為0。

本文在校園地圖內(nèi)選取了81個(gè)節(jié)點(diǎn)，通過計(jì)算各節(jié)點(diǎn)間的距離得到了各鄰接點(diǎn)的距離矩陣。本文所建立的電子地圖的部分鄰接矩陣如表3所示。

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

2.4 路徑搜索及道路還原

在全局路徑規(guī)劃中，基于圖形學(xué)的路徑規(guī)劃算法要與建模中的地圖構(gòu)建集成使用，所以校園電子地圖建立好之后，需要采用路徑規(guī)劃算法進(jìn)行搜索來(lái)完成機(jī)器人對(duì)多個(gè)目標(biāo)點(diǎn)的配送任務(wù)。

模擬退火算法適用于計(jì)算多目標(biāo)點(diǎn)的最短路徑問題，可以計(jì)算出圖中某一節(jié)點(diǎn)到所需要經(jīng)過的多個(gè)節(jié)點(diǎn)間的最短路徑，相比其他算法具有原理簡(jiǎn)單、運(yùn)算速度快的優(yōu)點(diǎn)。

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

圖4 路徑規(guī)劃結(jié)果圖

3 結(jié)論

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