電商物流智能搬運(yùn)機(jī)器人路徑規(guī)劃研究

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

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

一、前言

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

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

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

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

（一）智能搬運(yùn)機(jī)器人簡介

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

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

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

1.智能搬運(yùn)機(jī)器人行走方向

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

2.智能搬運(yùn)機(jī)器人等待時(shí)間規(guī)則

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.特殊情況說明

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

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

（一）柵格地圖二維平面

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

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

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

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

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

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

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

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

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

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

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

1.模型假設(shè)

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

假設(shè)2：智能搬運(yùn)機(jī)器人不能從移動(dòng)貨架下方穿行：

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

2.加入時(shí)間成本的A*算法模型

所需花費(fèi)總時(shí)間T（n）的表達(dá)式為：

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

四、加入時(shí)間成本的A *算法模型驗(yàn)證分析

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

（一）計(jì)算最短路徑

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

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

第二條：先向右轉(zhuǎn)彎沿Y軸方向行駛到坐標(biāo)（1，5），再向左轉(zhuǎn)彎沿X軸方向行駛到達(dá)目標(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的計(jì)算結(jié)果可知，根據(jù)傳統(tǒng)A*算法搜索出的最短路徑可能存在不只一條距離最短的路徑，因此需要引入時(shí)間成本概念擇優(yōu)選取。

（二）計(jì)算時(shí)間成本

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

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

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

五、結(jié)束語

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

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

參考文獻(xiàn)：

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

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

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

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

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

作者簡介：

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