李亞正，王 豐

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

0 引言

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

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

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

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

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

2 全局路徑規(guī)劃

2.1 路網(wǎng)抽象

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

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

2.2 路阻標(biāo)定

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

使用BIGEMAP坐標(biāo)采集系統(tǒng)中的谷歌地球無偏移地圖，采集校園道路交叉口的大地坐標(biāo)。在實際的采集系統(tǒng)使用過程中，直接采集的坐標(biāo)通常是以WGS-84坐標(biāo)系為基準(zhǔn)坐標(biāo)系測得的大地坐標(biāo)，由于大地坐標(biāo)無法直接用于電子地圖的建立，因此還需要對所測得的大地坐標(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所示，高斯-克呂格投影的幾何概念是：假定有一個橢圓柱與地球橢球體上某一經(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軸，兩軸交點為每個投影帶的坐標(biāo)原點。我國地處北半球，X值都為正值，而在每個投影帶中央經(jīng)線左邊坐標(biāo)值為負(fù)，規(guī)定使縱坐標(biāo)軸向左平移500 km，避免Y坐標(biāo)出現(xiàn)負(fù)值[5]。

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

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

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

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

2.3 電子地圖存儲

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

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

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

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

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

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

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

2.4 路徑搜索及道路還原

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

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

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

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

3 結(jié)論

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