一种面向移动机器人多站访问的订单与货架协同调度方法与流程
本发明涉及智能物流与机器人仓储调度,特别涉及一种面向移动机器人多站访问的订单与货架协同调度方法。
背景技术:
1、机器人移动履约仓库通常采用“货到人”拣选方式,由移动机器人将存放待拣物品的货架从仓储区搬运至拣选站。订单在拣选站开启后占用订单槽位,所需物品拣选完毕后释放对应槽位。随着订单数量和拣选站数量增加,订单、货架及拣选站之间的关联关系显著增强。
2、现有调度方式通常先将订单分配至各拣选站,再分别确定各站的货架访问顺序。该分步处理方式不易同时利用订单批内部、相邻订单批之间及不同拣选站之间的共享货架关系,可能使同一货架在完成一个拣选站的服务后返回仓储区,随后又被送往另一拣选站,造成重复回库和额外往返。
3、不同拣选站还可能在相同时间请求同一货架。若仅独立生成各站日程,所得结果可能违反同一货架在同一时刻只能位于一个拣选站的约束。简单延迟其中一个拣选站虽然能够消除冲突,却可能破坏原有订单处理顺序并增加站点空闲时间。
4、因此,需要一种订单与货架协同调度方法,在满足订单槽位容量、订单需求覆盖和单货架单站占用约束的条件下,利用共享货架组织订单批和货架序列,并将跨站共享货架的并发请求转换为顺序服务和直接转运,从而减少货架往返仓储区的次数。
技术实现思路
1、本发明的目的是克服现有技术存在的不足,为实现以上目的,采用一种面向移动机器人多站访问的订单与货架协同调度方法,以解决上述背景技术中提出的问题。
2、本发明提供一种面向移动机器人多站访问的订单与货架协同调度方法,用于包括仓储区、多个货架、多个移动机器人和多个拣选站的机器人移动履约系统,包括:
3、获取订单、货架、物品、拣选站数量p、订单槽位容量c、最大等待时隙w和等待货架数量上限b;
4、在订单槽位容量约束下,根据订单之间的货架共享关系生成订单批,并为各订单批确定覆盖其全部物品需求的批次货架集合;
5、以订单批为节点,在批次货架集合存在交集时建立边,得到共享货架图,将所述共享货架图划分为连通分量,按照批次货架集合之间的jaccard距离确定各连通分量内的订单批顺序,连接成全局订单批序列;
6、建立以拣选站为列、以处理层为行的二维网格,将所述全局订单批序列按照相邻列填入方向相反的蛇形方式映射至所述二维网格,得到各拣选站对应的订单批序列;
7、根据各拣选站对应的订单批序列确定货架访问序列,并基于所述货架访问序列生成初始调度日程;在最大等待时隙w和等待货架数量上限b的约束下,检测并消解同一时隙内多个拣选站请求同一货架产生的并发冲突,建立冲突货架的等待和跨站转运关系;
8、输出各拣选站的订单批序列、货架访问序列、货架等待安排和货架跨站转运关系。
9、作为本发明的进一步的方案:在生成订单批之前,对订单、物品和货架数据迭代执行预处理;以i(o)表示订单o所需的物品集合,以i(r)表示货架r存放的物品集合,以r(i)表示存放物品i的货架集合,所述预处理包括:
10、删除不存放任一待拣选订单所需物品的货架,并删除保留货架中不被任一待拣选订单需求的物品记录;
11、当第二货架的物品集合包含于第一货架的物品集合时,在库存能够满足订单需求的条件下保留第一货架并删除第二货架;
12、对于第一订单和第二订单,当存在非空物品集合j和包含不超过一种物品的集合k,使第一订单的物品需求为j∪k、第二订单的物品需求为j,且任何存放j中一种物品的货架均同时存放j中的全部物品时,将第一订单与第二订单合并处理;
13、对于锚订单和关联订单,当锚订单包含非空链接物品集合h及至多一种附加物品,关联订单需求非空物品集合j,h中的物品共同存放、j中的物品共同存放,且能够同时提供h中全部物品的货架集合包含于能够同时提供j中全部物品的货架集合时,将关联订单与锚订单合并处理;
14、当存放第一物品的货架集合包含于存放第二物品的货架集合,且同一订单同时需求所述第一物品和第二物品时,删除该订单对第二物品的冗余需求记录;
15、记录被合并订单及被删除需求记录与保留数据之间的恢复映射,并在输出调度结果时恢复原始订单及其物品需求。
16、作为本发明的进一步的方案:所述在订单槽位容量约束下,根据订单之间的货架共享关系生成订单批,并为各订单批确定覆盖其全部物品需求的批次货架集合,包括:
17、生成满足订单唯一分批条件和批内同时开启订单数量不超过订单槽位容量c的候选分批结果;
18、针对各候选分批结果,确定覆盖各订单批全部物品需求且不包含与批内订单需求无关货架的批次货架集合;
19、按照分配至全部订单批的货架数量之和由小至大筛选所述候选分批结果,确定订单分批结果及对应的批次货架集合。
20、作为本发明的进一步的方案:所述按照批次货架集合之间的jaccard距离确定各连通分量内的订单批顺序,包括:
21、订单批i与订单批j之间的jaccard距离为:
22、
23、其中,r(i)和r(j)分别表示订单批i和订单批j的批次货架集合;按照使相邻订单批之间的jaccard距离之和比较大小的方式,确定各连通分量内的订单批顺序。
24、作为本发明的进一步的方案:所述全局订单批序列按照相邻列填入方向相反的蛇形方式映射至所述二维网格,包括:
25、当订单批总数为k、拣选站数量为p时,将二维网格的行数设置为l=[k/p];
26、按照第一列自下而上、第二列自上而下且后续各列依次交替的方式,将全局订单批序列填入二维网格;
27、各拣选站按照其所在列的非空单元格自下而上的顺序取得对应的订单批序列。
28、作为本发明的进一步的方案:所述根据各拣选站对应的订单批序列确定货架访问顺序,包括:
29、针对每一拣选站,确定各订单批内的货架访问顺序;
30、当相邻订单批具有共享货架时,将一个共享货架分别设置为前一订单批的末货架和后一订单批的首货架,使所述共享货架形成一次连续访问;
31、并以不能通过共享货架连接的订单批边界为断点,将对应拣选站的货架访问序列划分为货架段。
32、作为本发明的进一步的方案:在划分货架段之后,通过调整相邻货架段的执行方向,将边界货架相同的相邻货架段合并,包括:
33、依次对同一拣选站的两个相邻货架段检验反转前一货架段、反转后一货架段以及同时反转两个货架段三种方向组合;
34、当任一方向组合使前一货架段的末货架与后一货架段的首货架相同时,采用该方向组合合并两个货架段,并重新从首个货架段开始检验,直至不存在能够继续合并的相邻货架段;
35、其中,反转一个货架段时,同步反转该货架段中的订单批顺序以及各订单批内的货架访问顺序。
36、作为本发明的进一步的方案:在完成同一拣选站内的货架段合并后,根据不同拣选站对共享货架的计划访问时刻调整各货架段的执行方向,以增加共享货架在不同拣选站之间连续访问的数量,包括:
37、分别计算各货架段正向执行和反向执行时各货架访问对应的计划时刻;
38、对于同时出现在另一拣选站的共享货架,当该共享货架在两个拣选站的计划访问时刻之差为正且不超过最大等待时隙w时,确定存在一次候选跨站转运;
39、选择候选跨站转运数量较多的货架段执行方向,在两个执行方向对应的候选跨站转运数量相同时保持原执行方向。
40、作为本发明的进一步的方案:所述在最大等待时隙w和等待货架数量上限b的约束下,检测并消解同一时隙内多个拣选站请求同一货架的并发冲突,建立冲突货架的等待和跨站转运关系,包括:
41、将发生并发冲突的拣选站中编号最小的拣选站确定为先服务拣选站,其余拣选站按照站点编号递增的顺序等待使用冲突货架;
42、等待期间,所述其余拣选站优先访问当前订单批内不依赖所述冲突货架的其他货架,并在不存在所述其他货架时保持等待;
43、当冲突货架在先服务拣选站释放后的等待时间不超过最大等待时隙w,且全部拣选站的等待货架总数未达到等待货架数量上限b时,记录该冲突货架的等待安排和跨站转运关系;
44、否则,记录该冲突货架返回仓储区后再次访问对应拣选站的安排。
45、作为本发明的进一步的方案:所述在订单槽位容量约束下,根据订单之间的货架共享关系生成订单批,还包括:
46、将能够由其所在订单批中一件已分配货架独立覆盖全部物品需求的订单识别为批内单货架订单;
47、当一个订单批包含至少一个所述批内单货架订单时,为该订单批预留一个订单槽位,将同时开启的非单货架订单数量限制为c-1,并在对应货架访问拣选站时,利用预留的订单槽位依次开启和完成一个或多个批内单货架订单;
48、当订单批不包含所述批内单货架订单时,不预留订单槽位,并允许同时开启不超过c个订单。
49、与现有技术相比,本发明存在以下技术效果:
50、采用上述的技术方案,通过在订单槽位容量约束下根据订单间货架共享关系生成订单批及覆盖全部需求的批次货架集合,以批次货架集合交集构建共享货架图并划分连通分量,按jaccard距离确定各连通分量内订单批顺序并连接成全局订单批序列,再通过以拣选站为列、处理层为行的二维网格按相邻列反向填入的蛇形方式映射至各拣选站,进而确定货架访问顺序并生成调度日程,在最大等待时隙w和等待货架数量上限b约束下检测并消解同一时隙多站请求同一货架的并发冲突,建立冲突货架的等待和跨站转运关系,最终输出订单批序列、货架访问序列、等待安排和跨站转运关系;该方案使共享货架比例高的订单批在站内或站间保持相邻,增加共享货架连续访问机会,减少货架重复回库和往返次数,并通过顺序服务与跨站直接转运避免同一货架同一时隙被多站占用,从而降低机器人能耗并提高多站拣选效率。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com