摘要：隨著電子商務(wù)的迅猛發(fā)展，給電商環(huán)節(jié)的物流作業(yè)帶來了新的要求和挑戰(zhàn)?；陔娮由虅?wù)物流任務(wù)多、揀選作業(yè)復(fù)雜的特性，越來越多的智能搬運機器人被投入使用。但多機器人同時進行工作，容易造成機器人擁堵與碰撞。本文通過規(guī)劃特殊道路規(guī)則，對智能搬運機器人行走路徑進行柵格法建模，設(shè)計其運行的合理路徑，避免多機器人同時作業(yè)擁堵問題，提高揀選效率。

關(guān)鍵詞：電商物流：智能搬運機器人：路徑規(guī)劃

一、前言

當(dāng)前，部分電商物流配送中心已實現(xiàn)“無人化”作業(yè)模式，主要通過運用先進的“無人倉”技術(shù)，使用自動化立體倉庫、無人叉車、智能搬運機器人等智能化設(shè)施設(shè)備進行倉儲作業(yè)。智能搬運機器人主要運用“貨到人”的揀選模式，與“人到貨”揀選模式相比，節(jié)約大量人力，提高揀選作業(yè)效率。

隨著電子商務(wù)的迅猛發(fā)展，給電商物流作業(yè)帶來了新的要求和挑戰(zhàn)。在倉儲中心，隨著機器人需完成的揀選作業(yè)以及搬運任務(wù)的復(fù)雜性與繁重性增加，多機器人同時進行工作時的調(diào)度問題也隨之成為難點問題，在實際應(yīng)用和學(xué)術(shù)研究領(lǐng)域，開始研究機器人的行走路徑規(guī)劃問題。智能搬運機器人在配送中心運作時，存在路線重疊、數(shù)量不足等問題。如果智能搬運機器人要充分發(fā)揮自身優(yōu)勢，就需要對倉儲中智能機器人的行走路徑做出優(yōu)化設(shè)計。

因此，針對現(xiàn)有電商物流中智能搬運機器人存在的問題，本文主要從四個方面進行研究。第一，對智能搬運機器人的行走路徑進行交通規(guī)劃：第二，運用柵格法建模分析機器人的行走路徑：第三，通過加入時間成本的A*算法設(shè)計機器人行走的合理路徑：第四，對算法模型進行驗證分析，確定方案的可行性。通過對智能搬運機器人路徑模型的建設(shè)，解決智能搬運機器人運行中的擁堵碰撞等問題。

二、智能搬運機器人行走路徑優(yōu)化規(guī)則設(shè)計

（一）智能搬運機器人簡介

智能搬運機器人是自動化控制領(lǐng)域出現(xiàn)的一項高新技術(shù)，配備電磁或光學(xué)等自動導(dǎo)引裝置，能夠沿規(guī)定的導(dǎo)引路徑行駛，具有安全保護及各種移載功能的運輸車。同時可以通過編程完成各種預(yù)期任務(wù)，在自身結(jié)構(gòu)和性能上擁有人和機器的各自優(yōu)勢，體現(xiàn)了人工智能的適應(yīng)性。

（二）路徑優(yōu)化規(guī)則設(shè)計

智能搬運機器人主要運用“貨到人”的揀選模式，與“人到貨”揀選模式相比，節(jié)約了大量人力，提高了揀選作業(yè)效率。但智能搬運機器人在實際倉儲中心運作時，也存在很多問題，例如路線重疊、設(shè)備碰撞等問題。為了使智能搬運機器人充分發(fā)揮自身優(yōu)勢，使路徑模型更優(yōu)化.對智能搬運機器的行走路徑規(guī)則做如下設(shè)計：

1.智能搬運機器人行走方向

根據(jù)智能搬運機器人的工作特點，同時結(jié)合物流配送中心智能揀選區(qū)地面為網(wǎng)點狀（智能搬運機器人沿地面二維碼運行），所以智能搬運機器人只能往正東、正西、正北、正南四個方向勻速移動，不能呈對角線勻速移動。

2.智能搬運機器人等待時間規(guī)則

多個機器人并行工作時，可通過自身傳感技術(shù)從而及時規(guī)避碰撞等不良相遇問題。因此，需要制定智能搬運機器人相遇等待規(guī)則。

（1）智能搬運機器人的工作狀態(tài)

在智能搬運機器人工作過程中，其工作階段主要包括從空車存放區(qū)到目標(biāo)貨架、從目標(biāo)貨架到揀選臺、從揀選臺到空貨位放置目標(biāo)貨架、從貨架到空車存放區(qū)四個階段;工作狀態(tài)主要包括空載、滿載。具體內(nèi)容如表1所示。

（2）智能搬運機器人的優(yōu)先級設(shè)計

智能搬運機器人在不同的工作狀態(tài)下，優(yōu)先級會有差異，下面對智能搬運機器人進行優(yōu)先級設(shè)定如下表2所示：

（三）行走路線交通規(guī)則

對智能搬運機器人行走線路的交通規(guī)則設(shè)計對于系統(tǒng)作業(yè)效率影響重大。設(shè)計作業(yè)區(qū)通道類型分為兩種，高速通行區(qū)和低速通行區(qū)。高速通行區(qū)指貨架區(qū)域外的多條通道，允許多個機器人并行行駛。低速通行區(qū)指貨架與貨架之間的單條通道，只允許一個機器人通行。

智能搬運機器人貨架行駛區(qū)域交通規(guī)則的劃分主要分為4大部分，如圖2所示。其中紅色箭頭代表向左行駛的通道，綠色箭頭代表向右行駛的通道，黑色箭頭代表向前行駛的通道，藍色箭頭代表向后行駛的通道，具體設(shè)置原則如下：

1.特殊通道交通規(guī)則設(shè)置原則

通道的貨架入口處均沒有揀貨臺，任務(wù)發(fā)布后，智能搬運機器人接收到信息，立即從存放區(qū)進入貨架區(qū)，不會造成擁堵，能夠減少等待時間以及提高揀選效率。

2.橫向通道交通規(guī)則設(shè)置原則

由貨架區(qū)通往揀選臺的所有通道中，至少設(shè)置一條可直接通往揀選臺的單行道，且與由揀選臺通往貨架區(qū)的單行道交替設(shè)置。

3.縱向通道交通規(guī)則設(shè)置原則

以橫向通道設(shè)置原則為基礎(chǔ)，縱向通道基本設(shè)置為由貨架區(qū)進入揀選臺的單行道兩側(cè)相向而行，同時設(shè)置為由揀選臺進入貨架區(qū)單行道兩側(cè)相背而行。為防止在貨架區(qū)造成擁堵，將其最中間的縱向通道和最右邊的通道設(shè)置為連貫單行道，加快智能搬運機器人進出貨架區(qū)的速度。

4.特殊情況說明

機器人統(tǒng)一遵守優(yōu)先級避讓原則，空載狀態(tài)下可在移動貨架下方通行。

三、智能搬運機器人行走區(qū)域柵格法建模

（一）柵格地圖二維平面

假設(shè)將智能搬運機器人在倉儲中心的行走區(qū)域看成一個二維平面，記為AT.每個柵格為智能搬運機器人的最大步長。記gEAT為任意柵格，每一個柵格g有確定的坐標(biāo)（x，y）;定義左上角第一個柵格的坐標(biāo)為（0，0），第二個柵格的坐標(biāo)為（1，0），第三個柵格的坐標(biāo)為（2，0），以此類推，同時每一個柵格代表一個節(jié)點。

（二）傳統(tǒng)A*算法

A*算法主要求解圖論中的最短路徑，廣泛應(yīng)用于路徑規(guī)劃領(lǐng)域。同時，A*算法具有實時性、高效性等，也應(yīng)用于實時系統(tǒng)和人工智能系統(tǒng)。A*算法通過選擇合適的估價函數(shù)計算從當(dāng)前節(jié)點到目標(biāo)節(jié)點代價最小的距離，從而確定路徑的搜索方向，并最終確定整個路徑。

傳統(tǒng)A*算法在確定搜索區(qū)域后，對路徑的節(jié)點搜索有開啟列表和關(guān)閉列表兩個集合（開啟列表指智能搬運機器人將要到達的柵格，關(guān)閉列表指智能搬運機器人已經(jīng)走過的柵格，行走過的柵格不可重復(fù)），通過估價函數(shù)[f（n）]對路徑進行評分，不斷選擇f值最低的節(jié)點，直至搜索到目標(biāo)節(jié)點，找出估值最低的路徑。

在柵格法中，一般使用曼哈頓距離法計算最短路徑，表達式為：

D（i，j）=lXi-Xjl+lYi-Yjl

A*算法的啟發(fā)式估價函數(shù)表達式為：

F（n）=g（n）+h（n）

其中n表示柵格地圖中某一需要被估算路徑代價的柵格節(jié)點，g（n）指從起始節(jié)點到當(dāng)前節(jié)點的代價實際值;h（n）指從當(dāng)前節(jié)點到目標(biāo)節(jié)點的代價估計值，一般用曼哈頓距離法求解。

（三）加入時間成本優(yōu)化的A*算法

根據(jù)物流中心特點，在進行揀選作業(yè)時，由系統(tǒng)自行分配最短路徑。在作業(yè)高峰期將會有多個智能搬運機器人同時工作，因此而產(chǎn)生動態(tài)障礙物，所以需要引入時間成本概念，即把智能搬運機器人在行駛過程中搜索到最短路徑后，從當(dāng)前節(jié)點行駛到目標(biāo)節(jié)點的過程將會耗費多少時間，納入考慮范圍，以達到在高效完成揀選作業(yè)的同時分析時間成本耗費量。

1.模型假設(shè)

假設(shè)1：智能搬運機器人均為勻速行駛：

假設(shè)2：智能搬運機器人不能從移動貨架下方穿行：

假設(shè)3：智能搬運機器人每轉(zhuǎn)一次彎所需時間小于每行駛一個柵格所需時間，姑且不計。

2.加入時間成本的A*算法模型

所需花費總時間T（n）的表達式為：

其中t表示以一個柵格的行駛距離作為單位時間成本，每行駛一個柵格需t秒：在行駛過程中遇到動態(tài)障礙物的等待次數(shù)為m，所需花費的時間為ti秒;f（n）指從當(dāng)前節(jié)點到目標(biāo)節(jié)點的總距離;T（n）指機器人從當(dāng)前節(jié)點以一條最短路徑到達目標(biāo)節(jié)點的總時間。

四、加入時間成本的A *算法模型驗證分析

假設(shè)圖4為倉儲中心設(shè)置了交通規(guī)則的部分區(qū)域，智能搬運機器人B，是由存放區(qū)前往目標(biāo)貨架P進行揀選作業(yè)，同時處于空載狀態(tài)的機器人：智能搬運機器人B2是由目標(biāo)貨架前往揀選臺，同時處于滿載狀態(tài)的機器人。顯然，B1的優(yōu)先級小于B2的優(yōu)先級。由于智能搬運機器人均為勻速行駛，因此B1與B2兩輛機器人將會在M柵格相遇，B1機器人需停車等待B2機器人離開后再前進。

（一）計算最短路徑

由圖4可知，判斷起始節(jié)點B1（1，2）到目標(biāo)節(jié)點P（4，4）的最短路徑時，會產(chǎn)生兩條可行通道：

第一條：先沿X軸方向行駛到坐標(biāo)（5，2），再向右轉(zhuǎn)彎沿Y軸方向行駛到達目標(biāo)貨架P右側(cè)柵格（5，4）;

第二條：先向右轉(zhuǎn)彎沿Y軸方向行駛到坐標(biāo)（1，5），再向左轉(zhuǎn)彎沿X軸方向行駛到達目標(biāo)貨架P下方柵格（4.5）。所以根據(jù)A*算法可知：

f（n） =g（n） +h（n）=1+l（1-5）l+l（2-4）l =7

f（n） =g（n） +h（n]=1+l（1-4）l+l（2-5）l =7

由f（n）1和f（n）2的計算結(jié)果可知，根據(jù)傳統(tǒng)A*算法搜索出的最短路徑可能存在不只一條距離最短的路徑，因此需要引入時間成本概念擇優(yōu)選取。

（二）計算時間成本

首先，計算第一條可行通道時間成本，根據(jù)假設(shè)條件可知：

由上述計算結(jié)果可知：第一條路徑行走的時間為7t，第二條路徑行走的時間為6t，在相同距離情況下，選擇用時最短的路徑。

在考慮時間成本進行路徑優(yōu)先選擇時，可能會存在路徑距離相同且路徑行走時間相同的情況，此時，智能搬運機器人應(yīng)自動選擇動態(tài)障礙物少的路徑或者不會出現(xiàn)等待時間的路徑擇優(yōu)先行。

五、結(jié)束語

本文主要通過對智能搬運機器人在電商物流配送中心進行揀貨作業(yè)時的行走路徑進行交通規(guī)則設(shè)置，從而有效避免在作業(yè)高峰期出現(xiàn)行走線路重復(fù)，并且改善設(shè)備交通擁堵情況?；诮煌ㄒ?guī)則，利用柵格法建模對智能搬運機器人行走路徑進行分析，同時引入時間成本完善了傳統(tǒng)的A*算法，設(shè)計智能搬運機器人合理路徑。最后，通過算例驗證，證明引入時間成本的A*算法模型具有可行性，能夠優(yōu)化智能搬運機器人行走路徑。

（指導(dǎo)老師：何娜敏）

參考文獻：

[1]潘成浩.倉儲物流機器人揀選路徑規(guī)劃仿真研究[D].太原：中北大學(xué)，2017.

[2]高小杰.倉儲系統(tǒng)中機器人小車路徑規(guī)劃算法研究[D].北京：北京郵電大學(xué)，2017.

[3]張喜妹.基于Kiva系統(tǒng)的揀選作業(yè)優(yōu)化與算法研究[D].北京：北京郵電大學(xué)，2015.

[4]胡少龍，胡志華，曹楊.基于多候選儲位的存取路徑優(yōu)化問題研究[J].運籌與管理，2013，22（5）：111-116.

[5]張丹露，基于智能倉庫的多機器人動態(tài)路徑規(guī)劃關(guān)鍵技術(shù)研究[D].北京：中國科學(xué)院大學(xué)（中國科學(xué)院重慶綠色智能技術(shù)研究院）.2017.

作者簡介：

高夢妮，重慶師范大學(xué)涉外商貿(mào)學(xué)院，重慶。