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

    車輛行駛途中定時獲取地面RFID標簽信息,當采集到如表1中坐標20 195 535時，即定位到2層廳廊(節點P)。

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

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

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

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

    本文提出的基于RFID倉儲車輛的智能導航與多車輛調度方法，充分利用了RFID模塊多路采集的特性，將貨物識別功能與車輛實時定位功能集成于一體。車載終端的設計，不僅為駕駛員提供了智能的路徑規劃，而且實現了多終端對路徑距離的分布式求解，有效提升了主機對多車輛協調調度的效率，從而縮短了貨物搬運周轉時間，節約了物流倉儲成本，具有很好的應用前景。
參考文獻
[1] OKTEM R, AYDIN E, CAGILTAY N E. An indoor navigation aid designed for visually impaired people[J]. Industrial Electronisc, 2008,34.
[2] 劉俊承. 室內移動機器人定位與導航關鍵技術研究[D].中國科學院自動化研究所，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] 常青, 楊東凱, 寇艷紅,等.車輛導航定位方法及應用[M]. 北京: 機械工業出版社, 2005.
[5] 張青. 導航系統中路徑規劃的研究[D]. 武漢:武漢科技大學, 2008.
[6] 張偉, 李守智, 高峰,等.幾種智能最優算法的比較研究[C]. Proceedings of the 24th Chinese Control Conference, Guangzhou, P.R. China July 15-18, 2005:1316-1320.