互聯網營銷環(huán)境下倉儲機器人集群調度問題研究

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

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

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

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

1 倉儲空間結構和物流任務優(yōu)化分析

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

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

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

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

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

2.1 機器人的智能調度算法

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

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

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

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

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

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

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

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

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

對比圖4 （a） 和圖4 （b） 發(fā)現， 以道路為節(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é)點為道路， 則需要調整并優(yōu)化評價函數， 如圖7 所示：

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

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

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

2.4 碰撞預防

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

3 仿真實驗

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

3.1 任務生成和實驗設定

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

3.2 實驗結果

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

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

表1 仿真實驗結果

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

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

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

4 結束語

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

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

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

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

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

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