互聯(lián)網(wǎng)營銷環(huán)境下倉儲機器人集群調(diào)度問題研究

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中，gn為停放在第n個位置的代價，cur.x（cur.y）為當前點的橫（縱） 坐標，n.x（n.y）為第n個停放位置的橫（縱） 坐標，abs為求絕對值函數(shù)。

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

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

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

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

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

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

若當前節(jié)點所處的道路與目標點相鄰， 即如圖6 所示， 當前節(jié)點處于n1， 其所在的道路為L1， 且L1與目標點n3相鄰， 此時n2可擴展為n3。

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

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

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

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

2.4 碰撞預(yù)防

理論上來說， 為避免碰撞， 在某一時刻某個特定位置設(shè)置獨立點。 實際操作中， 這一檢測過程主要通過安裝在機器人身上的紅外傳感器或超聲波來實現(xiàn)。

3 仿真實驗

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

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

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

3.2 實驗結(jié)果

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

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

表1 仿真實驗結(jié)果

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

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

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

4 結(jié)束語

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

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

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

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

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

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