基于A* 算法的搬運(yùn)機(jī)器人路徑規(guī)劃
——以菜鳥智能倉為例

閆 妍，陶美春 YAN Yan, TAO Meichun

（新疆財經(jīng)大學(xué) 工商管理學(xué)院，新疆 烏魯木齊830012）

(School of Business Abministration, Xinjiang University of Finance and Economics, Urumqi 830012, China)

0 引 言

隨著移動互聯(lián)網(wǎng)的普及和發(fā)展，電商物流平臺已經(jīng)迎來了新的世紀(jì)，物流業(yè)的發(fā)展作為其重要的支撐，也一直推動著其快速的發(fā)展。倉儲物流作為物流中一個重要環(huán)節(jié)，提高貨物流通效率降低成本已是當(dāng)今社會對倉儲物流的訴求。電商平臺訂單數(shù)量日益增長，傳統(tǒng)的揀選模式占整個倉庫操作流程的60%-70%[1]，效率低成本高，已難以適應(yīng)現(xiàn)在大型物流企業(yè)的需要。隨著自動化技術(shù)以及智能機(jī)器人的發(fā)展和應(yīng)用，倉儲物流開始大量發(fā)展自動化立體倉庫，一些大型物流企業(yè)率先使用智能搬運(yùn)機(jī)器人，使得揀選效率大大提高，智能搬運(yùn)機(jī)器人在物流業(yè)中占據(jù)著重要地位。

另一方面，伴隨著我國人口老齡化的到來，勞動資源豐富的“人口紅利”時代已經(jīng)逐漸退去[2]，企業(yè)成本日益增高，提升倉儲自動化水平，使用智能搬運(yùn)機(jī)器人代替人工已是必然趨勢。

綜上所述，電子商務(wù)的快速發(fā)展極大地推動著我國物流業(yè)的現(xiàn)代化、自動化，智能搬運(yùn)機(jī)器人在自動化倉庫中的使用已成趨勢。但是這項(xiàng)搬運(yùn)機(jī)器人技術(shù)的投資昂貴，我國的倉儲運(yùn)輸和物流發(fā)展相對薄弱，很多的企業(yè)可望而不可及，同時也面臨著搬運(yùn)機(jī)器人調(diào)度，路徑規(guī)劃不合理的問題，使得搬運(yùn)機(jī)器人的推廣和應(yīng)用受到了制約，所以研究搬運(yùn)機(jī)器人的路徑規(guī)劃問題迫在眉睫。

1 文獻(xiàn)綜述

1.1 算法研究

關(guān)于搬運(yùn)機(jī)器人的路徑規(guī)劃，算法是核心內(nèi)容，學(xué)者們對算法的研究成果頗豐。劉晶等人（2019） 對生物激勵神經(jīng)網(wǎng)絡(luò)算法產(chǎn)生的路徑規(guī)劃長度長，轉(zhuǎn)彎次數(shù)多的問題，提出結(jié)合A*算法進(jìn)行改進(jìn)，讓機(jī)器人使用最短的路徑逃離死鎖[3]。成怡、肖宏圖（2020） 融合改進(jìn)A*算法和Morphin 搜索樹算法，規(guī)劃全局路徑實(shí)現(xiàn)動態(tài)避障。雖然方法取得了一定的效果，但運(yùn)算復(fù)雜檢索速度慢[4]。薛緯洋（2016） 將A*算法作為基礎(chǔ)同時運(yùn)用三維地圖，使此算法具有方向搜索的功能，節(jié)約了計算的時間，可有效解決碰撞沖突的情況[5]。

1.2 避障研究

在搬運(yùn)機(jī)器人運(yùn)行的環(huán)境中，除了有倉庫中已有的設(shè)施設(shè)備以及其它靜態(tài)障礙物，還會碰到其它搬運(yùn)機(jī)器人擋道等動態(tài)障礙物。越來越多機(jī)器人的使用，除了紅外線、超聲波等感知技術(shù)不斷研究應(yīng)用，同時還引來許多學(xué)者對避障方法的研究。潘成浩（2017） 對存在碰撞沖突的搬運(yùn)機(jī)器人進(jìn)行優(yōu)先級的判斷，讓優(yōu)先級低的及時做出路徑調(diào)整避免沖突[6]。劉敬一（2018） 根據(jù)任務(wù)的需求對優(yōu)先級的設(shè)置進(jìn)行了詳細(xì)的闡述，并根據(jù)實(shí)時情況調(diào)整搬運(yùn)機(jī)器人的優(yōu)先級[7]。

通過對文獻(xiàn)的研究和梳理，可以發(fā)現(xiàn)對于搬運(yùn)機(jī)器人路徑規(guī)劃相關(guān)研究不少。但也發(fā)現(xiàn)還存在許多不足，如算法自身的缺陷，對于遺傳算法雖然迭代效果很好，但是搜索時間長。很多路徑規(guī)劃還停留在以規(guī)劃路徑最短為最終目標(biāo)，并未考慮到搬運(yùn)機(jī)器人在運(yùn)行過程中轉(zhuǎn)彎次數(shù)不同對時間和能量消耗也不同。目前對于倉儲中搬運(yùn)機(jī)器人的路徑規(guī)劃技術(shù)、避障技術(shù)尚處于研究的初級階段，并不是很成熟。同時缺乏全局動態(tài)路徑規(guī)劃，難以解決倉儲企業(yè)的實(shí)際問題?；贏*算法能通過啟發(fā)式函數(shù)找到環(huán)境中的最優(yōu)解，并且研究成果相對成熟，考慮到A*算法的可靠穩(wěn)定性，將以A*算法作為基礎(chǔ)來進(jìn)行路徑規(guī)劃。對于傳統(tǒng)的A*算法是以路徑最短為衡量標(biāo)準(zhǔn)對其進(jìn)行改進(jìn)，綜合考慮在路徑最短的前提下同時保證時間最短，因?yàn)閷τ谄髽I(yè)來說時間就是金錢。對于現(xiàn)實(shí)中動態(tài)避障，將時間預(yù)約表和交通規(guī)則結(jié)合，解決搬運(yùn)機(jī)器人在運(yùn)行過程中出現(xiàn)的碰撞沖突和死鎖問題。

2 菜鳥智能倉搬運(yùn)機(jī)器人作業(yè)環(huán)境簡介

2.1 菜鳥智能倉庫系統(tǒng)概述

菜鳥聯(lián)盟首個全自動化倉庫正式開倉運(yùn)營，位于我國廣州增城物流園區(qū)，占地面達(dá)10 萬多平方米。目前主要對天貓超市商品進(jìn)行存儲和分揀，菜鳥智能倉標(biāo)志著我國倉儲物流進(jìn)入了一個全新水平，智能化的設(shè)備代替人工作業(yè)精準(zhǔn)高效，實(shí)現(xiàn)了我國倉儲智能化的新突破。

菜鳥智能倉采用“貨到人”的揀選模式，在倉庫接到訂單以后，發(fā)布任務(wù)給搬運(yùn)機(jī)器人，機(jī)器人會在接到倉庫管理系統(tǒng)的指令后立即來到一個存放指定貨物的貨架前，將貨架從底部頂起，搬運(yùn)至進(jìn)行揀貨的平臺供倉庫揀貨員進(jìn)行揀選。這途中代替了傳統(tǒng)的人在貨架間奔波，尋找貨物的揀選任務(wù)模式。揀貨的效率至少可以提高30%，揀貨準(zhǔn)確率幾乎可以達(dá)到100%。這種自動化的倉庫大幅減少和降低了倉庫揀貨員的勞動強(qiáng)度，大大提高了分揀出庫的效率。

2.2 搬運(yùn)機(jī)器人作業(yè)環(huán)境描述及簡化模型

（1） 作業(yè)環(huán)境描述。菜鳥智能倉中搬運(yùn)機(jī)器人“小藍(lán)人”們，主要作業(yè)在貨物揀選區(qū)，揀選區(qū)有6 個揀貨臺，1 160 個存放小件貨物的移動貨架，230 個存放大件貨物的托盤，100 臺搬運(yùn)機(jī)器人，在倉庫最里面有搬運(yùn)機(jī)器人的充電樁。并對智能搬運(yùn)機(jī)器人的行走速度、移動貨架區(qū)的行走道路長度、揀選貨架的承載力進(jìn)行了詳細(xì)的調(diào)研，詳情見表1。

表1 揀貨作業(yè)相關(guān)數(shù)據(jù)調(diào)研

（2） 簡化模型。為了簡化菜鳥智能倉庫模型，首先對搬運(yùn)機(jī)器人和菜鳥智能倉庫環(huán)境做出如下分析：

·為了簡化菜鳥智能倉揀選作業(yè)區(qū)環(huán)境，本文使用柵格地圖。

·智能倉中搬運(yùn)機(jī)器人根據(jù)訂單分配指令搬運(yùn)貨架。

·搬運(yùn)機(jī)器人按照上、下、左、右的方向行駛。

·每一臺搬運(yùn)機(jī)器人都是勻速行駛的。

·搬運(yùn)機(jī)器人裝有傳感設(shè)備，可以感知周邊的障礙物。

·搬運(yùn)機(jī)器人和所有的貨物以及貨架都有自己的ID，磁軌上都鋪有二維碼，搬運(yùn)機(jī)器人通過掃描二維碼確定自己的路徑。

·搬運(yùn)機(jī)器人執(zhí)行任務(wù)時有三類指令：運(yùn)行、充電、休眠，每一臺搬運(yùn)機(jī)器人都是相對獨(dú)立自由的。

·以搬運(yùn)機(jī)器人完成任務(wù)的時間代價作為衡量運(yùn)行效率的標(biāo)準(zhǔn)。

根據(jù)菜鳥揀選作業(yè)區(qū)實(shí)際情況簡化智能倉庫模型，如圖1 所示。倉庫最左邊的區(qū)域?yàn)閽浌ぷ魅藛T進(jìn)行貨物分揀的區(qū)域，

總共有6 處揀選臺，由綠色方格代表，搬運(yùn)機(jī)器人把貨物搬運(yùn)至揀選臺附近供揀貨人員對貨物進(jìn)行揀選。倉庫右邊黃色區(qū)域?yàn)橐苿迂浖軈^(qū)域，每一臺貨架都有自己的ID 以便搬運(yùn)機(jī)器人查找。灰色區(qū)域?yàn)榇蠹斜P區(qū)，搬運(yùn)機(jī)器人只需直接將托盤搬運(yùn)至打包區(qū)進(jìn)行打包。白色部分為機(jī)器人行走的道路，紅色為目標(biāo)貨架，藍(lán)色圓圈代表智能搬運(yùn)機(jī)器人，機(jī)器人只能在白色道路上行走。

圖1 菜鳥智能倉庫簡化模型

2.3 搬運(yùn)機(jī)器人智能倉庫系統(tǒng)的問題分析

通過對菜鳥智能搬運(yùn)機(jī)器人的行走路徑調(diào)研，發(fā)現(xiàn)存在以下幾個問題，會出現(xiàn)站臺等待時間長，造成作業(yè)效率低下。

由于規(guī)劃錯誤原路返回和道路被占用，為了避讓和等待退回，導(dǎo)致機(jī)器人會在找到目標(biāo)貨架或者搬運(yùn)貨架時往返迂回。由于規(guī)劃不合理，導(dǎo)致行走路徑過長。同時多機(jī)器人同時工作時，沒有一定的交通規(guī)則必然會出現(xiàn)擁堵和等待，為了避讓機(jī)器人會選擇繞路，所以導(dǎo)致行走路徑過長。在機(jī)器人從充電區(qū)域進(jìn)入工作區(qū)域時，沒有合理的分配作業(yè)任務(wù)，導(dǎo)致先行走的機(jī)器人搬運(yùn)就近貨物，后行走的搬運(yùn)最遠(yuǎn)貨物，造成站臺等待時間過高。

3 搬運(yùn)機(jī)器人行走路徑建模

3.1 行走路徑建模概述

菜鳥智能倉庫中搬運(yùn)機(jī)器人動態(tài)路徑規(guī)劃系統(tǒng)可以表示為由ROB、Map、O、D四種元素組成的系統(tǒng)，ROB表示在菜鳥智能倉庫中運(yùn)行的搬運(yùn)機(jī)器人系統(tǒng)，即ROB=rob1,…,robn（倉庫中的N臺搬運(yùn)機(jī)器人）。Map表示由倉庫中放置的貨架、揀選臺、充電樁以及其它的設(shè)施設(shè)備，即這些靜態(tài)的障礙物，還包括機(jī)器人在運(yùn)行過程中遇到的工作人員和其它搬運(yùn)機(jī)器人，即動態(tài)障礙物組成的倉庫環(huán)境。O則表示所有機(jī)器人的起始點(diǎn)，在運(yùn)行過程中N臺機(jī)器人有N個起始點(diǎn)（O=o1,…,on），可以是揀選臺，可以是充電樁，也可以是倉庫中的任意位置，要看搬運(yùn)機(jī)器人在接到指令時的位置。D則表示搬運(yùn)機(jī)器人的目標(biāo)點(diǎn)，當(dāng)機(jī)器人是去尋找目標(biāo)貨架，則目標(biāo)點(diǎn)就是目標(biāo)貨架所在的位置。如果是將目標(biāo)貨架搬運(yùn)至相應(yīng)的揀選臺，則目標(biāo)點(diǎn)是揀選臺。為了提高菜鳥智能倉的揀貨作業(yè)效率，以智能搬運(yùn)機(jī)器人搬運(yùn)貨架的時間長短作為衡量標(biāo)準(zhǔn)，通過縮短機(jī)器人在行走中的時間浪費(fèi)，來減少揀貨站臺的等待時間。

3.2 基于傳統(tǒng)A*算法的行走路徑規(guī)劃建模

（1） 柵格地圖。為了更好地方便研究搬運(yùn)機(jī)器人在菜鳥智能倉的路徑規(guī)劃，首先采用了柵格地圖，例如圖2。由于搬運(yùn)機(jī)器人倉庫的環(huán)境為目前已知的一種結(jié)構(gòu)化倉庫環(huán)境，環(huán)境中往往存在大量的工具如倉庫揀選臺、貨架、機(jī)器人等倉庫基礎(chǔ)設(shè)施，他們的工具數(shù)量多、形狀規(guī)范且能夠整齊有序的排列在了倉庫中。因此，首先使用了柵格法地圖來設(shè)計和構(gòu)建一個基于菜鳥機(jī)器人的倉庫行走地圖，使多搬運(yùn)機(jī)器人根據(jù)菜鳥的柵格地圖信息進(jìn)行路徑的規(guī)劃，能夠達(dá)到最大限度地簡化機(jī)器人在菜鳥倉庫行走的地圖，并準(zhǔn)確達(dá)到表示柵格地圖信息的路徑規(guī)劃目的。將一個智能搬運(yùn)機(jī)器人的地圖和運(yùn)動環(huán)境的地圖看做一個二維的平面時，則為運(yùn)動環(huán)境的地圖Map，據(jù)菜鳥智能倉的調(diào)研數(shù)據(jù)顯示每格是1.5m*1.5m，所以每個柵格的邊長為1.5m*1.5m。柵格地圖X軸的坐標(biāo)表示柵格的列，Y軸的坐標(biāo)表示柵格的行，對柵格地圖中的每個柵格進(jìn)行標(biāo)號，每個柵格可以表示為點(diǎn)P，Pi的位置為Pi x,（ ）

y。

（2） 傳統(tǒng)A*算法。A*算法的啟發(fā)式估算函數(shù)表達(dá)式為：

其中：n表示柵格地圖中某一要被估算代價的節(jié)點(diǎn)，g（）

n則是指從某一起始點(diǎn)到該節(jié)點(diǎn)的真實(shí)代價，此代價主要為路程，h（n）則是指從柵格結(jié)點(diǎn)n移動到目標(biāo)節(jié)點(diǎn)的啟發(fā)估算代價。h*（n）表示從柵格節(jié)點(diǎn)n移動到目標(biāo)節(jié)點(diǎn)的真實(shí)最優(yōu)代價，該代價在機(jī)器人到達(dá)目標(biāo)節(jié)點(diǎn)之前可以估算范圍，不能計算準(zhǔn)確的值。f（n）由g（n）和h（n）結(jié)合估算得到，表示從起始節(jié)點(diǎn)，經(jīng)過柵格節(jié)點(diǎn)n后到達(dá)目標(biāo)節(jié)點(diǎn)的啟發(fā)式估算代價。只有當(dāng)h（n）≤h*（n）時，f（n）才能保證A*算法的完備性和最優(yōu)性。通常情況下，選擇采用的啟發(fā)式估算函數(shù)因?yàn)椴豢紤]其他環(huán)節(jié)因素，如障礙物等，均可以h（n）≤h*（n）的條件。

A*算法的啟發(fā)式估算函數(shù)在柵格地圖中有多重選擇，由于在智能倉庫環(huán)境結(jié)構(gòu)固定，通過采用曼哈頓距離進(jìn)行估算，能更接近搬運(yùn)機(jī)器人可能行走的實(shí)際路程。在以下的表達(dá)式中，n表示柵格地圖中的某個柵格節(jié)點(diǎn)，nx表示節(jié)點(diǎn)n的x坐標(biāo)，ny表示節(jié)點(diǎn)n的y坐標(biāo)，同理，goal.x表示目標(biāo)節(jié)點(diǎn)goal的x坐標(biāo)，goal.y表示目標(biāo)節(jié)點(diǎn)goal的y坐標(biāo)，常用估算函數(shù)如下：

曼哈頓距離：

它表示為兩個節(jié)點(diǎn)之間在x軸和y軸方向的距離之和。

4 基于合作的多機(jī)器人協(xié)同路徑規(guī)劃

傳統(tǒng)的A*算法雖然能幫助搬運(yùn)機(jī)器人在倉庫中找到一條距離最短的路徑，但是在實(shí)際情況中仍然還有很多問題，比如多機(jī)器人在同時運(yùn)行會出現(xiàn)碰撞和死鎖等問題，下面將提出機(jī)器人的交通規(guī)則和預(yù)約表來解決這些問題，并進(jìn)一步優(yōu)化傳統(tǒng)的A*算法。

4.1 基于合作的交通規(guī)則

菜鳥智能倉庫中，多個搬運(yùn)機(jī)器人在同一個貨架區(qū)域和揀選區(qū)域之間來回的穿梭，所以在他們共同行走的過程中難免會出現(xiàn)碰撞。這種碰撞通常分為以下三種情況：

a. 迎面碰撞：正面相遇碰撞的具體情況。

b. 交叉碰撞：搬運(yùn)機(jī)器人在其行駛的整個過程中雖然沒有面對面的走，但是在拐角處仍然存在交叉碰撞相遇的情況。

c. 多個碰撞并存：當(dāng)多個機(jī)器人同時在拐角處相遇時，迎面碰撞和交叉碰撞的情況將同時發(fā)生。

對于以上三種碰撞情況，交叉碰撞時機(jī)器人可以設(shè)置有優(yōu)先級，由優(yōu)先級低的機(jī)器人等待優(yōu)先級高的機(jī)器人通過之后再通行，這種情況雖然很好解決，但是在遇到迎面碰撞和多種碰撞并存的情況時，就只有由一臺機(jī)器人避讓或者繞路，這樣在運(yùn)行中可能就會出現(xiàn)不停的避讓和繞路的情況，使得機(jī)器人效率低下，行走更多不必要的路程。所以給倉庫中的道路規(guī)定為不同方向的單行道，這樣就可以很好地解決迎面碰撞和多種碰撞并存的情況。

本文將搬運(yùn)機(jī)器人運(yùn)行的倉庫環(huán)境設(shè)置如圖3 所示的交通規(guī)則，在貨架所在的通道設(shè)置成單向行駛的通道，橫向的則設(shè)置為向左向右交替行駛的單向通道，縱向的則設(shè)置為向上向下交替的單向行駛通道，然而在倉庫的最左邊是揀貨區(qū)，所以留出兩行供搬運(yùn)機(jī)器人?？俊Ｓ捎诳赡苡卸嗯_機(jī)器人服務(wù)于一個揀選臺，就有可能出現(xiàn)碰撞，所以我們規(guī)定所有的機(jī)器人到達(dá)揀選區(qū)域要遵循左邊進(jìn)右邊出的規(guī)則，這樣就可以有效避免沖突。

4.2 基于合作的預(yù)約表

在采用上文的交通規(guī)則之后可以有效解決迎面碰撞和多種碰撞并存的情況，但是像圖4 所示的交叉碰撞并沒有很好的得到解決，所以本文將進(jìn)一步提出預(yù)約表，對搬運(yùn)機(jī)器人進(jìn)行優(yōu)先級的設(shè)定，通過識別優(yōu)先級進(jìn)行避讓，可以有效解決交叉碰撞的情況。除此之外，不同機(jī)器人可能還會有搬運(yùn)同一貨架的取貨沖突，設(shè)定優(yōu)先級還可以有效解決機(jī)器人的取貨沖突。

本文用柵格地圖對菜鳥智能倉進(jìn)行簡化后，每一個柵格都表示一個節(jié)點(diǎn)，在預(yù)約表中每一個柵格都是一個時點(diǎn)，當(dāng)一臺搬運(yùn)機(jī)器人準(zhǔn)備駛?cè)脒@個節(jié)點(diǎn)時，先要占有這個節(jié)點(diǎn)，將此節(jié)點(diǎn)在預(yù)約表上的狀態(tài)改為占有，其它搬運(yùn)機(jī)器人就不能再駛?cè)朐摴?jié)點(diǎn)，只有等待其變?yōu)槲幢徽加械臓顟B(tài)，才能通行。每一臺搬運(yùn)機(jī)器人在駛?cè)肽骋还?jié)點(diǎn)時都需要查詢預(yù)約表的狀態(tài)，只有查詢在未被占有的狀態(tài)下將該節(jié)點(diǎn)的狀態(tài)更改為占有才能順利通行。每一臺搬運(yùn)機(jī)器人也有自己的ID，當(dāng)它要占有某一個節(jié)點(diǎn)時，就將其自己的ID 輸入預(yù)約表的時點(diǎn)內(nèi)，這樣在其它機(jī)器人查詢時就會知道該搬運(yùn)機(jī)器人已經(jīng)占有該時點(diǎn)，就會根據(jù)情況作出相應(yīng)的調(diào)整，要么等待要么調(diào)整路徑重新作出規(guī)劃。

圖3 交通規(guī)則地圖

4.3 基于合作優(yōu)化A*算法進(jìn)行路徑規(guī)劃建模

根據(jù)上面制定的交通規(guī)則和預(yù)約表，將其相結(jié)合幾乎可以實(shí)現(xiàn)多搬運(yùn)機(jī)器人完全無碰撞的運(yùn)行?；诮煌ㄒ?guī)則和預(yù)約表的運(yùn)用和啟發(fā)，可以對傳統(tǒng)的A*算法做進(jìn)一步的改進(jìn)和優(yōu)化，來提升多搬運(yùn)機(jī)器人系統(tǒng)中單個搬運(yùn)機(jī)器人的運(yùn)行管理效率。

本文之前介紹了傳統(tǒng)的A*算法估算函數(shù)，通常情況下是用它來估算搬運(yùn)機(jī)器人到達(dá)目標(biāo)節(jié)點(diǎn)的距離代價，而在現(xiàn)實(shí)倉儲物流中，通常以完成一項(xiàng)任務(wù)的時間長短來評判一項(xiàng)作業(yè)的效率。因此，對傳統(tǒng)的A*算法進(jìn)行改進(jìn)，將采用時間代價作為估算函數(shù)估算的代價。將g（n）和h（n）的距離估算同時除以一個搬運(yùn)機(jī)器人的行駛速度，轉(zhuǎn)化為時間估算代價g'（n）和h'（n）。其中g(shù)'（n）代表搬運(yùn)機(jī)器人從起始柵格節(jié)點(diǎn)出發(fā)移動到當(dāng)前柵格節(jié)點(diǎn)n所花費(fèi)的真實(shí)時間代價：

其中：v表示搬運(yùn)機(jī)器人取貨時的行駛速度，d表示搬運(yùn)機(jī)器人從起始柵格移動到當(dāng)前柵格n的真實(shí)距離。h'（n）表示搬運(yùn)機(jī)器人從當(dāng)前柵格n行走到目標(biāo)柵格的估算時間代價：

其中：h（n）是上文所示的曼哈頓距離。

圖4 相同長度下的不同路徑

在傳統(tǒng)的A*算法下，從相同的起點(diǎn)出發(fā)到達(dá)相同的目標(biāo)點(diǎn)，會產(chǎn)生三條長度相等的不同路徑，將其稱為路徑①、路徑②、路徑③，如圖4 所示。這三條路徑均滿足距離最短的條件，傳統(tǒng)的A*算法會選擇其中任意一條作為最佳路徑。在實(shí)際倉庫中機(jī)器人的轉(zhuǎn)彎也會帶來時間的消耗，選擇不同的路徑產(chǎn)生的時間代價也不同。選擇路徑①時則只有一次轉(zhuǎn)彎，選擇路徑②時會有三次轉(zhuǎn)彎，選擇路徑③時甚至?xí)兴拇无D(zhuǎn)彎。無疑轉(zhuǎn)彎次數(shù)越多，所消耗的時間越多。考慮到這一因素，將機(jī)器人轉(zhuǎn)彎的時間代價t也加入到算法中。當(dāng)搬運(yùn)機(jī)器人在柵格地圖中行走時，如果下一節(jié)點(diǎn)的方向和上一節(jié)點(diǎn)不一樣，即機(jī)器人將要進(jìn)行轉(zhuǎn)彎，那么就需要將轉(zhuǎn)彎時間代價t考慮到估算函數(shù)f（n）中。此時將公式優(yōu)化為：

其中：m表示搬運(yùn)機(jī)器人在路徑規(guī)劃中轉(zhuǎn)彎的次數(shù)。

運(yùn)用此方法不僅可以減少機(jī)器人的行駛距離，還可以很快找到一條時間最短的路徑，最快最準(zhǔn)確地找到一條最高效率、最低成本的路徑規(guī)劃來完成揀貨作業(yè)。

5 方案的實(shí)施及評價

5.1 方案的實(shí)施

下面以菜鳥智能倉揀貨作業(yè)過程中的其中一個智能搬運(yùn)機(jī)器人的行走路徑為例，用運(yùn)改進(jìn)后的A*算法對它重新進(jìn)行路徑規(guī)劃，求出最優(yōu)解，減少搬運(yùn)時間，提高作業(yè)效率。

如圖5 菜鳥智能倉某一搬運(yùn)機(jī)器人的行走路徑，可以看出它的行走路徑有重疊，有迂回。據(jù)調(diào)研顯示搬運(yùn)機(jī)器人的行走速度是1.5m/s，轉(zhuǎn)一次彎大概花費(fèi)0.5s。可得整個行走路徑長達(dá)115.5 米，耗時104 秒，總共轉(zhuǎn)彎5 次。

圖5 某一搬運(yùn)機(jī)器人行走路徑

接下來運(yùn)用改進(jìn)后的A*算法，對搬運(yùn)機(jī)器人重新進(jìn)行路徑規(guī)劃，如圖6 基于改進(jìn)后的A*算法路徑規(guī)劃，此時整個行走路徑長達(dá)108 米，耗時98 秒，總共轉(zhuǎn)彎3 次。

圖6 改進(jìn)后的A*算法路徑規(guī)劃

用運(yùn)改進(jìn)后的A*算法，不僅可以解決搬運(yùn)機(jī)器人行走路徑重疊，迂回的問題，配合交通規(guī)則和預(yù)約表可以解決機(jī)器人擁堵和避讓而繞路導(dǎo)致行走路徑過長的問題，考慮先走搬遠(yuǎn)，后走搬近的原則減少等待時間。以上規(guī)劃從原來的總路徑長達(dá)115.5m 縮短至108m，總耗時由原來的104s 減少到98s，轉(zhuǎn)彎次數(shù)由原來的5 次減低到3 次，大大降低了總的消耗代價，詳情見表2 某一機(jī)器人路徑規(guī)劃數(shù)據(jù)對比。

5.2 方案的評價

（1） 搬運(yùn)機(jī)器人購買成本計算。通過菜鳥智能倉的調(diào)研，搬運(yùn)機(jī)器人數(shù)量為100 臺，根據(jù)實(shí)地調(diào)查一個智能搬運(yùn)機(jī)器人的單價大概是10 萬元，所需要花費(fèi)的購買費(fèi)用是：購買總費(fèi)用=單價*購買數(shù)量=10*100=1 000 萬元。

表2 某一機(jī)器人路徑規(guī)劃數(shù)據(jù)對比圖

（2） 電費(fèi)成本計算。通過查詢智能搬運(yùn)機(jī)器人的充電瓦數(shù)是1.8kw/h，充滿一次電需要2 小時，可連續(xù)使用6 小時，那么一天24 小時至少要充3 次電。廣州市商業(yè)用電的平均電費(fèi)是0.617 元/度，則智能搬運(yùn)機(jī)器人一年需要消耗的電費(fèi)是：一年總電費(fèi)=用電度數(shù)*用電時間*平均電費(fèi)*臺數(shù)=1.8*6*365*0.617*100=24.32 萬元。

（3） 搬運(yùn)機(jī)器人年折舊成本計算。年折舊率= （1-預(yù)計殘值率）/折舊年限×100%（注：預(yù)計殘值率為固定資產(chǎn)原值的3%～5%），根據(jù)調(diào)查與生產(chǎn)經(jīng)營有關(guān)的工具計提折舊的最低年限為5 年，所以確定折舊年限為5 年，預(yù)計殘值率取原值的5%。所以一年的折舊費(fèi)用是：年折舊費(fèi)用=年折舊率*總價值=19%*1 000=190 萬元。

（4） 搬運(yùn)機(jī)器人維護(hù)費(fèi)成本計算。根據(jù)調(diào)查智能搬運(yùn)機(jī)器人的電池使用壽命大概是兩年，更換一次電池的成本大概是11 000 元。為了對智能搬運(yùn)機(jī)器人定期進(jìn)行維護(hù)保養(yǎng)，至少三個月清掃一次灰塵和添加潤滑油，一次成本300 元左右，所以智能搬運(yùn)機(jī)器人的一年維護(hù)費(fèi)用是：年維護(hù)費(fèi)用= （電池折舊+保養(yǎng)費(fèi)）*機(jī)器人數(shù)量= （0.55+0.12 ）*100=67 萬元。

（5） 使用人工的成本計算。倉庫分揀人員的工資平均在4 500 元/月左右，每年的高溫補(bǔ)貼費(fèi)、高峰期加班費(fèi)和節(jié)假日福利一年大概在2 500 元/人左右，工作人員一般是工作八小時，進(jìn)行三班倒。綜合以上使用人工的一年成本為：年人工成本=（基本工資+福利補(bǔ)貼） *工作人員數(shù)= （0.45*12+0.25 ）*300=1 695 萬元。

（6） 成本對比分析。使用機(jī)器人的年平均成本=折舊費(fèi)+電費(fèi)+維護(hù)費(fèi)=190 萬元+24.32 萬元+67 萬元=281.32 萬元。

使用人工的年平均費(fèi)用=總基本工資+總福利補(bǔ)貼=1 620 萬元+75 萬元=1 695 萬元。

根據(jù)以上公式分別計算出了菜鳥智能倉使用機(jī)器人的成本費(fèi)用和使用人工的成本費(fèi)用，機(jī)器人可以24 小時工作，人工需要三班倒，所以使用1 個機(jī)器人相當(dāng)于雇傭3 個工作人員，從以上所述進(jìn)行成本對比分析，可以看出使用機(jī)器人要比使用人工減少1 413.68 萬元的成本。

6 總 結(jié)

菜鳥聯(lián)盟憑借全面覆蓋的物流網(wǎng)點(diǎn)、高效的配送服務(wù)、先進(jìn)的現(xiàn)代物流技術(shù)、專業(yè)的物流倉儲的服務(wù)和管理能力，在國內(nèi)電商物流零售倉儲服務(wù)領(lǐng)域名列前茅。但其中還是存在著發(fā)展道路上的一些問題，還需要進(jìn)一步的研究和創(chuàng)新加以解決。本文對菜鳥智能倉庫中的智能搬運(yùn)機(jī)器人的路徑規(guī)劃相關(guān)問題進(jìn)行了針對性的優(yōu)化分析設(shè)計。目的主要是在當(dāng)前傳統(tǒng)電商服務(wù)行業(yè)和現(xiàn)代工業(yè)自動化制造行業(yè)快速發(fā)展的背景和情況下，通過優(yōu)化設(shè)計，來有效提高機(jī)器人服務(wù)的效率。結(jié)合菜鳥智能倉的實(shí)際情況，改進(jìn)了傳統(tǒng)的A*算法，以時間代價作為優(yōu)化的衡量標(biāo)準(zhǔn)，并考慮搬運(yùn)機(jī)器人轉(zhuǎn)彎的時間代價t，實(shí)現(xiàn)為搬運(yùn)機(jī)器人尋找一條最高效最準(zhǔn)確的路徑。