倉(cāng)儲(chǔ)是物流行業(yè)中重要的環(huán)節(jié)，高效合理的倉(cāng)儲(chǔ)有利于對(duì)入庫(kù)、移庫(kù)、盤(pán)點(diǎn)及出庫(kù)等環(huán)節(jié)進(jìn)行全面控制和規(guī)范管理，從而實(shí)現(xiàn)物資的快速周轉(zhuǎn)流通。
     大型倉(cāng)儲(chǔ)中心物資吞吐量每日可多達(dá)5萬(wàn)單，由于物品分類(lèi)繁雜、庫(kù)房數(shù)目眾多、道路情況復(fù)雜，搬運(yùn)叉車(chē)駕駛員在尋找目標(biāo)貨架時(shí)只能憑借記憶或路牌指引，既費(fèi)時(shí)費(fèi)力又極易出錯(cuò)。針對(duì)這一現(xiàn)狀,本文提出了一種基于RFID的室內(nèi)定位導(dǎo)航方法，通過(guò)車(chē)載射頻天線(xiàn)讀取地面標(biāo)簽信息，建立運(yùn)輸車(chē)輛與所在倉(cāng)庫(kù)地圖的坐標(biāo)關(guān)系，實(shí)現(xiàn)對(duì)車(chē)輛的實(shí)時(shí)追蹤定位，進(jìn)而由車(chē)載運(yùn)算終端生成最優(yōu)行駛路徑，并協(xié)同主機(jī)解決多車(chē)輛的任務(wù)分派、協(xié)同調(diào)度等問(wèn)題。
1 系統(tǒng)結(jié)構(gòu)
    系統(tǒng)由調(diào)度主機(jī)、車(chē)載終端和RFID模塊三個(gè)部分構(gòu)成，如圖1所示。調(diào)度主機(jī)作為數(shù)據(jù)匯總中心，一方面通過(guò)Wi-Fi無(wú)線(xiàn)網(wǎng)絡(luò)與車(chē)載終端進(jìn)行信息交互[1]，內(nèi)容包括下行的指令下達(dá)、地圖下載以及上行的信息反饋、任務(wù)回執(zhí)等；另一方面主機(jī)作為后端MIS管理系統(tǒng)，對(duì)物資、員工、車(chē)輛等實(shí)體進(jìn)行信息維護(hù)。
    車(chē)載終端是連接RFID模塊與主機(jī)的橋梁,其任務(wù)包括接收主機(jī)調(diào)度指令、規(guī)劃最優(yōu)路徑、控制RFID讀寫(xiě)等，為駕駛員提供可視的圖形界面和便利的操作方式(如觸摸屏、語(yǔ)音識(shí)別)，并為可能使用到的外部器件提供充足的通信接口(如RFID常用的RS232/485、條碼掃描槍、擴(kuò)展存儲(chǔ)器等接口)。
     RFID模塊用作倉(cāng)儲(chǔ)傳感器網(wǎng)絡(luò)的核心傳感單元，通過(guò)射頻信號(hào)的空間耦合，實(shí)現(xiàn)讀卡器對(duì)標(biāo)簽信息的采集與修改。因此RFID模塊應(yīng)支持ISO18000-6b/c標(biāo)準(zhǔn)，具備完善通信協(xié)議及多標(biāo)簽防沖突檢測(cè)算法。
2 地圖與定位
     根據(jù)大型倉(cāng)儲(chǔ)中心的布局特征，本文采取了拓?fù)渑c柵格相結(jié)合的地圖構(gòu)造方式[2]：將整個(gè)空間劃分為若干個(gè)以柵格地圖表示的子區(qū)域（Room），各子區(qū)域與廳廊（Hall）之間以拓?fù)浞绞竭B接，如圖2所示。
    此方法充分結(jié)合了柵格地圖的定位優(yōu)勢(shì)及拓?fù)涞貓D在路徑規(guī)劃上的便捷性，不僅克服了單一地圖下柵格數(shù)量過(guò)多對(duì)處理器資源過(guò)度消耗的缺點(diǎn),減少了實(shí)時(shí)處理的負(fù)擔(dān)，而且通過(guò)弱化拓?fù)鋸?fù)雜度，彌補(bǔ)了拓?fù)涞貓D難以創(chuàng)建和維護(hù)的不足。
    圖2中,實(shí)圓點(diǎn)代表RFID標(biāo)簽節(jié)點(diǎn)，8位數(shù)字表示對(duì)應(yīng)節(jié)點(diǎn)坐標(biāo)。其中包括bit[7]樓層號(hào)，bit[6]子區(qū)域號(hào)， bit[5]節(jié)點(diǎn)屬性(1：拓?fù)渥鴺?biāo)；0：柵格坐標(biāo))，bit[4:0]坐標(biāo)值。坐標(biāo)以9 000為中心依據(jù)索引法[3]向四周擴(kuò)散。

    車(chē)輛行駛途中定時(shí)獲取地面RFID標(biāo)簽信息,當(dāng)采集到如表1中坐標(biāo)20 195 535時(shí)，即定位到2層廳廊(節(jié)點(diǎn)P)。

3 單車(chē)導(dǎo)航
    當(dāng)車(chē)輛接收到主機(jī)下達(dá)的行駛指令后，對(duì)應(yīng)車(chē)載終端以當(dāng)前位置為起點(diǎn)，計(jì)算生成一條到達(dá)任務(wù)節(jié)點(diǎn)的最佳路線(xiàn)。其路線(xiàn)既要求避開(kāi)障礙，又要求保證最小的行駛耗費(fèi)(如時(shí)間、路程、轉(zhuǎn)彎次數(shù)等)。
    尋徑算法決定了路徑規(guī)劃的效率，不同的尋徑算法適應(yīng)于不同的場(chǎng)合。根據(jù)物流倉(cāng)庫(kù)內(nèi)的貨架擺放布局不需經(jīng)常更新，因此，可采用靜態(tài)地圖尋徑常用的Dijkstra或A*算法[4]。對(duì)于A*算法，通常用G(n)表示從起點(diǎn)s到任意定點(diǎn)n的實(shí)際耗費(fèi)。G(n)是一個(gè)定值，但有可能找到一條從起點(diǎn)到節(jié)點(diǎn)n更近的路徑，因此有可能被更新。H(n)用于表示從任一點(diǎn)n到終點(diǎn)所耗費(fèi)的期望值,因?yàn)镠(n)是個(gè)估計(jì)值，所以一般值不變。由G(n)和H(n)得到節(jié)點(diǎn)n的估價(jià)函數(shù)如式(1)所示,它表示從起點(diǎn)經(jīng)過(guò)定點(diǎn)n到達(dá)終點(diǎn)的耗費(fèi)值估計(jì)。每次查找，算法都將檢查F(n)值最小的定點(diǎn)。
    
    圖3對(duì)應(yīng)于圖2中Room2的柵格地圖。圖中S為起始節(jié)點(diǎn)，G為目標(biāo)節(jié)點(diǎn)，假設(shè)相鄰格點(diǎn)間距離權(quán)重D相同，運(yùn)用A*算法實(shí)現(xiàn)的路徑軌跡如圖中S到G間的實(shí)圓點(diǎn)所示，不同指向的箭頭表示A*算法的擴(kuò)散方向。值得注意的是，實(shí)線(xiàn)邊框內(nèi)的區(qū)域是查找到目標(biāo)時(shí)所有遍歷過(guò)的節(jié)點(diǎn)，其數(shù)量明顯小于Dijsktra算法(Dijsktra算法同樣尋徑幾乎遍歷了整張網(wǎng)格地圖)。效率的差異即是本文采用A*算法的依據(jù)。

4 多車(chē)輛調(diào)度
    倉(cāng)儲(chǔ)運(yùn)營(yíng)現(xiàn)場(chǎng)，運(yùn)輸車(chē)隊(duì)可能一次性接收到大量任務(wù)，如裝載、卸貨、盤(pán)點(diǎn)等。如何為每輛車(chē)分配恰當(dāng)?shù)娜蝿?wù)，調(diào)整執(zhí)行次序，使車(chē)隊(duì)在滿(mǎn)足一定約束條件（載貨量、總行程、時(shí)間限制等）下，最高效地完成指令目標(biāo)，也即是求解車(chē)輛最優(yōu)化調(diào)度的問(wèn)題VRP(Vehicle Routing Problem)[5]。
    VRP精確算法所需的計(jì)算量非常大，只適合于小規(guī)模調(diào)度。而啟發(fā)式算法如遺傳算法、模擬退火算法、禁忌搜索算法、蟻群算法等[6],可在可接受的時(shí)間限制下盡可能得到問(wèn)題的最優(yōu)解。本文采用遺傳算法，不僅是因?yàn)槠渚哂腥炙阉髂芰?而且利用了它的隱式并行性、魯棒性強(qiáng)和實(shí)現(xiàn)簡(jiǎn)單等優(yōu)點(diǎn)，極大地減少了計(jì)算時(shí)間，提高了調(diào)度效率。
    應(yīng)用于運(yùn)輸車(chē)隊(duì)調(diào)度的遺傳算法流程定義如下：
    (1) 初始化算法前期準(zhǔn)備信息,包括最大使用車(chē)輛數(shù)Nv、各車(chē)輛最大載貨量Lm、各任務(wù)點(diǎn)坐標(biāo)Pt、車(chē)輛當(dāng)前所在坐標(biāo)Pv以及各坐標(biāo)點(diǎn)間距離Dij。其中由Dij由車(chē)載終端多機(jī)并行計(jì)算，并交由主機(jī)匯總。
    (2) 由任務(wù)數(shù)目與車(chē)輛數(shù)目之和確定染色體長(zhǎng)度(ChromSize)，如取任務(wù)點(diǎn)A、B、C、D、E、F共6個(gè),車(chē)輛有Vs、Vm、Ve共3輛，則ChSize=6+3=9。初始化種群規(guī)模PopSize、進(jìn)化代數(shù)Ge、交叉概率Pc、變異概率Pm,隨即初始化原始種群。
    (3) 計(jì)算個(gè)體自適應(yīng)度，從而確定其遺傳幾率。對(duì)于染色體x，設(shè)定其適應(yīng)度函數(shù)如下：

     (5) 新種群內(nèi)個(gè)體間隨機(jī)兩兩配對(duì),以交叉概率Pc交換部分基因，從而交叉形成兩個(gè)新的個(gè)體（本文選取單點(diǎn)交叉算子）。
    (6) 以變異概率Pm將個(gè)體中某些基因位置對(duì)換，從而變異出一個(gè)新的個(gè)體。變異運(yùn)算是產(chǎn)生個(gè)體的輔助方法，決定了遺傳算法的局部搜索能力，同時(shí)保持了種群的多樣性，與交叉運(yùn)算相結(jié)合，實(shí)現(xiàn)了對(duì)空間全局與局部的同步搜索。
    (7) 循環(huán)執(zhí)行(3)~(6)步驟，直至達(dá)到進(jìn)化代數(shù)Ge次為止。
    (8) 根據(jù)每次進(jìn)化結(jié)果統(tǒng)計(jì)信息，得出算法結(jié)果。
    設(shè)定任務(wù)節(jié)點(diǎn)A、B、C、D、E、F及車(chē)輛Vs、Vm、Ve位置信息如圖3所示,水平與垂直方向相鄰網(wǎng)格距離權(quán)重為10，斜向權(quán)重為14，種群規(guī)模為10，進(jìn)化代數(shù)為100，交叉概率為0.5，變異概率為0.01。對(duì)每一代適應(yīng)度最高結(jié)果記錄如圖4所示，橫軸為進(jìn)化代數(shù)，縱軸實(shí)線(xiàn)為最短距離，虛線(xiàn)為對(duì)應(yīng)序列平均適應(yīng)度。

     由圖可見(jiàn)，種群進(jìn)化使最優(yōu)個(gè)體的適應(yīng)度有降至平均的趨勢(shì)，如第21代~第30代。此外,良性進(jìn)化使變異個(gè)體適應(yīng)度有明顯的提升，如第10代。隨即初始化樣本在有限進(jìn)化代數(shù)內(nèi)達(dá)到了一定的收斂性，在第21代取得了以行駛路程為約束條件的局部最優(yōu)值382，染色體序列Ve-D-B-E-Vm-A-Vs-C-F,對(duì)應(yīng)車(chē)輛規(guī)劃為：Vs負(fù)責(zé)任務(wù)C、F，車(chē)輛Vm負(fù)責(zé)任務(wù)A，Ve負(fù)責(zé)任務(wù)D、B、E。
    應(yīng)用本文方法及參數(shù)在某超市現(xiàn)場(chǎng)環(huán)境下進(jìn)行5次隨機(jī)測(cè)試。與傳統(tǒng)的人工尋路及順序執(zhí)行方式相比較，引入A*算法及遺傳算法后，節(jié)省了約60%的任務(wù)執(zhí)行時(shí)間，如表2所示。

    本文提出的基于RFID倉(cāng)儲(chǔ)車(chē)輛的智能導(dǎo)航與多車(chē)輛調(diào)度方法，充分利用了RFID模塊多路采集的特性，將貨物識(shí)別功能與車(chē)輛實(shí)時(shí)定位功能集成于一體。車(chē)載終端的設(shè)計(jì)，不僅為駕駛員提供了智能的路徑規(guī)劃，而且實(shí)現(xiàn)了多終端對(duì)路徑距離的分布式求解，有效提升了主機(jī)對(duì)多車(chē)輛協(xié)調(diào)調(diào)度的效率，從而縮短了貨物搬運(yùn)周轉(zhuǎn)時(shí)間，節(jié)約了物流倉(cāng)儲(chǔ)成本，具有很好的應(yīng)用前景。
參考文獻(xiàn)
[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òng)機(jī)器人定位與導(dǎo)航關(guān)鍵技術(shù)研究[D].中國(guó)科學(xué)院自動(dòng)化研究所，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] 常青, 楊東凱, 寇艷紅,等.車(chē)輛導(dǎo)航定位方法及應(yīng)用[M]. 北京: 機(jī)械工業(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.