1 引言

随着电子商务行业的迅速生长, 网络购物成为一种潮流, 很大一部分人热衷于通过网络购置需要的工具。在这样的生长趋势下, 人们对物流效劳也越来越重视, 而运转效率就是物流效劳的一个重要指标。关于普通客户来讲, 速度是评价效劳的重要标准之一。

货仓作为货物运转的节点, 对货物运转有着至关重要的影响。现如今大大都的货仓自动化水平还比较低, 订单的拣选基本依靠劳动力完成, 这样一来效率低, 二来过失率高, 用户体验较差。并且现今人力本钱上升, 古板的事情方法早已不可满足社会需求[1]。

为解决这样的窘境, 各大运营商纷纷在机械人方面加大投入研发, 比较典范的如亚马逊的Kiva机械人、阿里巴巴的“曹操”机械人、京东的六轴机械臂等, 目前已有部分货仓将机械人运用到现实的作业中。在电商货仓配送中心的搬运本钱中, 拣货的搬运本钱约占90%, 与拣货直接相关的人力占50%。拣货时间约占整个配送中心操作时间的30%-40%。在配送历程中, 拣货是整个配送中心操作系统的焦点, 合理计划与治理拣货历程, 对配送中心事情效率的提高具有决定性的影响。

本文就提高电商货仓配送中心事情效率提出拣货机械人路径优化要领, 就路径优化中的最短路径及多机械人之间的避障进行研究并建模得出结果。

2 计划设计

2.1 地图设计

合理的货仓地图设计有利于货仓存储物资的合理安排, 能够降低货仓事情人员的事情量, 减少不须要的重复劳动。货仓路径、货架的合理结构有利于通道的流通, 确保货仓事情人员和机械人的通行宁静。地图的设计应凭据货物种类、障碍物位置、货仓规模等因素做一些合理的计划。

图文件使用Tiled Map辅助绘制, 实验凭据货架位置及障碍物位置做一个简单的路径设计, 具体货仓地图结构如图1所示, 其中包括货架位置、障碍物、路径以及路径的交叉点。为便当机械人与效劳器的信息相同, 每个交叉点处会设置二维码以体现该交叉点在地图上的坐标位置, 由于交叉点为一个正方形, 这里以正方形左上角位置为交叉点坐标并设置相应序号。图文件完成同时生成tmx文件, JAVA语言读取文件生成有效信息。这里的有效信息主要是路径和路径交叉点的相关描述, 包括序号、长度、坐标等[2]。如:

以上是交叉点描述信息以及交叉点信息的二维码描述方法, 其中id体现的信息包括该点的所在图层、序号及其坐标。二维码信息体现该点坐标。

图1 货仓图   

以上是路径描述信息, id体现该路径起点与终点坐标, point体现起点与终点信息。

下面凭据路径与交叉点的关系生成矩阵, 矩阵的行和列划分为两个点的序号。当图中两点可通过某条路径相连接, 则在矩阵相对应的位置输出1, 不可连接的输出0。这样最后输出一个m×m的矩阵, 矩阵可直观的体现出图信息。第二个矩阵与第一个矩阵类似, 两点不可连接的输出0, 可通过某条路径连接的输出该路径的长度。至此地图信息对应的矩阵开端形成。

机械人每到一个节点扫描到二维码信息, 同时向效劳器发送实时位置, 效劳器凭据此信息确定机械人接下来的路径同时向机械人发送行动指令。为制止多机械人路径冲突, 当机械人向效劳器发送定点位置时, 将下一步运行的路径置∞, 即断开该路径, 这样制止同时事情的机械人路过此路径, 实现多机械人之间的避障。

2.2 数据库设计

常见的数据库类型有Oracle、SQL Server、My SQL等。综合数据容量、价格以及操作难易水平等因素, 本次实验选择了My SQL数据库。

JSP通过Connection接口会见数据库, java.sql.Satatement接口用来执行静态的SQL语句, java.sql.Prepared Satatement接口执行动态的SQL语句。

实验中数据库新建两个表。表1存储种种商品的拣货点等信息。当订单爆发时获得一个订单中所有商品的名称, 效劳器凭据商品名称从数据库获得对应取货点, 将这些取货点加入到一个事情进程中, 并宣布给机械人开始事情。表2存储机械人序号、机械人所在位置的坐标以及该坐标对应交叉点的序号。当机械人运行到某交叉点扫描到二维码, 将自身序号以及二维码包括的信息输入到数据库, 当二维码显示的点序号与取货点的序号一致, 则机械人执行取货行为。

2.3 算法设计

求最短路径的算法有许多, 常用的要领有人工势场法[3]、A*算法[4]等, 都是针对简单的点到点的路径计划任务。本次设计选用Dijkstra算法与最邻近算法相结合, 以整体时间最优为目标。

Dijkstra算法首先是获得起点V0到其他各极点距离, V0->V0的权值为0, 当V0与Vi可连接, 其权值为V0->Vi的长度, 当V0与Vi不可连接, V0->Vi权值为∞, 这样可获得一个描绘路径权值的矩阵。Dijkstra算法适合运用于求解单源最短路径的问题, 可获取得其他各极点的最短路径, 而订单需求的节点可能是多个, 所以纯粹使用Dijkstra算法不可满足需求[5]。最邻近算法, 即优先选择前往与目今所在点最接近的点, 然后以该点为起点前往下一个点, 最后获得一个最接近于最短路径的谜底。

针对电商货仓的特点, 单个机械人无法满足事情的需求, 所以另有一个重点问题, 多机械人同时事情时要如何分派才华不爆发冲突。本文接纳的避障方法有两种:一种是当某条路径正在被占用时, 更改其对应权值为∞, 下一个订单对应的路径计划就会避开这两条路径, 直至被占用路径任务完成, 释放被占用路径, 更改权值为原来的长度数值。第二种是期待, 当路径被占用, 下一个需要经过该路径的机械人可选择期待, 等前一个机械人离开本路径后再进入该路径。如有多个机械人同时期待同一个路径, 以订单爆发时间设置优先级, 先爆发的订单优先级较高。当冲突爆发时, 通过预估前一个任务完成释放路径的时间及下一个任务的期待时间, 盘算绕行泯灭时间即绕行比原路径多花的时间, 并对期待时间与绕行时间进行比较, 选择时间较短的方法。

整个运行历程为:首先效劳器获得需要拣取的商品名称, 然后从数据库获取各商品对应拣货点, 即需要抵达的各极点, 将各极点带入算法中获得经过多点的最短路径, 到此一个订单的开端路径计划事情完成。运行历程中, 如计划的某条路径正在被占用, 则重新计划接下来的路径, 不绝更新, 确保不会爆发碰撞或者梗塞。

3 功效实现

首先读取地图信息, 生成矩阵。然后将矩阵带入算法, 同时输入任务点, 获得多点之间的最短路径。最后向机械人发送任务要求, 机械人执行任务历程中经过交叉点时读取对应二维码信息, 与效劳器的信息交互, 实现避障, 即多个任务同时进行, 路径之间无交叉点。

本文的地图文件是针对电商货仓设计的。目的在于确定机械人位置与离拣货货架最近的路径上的点, 获得机械人到拣货点最短线路的盘算。确定了货仓中的多个点后, 凭据货仓地图描述文件盘算多点之间的最短线路, 并能够实现避障, 机械人之间不会碰撞且不会导致门路梗塞。任务起点为机械人休息区或者存放点, 终点为订单打包区, 这个凭据需求进行设计, 存入地图信息。其它节点凭据订单所需货物, 通过数据库信息获取货物所在货架信息。凭据多点信息及描述文件盘算最短线路的办法如下:

(1) 确定起点、取货点及货仓地图描述文件。

(2) 界说图的邻接矩阵、图的点荟萃以及路径荟萃。

(3) 解析货仓描述文件, 初始化图的点集和边集。

(4) 凭据订单确定会见点, 带入算法获得最短路径。

(5) 效劳器向机械人发送指令, 机械人路过极点扫描到二维码, 向效劳器发送实时位置。

(6) 效劳器凭据机械人实时位置信息实时更新门路实现避障, 在某条路径被会见时, 下一个任务避开该路径, 以及计划下一条路径, 找到另一条最短路径。

4 实验结果

实验开端设置两个任务实现避障。即实现图1中点到点之间的最短路径的获取, 当两个任务同时进行时, 后一个任务不会同时与前一个任务在同一路径重合, 制止碰撞的情况爆发。

实验历程首先凭据Tiled Map获得的描述文件, 使用My Eclipse软件读取描述文件信息获得路径及交叉点关系的矩阵。然后使用软件进行仿真, 将矩阵带入获得带权图 (Graph) [6]。最后输入任务, 通过Dijkstra算法获得最短路径, 经过对算法的革新实现避障。

任务一, 2->50, 任务二, 2->49。单独运行时, 实验得出结果, 任务一生成路径如图2所示, 经过节点2、9、50, 由于有1个转弯, 这里设置速度, 一个单位长度需1s, 转弯需多增加2s, 总任务时间为90s。任务二生成路径如图3所示, 经过节点2、9、49, 也有1个转弯, 总任务时间为90s。同时运行时, 由于任务一优先级高, 路径不爆发改变, 任务二为了制止与任务一爆发冲突, 可选择绕行或者期待。这里可以预估任务一抵达节点9的时间, 2->9距离56, 则需要56s, 所以预估56s抵达节点9, 即任务二需期待56s。如果绕行经过的路径节点修改为2、45、1、8、49, 有2个转弯, 总任务时间变为156s, 比之前计划多了66s。相较于绕行, 期待反而快了10s, 所以这里选择了期待, 生成路径如图4所示, 这样的计划制止了两个机械人事情途中碰撞的可能性。

从实验结果可直观的看到最短路径, 多个任务时会制止碰撞或者拥堵。

图2 任务一路径   

图3 任务二路径   

图4 任务一、二同时执行时路径  

5 结语

本文实现了对订单路径计划的计划制定, 计划了整个流程, 并模拟完成了历程中最短路径的获取及机械人之间的避障。可是对路径计划算法的优化还不敷完善, 另有其他约束条件以及可能爆发碰撞的情况没有考虑完全, 后期还需考虑, 以抵达越发高效、实时、准确的实现路径计划及避障。并且本文实现的仅仅是路径方面的优化避障, 并未涉及机械人设计, 后期会涉及到机械人主芯片的设计, 开端考虑使用Android系统的嵌入式电路板实现机械人与效劳器信息交流。至于机械人取货等行为有待进一步开发设计。

相信随着电商行业的不绝生长, 电商货仓事情量会越来越大, 如何简化事情流程, 节约事情时间愈加酿成一个重点问题, 未来机械人的使用也会越来越普及。