互联网营销环境下仓储机器人集群调度问题研究

黎 娟 （成都航空职业技术学院， 四川 成都610100）

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

近年来， 电子商务的发展日新月异， 仓储物流中心面临数量和种类繁多的需调配资源而迎来了新的挑战。 有关数据显示，传统仓库中的工人在取货上所耗费的时间大约为整个物流过程的60%～70%[1]。 然而， 与传统的仓储物流方式相比， 当前的仓储物流具有周期短、 批次多、 批量小、 种类繁多等特征， 于是， 以移动机器人为基础的自动化仓储模式应运而生。

机器人集群的仓储物流的引入， 有效地节省了工人的劳动量， 提高了劳动效率。 可重构的智能化仓储物流可通过无线网得以实现， 继而实现在仓储空间的定位。 其中， 该智能化过程需要解决智能调度问题、 检测移动路径规划和防止碰撞、 优化配置机器人数量等问题。

1 仓储空间结构和物流任务优化分析

图1 为基于机器人的自动化仓储空间结构的模型。 该模型主要由货架占用（空闲） 停放位置、 入（出） 货口、 纵向（横向） 道路等构成。

该模型中入（出） 货口数量、 货架数量等参数可根据实际需求来灵活设置， 由此可见， 该模型具有很好的可重构性。 为避免多个移动机器人发生碰撞冲突、 提高系统安全可靠系数， 该模型中货架区域间需将横向（纵向） 道路设定为单行道。

如图2 所示， 该模型中物流任务形式表现为机器人将某一货架从占用的停放位置n1移到某个入（出） 货口n2， 任务完成后， 重新移动到货架区域位置n3。

一个物流任务可具体为以下三个步骤： 第一步， 机器人移动到货架占用停放位置； 第二步， 机器人将货架移动到相应入（出） 货口； 第三步， 机器人将货架移动到空闲停放位置。 其中， 第一步和第三步经任务调度决定； 第二步经路径规划法进行优化， 如图3 所示。

2 机器人的智能调度和路径规划

2.1 机器人的智能调度算法

在上述物流任务第一步的优化过程中， 应依据评价函数对执行任务的机器人进行评价以选出最优的机器人[2]， 其中， 该评价函数为：

式（1） 为第n个机器人执行任务付出的代价，tn1表示第n个机器人完成前两步需要的时间（若空闲则该项为0） ，tn1表示第n个机器人完成第三步需要的时间， 其中w为拥塞系数。

依评价函数（1） ， 所有机器人被分成两类： 一类为执行当前任务状态， 另一类为空闲状态。 首先计算两类情况下各自的等待代价和路径代价， 然后计算两者之和， 最后通过比较总代价gn的大小做出最优选择。

物流任务的第三步中， 空闲停放位置成为其决定因素， 在此采用曼哈顿距离来进行估计：

其中，gn为停放在第n个位置的代价，cur.x（cur.y）为当前点的横（纵） 坐标，n.x（n.y）为第n个停放位置的横（纵） 坐标，abs为求绝对值函数。

2.2 特殊规则约束下基于A*算法的路径规划

目前， 将机器人应用于仓储空间模型结构的路径规划方法很多[3-5]， 如人工势场法、 神经网络、 模糊逻辑、 A*算法等。 其中， A*算法不仅可以获得最优求解路径， 而且还得以广泛应用。 基于仓储空间结构单向运行的规则约束， 对A*算法加以修正。

A*算法是一种静态路网中有效求解最短路径的方法。 其中， 估价值和实际值之间越接近， 估价函数越好。 估价函数表示如下：

仓储空间结构模型中的道路为单行有序的， 如图4 （a） 所示为以网格为节点的扩展， 可描述为沿纵向道路L1从节点n1扩展到n2、n3、n4、n5、n6、n7， 其中n4、n7成为其关键节点。 为简化流程， A*算法转化为以道路为节点扩展， 如图4 （b） 所示， 即由初始点经道路H1、 道路H2…到达终点。

对比图4 （a） 和图4 （b） 发现， 以道路为节点扩展减少了节点， 节约了时间成本。 然而， 考虑到路径的初始点和终点可能不是道路， 在此需要特殊处理， 具体分以下三种情况： 初始点扩展道路、 道路扩展道路以及道路扩展终点。

如图5 （a） 所示， 当前处于初始点n1， 可扩展的节点为n2、n3。 如图5 （b） 所示，当前处于道路节点n1， 可扩展的节点为n2、n3、n4。

若当前节点所处的道路与目标点相邻， 即如图6 所示， 当前节点处于n1， 其所在的道路为L1， 且L1与目标点n3相邻， 此时n2可扩展为n3。

若节点为道路， 则需要调整并优化评价函数， 如图7 所示：

2.3 A*算法中加入时序的路径规划

为有效预测和避免可能存在的道路冲突， 规划路径时设置“ 时空运行地图”， 将机器人的运行轨迹以一张“ 横—纵—时间” 的三维图呈现出来。

考虑到道路的单向性， 为保证实际轨迹与原有规划完全吻合， 在此， 基于A*算法修正路径规划， 即加入时序以有效减少路径过程中产生的冲突， 最终实现地图与实际情况的一致。

2.4 碰撞预防

理论上来说， 为避免碰撞， 在某一时刻某个特定位置设置独立点。 实际操作中， 这一检测过程主要通过安装在机器人身上的红外传感器或超声波来实现。

3 仿真实验

仿真实验不仅可确保智能调度和路径规划的效度， 还可以研究机器人的任务执行情况。 该实验主要通过MATLAB2013a 软件得以实现。

3.1 任务生成和实验设定

为保证仿真实验的客观性， （1） 采用随机算法生成任务。 货架停放位置、 机器人初始位置、 入（出） 货口随机分布。（2） 实验设定如下， 1 000 的任务数量随机产生10 组任务， 其中机器人数量设定为10、 20、 30、 40、 50， 进行100 次实验。

3.2 实验结果

上述100 次实验所有任务的完成充分验证了仓储空间结构和路径规划的信度和效度。

表1 所示为双因子方差分析的结果。 其中，p=0.05 的置信水平下， 机器人数量相对于运行行程、 耗费成本以及抢路冲突具有显著性； 而路径规划算法相对于抢路冲突具有显著性， 但相对于运行行程、 耗费成本未表现出差异。

表1 仿真实验结果

图8 显示， 机器人集群在两种路径规划算法下1 000 个任务的运行行程的10 次试验的均值， 具体表现为完成任务设定的运行行程随机器人数量增加而减少， 大大提高了系统调度的灵活性。

图9 给出机器人集群在两种路径规划算法下1 000 个任务的耗费时间成本的10 次试验的均值， 具体表现为完成任务设定所耗费的时间成本随着机器人数量的增加而降低， 但抢路冲突却随机器人数量的增加而增加， 如图10 所示。

比较图8、 图9、 图10 可得， 任务运行过程中， 尽管加入时序的路径规划算法降低了抢路冲突的比例， 但面对仓储物流空间单向道路的实际情况， 抢路冲突却又无法全部避免， 冲突次数表现为随机器人数量的增加而呈现上升趋势。

4 结束语

在突飞猛进的电子商务时代， 仓储物流也迅速蓬勃发展起来。 本文探索了基于移动机器人的自动化仓储物流， 构建了可重构的仓储物流空间结构模型， 最终通过仿真实验证实了智能调度和路径规划的效度和信度。

[1] 邹爽心. 仓储机器人的应用现状与发展战略探讨[J]. 物流工程与管理， 2013,35(6):171-172.

[2] 曹宝文. 自动化仓库中多AGV 系统路径规划研究[D]. 天津： 南开大学（硕士学位论文） ， 2012:21-23.

[3] 胡克满， 胡海燕， 孙慧平,等. 基于改进型PID 控制算法在小型仓储物流智能机器人中的应用研究[J]. 物流技术， 2012(7):84-86.

[4] 杨杰， 程源. 基于多权重启发优化的物流仓储补货模式优化研究[J]. 物流技术， 2014(9):338-340.

[5] 王勇. 智能仓库系统多移动机器人路径规划研究[D]. 哈尔滨: 哈尔滨工业大学（硕士学位论文） ， 2010:19-30.