（浙江萬里學(xué)院，浙江 寧波 315100）

1 引言

隨著電子商務(wù)行業(yè)的迅速發(fā)展，網(wǎng)絡(luò)購物成為一種潮流，很大一部分人熱衷于通過網(wǎng)絡(luò)購買需要的東西。在這樣的發(fā)展趨勢下，人們對物流服務(wù)也越來越重視，而運轉(zhuǎn)效率就是物流服務(wù)的一個重要指標(biāo)。對于普通客戶來講，速度是評價服務(wù)的重要標(biāo)準(zhǔn)之一。

倉庫作為貨物運轉(zhuǎn)的節(jié)點，對貨物運轉(zhuǎn)有著至關(guān)重要的影響?，F(xiàn)如今大多數(shù)的倉庫自動化水平還比較低，訂單的揀選基本依靠勞動力完成，這樣一來效率低，二來錯誤率高，用戶體驗較差。并且現(xiàn)今人力成本上升，傳統(tǒng)的工作方式早已不能滿足社會需求[1]。

為解決這樣的窘境，各大運營商紛紛在機器人方面加大投入研發(fā)，比較典型的如亞馬遜的Kiva機器人、阿里巴巴的“曹操”機器人、京東的六軸機械臂等，目前已有部分倉庫將機器人運用到現(xiàn)實的作業(yè)中。在電商倉庫配送中心的搬運成本中，揀貨的搬運成本約占90%，與揀貨直接相關(guān)的人力占50%。揀貨時間約占整個配送中心操作時間的30%-40%。在配送過程中，揀貨是整個配送中心操作系統(tǒng)的核心，合理規(guī)劃與管理揀貨過程，對配送中心工作效率的提高具有決定性的影響。

本文就提高電商倉庫配送中心工作效率提出揀貨機器人路徑優(yōu)化方法，就路徑優(yōu)化中的最短路徑及多機器人之間的避障進行研究并建模得出結(jié)果。

2 方案設(shè)計

2.1 地圖設(shè)計

合理的倉庫地圖設(shè)計有利于倉庫存儲物資的合理安排，能夠降低倉庫工作人員的工作量，減少不必要的重復(fù)勞動。倉庫路徑、貨架的合理布局有利于通道的暢通，確保倉庫工作人員和機器人的通行安全。地圖的設(shè)計應(yīng)根據(jù)貨物種類、障礙物位置、倉庫規(guī)模等因素做一些合理的規(guī)劃。

圖文件使用Tiled Map輔助繪制，實驗根據(jù)貨架位置及障礙物位置做一個簡單的路徑設(shè)計，具體倉庫地圖結(jié)構(gòu)如圖1所示，其中包括貨架位置、障礙物、路徑以及路徑的交叉點。為方便機器人與服務(wù)器的信息溝通，每個交叉點處會設(shè)置二維碼以表示該交叉點在地圖上的坐標(biāo)位置，由于交叉點為一個正方形，這里以正方形左上角位置為交叉點坐標(biāo)并設(shè)置相應(yīng)序號。圖文件完成同時生成tmx文件，JAVA語言讀取文件生成有效信息。這里的有效信息主要是路徑和路徑交叉點的相關(guān)描述，包括序號、長度、坐標(biāo)等[2]。如：

以上是交叉點描述信息以及交叉點信息的二維碼描述方式，其中id表示的信息包含該點的所在圖層、序號及其坐標(biāo)。二維碼信息表示該點坐標(biāo)。

圖1 倉庫圖

以上是路徑描述信息，id表示該路徑起點與終點坐標(biāo)，point表示起點與終點信息。

下面根據(jù)路徑與交叉點的關(guān)系生成矩陣，矩陣的行和列分別為兩個點的序號。當(dāng)圖中兩點可通過某條路徑相連接，則在矩陣相對應(yīng)的位置輸出1，不能連接的輸出0。這樣最后輸出一個m×m的矩陣，矩陣可直觀的表示出圖信息。第二個矩陣與第一個矩陣類似，兩點不能連接的輸出0，可通過某條路徑連接的輸出該路徑的長度。至此地圖信息對應(yīng)的矩陣初步形成。

機器人每到一個節(jié)點掃描到二維碼信息，同時向服務(wù)器發(fā)送實時位置，服務(wù)器根據(jù)此信息確定機器人接下來的路徑同時向機器人發(fā)送行動指令。為避免多機器人路徑?jīng)_突，當(dāng)機器人向服務(wù)器發(fā)送定點位置時，將下一步運行的路徑置∞，即斷開該路徑，這樣避免同時工作的機器人路過此路徑，實現(xiàn)多機器人之間的避障。

2.2 數(shù)據(jù)庫設(shè)計

常見的數(shù)據(jù)庫類型有Oracle、SQL Server、MySQL等。綜合數(shù)據(jù)容量、價格以及操作難易程度等因素，本次實驗選擇了MySQL數(shù)據(jù)庫。

JSP通過Connection接口訪問數(shù)據(jù)庫，java.sql.Satatement接口用來執(zhí)行靜態(tài)的SQL語句，java.sql.PreparedSatatement接口執(zhí)行動態(tài)的SQL語句。

實驗中數(shù)據(jù)庫新建兩個表。表1存儲各類商品的揀貨點等信息。當(dāng)訂單產(chǎn)生時得到一個訂單中所有商品的名稱，服務(wù)器根據(jù)商品名稱從數(shù)據(jù)庫獲得對應(yīng)取貨點，將這些取貨點加入到一個工作進程中，并發(fā)布給機器人開始工作。表2存儲機器人序號、機器人所在位置的坐標(biāo)以及該坐標(biāo)對應(yīng)交叉點的序號。當(dāng)機器人運行到某交叉點掃描到二維碼，將自身序號以及二維碼包含的信息輸入到數(shù)據(jù)庫，當(dāng)二維碼顯示的點序號與取貨點的序號一致，則機器人執(zhí)行取貨行為。

2.3 算法設(shè)計

求最短路徑的算法有很多，常用的方法有人工勢場法[3]、A*算法[4]等，都是針對簡單的點到點的路徑規(guī)劃任務(wù)。本次設(shè)計選用Dijkstra算法與最鄰近算法相結(jié)合，以整體時間最優(yōu)為目標(biāo)。

Dijkstra算法首先是得到起點V0到其他各頂點距離，V0-＞V0的權(quán)值為0，當(dāng) V0與Vi可連接，其權(quán)值為V0-＞Vi的長度，當(dāng) V0與 Vi不可連接，V0-＞Vi權(quán)值為∞，這樣可得到一個描繪路徑權(quán)值的矩陣。Dijkstra算法適合運用于求解單源最短路徑的問題，可得到到其他各頂點的最短路徑，而訂單需求的節(jié)點可能是多個，所以單純使用Dijkstra算法不能滿足需求[5]。最鄰近算法，即優(yōu)先選擇前往與當(dāng)前所在點最接近的點，然后以該點為起點前往下一個點，最后得到一個最接近于最短路徑的答案。

針對電商倉庫的特點，單個機器人無法滿足工作的需求，所以還有一個重點問題，多機器人同時工作時要如何分配才能不發(fā)生沖突。本文采取的避障方式有兩種：一種是當(dāng)某條路徑正在被占用時，更改其對應(yīng)權(quán)值為∞，下一個訂單對應(yīng)的路徑規(guī)劃就會避開這兩條路徑，直至被占用路徑任務(wù)完成，釋放被占用路徑，更改權(quán)值為原來的長度數(shù)值。第二種是等待，當(dāng)路徑被占用，下一個需要經(jīng)過該路徑的機器人可選擇等待，等前一個機器人離開本路徑后再進入該路徑。如有多個機器人同時等待同一個路徑，以訂單產(chǎn)生時間設(shè)置優(yōu)先級，先產(chǎn)生的訂單優(yōu)先級較高。當(dāng)沖突發(fā)生時，通過預(yù)估前一個任務(wù)完成釋放路徑的時間及下一個任務(wù)的等待時間，計算繞行耗費時間即繞行比原路徑多花的時間，并對等待時間與繞行時間進行比較，選擇時間較短的方式。

整個運行過程為：首先服務(wù)器獲得需要揀取的商品名稱，然后從數(shù)據(jù)庫獲取各商品對應(yīng)揀貨點，即需要到達(dá)的各頂點，將各頂點帶入算法中得到經(jīng)過多點的最短路徑，到此一個訂單的初步路徑規(guī)劃工作完成。運行過程中，如規(guī)劃的某條路徑正在被占用，則重新規(guī)劃接下來的路徑，不斷更新，確保不會產(chǎn)生碰撞或者堵塞。

3 功能實現(xiàn)

首先讀取地圖信息，生成矩陣。然后將矩陣帶入算法，同時輸入任務(wù)點，獲得多點之間的最短路徑。最后向機器人發(fā)送任務(wù)要求，機器人執(zhí)行任務(wù)過程中經(jīng)過交叉點時讀取對應(yīng)二維碼信息，與服務(wù)器的信息交互，實現(xiàn)避障，即多個任務(wù)同時進行，路徑之間無交叉點。

本文的地圖文件是針對電商倉庫設(shè)計的。目的在于確定機器人位置與離揀貨貨架最近的路徑上的點，得到機器人到揀貨點最短線路的計算。確定了倉庫中的多個點后，根據(jù)倉庫地圖描述文件計算多點之間的最短線路，并能夠?qū)崿F(xiàn)避障，機器人之間不會碰撞且不會導(dǎo)致道路堵塞。任務(wù)起點為機器人休息區(qū)或者存放點，終點為訂單打包區(qū)，這個根據(jù)需求進行設(shè)計，存入地圖信息。其它節(jié)點根據(jù)訂單所需貨物，通過數(shù)據(jù)庫信息獲取貨物所在貨架信息。根據(jù)多點信息及描述文件計算最短線路的步驟如下：

（1）確定起點、取貨點及倉庫地圖描述文件。

（2）定義圖的鄰接矩陣、圖的點集合以及路徑集合。

（3）解析倉庫描述文件，初始化圖的點集和邊集。

（4）根據(jù)訂單確定訪問點，帶入算法得到最短路徑。

（5）服務(wù)器向機器人發(fā)送指令，機器人路過頂點掃描到二維碼，向服務(wù)器發(fā)送實時位置。

（6）服務(wù)器根據(jù)機器人實時位置信息實時更新道路實現(xiàn)避障，在某條路徑被訪問時，下一個任務(wù)避開該路徑，以及規(guī)劃下一條路徑，找到另一條最短路徑。

4 實驗結(jié)果

實驗初步設(shè)置兩個任務(wù)實現(xiàn)避障。即實現(xiàn)圖1中點到點之間的最短路徑的獲取，當(dāng)兩個任務(wù)同時進行時，后一個任務(wù)不會同時與前一個任務(wù)在同一路徑重合，避免碰撞的情況發(fā)生。

實驗過程首先根據(jù)Tiled Map獲得的描述文件，使用MyEclipse軟件讀取描述文件信息獲得路徑及交叉點關(guān)系的矩陣。然后使用軟件進行仿真，將矩陣帶入得到帶權(quán)圖（Graph）[6]。最后輸入任務(wù)，通過Dijkstra算法獲得最短路徑，經(jīng)過對算法的改進實現(xiàn)避障。

任務(wù)一，2-＞50,任務(wù)二，2-＞49。獨自運行時，實驗得出結(jié)果，任務(wù)一生成路徑如圖2所示，經(jīng)過節(jié)點2、9、50，由于有1個轉(zhuǎn)彎，這里設(shè)置速度，一個單位長度需1s，轉(zhuǎn)彎需多增加2s，總?cè)蝿?wù)時間為90s。任務(wù)二生成路徑如圖3所示，經(jīng)過節(jié)點2、9、49，也有1個轉(zhuǎn)彎，總?cè)蝿?wù)時間為90s。同時運行時，由于任務(wù)一優(yōu)先級高，路徑不發(fā)生改變，任務(wù)二為了避免與任務(wù)一產(chǎn)生沖突，可選擇繞行或者等待。這里可以預(yù)估任務(wù)一到達(dá)節(jié)點9的時間，2-＞9距離56，則需要56s，所以預(yù)估56s到達(dá)節(jié)點9，即任務(wù)二需等待56s。如果繞行經(jīng)過的路徑節(jié)點修改為2、45、1、8、49，有2個轉(zhuǎn)彎，總?cè)蝿?wù)時間變?yōu)?56s，比之前規(guī)劃多了66s。相較于繞行，等待反而快了10s，所以這里選擇了等待，生成路徑如圖4所示，這樣的規(guī)劃避免了兩個機器人工作途中碰撞的可能性。

從實驗結(jié)果可直觀的看到最短路徑，多個任務(wù)時會避免碰撞或者擁堵。

圖2 任務(wù)一路徑

圖3 任務(wù)二路徑

圖4 任務(wù)一、二同時執(zhí)行時路徑

5 結(jié)語

本文實現(xiàn)了對訂單路徑規(guī)劃的方案制定，規(guī)劃了整個流程，并模擬完成了過程中最短路徑的獲取及機器人之間的避障。但是對路徑規(guī)劃算法的優(yōu)化還不夠完善，還有其他約束條件以及可能產(chǎn)生碰撞的情況沒有考慮完全，后期還需考慮，以達(dá)到更加高效、實時、準(zhǔn)確的實現(xiàn)路徑規(guī)劃及避障。并且本文實現(xiàn)的僅僅是路徑方面的優(yōu)化避障，并未涉及機器人設(shè)計，后期會涉及到機器人主芯片的設(shè)計，初步考慮使用Android系統(tǒng)的嵌入式電路板實現(xiàn)機器人與服務(wù)器信息交流。至于機器人取貨等行為有待進一步開發(fā)設(shè)計。

相信隨著電商行業(yè)的不斷發(fā)展，電商倉庫工作量會越來越大，如何簡化工作流程，節(jié)約工作時間愈加變成一個重點問題，未來機器人的使用也會越來越普及。