仓储是物流行业中重要的环节，高效合理的仓储有利于对入库、移库、盘点及出库等环节进行全面控制和规范管理，从而实现物资的快速周转流通。
     大型仓储中心物资吞吐量每日可多达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.