黎 娟 （成都航空職業(yè)技術(shù)學(xué)院， 四川 成都610100）

LI Juan (Chengdu Aeronautic Vocational and Technical College, Chengdu 610100, China)

近年來(lái)， 電子商務(wù)的發(fā)展日新月異， 倉(cāng)儲(chǔ)物流中心面臨數(shù)量和種類(lèi)繁多的需調(diào)配資源而迎來(lái)了新的挑戰(zhàn)。 有關(guān)數(shù)據(jù)顯示，傳統(tǒng)倉(cāng)庫(kù)中的工人在取貨上所耗費(fèi)的時(shí)間大約為整個(gè)物流過(guò)程的60%～70%[1]。 然而， 與傳統(tǒng)的倉(cāng)儲(chǔ)物流方式相比， 當(dāng)前的倉(cāng)儲(chǔ)物流具有周期短、 批次多、 批量小、 種類(lèi)繁多等特征， 于是， 以移動(dòng)機(jī)器人為基礎(chǔ)的自動(dòng)化倉(cāng)儲(chǔ)模式應(yīng)運(yùn)而生。

機(jī)器人集群的倉(cāng)儲(chǔ)物流的引入， 有效地節(jié)省了工人的勞動(dòng)量， 提高了勞動(dòng)效率。 可重構(gòu)的智能化倉(cāng)儲(chǔ)物流可通過(guò)無(wú)線網(wǎng)得以實(shí)現(xiàn)， 繼而實(shí)現(xiàn)在倉(cāng)儲(chǔ)空間的定位。 其中， 該智能化過(guò)程需要解決智能調(diào)度問(wèn)題、 檢測(cè)移動(dòng)路徑規(guī)劃和防止碰撞、 優(yōu)化配置機(jī)器人數(shù)量等問(wèn)題。

1 倉(cāng)儲(chǔ)空間結(jié)構(gòu)和物流任務(wù)優(yōu)化分析

圖1 為基于機(jī)器人的自動(dòng)化倉(cāng)儲(chǔ)空間結(jié)構(gòu)的模型。 該模型主要由貨架占用（空閑） 停放位置、 入（出） 貨口、 縱向（橫向） 道路等構(gòu)成。

該模型中入（出） 貨口數(shù)量、 貨架數(shù)量等參數(shù)可根據(jù)實(shí)際需求來(lái)靈活設(shè)置， 由此可見(jiàn)， 該模型具有很好的可重構(gòu)性。 為避免多個(gè)移動(dòng)機(jī)器人發(fā)生碰撞沖突、 提高系統(tǒng)安全可靠系數(shù)， 該模型中貨架區(qū)域間需將橫向（縱向） 道路設(shè)定為單行道。

如圖2 所示， 該模型中物流任務(wù)形式表現(xiàn)為機(jī)器人將某一貨架從占用的停放位置n1移到某個(gè)入（出） 貨口n2， 任務(wù)完成后， 重新移動(dòng)到貨架區(qū)域位置n3。

一個(gè)物流任務(wù)可具體為以下三個(gè)步驟： 第一步， 機(jī)器人移動(dòng)到貨架占用停放位置； 第二步， 機(jī)器人將貨架移動(dòng)到相應(yīng)入（出） 貨口； 第三步， 機(jī)器人將貨架移動(dòng)到空閑停放位置。 其中， 第一步和第三步經(jīng)任務(wù)調(diào)度決定； 第二步經(jīng)路徑規(guī)劃法進(jìn)行優(yōu)化， 如圖3 所示。

2 機(jī)器人的智能調(diào)度和路徑規(guī)劃

2.1 機(jī)器人的智能調(diào)度算法

在上述物流任務(wù)第一步的優(yōu)化過(guò)程中， 應(yīng)依據(jù)評(píng)價(jià)函數(shù)對(duì)執(zhí)行任務(wù)的機(jī)器人進(jìn)行評(píng)價(jià)以選出最優(yōu)的機(jī)器人[2]， 其中， 該評(píng)價(jià)函數(shù)為：

式（1） 為第n個(gè)機(jī)器人執(zhí)行任務(wù)付出的代價(jià)，tn1表示第n個(gè)機(jī)器人完成前兩步需要的時(shí)間（若空閑則該項(xiàng)為0） ，tn1表示第n個(gè)機(jī)器人完成第三步需要的時(shí)間， 其中w為擁塞系數(shù)。

依評(píng)價(jià)函數(shù)（1） ， 所有機(jī)器人被分成兩類(lèi)： 一類(lèi)為執(zhí)行當(dāng)前任務(wù)狀態(tài)， 另一類(lèi)為空閑狀態(tài)。 首先計(jì)算兩類(lèi)情況下各自的等待代價(jià)和路徑代價(jià)， 然后計(jì)算兩者之和， 最后通過(guò)比較總代價(jià)gn的大小做出最優(yōu)選擇。

物流任務(wù)的第三步中， 空閑停放位置成為其決定因素， 在此采用曼哈頓距離來(lái)進(jìn)行估計(jì)：

其中，gn為停放在第n個(gè)位置的代價(jià)，cur.x（cur.y）為當(dāng)前點(diǎn)的橫（縱） 坐標(biāo)，n.x（n.y）為第n個(gè)停放位置的橫（縱） 坐標(biāo)，abs為求絕對(duì)值函數(shù)。

2.2 特殊規(guī)則約束下基于A*算法的路徑規(guī)劃

目前， 將機(jī)器人應(yīng)用于倉(cāng)儲(chǔ)空間模型結(jié)構(gòu)的路徑規(guī)劃方法很多[3-5]， 如人工勢(shì)場(chǎng)法、 神經(jīng)網(wǎng)絡(luò)、 模糊邏輯、 A*算法等。 其中， A*算法不僅可以獲得最優(yōu)求解路徑， 而且還得以廣泛應(yīng)用。 基于倉(cāng)儲(chǔ)空間結(jié)構(gòu)單向運(yùn)行的規(guī)則約束， 對(duì)A*算法加以修正。

A*算法是一種靜態(tài)路網(wǎng)中有效求解最短路徑的方法。 其中， 估價(jià)值和實(shí)際值之間越接近， 估價(jià)函數(shù)越好。 估價(jià)函數(shù)表示如下：

倉(cāng)儲(chǔ)空間結(jié)構(gòu)模型中的道路為單行有序的， 如圖4 （a） 所示為以網(wǎng)格為節(jié)點(diǎn)的擴(kuò)展， 可描述為沿縱向道路L1從節(jié)點(diǎn)n1擴(kuò)展到n2、n3、n4、n5、n6、n7， 其中n4、n7成為其關(guān)鍵節(jié)點(diǎn)。 為簡(jiǎn)化流程， A*算法轉(zhuǎn)化為以道路為節(jié)點(diǎn)擴(kuò)展， 如圖4 （b） 所示， 即由初始點(diǎn)經(jīng)道路H1、 道路H2…到達(dá)終點(diǎn)。

對(duì)比圖4 （a） 和圖4 （b） 發(fā)現(xiàn)， 以道路為節(jié)點(diǎn)擴(kuò)展減少了節(jié)點(diǎn)， 節(jié)約了時(shí)間成本。 然而， 考慮到路徑的初始點(diǎn)和終點(diǎn)可能不是道路， 在此需要特殊處理， 具體分以下三種情況： 初始點(diǎn)擴(kuò)展道路、 道路擴(kuò)展道路以及道路擴(kuò)展終點(diǎn)。

如圖5 （a） 所示， 當(dāng)前處于初始點(diǎn)n1， 可擴(kuò)展的節(jié)點(diǎn)為n2、n3。 如圖5 （b） 所示，當(dāng)前處于道路節(jié)點(diǎn)n1， 可擴(kuò)展的節(jié)點(diǎn)為n2、n3、n4。

若當(dāng)前節(jié)點(diǎn)所處的道路與目標(biāo)點(diǎn)相鄰， 即如圖6 所示， 當(dāng)前節(jié)點(diǎn)處于n1， 其所在的道路為L(zhǎng)1， 且L1與目標(biāo)點(diǎn)n3相鄰， 此時(shí)n2可擴(kuò)展為n3。

若節(jié)點(diǎn)為道路， 則需要調(diào)整并優(yōu)化評(píng)價(jià)函數(shù)， 如圖7 所示：

2.3 A*算法中加入時(shí)序的路徑規(guī)劃

為有效預(yù)測(cè)和避免可能存在的道路沖突， 規(guī)劃路徑時(shí)設(shè)置“ 時(shí)空運(yùn)行地圖”， 將機(jī)器人的運(yùn)行軌跡以一張“ 橫—縱—時(shí)間” 的三維圖呈現(xiàn)出來(lái)。

考慮到道路的單向性， 為保證實(shí)際軌跡與原有規(guī)劃完全吻合， 在此， 基于A*算法修正路徑規(guī)劃， 即加入時(shí)序以有效減少路徑過(guò)程中產(chǎn)生的沖突， 最終實(shí)現(xiàn)地圖與實(shí)際情況的一致。

2.4 碰撞預(yù)防

理論上來(lái)說(shuō)， 為避免碰撞， 在某一時(shí)刻某個(gè)特定位置設(shè)置獨(dú)立點(diǎn)。 實(shí)際操作中， 這一檢測(cè)過(guò)程主要通過(guò)安裝在機(jī)器人身上的紅外傳感器或超聲波來(lái)實(shí)現(xiàn)。

3 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)不僅可確保智能調(diào)度和路徑規(guī)劃的效度， 還可以研究機(jī)器人的任務(wù)執(zhí)行情況。 該實(shí)驗(yàn)主要通過(guò)MATLAB2013a 軟件得以實(shí)現(xiàn)。

3.1 任務(wù)生成和實(shí)驗(yàn)設(shè)定

為保證仿真實(shí)驗(yàn)的客觀性， （1） 采用隨機(jī)算法生成任務(wù)。 貨架停放位置、 機(jī)器人初始位置、 入（出） 貨口隨機(jī)分布。（2） 實(shí)驗(yàn)設(shè)定如下， 1 000 的任務(wù)數(shù)量隨機(jī)產(chǎn)生10 組任務(wù)， 其中機(jī)器人數(shù)量設(shè)定為10、 20、 30、 40、 50， 進(jìn)行100 次實(shí)驗(yàn)。

3.2 實(shí)驗(yàn)結(jié)果

上述100 次實(shí)驗(yàn)所有任務(wù)的完成充分驗(yàn)證了倉(cāng)儲(chǔ)空間結(jié)構(gòu)和路徑規(guī)劃的信度和效度。

表1 所示為雙因子方差分析的結(jié)果。 其中，p=0.05 的置信水平下， 機(jī)器人數(shù)量相對(duì)于運(yùn)行行程、 耗費(fèi)成本以及搶路沖突具有顯著性； 而路徑規(guī)劃算法相對(duì)于搶路沖突具有顯著性， 但相對(duì)于運(yùn)行行程、 耗費(fèi)成本未表現(xiàn)出差異。

表1 仿真實(shí)驗(yàn)結(jié)果

圖8 顯示， 機(jī)器人集群在兩種路徑規(guī)劃算法下1 000 個(gè)任務(wù)的運(yùn)行行程的10 次試驗(yàn)的均值， 具體表現(xiàn)為完成任務(wù)設(shè)定的運(yùn)行行程隨機(jī)器人數(shù)量增加而減少， 大大提高了系統(tǒng)調(diào)度的靈活性。

圖9 給出機(jī)器人集群在兩種路徑規(guī)劃算法下1 000 個(gè)任務(wù)的耗費(fèi)時(shí)間成本的10 次試驗(yàn)的均值， 具體表現(xiàn)為完成任務(wù)設(shè)定所耗費(fèi)的時(shí)間成本隨著機(jī)器人數(shù)量的增加而降低， 但搶路沖突卻隨機(jī)器人數(shù)量的增加而增加， 如圖10 所示。

比較圖8、 圖9、 圖10 可得， 任務(wù)運(yùn)行過(guò)程中， 盡管加入時(shí)序的路徑規(guī)劃算法降低了搶路沖突的比例， 但面對(duì)倉(cāng)儲(chǔ)物流空間單向道路的實(shí)際情況， 搶路沖突卻又無(wú)法全部避免， 沖突次數(shù)表現(xiàn)為隨機(jī)器人數(shù)量的增加而呈現(xiàn)上升趨勢(shì)。

4 結(jié)束語(yǔ)

在突飛猛進(jìn)的電子商務(wù)時(shí)代， 倉(cāng)儲(chǔ)物流也迅速蓬勃發(fā)展起來(lái)。 本文探索了基于移動(dòng)機(jī)器人的自動(dòng)化倉(cāng)儲(chǔ)物流， 構(gòu)建了可重構(gòu)的倉(cāng)儲(chǔ)物流空間結(jié)構(gòu)模型， 最終通過(guò)仿真實(shí)驗(yàn)證實(shí)了智能調(diào)度和路徑規(guī)劃的效度和信度。

[1] 鄒爽心. 倉(cāng)儲(chǔ)機(jī)器人的應(yīng)用現(xiàn)狀與發(fā)展戰(zhàn)略探討[J]. 物流工程與管理， 2013,35(6):171-172.

[2] 曹寶文. 自動(dòng)化倉(cāng)庫(kù)中多AGV 系統(tǒng)路徑規(guī)劃研究[D]. 天津： 南開(kāi)大學(xué)（碩士學(xué)位論文） ， 2012:21-23.

[3] 胡克滿， 胡海燕， 孫慧平,等. 基于改進(jìn)型PID 控制算法在小型倉(cāng)儲(chǔ)物流智能機(jī)器人中的應(yīng)用研究[J]. 物流技術(shù)， 2012(7):84-86.

[4] 楊杰， 程源. 基于多權(quán)重啟發(fā)優(yōu)化的物流倉(cāng)儲(chǔ)補(bǔ)貨模式優(yōu)化研究[J]. 物流技術(shù)， 2014(9):338-340.

[5] 王勇. 智能倉(cāng)庫(kù)系統(tǒng)多移動(dòng)機(jī)器人路徑規(guī)劃研究[D]. 哈爾濱: 哈爾濱工業(yè)大學(xué)（碩士學(xué)位論文） ， 2010:19-30.