文獻標(biāo)識碼: A
文章編號: 0258-7998(2011)07-138-03
倉儲是物流行業(yè)中重要的環(huán)節(jié),高效合理的倉儲有利于對入庫、移庫、盤點及出庫等環(huán)節(jié)進行全面控制和規(guī)范管理,從而實現(xiàn)物資的快速周轉(zhuǎn)流通。
大型倉儲中心物資吞吐量每日可多達5萬單,由于物品分類繁雜、庫房數(shù)目眾多、道路情況復(fù)雜,搬運叉車駕駛員在尋找目標(biāo)貨架時只能憑借記憶或路牌指引,既費時費力又極易出錯。針對這一現(xiàn)狀,本文提出了一種基于RFID的室內(nèi)定位導(dǎo)航方法,通過車載射頻天線讀取地面標(biāo)簽信息,建立運輸車輛與所在倉庫地圖的坐標(biāo)關(guān)系,實現(xiàn)對車輛的實時追蹤定位,進而由車載運算終端生成最優(yōu)行駛路徑,并協(xié)同主機解決多車輛的任務(wù)分派、協(xié)同調(diào)度等問題。
1 系統(tǒng)結(jié)構(gòu)
系統(tǒng)由調(diào)度主機、車載終端和RFID模塊三個部分構(gòu)成,如圖1所示。調(diào)度主機作為數(shù)據(jù)匯總中心,一方面通過Wi-Fi無線網(wǎng)絡(luò)與車載終端進行信息交互[1],內(nèi)容包括下行的指令下達、地圖下載以及上行的信息反饋、任務(wù)回執(zhí)等;另一方面主機作為后端MIS管理系統(tǒng),對物資、員工、車輛等實體進行信息維護。
車載終端是連接RFID模塊與主機的橋梁,其任務(wù)包括接收主機調(diào)度指令、規(guī)劃最優(yōu)路徑、控制RFID讀寫等,為駕駛員提供可視的圖形界面和便利的操作方式(如觸摸屏、語音識別),并為可能使用到的外部器件提供充足的通信接口(如RFID常用的RS232/485、條碼掃描槍、擴展存儲器等接口)。
RFID模塊用作倉儲傳感器網(wǎng)絡(luò)的核心傳感單元,通過射頻信號的空間耦合,實現(xiàn)讀卡器對標(biāo)簽信息的采集與修改。因此RFID模塊應(yīng)支持ISO18000-6b/c標(biāo)準(zhǔn),具備完善通信協(xié)議及多標(biāo)簽防沖突檢測算法。
2 地圖與定位
根據(jù)大型倉儲中心的布局特征,本文采取了拓撲與柵格相結(jié)合的地圖構(gòu)造方式[2]:將整個空間劃分為若干個以柵格地圖表示的子區(qū)域(Room),各子區(qū)域與廳廊(Hall)之間以拓撲方式連接,如圖2所示。
此方法充分結(jié)合了柵格地圖的定位優(yōu)勢及拓撲地圖在路徑規(guī)劃上的便捷性,不僅克服了單一地圖下柵格數(shù)量過多對處理器資源過度消耗的缺點,減少了實時處理的負擔(dān),而且通過弱化拓撲復(fù)雜度,彌補了拓撲地圖難以創(chuàng)建和維護的不足。
圖2中,實圓點代表RFID標(biāo)簽節(jié)點,8位數(shù)字表示對應(yīng)節(jié)點坐標(biāo)。其中包括bit[7]樓層號,bit[6]子區(qū)域號, bit[5]節(jié)點屬性(1:拓撲坐標(biāo);0:柵格坐標(biāo)),bit[4:0]坐標(biāo)值。坐標(biāo)以9 000為中心依據(jù)索引法[3]向四周擴散。
車輛行駛途中定時獲取地面RFID標(biāo)簽信息,當(dāng)采集到如表1中坐標(biāo)20 195 535時,即定位到2層廳廊(節(jié)點P)。
3 單車導(dǎo)航
當(dāng)車輛接收到主機下達的行駛指令后,對應(yīng)車載終端以當(dāng)前位置為起點,計算生成一條到達任務(wù)節(jié)點的最佳路線。其路線既要求避開障礙,又要求保證最小的行駛耗費(如時間、路程、轉(zhuǎn)彎次數(shù)等)。
尋徑算法決定了路徑規(guī)劃的效率,不同的尋徑算法適應(yīng)于不同的場合。根據(jù)物流倉庫內(nèi)的貨架擺放布局不需經(jīng)常更新,因此,可采用靜態(tài)地圖尋徑常用的Dijkstra或A*算法[4]。對于A*算法,通常用G(n)表示從起點s到任意定點n的實際耗費。G(n)是一個定值,但有可能找到一條從起點到節(jié)點n更近的路徑,因此有可能被更新。H(n)用于表示從任一點n到終點所耗費的期望值,因為H(n)是個估計值,所以一般值不變。由G(n)和H(n)得到節(jié)點n的估價函數(shù)如式(1)所示,它表示從起點經(jīng)過定點n到達終點的耗費值估計。每次查找,算法都將檢查F(n)值最小的定點。
圖3對應(yīng)于圖2中Room2的柵格地圖。圖中S為起始節(jié)點,G為目標(biāo)節(jié)點,假設(shè)相鄰格點間距離權(quán)重D相同,運用A*算法實現(xiàn)的路徑軌跡如圖中S到G間的實圓點所示,不同指向的箭頭表示A*算法的擴散方向。值得注意的是,實線邊框內(nèi)的區(qū)域是查找到目標(biāo)時所有遍歷過的節(jié)點,其數(shù)量明顯小于Dijsktra算法(Dijsktra算法同樣尋徑幾乎遍歷了整張網(wǎng)格地圖)。效率的差異即是本文采用A*算法的依據(jù)。
4 多車輛調(diào)度
倉儲運營現(xiàn)場,運輸車隊可能一次性接收到大量任務(wù),如裝載、卸貨、盤點等。如何為每輛車分配恰當(dāng)?shù)娜蝿?wù),調(diào)整執(zhí)行次序,使車隊在滿足一定約束條件(載貨量、總行程、時間限制等)下,最高效地完成指令目標(biāo),也即是求解車輛最優(yōu)化調(diào)度的問題VRP(Vehicle Routing Problem)[5]。
VRP精確算法所需的計算量非常大,只適合于小規(guī)模調(diào)度。而啟發(fā)式算法如遺傳算法、模擬退火算法、禁忌搜索算法、蟻群算法等[6],可在可接受的時間限制下盡可能得到問題的最優(yōu)解。本文采用遺傳算法,不僅是因為其具有全局搜索能力,而且利用了它的隱式并行性、魯棒性強和實現(xiàn)簡單等優(yōu)點,極大地減少了計算時間,提高了調(diào)度效率。
應(yīng)用于運輸車隊調(diào)度的遺傳算法流程定義如下:
(1) 初始化算法前期準(zhǔn)備信息,包括最大使用車輛數(shù)Nv、各車輛最大載貨量Lm、各任務(wù)點坐標(biāo)Pt、車輛當(dāng)前所在坐標(biāo)Pv以及各坐標(biāo)點間距離Dij。其中由Dij由車載終端多機并行計算,并交由主機匯總。
(2) 由任務(wù)數(shù)目與車輛數(shù)目之和確定染色體長度(ChromSize),如取任務(wù)點A、B、C、D、E、F共6個,車輛有Vs、Vm、Ve共3輛,則ChSize=6+3=9。初始化種群規(guī)模PopSize、進化代數(shù)Ge、交叉概率Pc、變異概率Pm,隨即初始化原始種群。
(3) 計算個體自適應(yīng)度,從而確定其遺傳幾率。對于染色體x,設(shè)定其適應(yīng)度函數(shù)如下:
(5) 新種群內(nèi)個體間隨機兩兩配對,以交叉概率Pc交換部分基因,從而交叉形成兩個新的個體(本文選取單點交叉算子)。
(6) 以變異概率Pm將個體中某些基因位置對換,從而變異出一個新的個體。變異運算是產(chǎn)生個體的輔助方法,決定了遺傳算法的局部搜索能力,同時保持了種群的多樣性,與交叉運算相結(jié)合,實現(xiàn)了對空間全局與局部的同步搜索。
(7) 循環(huán)執(zhí)行(3)~(6)步驟,直至達到進化代數(shù)Ge次為止。
(8) 根據(jù)每次進化結(jié)果統(tǒng)計信息,得出算法結(jié)果。
設(shè)定任務(wù)節(jié)點A、B、C、D、E、F及車輛Vs、Vm、Ve位置信息如圖3所示,水平與垂直方向相鄰網(wǎng)格距離權(quán)重為10,斜向權(quán)重為14,種群規(guī)模為10,進化代數(shù)為100,交叉概率為0.5,變異概率為0.01。對每一代適應(yīng)度最高結(jié)果記錄如圖4所示,橫軸為進化代數(shù),縱軸實線為最短距離,虛線為對應(yīng)序列平均適應(yīng)度。
由圖可見,種群進化使最優(yōu)個體的適應(yīng)度有降至平均的趨勢,如第21代~第30代。此外,良性進化使變異個體適應(yīng)度有明顯的提升,如第10代。隨即初始化樣本在有限進化代數(shù)內(nèi)達到了一定的收斂性,在第21代取得了以行駛路程為約束條件的局部最優(yōu)值382,染色體序列Ve-D-B-E-Vm-A-Vs-C-F,對應(yīng)車輛規(guī)劃為:Vs負責(zé)任務(wù)C、F,車輛Vm負責(zé)任務(wù)A,Ve負責(zé)任務(wù)D、B、E。
應(yīng)用本文方法及參數(shù)在某超市現(xiàn)場環(huán)境下進行5次隨機測試。與傳統(tǒng)的人工尋路及順序執(zhí)行方式相比較,引入A*算法及遺傳算法后,節(jié)省了約60%的任務(wù)執(zhí)行時間,如表2所示。
本文提出的基于RFID倉儲車輛的智能導(dǎo)航與多車輛調(diào)度方法,充分利用了RFID模塊多路采集的特性,將貨物識別功能與車輛實時定位功能集成于一體。車載終端的設(shè)計,不僅為駕駛員提供了智能的路徑規(guī)劃,而且實現(xiàn)了多終端對路徑距離的分布式求解,有效提升了主機對多車輛協(xié)調(diào)調(diào)度的效率,從而縮短了貨物搬運周轉(zhuǎn)時間,節(jié)約了物流倉儲成本,具有很好的應(yīng)用前景。
參考文獻
[1] OKTEM R, AYDIN E, CAGILTAY N E. An indoor navigation aid designed for visually impaired people[J]. Industrial Electronisc, 2008,34.
[2] 劉俊承. 室內(nèi)移動機器人定位與導(dǎo)航關(guān)鍵技術(shù)研究[D].中國科學(xué)院自動化研究所,2005.
[3] Lin Weiguo, Mu Changli, TAKASE K. Path planning with topological map built with ID tag and WEB camera[C]. Proceedings of the 2006 IEEE, June 25-28, 2006.
[4] 常青, 楊東凱, 寇艷紅,等.車輛導(dǎo)航定位方法及應(yīng)用[M]. 北京: 機械工業(yè)出版社, 2005.
[5] 張青. 導(dǎo)航系統(tǒng)中路徑規(guī)劃的研究[D]. 武漢:武漢科技大學(xué), 2008.
[6] 張偉, 李守智, 高峰,等.幾種智能最優(yōu)算法的比較研究[C]. Proceedings of the 24th Chinese Control Conference, Guangzhou, P.R. China July 15-18, 2005:1316-1320.