2.793

2018影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于移动机器人的拣货系统研究进展

徐翔斌 马中强

徐翔斌, 马中强. 基于移动机器人的拣货系统研究进展. 自动化学报, 2020, 46(x): 1−20. doi: 10.16383/j.aas.c190728
引用本文: 徐翔斌, 马中强. 基于移动机器人的拣货系统研究进展. 自动化学报, 2020, 46(x): 1−20. doi: 10.16383/j.aas.c190728
Xu Xiang-Bin, Ma Zhong-Qiang. Robotic mobile fulfillment systems: state-of-the-art and prospects. Acta Automatica Sinica, 2020, 46(x): 1−20. doi: 10.16383/j.aas.c190728
Citation: Xu Xiang-Bin, Ma Zhong-Qiang. Robotic mobile fulfillment systems: state-of-the-art and prospects. Acta Automatica Sinica, 2020, 46(x): 1−20. doi: 10.16383/j.aas.c190728

基于移动机器人的拣货系统研究进展


DOI: 10.16383/j.aas.c190728
详细信息
    作者简介:

    华东交通大学交通运输与物流学院教授.2015年获中南大学工学博士学位, 主要研究方向为物流与供应链管理, 本文通信作者. E-mail: champagnewq@aliyun.com

    中南大学交通运输工程学院博士研究生. 主要研究方向仓库拣货优化, 智能优化算法. E-mail: mzq11302@163.com

  • 基金项目:  国家自然科学基金(71761013), 江西省自然科学基金面上项目(20181BAB201010)资助

Robotic Mobile Fulfillment Systems: State-of-the-art and Prospects

More Information
  • Fund Project:  Supported by National Natural Science Foundation of China (71761013), General Program of Natural Science Foundation of Jiangxi Province (20181BAB201010)
  • 摘要: 基于移动机器人的拣货系统(Robotic Mobile Fulfillment Systems, RMFS)作为一种新型物至人的拣货系统, 相比人工拣货系统和AS/RS拣货系统(下文统称传统拣货系统)具有更高的拣货效率、更好的系统可扩展性和柔性. 为全面了解RMFS的运行模式及其优化方向, 本文首先回顾了RMFS的工作流程及优化理论框架, 然后对RMFS的货位指派、订单分批、任务分配、路径规划以及建模方法等问题进行了文献回顾和总结, 并指出了RMFS与传统拣货系统在拣货过程方面的异同及当前研究的不足. 最后, 讨论了RMFS的几个重要研究方向, 为RMFS的理论研究和应用实践提供参考.
  • 图  1  RMFS拣货区域布局图

    Fig.  1  RMFS picking area layout

    图  2  RMFS订单拣选作业流程

    Fig.  2  RMFS order picking process

    图  3  RMFS拣货优化流程

    Fig.  3  RMFS picking optimization process

    图  4  RMFS优化理论框架

    Fig.  4  RMFS optimization theory framework

    图  5  RMFS货位指派示意图

    Fig.  5  RMFS location assignment diagram

    图  6  RMFS订单分批示意图

    Fig.  6  RMFS order batching diagram

    图  7  RMFS的货架与机器人分配示意图

    Fig.  7  RMFS shelf and robot distribution diagram

    图  8  RMFS的路径规划示意图

    Fig.  8  RMFS path planning diagram

    图  9  RMFS绩效评估的半开放排队网络模型

    Fig.  9  Semi-open queueing network for performance estimation of RMFS

    图  10  RMFS路径规划及其图表示

    Fig.  10  RMFS path planning and its graph representation

    图  11  基于强化学习的RMFS优化框架

    Fig.  11  RMFS optimization framework based on Reinforcement Learning

    图  12  基于Agent的RMFS多机器人运作结构

    Fig.  12  Agent-based multi-robot operation structure of RMFS

    表  1  RMFS研究文献汇总

    Table  1  Summary of literature on RMFS

    问题分类 作者 研究问题 解决方法
    货位指派 Nigam et al.[4](2014) 货架储位指派问题 多类封闭排队网络
    Lamballais et al.[3](2017) 仓库布局、商品储位指派、补货作业优化问题 半开放排队网络
    Onal et al.[15](2017) 商品储位指派问题 爆炸存储策略、仿真方法
    Krenzler et al.[16](2018) 货架储位再指派问题 确定性模型、组合优化算法
    Yuan et al.[17](2018) 货架储位指派问题 流体模型、基于策略的存储方法
    Weidinger et al.[18](2018) 货架储位动态指派 混合整数规划模型、自适应规划方法
    Yuan et al.[19](2018) 货位指派问题 分区存储策略、仿真方法
    Xiang et al.[20](2018) 商品储位指派问题与订单分批协同优化 混合整数规划模型、可变邻域搜索方法、自适应算法
    蔺一帅等[21](2020) 商品储位指派与路径规划协同优化 改进的协同优化遗传算法
    徐翔斌等[22](2020) 货架储位动态指派 改进的模拟退火算法
    订单分批 吴颖颖等[23](2016) 订单排序问题 订单排序优化模型、k-means聚类算法
    Boysen et al.[24](2017) 订单分批与订单排序以及货架在拣货站台排序的综合优化 混合整数规划模型、Cplex以及仿真方法
    Xiang et al.[20](2018) 商品储位指派问题与订单分批协同优化 混合整数规划模型、可变邻域搜索方法、自适应算法
    任务分配及调度 Zhou et al.[11](2014) 多机器人任务分配问题 平衡启发式机制与仿真
    Dou et al.[25](2015) 任务调度和路径规划协同优化 遗传算法、强化学习
    徐贤浩等[26](2016) 搬运机器人待命泊位策略问题 统计建模方法、基于策略的方法
    Yuan et al.[27](2017) 搬运机器人共享分配问题 共享协议策略、排队网络
    Zou et al.[28](2017) RMFS分配规则问题 半开放排队网络、基于规则的方法、邻域搜索方法
    Merschformann et al.[12] (2017) RMFS作业调度决策问题 基于行走策略的研究方法
    Merschformann et al.[29](2018) RMFS作业调度决策问题 基于策略的存储和仿真方法
    Ghassemi et al.[30](2018) 多机器人任务分配问题 基于二部图匹配和模糊聚类的分散多主体任务分配算法、仿真
    Zou et al.[31](2018) 评估机器人充电与更换电池策略的优劣 半开放排队网络、Arena仿真
    袁瑞萍等[32](2018) 拣货过程任务调度 共同进化遗传算法
    Roy et al.[33](2019) RMFS系统绩效评估、机器人分配策略 封闭排队网络、两阶段随机模型、Arena仿真
    Yoshitake et al.[34](2019) 机器人调度 实时全息调度方法
    Zhang et al.[35](2019) RMFS多机器人分配问题 改进的遗传算法
    路径规划 沈博闻等[8](2014) 多机器人路径规划问题 改进的A*算法
    Dou et al.[25](2015) 任务调度和路径规划协同优化 遗传算法、强化学习
    Kumar et al.[36](2018) RMFS路径规划问题 无冲突路径规划算法
    Zheng et al.[37](2018) 多机器人无冲突路径规划 改进的Dijkstra算法、避碰规则
    张丹霞等[38](2018) 多机器人协同路径规划 改进的A*算法、动态加权图
    夏清松等[39](2019) 路径规划与作业避障协同研究 蚁群算法、避障规则设计
    Lee et al.[40](2019) 多机器人无冲突路径规划 网络物理系统模型、改进的A*算法以及避碰规则
    于赫年等[41](2020) 多机器人路径规划问题 自调优A*算法、主动避障规则
    蔺一帅等[21](2020) 商品储位指派与路径规划协同优化 改进的协同优化遗传算法
    RMFS系统设计、
    评估及其它问题研究
    Gue et al.[42](2014) RMFS机器人系统控制与评估 面向对象建模与仿真
    Yuan et al.[43](2016) 评估RMFS的性能, 主要关注机器人数量、速度优化 开放排队网络模型
    Lee et al.[44](2018) 变形RMFS的拣货流程优化 混合整数规划模型、Gurobi
    Bozer et al.[45](2018) RMFS系统与miniload系统对比 仿真方法
    Wang et al.[46](2019) 机器人搬运货架的运行周期问题 旅行时间模型
    Zhang et al.[47](2019) RMFS快递分拣仓库布局自动化设计 机器学习与进化计算组合的方法
    Petković et al.[48](2019) RMFS工作人员的意图评估 隐马尔科夫模型和心理理论
    Wang et al.[49](2020) RMFS系统设计框架研究 基于瓶颈的模型和开放排队网络模型
    下载: 导出CSV
  • [1] Koster R D, Le-Duc T, Roodbergen K J. Design and control of warehouse order picking: a literature review. European Journal of Operational Research, 2007, 182(2): 481−501 doi:  10.1016/j.ejor.2006.07.009
    [2] Guizzo E. Three engineers, hundreds of robots, one warehouse. IEEE Spectrum, 2008, 45(7): 26−34 doi:  10.1109/MSPEC.2008.4547508
    [3] Lamballais T, Roy D, Koster M B M D. Estimating performance in a robotic mobile fulfillment system. European Journal of Operational Research, 2017, 256(3): 976−990 doi:  10.1016/j.ejor.2016.06.063
    [4] Nigam S, Roy D, Koster R D, Adan I. "Analysis of Class-based Storage Strategies for the Mobile Shelf-based Order Pick System". Cincinnati, Ohio, USA: 13th IMHRC Proceedings, 2014. 19.
    [5] D'andrea R. Guest editorial: a revolution in the warehouse-a retrospective on kiva systems and the grand challenges ahead. IEEE Transactions on Automation Science & Engineering, 2012, 9(4): 638−639
    [6] Wurman P R, Mountz M, Mountz M. Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI magazine, 2008, 29(1): 9−19
    [7] D'Andrea R, Wurman P. Future challenges of coordinating hundreds of autonomous vehicles in distribution facilities. In: Proceedings of IEEE International Conference on Technologies for Practical Robot Applications. Woburn, MA, USA: IEEE, 2008. 80−83.
    [8] 沈博闻, 于宁波, 刘景泰. 仓储物流机器人集群的智能调度和路径规划. 智能系统学报, 2014, 9(6): 659−664

    SHEN Bo-Wen, YU Ning-Bo, LIU Jing-Tai. Intelligent scheduling and path planning of warehouse mobile robots. CAAI Transactions on Intelligent Systems, 2014, 9(6): 659−664
    [9] Flipse M. Altering and improving kiva some suggestions for improvement of the current kiva system. Articial Intelligence Department, 2011, 26(12): 45−61
    [10] Zhang J, Wang X P, Chan F T S, Ruan J H. On-line order batching and sequencing problem with multiple pickers: A hybrid rule-based algorithm. Applied Mathematical Modelling, 2017, 45: 271−284 doi:  10.1016/j.apm.2016.12.012
    [11] Zhou L W, Shi Y Y, Wang J L, Yang P. A balanced heuristic mechanism for multirobot task allocation of intelligent warehouses[Online], available: http://downloads.hindawi.com/journals/mpe/2014/380480.pdf, August 31, 2020.
    [12] Merschformann M, Lin X, Erdmann D. Path planning for Robotic Mobile Fulfillment Systems [Online], available: https://arxiv.org/abs/1706.09347.pdf, June 28, 2017.
    [13] 徐翔斌, 李秀. 自组织物流研究综述及前景展望. 包装工程, 2017, 38(11): 111−116

    XU Xiang-Bin, LI Xiu. Research overview and prospects of self-organizing logistics. Packaging Engineering, 2017, 38(11): 111−116
    [14] Roodbergen K J, Vis I F A. A survey of literature on automated storage and retrieval systems. European Journal of Operational Research, 2009, 194(2): 343−362 doi:  10.1016/j.ejor.2008.01.038
    [15] Onal S, Zhang J, Das S. Modelling and performance evaluation of explosive storage policies in internet fulfilment warehouses. International Journal of Production Research, 2017, 55(20): 5902−5915 doi:  10.1080/00207543.2017.1304663
    [16] Krenzler R, Xie L, Li H. Deterministic pod repositioning problem in robotic mobile fulfillment systems [Online], available: https://arxiv.org/pdf/1810.05514.pdf, October 9, 2018.
    [17] Yuan R, Graves S C, Cezik T. Velocity-based storage assignment in semi-automated storage systems. Production and Operations Management, 2019, 28(2): 354−373 doi:  10.1111/poms.12925
    [18] Weidinger F, Boysen N, Briskorn D. Storage assignment with rack-moving mobile robots in kiva warehouses. Transportation Science, 2018, 52(6): 1479−1495 doi:  10.1287/trsc.2018.0826
    [19] Yuan R, Cezik T, Graves S C. Stowage decisions in multi-zone storage systems. International Journal of Production Research, 2018, 56(1-2): 333−343 doi:  10.1080/00207543.2017.1398428
    [20] Xiang X, Liu C C, Miao L X. Storage assignment and order batching problem in kiva mobile fulfilment system. Engineering Optimization, 2018, 50(11): 1941−1962 doi:  10.1080/0305215X.2017.1419346
    [21] 蔺一帅, 李青山, 陆鹏浩, 孙雨楠, 王亮, 王颖芝. 智能仓储货位规划与AGV路径规划协同优化算法. 软件学报, 录用待出版.

    LIN Yi-Shuai, LI Qing-Shan, LU Peng-Hao, SUN Yu-Nan, WANG Liang, WANG Ying-Zhi. Shelf and AGV path coopeartive optimization algorithm used in intelligent warehousing. Journal of Software, to be published.
    [22] 徐翔斌, 马中强. RMFS订单拣选系统动态货位再指派研究. 计算机集成制造系统, 录用待出版.

    XU Xiang-Bin, MA Zhong-Qiang. Research on Dynamic Location Reassignment of RMFS Order Picking System. Computer Integrated Manufacturing System, to be published.
    [23] 吴颖颖, 孟祥旭, 王艳艳, 胡金昌. “货到人”拣选系统订单排序优化. 机械工程学报, 2016, 52(4): 206−212 doi:  10.3901/JME.2016.04.206

    WU Ying-Ying, MENG Xiang-Xu, WANG Yan-Yan, HU Jin-Chang. Order sequence optimization for “part-to-picker” order picking system. Journal of Mechanical Engineering, 2016, 52(4): 206−212 doi:  10.3901/JME.2016.04.206
    [24] Boysen N, Briskorn D, Emde S. Parts-to-picker based order processing in a rack-moving mobile robots environment. European Journal of Operational Research, 2017, 262(2): 550−562 doi:  10.1016/j.ejor.2017.03.053
    [25] Dou J, Chen C L, Yang P. Genetic Scheduling and Reinforcement Learning in Multirobot Systems for Intelligent Warehouses[Online], available: http://downloads.hindawi.com/journals/mpe/2015/597956.pdf, August 31, 2020.
    [26] 徐贤浩, 郭依, 邹碧攀. 基于最短取货时间的仓储机器人待命位策略研究. 工业工程与管理, 2016, 21(4): 35−42 doi:  10.3969/j.issn.1007-5429.2016.04.006

    XU Xiang-Hao, Guo Yi, ZOU Bi-Pan. Research on the dwell point policy for the warehouse robot based on minimum expected travel time. Industrial Engineering and Management, 2016, 21(4): 35−42 doi:  10.3969/j.issn.1007-5429.2016.04.006
    [27] Yuan Z, Gong Y Y. Bot-in-time delivery for robotic mobile fulfillment systems. IEEE Transactions on Engineering Management, 2017, 64(1): 83−93 doi:  10.1109/TEM.2016.2634540
    [28] Zou B P, Gong Y M, Xu X H, Zhe Y. Assignment rules in robotic mobile fulfilment systems for online retailers. International Journal of Production Research, 2017, 55(20): 6175−6192 doi:  10.1080/00207543.2017.1331050
    [29] Merschformann M, Lamballais T, De Koster R, Suhl L. Decision Rules for Robotic Mobile Fulfillment Systems [Online], available: https://arxiv.org/abs/1801.06703.pdf, January 20, 2018.
    [30] Ghassemi P, Chowdhury S. Decentralized task allocation in multi-robot systems via bipartite graph matching augmented with fuzzy clustering. In: Proceedings of the ASME 2018 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. Quebec City, Quebec, Canada: American Society of Mechanical Engineers Digital Collection, 2018. V02AT03A014–V02AT03A014.
    [31] Zou B P, Xu X H, Gong Y M, Koster R D. Evaluating battery charging and swapping strategies in a robotic mobile fulfillment system. European Journal of Operational Research, 2018, 267(2): 733−753 doi:  10.1016/j.ejor.2017.12.008
    [32] 袁瑞萍, 王慧玲, 孙利瑞, 李俊韬. 基于物流AGV的“货到人”订单拣选系统任务调度研究. 运筹与管理, 2018, 27(10): 133−138

    YUAN Rui-Ping, WANG Hui-Ling, SUN Li-Rui, LI Jun-Tao. Research on the task scheduling of “goods to picker”order picking system based on logistics AGV. Operations Research and Management Science, 2018, 27(10): 133−138
    [33] Roy D, Nigam S, De Koster R, Adan I, Resing J. Robot-storage zone assignment strategies in mobile fulfillment systems. Transportation Research Part E: Logistics and Transportation Review, 2019, 122: 119−142 doi:  10.1016/j.tre.2018.11.005
    [34] Yoshitake H, Kamoshida R, Nagashima Y. New automated guided vehicle system using real-time holonic scheduling for warehouse picking. IEEE Robotics and Automation Letters, 2019, 4(2): 1045−1052 doi:  10.1109/LRA.2019.2894001
    [35] Zhang J T, Yang F X, Weng X. A building-block-based genetic algorithm for solving the robots allocation problem in a robotic mobile fulfilment system[Online], available: http://downloads.hindawi.com/journals/mpe/2019/6153848.pdf, August 31, 2020.
    [36] Kumar N V, Kumar C S. Development of collision free path planning algorithm for warehouse mobile robot. Procedia computer science, 2018, 133: 456−463 doi:  10.1016/j.procs.2018.07.056
    [37] Zheng Z, Guo Q, Chen J, Yuan P J. Collision-free route planning for multiple AGVs in automated warehouse based on collision classification. IEEE Access, 2018, 6: 26022−26035 doi:  10.1109/ACCESS.2018.2819199
    [38] 张丹露, 孙小勇, 傅顺, 郑彬. 智能仓库中的多机器人协同路径规划方法. 计算机集成制造系统, 2018, 24(2): 410−418

    ZHANG Dan-Lu, SUN Xiao-Yong, FU Shun, ZHENG Bin. Cooperative path planning in multi-robots for intelligent warehouse. Computer Integrated Manufacturing System, 2018, 24(2): 410−418
    [39] 夏清松, 唐秋华, 张利平. 多仓储机器人协同路径规划与作业避碰. 信息与控制, 2019, 48(1): 22−28, 34

    XIA Qing-Song, TANG Qiu-Hua, ZHANG Li-Ping. Cooperative path planning and operation collision avoidance for multiple storage robots. Information and control, 2019, 48(1): 22−28, 34
    [40] Lee C K M, Lin B B, Ng K K H, Lv T Q, Tai W C. Smart robotic mobile fulfillment system with dynamic conflict-free strategies considering cyber-physical integration. Advanced Engineering Informatics, 2019, 42: 100998 doi:  10.1016/j.aei.2019.100998
    [41] 于赫年, 白桦, 李超. 仓储式多AGV系统的路径规划研究及仿真. 计算机工程与应用, 2020, 56(2): 233−241 doi:  10.3778/j.issn.1002-8331.1904-0178

    YU He-Nian, BAI Hua, LI Chao. Research and simulation on path planning of warehouse multi-AGV system. Computer Engineering and Applications, 2020, 56(2): 233−241 doi:  10.3778/j.issn.1002-8331.1904-0178
    [42] Gue K R, Furmans K, Seibold Z, Onur U. Gridstore a puzzle-based storage system with decentralized control. IEEE Transactions on Automation Science and Engineering, 2014, 11(2): 429−438 doi:  10.1109/TASE.2013.2278252
    [43] Yuan Z, Gong Y. Improving the speed delivery for robotic warehouses*. Ifac Papersonline, 2016, 49(12): 1164−1168 doi:  10.1016/j.ifacol.2016.07.661
    [44] Lee H Y, Murray C C. Robotics in order picking: evaluating warehouse layouts for pick, place, and transport vehicle routing systems. International Journal of Production Research, 2018: 1−21
    [45] Bozer Y A, Aldarondo F J. A simulation-based comparison of two goods-to-person order picking systems in an online retail setting. International Journal of Production Research, 2018, 56(11): 3838−3858 doi:  10.1080/00207543.2018.1424364
    [46] Wang K, Yang Y M, Li R X. Travel time models for the rack-moving mobile robot system. International Journal of Production Research, 2019: 1−19
    [47] Zhang H F, Guo Z L, Zhang W N, Cai H, Wang C, Yu Y, et al. Layout design for intelligent warehouse by evolution with fitness approximation. IEEE Access, 2019, 7: 166310−166317 doi:  10.1109/ACCESS.2019.2953486
    [48] Petković T, Puljiz D, Marković I, Hein B. Human intention estimation based on hidden markov model motion validation for safe flexible robotized warehouses. Robotics and Computer-Integrated Manufacturing, 2019, 57: 182−196 doi:  10.1016/j.rcim.2018.11.004
    [49] Wang W, Wu Y H, Zheng J, Chi C. A comprehensive framework for the design of modular robotic mobile fulfillment systems. IEEE Access, 2020, 8: 13259−13269 doi:  10.1109/ACCESS.2020.2966403
    [50] Öncan T. A survey of the generalized assignment problem and its applications. INFOR: Information Systems and Operational Research, 2007, 45(3): 123−141 doi:  10.3138/infor.45.3.123
    [51] 徐翔斌, 李秀. 固定路径下多阶段货位调整研究. 工业工程与管理, 2017, 22(5): 24−31

    XU Xiang-Bin, LI Xiu. Research overview and prospects of self-organizing logistics. Industrial Engineering and Management, 2017, 22(5): 24−31
    [52] Roodbergen K J, Koster R D. Routing order pickers in a warehouse with a middle aisle. European Journal of Operational Research, 2001, 133(1): 32−43 doi:  10.1016/S0377-2217(00)00177-6
    [53] Hausman W H, Schwarz L B, Graves S C. Optimal storage assignment in automatic warehousing systems. Management Science, 1976, 22(6): 629−638 doi:  10.1287/mnsc.22.6.629
    [54] Manzini R. Correlated storage assignment in an order picking system. International Journal of Industrial Engineering Theory Applications & Practice, 2006, 13(4): 384−394
    [55] 李英德. 波次分区拣货时装箱与货位指派问题协同优化的模型与算法. 系统工程理论与实践, 2013, 33(5): 1269−1276 doi:  10.3969/j.issn.1000-6788.2013.05.023

    LI Ying-De. Model and algorithm for cartonization and slotting optimization simultaneously in wave-picking zonebased system. Systems Engineering - Theory & Practice, 2013, 33(5): 1269−1276 doi:  10.3969/j.issn.1000-6788.2013.05.023
    [56] Petersen C G, Schmenner R W. An evaluation of routing and volume-based storage policies in an order picking operation. Decision Sciences, 1999, 30(2): 481−501 doi:  10.1111/j.1540-5915.1999.tb01619.x
    [57] Caron F, Marchet G, Perego A. Routing policies and COI-based storage policies in picker-to-part systems. International Journal of Production Research, 1998, 36(3): 713−732 doi:  10.1080/002075498193651
    [58] 李建斌, 杨光耀, 陈峰. 零售业电子商务仓储中心货位指派问题研究. 工业工程与管理, 2013, 18(4): 102−108 doi:  10.3969/j.issn.1007-5429.2013.04.016

    LI Jian-Bin, YANG Guang-Yao, CHEN Feng. Retail warehouse center storage location assignment research for ecommerce. Industrial Engineering and Management, 2013, 18(4): 102−108 doi:  10.3969/j.issn.1007-5429.2013.04.016
    [59] Wutthisirisart P, Noble J S, Chang C A. A two-phased heuristic for relation-based item location. Computers & Industrial Engineering, 2015, 82: 94−102
    [60] Li J X, Moghaddam M, Nof S Y. Dynamic storage assignment with product affinity and ABC classification—a case study. International Journal of Advanced Manufacturing Technology, 2016, 84(9-12): 1−16
    [61] 李英德, 鲁建厦, 潘国强. 穿越策略下考虑相关性的货位优化方法. 浙江大学学报(工学版), 2012, 46(8): 1424−1430 doi:  10.3785/j.issn.1008-973X.2012.08.011

    LI Ying-De, LU Jian-Sha, PAN Guo-Qiang. Slotting optimization based on SKUs correlations with serpentine routing policy. Journal of Zhejiang University (Engineering Science), 2012, 46(8): 1424−1430 doi:  10.3785/j.issn.1008-973X.2012.08.011
    [62] Ho S. Intentional Fragmentation for Material Storage[Ph. D. dissertation], Boston: Massachusetts Institute of Technology, 2004.
    [63] Grosse E H, Glock C H, Neumann W P. Human factors in order picking: a content analysis of the literature. International Journal of Production Research, 2017, 55(5): 1260−1276 doi:  10.1080/00207543.2016.1186296
    [64] Cai J W, Kuang X A, Song S H, Zhao Q L. Automated warehouse storage assignment policy based on storage frequency and workload balance. In: Proceedings of 2016 International Conference on Logistics, Informatics and Service Sciences (LISS). Sydney, NSW: IEEE, 2017. 1−6.
    [65] Matusiak M, Koster R D, Saarinen J. Utilizing individual picker skills to improve order batching in a warehouse. European Journal of Operational Research, 2017, 263(3): 888−899 doi:  10.1016/j.ejor.2017.05.002
    [66] Pan J C H, Shih P H, Wu M H. Storage assignment problem with travel distance and blocking considerations for a picker-to-part order picking system. Computers & Industrial Engineering, 2012, 62(2): 527−535
    [67] Bodnar P, Lysgaard J. A dynamic programming algorithm for the space allocation and aisle positioning problem. Journal of the Operational Research Society, 2014, 65(9): 1315−1324 doi:  10.1057/jors.2013.64
    [68] Yang P, Miao L X, Xue Z J, Ye B. Variable neighborhood search heuristic for storage location assignment and storage/retrieval scheduling under shared storage in multi-shuttle automated storage/retrieval systems. Transportation Research Part E: Logistics and Transportation Review, 2015, 79: 164−177 doi:  10.1016/j.tre.2015.04.009
    [69] Pang K W, Chan H L. Data mining-based algorithm for storage location assignment in a randomised warehouse. International Journal of Production Research, 2017, 55(14): 4035−4052 doi:  10.1080/00207543.2016.1244615
    [70] 冯乾, 乐美龙, 赵毅. 物料聚类分析下的仓库货位指派优化. 辽宁工程技术大学学报, 2015, 34(10): 1207−1212

    FENG Qian, LE Mei-Long, ZHAO Yi. Optimization of storage location assignment based on materials clustering analysis. Journal of LNTU. Natural Science, 2015, 34(10): 1207−1212
    [71] Weidinger F, Boysen N. Scattered storage: how to distribute stock keeping units all around a mixed-shelves warehouse. Transportation Science, 2018, 52(6): 1412−1427 doi:  10.1287/trsc.2017.0779
    [72] Gademann N, Velde S. Order batching to minimize total travel time in a parallel-aisle warehouse. IIE Transactions, 2005, 37(1): 63−75 doi:  10.1080/07408170590516917
    [73] Ackerman K B. Practical Handbook of Warehousing. New York: Springer US, 1990.
    [74] 王旭坪, 张珺, 马骏. 考虑完成期限的电子商务在线订单分批模型及算法. 管理科学, 2014, 27(6): 103−113 doi:  10.3969/j.issn.1672-0334.2014.06.009

    Wang Xu-Ping, Zhang Jun, Ma Jun. E-commerce on-line order batching model and algorithm: considering due time. Journal of Management Science, 2014, 27(6): 103−113 doi:  10.3969/j.issn.1672-0334.2014.06.009
    [75] Gademann N, Velde V D S. Order batching to minimize total travel time in a parallel-aisle warehouse. IIE Transactions, 2005, 37(1): 63−75 doi:  10.1080/07408170590516917
    [76] Menéndez B, Pardo E G, Alonso-Ayuso A, Molina E, Duarte A. Variable neighborhood search strategies for the order batching problem. Computers & Operations Research, 2017, 78: 500−512
    [77] Scholz A, Wäscher G. Order batching and picker routing in manual order picking systems: the benefits of integrated routing. Central European Journal of Operations Research, 2017, 25(2): 491−520 doi:  10.1007/s10100-017-0467-x
    [78] Chen M C, Wu H P. An association-based clustering approach to order batching considering customer demand patterns. Omega, 2005, 33(4): 333−343 doi:  10.1016/j.omega.2004.05.003
    [79] 李诗珍, 杜文宏. 基于聚类分析的订单分批拣货模型及启发式算法. 统计与决策, 2008, (12): 53−56

    LI Shi-Zhen, DU Wen-Hong. Order batch picking model and heuristic algorithm based on cluster analysis. Statistics & Decision, 2008, (12): 53−56
    [80] Henn S W G. Tabu search heuristics for the order batching problem in manual order picking systems. European Journal of Operational Research, 2012, 222(3): 484−494 doi:  10.1016/j.ejor.2012.05.049
    [81] 马士华, 文坚. 基于时间延迟的订单分批策略研究. 工业工程与管理, 2004, 9(6): 92−95

    Ma Shi-Hua, Wen Jian. The order batching strategies based on time postponement. Industrial Engineering and Management, 2004, 9(6): 92−95
    [82] Zhang J, Wang X P, Huang K. Integrated on-line scheduling of order batching and delivery under B2C e-commerce. Computers & Industrial Engineering, 2016, 94: 280−289
    [83] Hong S, Johnson A L, Peters B A. Batch picking in narrow-aisle order picking systems with consideration for picker blocking. European Journal of Operational Research, 2012, 221(3): 557−570 doi:  10.1016/j.ejor.2012.03.045
    [84] Tsai C Y, Liou J J H, Huang T M. Using a multiple-GA method to solve the batch picking problem: considering travel distance and order due time. International Journal of Production Research, 2008, 46(22): 6533−6555 doi:  10.1080/00207540701441947
    [85] Scholz A, Schubert D, Wäscher G. Order picking with multiple pickers and due dates–simultaneous solution of order batching, batch assignment and sequencing, and picker routing problems. European Journal of Operational Research, 2017, 263(2): 461−478 doi:  10.1016/j.ejor.2017.04.038
    [86] Yu M, Koster R B M D. The impact of order batching and picking area zoning on order picking system performance. European Journal of Operational Research, 2009, 198(2): 480−490 doi:  10.1016/j.ejor.2008.09.011
    [87] Hur S, Lee Y H, Lim S Y, Lee M H. A performance estimation model for AS/RS by M/G/1 queuing system. Computers & Industrial Engineering, 2004, 46(2): 233−241
    [88] 王艳艳, 周以齐, 沈长鹏, 吴耀华. 一种两类“货到人”订单拣选系统的适用性选择方法. 机械工程学报, 2015, 51(4): 206−212 doi:  10.3901/JME.2015.04.206

    WANG Yan-Yan, ZHOU Yi-Qi, SHEN Chang-Peng, WU Yao-Hua. Applicability selection method of two parts-to-picker order picking systems. Journal of Mechanical Engineering, 2015, 51(4): 206−212 doi:  10.3901/JME.2015.04.206
    [89] Araidah O A, Dalalah D, Azeez M A A, Khasawneh M T. A heuristic for clustering and picking small items considering safe reach of the order picker. European Journal of Industrial Engineering, 2017, 11(2): 256−269 doi:  10.1504/EJIE.2017.083256
    [90] Khamis A, Hussein A, Elmogy A. Multi-robot task allocation: a review of the state-of-the-art, Cooperative Robots and Sensor Networks 2015. Cham, Switzerland: Springer-Verlag, 2015. 31−51.
    [91] 张嵛, 刘淑华. 多机器人任务分配的研究与进展. 智能系统学报, 2008, 3(2): 115−120

    ZHANG Yu, LIU Shu-Hua. Survey of multi robot task allocation. CAAI Transactions on Intelligent Systems, 2008, 3(2): 115−120
    [92] Ross G T, Zoltners A A. Weighted assignment models and their application. Management Science, 1979, 25(7): 683−696 doi:  10.1287/mnsc.25.7.683
    [93] 施展, 陈庆伟. 基于改进的多目标量子行为粒子群优化算法的多无人机协同任务分配. 南京理工大学学报(自然科学版), 2012, 36(6): 945−951

    SHI Zhan, CHEN Qing-Wei. Cooperative task allocation for multiple uavs based on improved multi objective quantum behaved particle swarm optimization algorithm. Journal of Nanjing University of Science and Technology, 2012, 36(6): 945−951
    [94] 孙博寒, 王浩, 方宝富, 凌兆龙, 林杰华. 基于自组织算法的情感机器人追捕任务分配. 机器人, 2017, 39(5): 680−687

    SUN Bo-Han, WANG Hao, FANG Bao-Fu, LING Zhao-Long, LIN Jie-Hua. Task allocation in emotional robot pursuit based on self-organizing algorithm. Robot, 2017, 39(5): 680−687
    [95] Fang B F, Chen L, Wang H, Dai S L, Zhong Q B. Research on multirobot pursuit task allocation algorithm based on emotional cooperation factor. The Scientific World Journal, 2014, 2014(4): 864−180
    [96] 柳林, 季秀才, 郑志强. 基于市场法及能力分类的多机器人任务分配方法. 机器人, 2006, 28(3): 337−343 doi:  10.3321/j.issn:1002-0446.2006.03.019

    LIU Lin, JI Xiu-Cai, ZHENG Zhi-Qiang. Multi-robot task allocation based on market and capability classification. Robot, 2006, 28(3): 337−343 doi:  10.3321/j.issn:1002-0446.2006.03.019
    [97] Irfan M, Farooq A. Auction-based task allocation scheme for dynamic coalition formations in limited robotic swarms with heterogeneous capabilities. In: Proceedings of 2016 International Conference on Intelligent Systems Engineering (ICISE). Islamabad, Pakistan: IEEE, 2016. 210−215.
    [98] 刘淑华, 张嵛, 吴洪岩, 刘杰. 基于群体智能的多机器人任务分配. 吉林大学学报(工学版), 2010, 40(1): 123−129

    LIU Shu-Hua, ZHANG Yu, WU Hong-Yan, LIU Jie. Multi-robot task allocation based on swarm intelligence. Journal of Jinlin University Enginnering and Technology Edition, 2010, 40(1): 123−129
    [99] Gong J W, Qi J Y, Xiong G M, Chen H Y, Huang W N. A GA Based Combinatorial Auction Algorithm for Multi-robot Cooperative Hunting. In: Proceedings of 2007 International Conference on Computational Intelligence and Security (CIS 2007), Harbin, China: IEEE, 2007. 137−141.
    [100] Janati F, Abdollahi F, Ghidary S S, Jannatifar M, Baltes J, Sadeghnejad S. Multi-robot task allocation using clustering method, Robot Intelligence Technology and Applications 4. Cham, Switzerland: Springer, 2017. 233−247.
    [101] Farinelli A, Iocchi L, Nardi D. Distributed on-line dynamic task assignment for multi-robot patrolling. Autonomous Robots, 2017, 41(6): 1−25
    [102] 陈培友, 汪定伟. 组合拍卖竞胜标确定问题的混沌搜索算法. 管理科学学报, 2003, 6(5): 24−28 doi:  10.3321/j.issn:1007-9807.2003.05.005

    CHEN Pei-You, Wang Ding-Wei. Chaotic search algorithm for winner determination in combinatorial auctions. Journal of Management Sciences in China, 2003, 6(5): 24−28 doi:  10.3321/j.issn:1007-9807.2003.05.005
    [103] Cavalcante R C, Noronha T F, Chaimowicz L. Improving combinatorial auctions for multi-robot exploration. In: Proceedings of 2013 16th International Conference on Advanced Robotics (ICAR), Montevideo, Uruguay: IEEE, 2013. 1−6.
    [104] 马磊, 张文旭, 戴朝华. 多机器人系统强化学习研究综述. 西南交通大学学报, 2014, 49(06): 1032−1044 doi:  10.3969/j.issn.0258-2724.2014.06.015

    MA Lei, ZHANG Wen-Xu, DAI Chao-Hua. A review of developments in reinforcement learning for multi-robot systems. Journal of Southwest JiaoTong University, 2014, 49(06): 1032−1044 doi:  10.3969/j.issn.0258-2724.2014.06.015
    [105] Bektas T. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 2006, 34(3): 209−219 doi:  10.1016/j.omega.2004.10.004
    [106] Pandey A. Mobile robot navigation and obstacle avoidance techniques: a review. International Journal of Robotics & Automation, 2017, 2(3): 1−12
    [107] 成伟明, 唐振民, 赵春霞, 刘华军. 移动机器人路径规划中的图方法应用综述. 图学学报, 2008, 29(4): 6−14 doi:  10.3969/j.issn.1003-0158.2008.04.002

    CHENG Wei-Ming, TANG Zhen-Min, ZHAO Chun-Xia, LIU Hua-Jun. A survey of mobile robots path planning using geometric methods. Journal of Engineering Graphics, 2008, 29(4): 6−14 doi:  10.3969/j.issn.1003-0158.2008.04.002
    [108] 王慧, 王光宇, 潘德文. 基于改进粒子群算法的移动机器人路径规划. 传感器与微系统, 2017, 36(5): 77−79

    WANG Hui, WANG Guang-Yu, PAN De-Wen. Mobile robot path planning based on modified particle swarm optimization algorithm. Transducer and Microsystem Technologies, 2017, 36(5): 77−79
    [109] Cheng E S, Jun H. A hybrid path planning algorithm for indoor mobile robot using hierarchy reinforcement learning. International Journal of Control and Automation, 2016, 9(5): 351−362 doi:  10.14257/ijca.2016.9.5.34
    [110] 高翔, 苏青. 基于双层模糊逻辑的多机器人路径规划与避碰. 计算机技术与发展, 2014, 24(11): 79−82

    GAO Xiang, SU Qing. Multi-robot path planning and collision avoidance based on double fuzzy logic. Computer Technology and Development, 2014, 24(11): 79−82
    [111] 胡世亮, 席裕庚. 一种通用的移动机器人路径规划仿真系统. 系统仿真学报, 2004, 16(8): 1714−1716+1720 doi:  10.3969/j.issn.1004-731X.2004.08.029

    HU Shi-Liang, XI Yu-Geng. A general-purpose moving robot path-planning simulation system. Journal of System Simulation, 2004, 16(8): 1714−1716+1720 doi:  10.3969/j.issn.1004-731X.2004.08.029
    [112] Lu W R, McFarlane D, Giannikas V, Zhang Q. An algorithm for dynamic order-picking in warehouse operations. European Journal of Operational Research, 2016, 248(1): 107−122 doi:  10.1016/j.ejor.2015.06.074
    [113] 高志伟, 代学武, 郑志达. 基于运动控制和频域分析的移动机器人能耗最优轨迹规划. 自动化学报, 2020, 46(5): 934−945

    GAO Zhi-Wei, DAI Xue-Wu, ZHENG Zhi-Da. Optimal energy consumption trajectory planning for mobile robot based on motion control and frequency domain analysis. Acta Automatica Sinica, 2020, 46(5): 934−945
    [114] 宋勇, 李贻斌, 栗春, 李彩虹. 基于神经网络的移动机器人路径规划方法. 系统工程与电子技术, 2008, 30(2): 316−319 doi:  10.3321/j.issn:1001-506X.2008.02.030

    SONG Yong, LI Yi-Bin, LI Chen, LI Cai-Hong. Path planning methods of mobile robot based on neural network. System Engineering and Electronice, 2008, 30(2): 316−319 doi:  10.3321/j.issn:1001-506X.2008.02.030
    [115] 孙志军, 薛磊, 许阳明, 王正. 深度学习研究综述. 计算机应用研究, 2012, 29(8): 2806−2810 doi:  10.3969/j.issn.1001-3695.2012.08.002

    SUN Zhi-Jun, XUE Lei, XU Yang-Ming, WANG Zheng. Overview of deep learning. Application Research of Computers, 2012, 29(8): 2806−2810 doi:  10.3969/j.issn.1001-3695.2012.08.002
    [116] Li H, Yang S X, Seto M L. Neural-network-based path planning for a multirobot system with moving obstacles. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2009, 39(4): 410−419 doi:  10.1109/TSMCC.2009.2020789
    [117] Zhu A, Yang S X. A neural network approach to dynamic task assignment of multirobots. IEEE transactions on neural networks, 2006, 17(5): 1278−1287 doi:  10.1109/TNN.2006.875994
    [118] Heo Y J, Kim D, Lee W, Kim H, Park J, Chung W K. Collision detection for industrial collaborative robots: A deep learning approach. IEEE Robotics and Automation Letters, 2019, 4(2): 740−746 doi:  10.1109/LRA.2019.2893400
    [119] 徐翔斌, 李志鹏. 强化学习在运筹学的应用: 研究进展与展望. 运筹与管理, 2020, 29(5): 227−239

    Xu Xiang-Bin, Li Zhi-Peng. Research progress and prospects for application of reinforcement learning in operations research. Operations Research and Management Science, 2020, 29(5): 227−239
    [120] 刘丹, 曹建彤, 陈建名. 基于Agent建模的应用: 研究综述. 技术经济, 2014, 11: 96−102 doi:  10.3969/j.issn.1002-980X.2014.02.015

    LIU Dan, CAO Jing-Tong, CHEN Jian-Ming. Application of agent-based modeling: literature review. Technology Economics, 2014, 11: 96−102 doi:  10.3969/j.issn.1002-980X.2014.02.015
    [121] Green D G. Hierarchy, complexity and agent based models. Our Fragile World: Challenges and Opportunities for Sustainable Development, Pairs: UNESCO, 2010. 1273−1292.
    [122] 陈仁际, 吴镇炜, 王韬, 董昌. 基于Agent的分布式多机器人系统建模及分析. 中国机械工程, 2001, 12(6): 667−671 doi:  10.3321/j.issn:1004-132X.2001.06.017

    CHEN Ren-Ji, WU Zhen-Wei, WANG Tao, DONG Chang. Modeling and analysis for agent-based distributed multiple robot system. China Mechanical Engineering, 2001, 12(6): 667−671 doi:  10.3321/j.issn:1004-132X.2001.06.017
    [123] 柏继云, 李士勇. 基于agent的蚁群觅食行为建模及在机器人路径规划问题中的应用. 计算机应用研究, 2014, 31(1): 47−50 doi:  10.3969/j.issn.1001-3695.2014.01.010

    BAI Ji-Yun, LI Shi-Yong. Modeling of colony foraging behavior based on agent and application of model in robotic path planning. Application Research of Computers, 2014, 31(1): 47−50 doi:  10.3969/j.issn.1001-3695.2014.01.010
    [124] Hazard C J, Wurman P R, 'Andrea R D. Alphabet Soup: A Testbed for Studying Resource Allocation in Multi-vehicle Systems. In: Proceedings of the In Proceedings of the 2006 AAAI Workshop on Auction Mechanisms for Robot Coordination, Massachusetts, USA: AAAI, 2006. 23−30.
    [125] Merschformann M, Xie L, Li H Y. RAWSim-O: A simulation framework for robotic mobile fulfillment systems [Online], available: https://arxiv.org/pdf/1710.04726.pdf, October 12, 2017.
    [126] Keung K L, Lee C K M, Ji P, Ng K K H. Cloud-based cyber-physical robotic mobile fulfillment systems: a case study of collision avoidance. IEEE Access, 2020, 8: 89318−89336 doi:  10.1109/ACCESS.2020.2992475
    [127] Azadeh K, De Koster R, Roy D. Robotized and automated warehouse systems: review and recent developments. Transportation Science, 2019, 53(4): 917−945 doi:  10.1287/trsc.2018.0873
    [128] 孙长银, 穆朝絮. 多智能体深度强化学习的若干关键科学问题. 自动化学报, 2020, 46(7): 1−12

    Sun Chang-Yin, Mu Chao-Xu. Important scientific problems of multi-agent deep reinforcement learning. Acta Automatica Sinica, 2020, 46(7): 1−12
    [129] 秦方博, 徐德. 机器人操作技能模型综述. 自动化学报, 2019, 45(8): 1401−1418

    Qin Fang-Bo, Xu De. Review of robot manipulation skill models. Acta Automatica Sinica, 2019, 45(8): 1401−1418
    [130] 曹风魁, 庄严, 闫飞, 杨奇峰, 王伟. 移动机器人长期自主环境适应研究进展和展望. 自动化学报, 2020, 46(2): 205−221

    CAO Feng-Kui, ZHUANG Yan, YAN Fei, YANG Qi-Feng, WANG Wei. Long-term autonomous environment adaptation of mobile robots: state-of-the-art methods and prospects. Acta Automatica Sinica, 2020, 46(2): 205−221
  • [1] 滕菲, 单麒赫, 李铁山. 智能船舶综合能源系统及其分布式优化调度方法[J]. 自动化学报, doi: 10.16383/j.aas.c200176
    [2] 李勇, 李坤成, 孙柏青, 张秋豪, 王义娜, 杨俊友. 智能体Petri网融合的多机器人 多任务协调框架[J]. 自动化学报, doi: 10.16383/j.aas.c190400
    [3] 胡亚南, 马书根, 李斌, 王明辉, 王越超. 轮手一体机器人能量次优重构规划方法[J]. 自动化学报, doi: 10.16383/j.aas.2017.c150752
    [4] 田彦涛, 孙中波, 李宏扬, 王静. 动态双足机器人的控制与优化研究进展[J]. 自动化学报, doi: 10.16383/j.aas.2016.c150821
    [5] 侯增广, 赵新刚, 程龙, 王启宁, 王卫群. 康复机器人与智能辅助系统的研究进展[J]. 自动化学报, doi: 10.16383/j.aas.2016.y000006
    [6] 陈世明, 化俞新, 祝振敏, 赖强. 邻域交互结构优化的多智能体快速蜂拥控制算法[J]. 自动化学报, doi: 10.16383/j.aas.2015.c150254
    [7] 李新德, 张秀龙. 一种面向室内智能机器人导航的路径自然语言处理方法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2014.00289
    [8] 王大志, 刘士新, 郭希旺. 求解总拖期时间最小化流水车间调度问题的多智能体进化算法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2014.00548
    [9] 罗小元, 邵士凯, 关新平, 赵渊洁. 多智能体最优持久编队动态生成与控制[J]. 自动化学报, doi: 10.3724/SP.J.1004.2013.01431
    [10] 陈新伟, 刘景泰, 林森, 石涛, 陈阔, 魏青. 大型实景地理模型3D喷绘机器人及其喷绘方法优化[J]. 自动化学报, doi: 10.3724/SP.J.1004.2012.00023
    [11] 柯文德, 崔刚, 洪炳, 蔡则苏, 朴松昊, 钟秋波. 参数化优化的仿人机器人相似性前向倒地研究[J]. 自动化学报, doi: 10.3724/SP.J.1004.2011.01006
    [12] 姜健, 赵杰, 李力坤. 面向群智能机器人系统的声音协作定向[J]. 自动化学报, doi: 10.1360/aas-007-0385
    [13] 徐玉如, 肖坤. 智能海洋机器人技术进展[J]. 自动化学报, doi: 10.1360/aas-007-0518
    [14] 钟伟才, 刘静, 焦李成. 多智能体遗传算法用于线性系统逼近[J]. 自动化学报
    [15] 操龙兵, 戴汝为. 基于多智能体的人机协作智能信息系统[J]. 自动化学报
    [16] 王硕, 范永, 谭民. 基于遗传算法的参数优化在多移动机器人系统中的应用[J]. 自动化学报
    [17] 张启忠, 蒋静坪. 用于机器人信息融合的RS智能系统[J]. 自动化学报
    [18] 卜永洪, 王翼. 机器人几何连杆参数辨识[J]. 自动化学报
    [19] 李善本, 徐毓良. 机器人图形仿真软件[J]. 自动化学报
    [20] 肖春林, 刘兴良. 机器人控制系统[J]. 自动化学报
  • 加载中
计量
  • 文章访问数:  14
  • HTML全文浏览量:  3
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-10-21
  • 录用日期:  2020-08-27

基于移动机器人的拣货系统研究进展

doi: 10.16383/j.aas.c190728
    基金项目:  国家自然科学基金(71761013), 江西省自然科学基金面上项目(20181BAB201010)资助
    作者简介:

    华东交通大学交通运输与物流学院教授.2015年获中南大学工学博士学位, 主要研究方向为物流与供应链管理, 本文通信作者. E-mail: champagnewq@aliyun.com

    中南大学交通运输工程学院博士研究生. 主要研究方向仓库拣货优化, 智能优化算法. E-mail: mzq11302@163.com

摘要: 基于移动机器人的拣货系统(Robotic Mobile Fulfillment Systems, RMFS)作为一种新型物至人的拣货系统, 相比人工拣货系统和AS/RS拣货系统(下文统称传统拣货系统)具有更高的拣货效率、更好的系统可扩展性和柔性. 为全面了解RMFS的运行模式及其优化方向, 本文首先回顾了RMFS的工作流程及优化理论框架, 然后对RMFS的货位指派、订单分批、任务分配、路径规划以及建模方法等问题进行了文献回顾和总结, 并指出了RMFS与传统拣货系统在拣货过程方面的异同及当前研究的不足. 最后, 讨论了RMFS的几个重要研究方向, 为RMFS的理论研究和应用实践提供参考.

English Abstract

徐翔斌, 马中强. 基于移动机器人的拣货系统研究进展. 自动化学报, 2020, 46(x): 1−20. doi: 10.16383/j.aas.c190728
引用本文: 徐翔斌, 马中强. 基于移动机器人的拣货系统研究进展. 自动化学报, 2020, 46(x): 1−20. doi: 10.16383/j.aas.c190728
Xu Xiang-Bin, Ma Zhong-Qiang. Robotic mobile fulfillment systems: state-of-the-art and prospects. Acta Automatica Sinica, 2020, 46(x): 1−20. doi: 10.16383/j.aas.c190728
Citation: Xu Xiang-Bin, Ma Zhong-Qiang. Robotic mobile fulfillment systems: state-of-the-art and prospects. Acta Automatica Sinica, 2020, 46(x): 1−20. doi: 10.16383/j.aas.c190728
  • 订单拣选是将商品从其存储位置拣出以满足客户订单需求的过程, 订单拣选是典型的劳动密集型作业, 占仓库运作总成本的60%-70%[1]. 随着客户需求从大批量少批次向小批量个性化转变, 客户对订单的配送时限和服务质量要求越来越高, 提升订单拣选效率已成为当今学术界和工业界共同关心的难题. 基于移动机器人的拣货系统(Robotic Mobile Fulfillment Systems, 以下简称RMFS)的订单拣选效率是传统拣货系统的2-3倍[23], 彻底颠覆了传统仓库的拣货作业模式, 为仓库的广泛应用和研究开辟了新途径.

    RMFS系统2003年由Kiva公司最先开发, 2012年亚马逊收购Kiva后在其北美各大配送中心开始部署[45], 国内已有菜鸟、京东和快仓等公司成功应用RMFS. RMFS的核心思想是利用移动机器人将存储商品的移动式货架搬运到拣货站台, 拣货人员拣取商品后再由机器人将货架送回存储区存储. 相比传统拣货系统, RMFS提高了拣货效率、准确性以及仓库空间利用率, 缩短了仓库部署和调试时间, 并可根据客户需求的变化实时、动态调整仓库布局结构, 特别适合需求波动性大、时效性强的电商企业的订单拣选[23, 6].

    与传统拣货系统类似, RMFS也面临货位指派、订单分批、任务分配以及路径规划等方面的问题, 但在实际运作过程中, RMFS与传统拣货系统相比存在诸多不同, 面临一些新的亟需解决的问题. 鉴于此, 本文对RMFS订单拣选过程的几个关键问题进行综述研究, 并给出未来的研究方向, 为RMFS的实践应用及学术研究提供参考.

    • RMFS的仓库布局可分为存储区、拣选区和运输区(如图1(a)所示), 订单拣选作业主要在拣选区进行(如图1(b)-(d)所示). 仓库一般采用栅格化布局, 利用条码、RFID等技术实现信息识别, 并利用室内GPS和传感器技术进行导航、定位和避障[6-8]. RMFS的货架为移动式货架, 有运输货架和存货货架两种, 运输货架是存放订单容器的货架, 存货货架又可分为托盘货架和单品货架, 托盘货架的作用是存放和拣选整箱商品, 单品货架则存放零拣商品[4, 6]. 补货站台位于存储区和拣选区之间, 拣选站台位于拣选区和运输区之间, 拣货和补货人员分别位于拣选站台和补货站台, 他们只需要站在原地等待移动机器人搬运货架到来, 并根据系统指示进行订单拣选或仓库补货作业. RMFS的作业流程为: 系统先按照一定策略将商品分配到各存储货架(货位指派问题), 在收到客户订单后, 基于特定的订单分配分批和任务分配策略将订单分批, 再分配给相应的拣选站台(订单分批和分配问题), 同时向运输机器人发布运输任务(多机器人任务分配问题), 机器人将目标货架从其存储位置搬运到指定的拣选站台(多机器人路径规划问题), 拣选人员按照系统指示依次进行拣选、扫描确认、存放等作业, 完成商品拣选后, 运输机器人再将货架送回存储区存储(多机器人路径规划问题), 需要说明的是, 货架返回后的存储位置不一定是其原来的存储位置(货架储位动态分配问题)[2]. RMFS的整个作业流程如图2所示, 有关图2的具体说明可参考文献[2].

      图  1  RMFS拣货区域布局图

      Figure 1.  RMFS picking area layout

      图  2  RMFS订单拣选作业流程

      Figure 2.  RMFS order picking process

      图2的作业流程可以发现RMFS的几个关键的优化和研究方向: 首先, RMFS的正常运作依靠自动识别技术、传感器及通信等技术的支撑, 可以对这些使能技术进行研究[9]. 其次, 与传统拣货系统类似, 货位指派[4]、订单分批[10]、任务分配[11]、路径规划[12]等问题的优化研究也是提升RMFS效率的关键途径. 再次, RMFS本质上是一个自组织模式运营的分布式多机器人系统, 可基于分布式、去中心化的思路进行系统优化, 这与传统拣货系统有很大的不同[13]. 总的来说, RMFS的优化可从使能技术、仓库布局设计、货位指派、订单分批、路径规划、分区拣选以及多机器人任务分配及协作等方面开展研究[1, 14](如图3所示). RMFS的优化研究可分为系统实现、系统作业以及研究方法三个层面, 其优化理论框架如图4所示.

      图  3  RMFS拣货优化流程

      Figure 3.  RMFS picking optimization process

      图  4  RMFS优化理论框架

      Figure 4.  RMFS optimization theory framework

    • RMFS的相关研究主要涉及货位指派、订单分批、任务分配与调度、路径规划以及系统设计与评估等问题, 相关问题的研究文献总结如表1所示.

      表 1  RMFS研究文献汇总

      Table 1.  Summary of literature on RMFS

      问题分类 作者 研究问题 解决方法
      货位指派 Nigam et al.[4](2014) 货架储位指派问题 多类封闭排队网络
      Lamballais et al.[3](2017) 仓库布局、商品储位指派、补货作业优化问题 半开放排队网络
      Onal et al.[15](2017) 商品储位指派问题 爆炸存储策略、仿真方法
      Krenzler et al.[16](2018) 货架储位再指派问题 确定性模型、组合优化算法
      Yuan et al.[17](2018) 货架储位指派问题 流体模型、基于策略的存储方法
      Weidinger et al.[18](2018) 货架储位动态指派 混合整数规划模型、自适应规划方法
      Yuan et al.[19](2018) 货位指派问题 分区存储策略、仿真方法
      Xiang et al.[20](2018) 商品储位指派问题与订单分批协同优化 混合整数规划模型、可变邻域搜索方法、自适应算法
      蔺一帅等[21](2020) 商品储位指派与路径规划协同优化 改进的协同优化遗传算法
      徐翔斌等[22](2020) 货架储位动态指派 改进的模拟退火算法
      订单分批 吴颖颖等[23](2016) 订单排序问题 订单排序优化模型、k-means聚类算法
      Boysen et al.[24](2017) 订单分批与订单排序以及货架在拣货站台排序的综合优化 混合整数规划模型、Cplex以及仿真方法
      Xiang et al.[20](2018) 商品储位指派问题与订单分批协同优化 混合整数规划模型、可变邻域搜索方法、自适应算法
      任务分配及调度 Zhou et al.[11](2014) 多机器人任务分配问题 平衡启发式机制与仿真
      Dou et al.[25](2015) 任务调度和路径规划协同优化 遗传算法、强化学习
      徐贤浩等[26](2016) 搬运机器人待命泊位策略问题 统计建模方法、基于策略的方法
      Yuan et al.[27](2017) 搬运机器人共享分配问题 共享协议策略、排队网络
      Zou et al.[28](2017) RMFS分配规则问题 半开放排队网络、基于规则的方法、邻域搜索方法
      Merschformann et al.[12] (2017) RMFS作业调度决策问题 基于行走策略的研究方法
      Merschformann et al.[29](2018) RMFS作业调度决策问题 基于策略的存储和仿真方法
      Ghassemi et al.[30](2018) 多机器人任务分配问题 基于二部图匹配和模糊聚类的分散多主体任务分配算法、仿真
      Zou et al.[31](2018) 评估机器人充电与更换电池策略的优劣 半开放排队网络、Arena仿真
      袁瑞萍等[32](2018) 拣货过程任务调度 共同进化遗传算法
      Roy et al.[33](2019) RMFS系统绩效评估、机器人分配策略 封闭排队网络、两阶段随机模型、Arena仿真
      Yoshitake et al.[34](2019) 机器人调度 实时全息调度方法
      Zhang et al.[35](2019) RMFS多机器人分配问题 改进的遗传算法
      路径规划 沈博闻等[8](2014) 多机器人路径规划问题 改进的A*算法
      Dou et al.[25](2015) 任务调度和路径规划协同优化 遗传算法、强化学习
      Kumar et al.[36](2018) RMFS路径规划问题 无冲突路径规划算法
      Zheng et al.[37](2018) 多机器人无冲突路径规划 改进的Dijkstra算法、避碰规则
      张丹霞等[38](2018) 多机器人协同路径规划 改进的A*算法、动态加权图
      夏清松等[39](2019) 路径规划与作业避障协同研究 蚁群算法、避障规则设计
      Lee et al.[40](2019) 多机器人无冲突路径规划 网络物理系统模型、改进的A*算法以及避碰规则
      于赫年等[41](2020) 多机器人路径规划问题 自调优A*算法、主动避障规则
      蔺一帅等[21](2020) 商品储位指派与路径规划协同优化 改进的协同优化遗传算法
      RMFS系统设计、
      评估及其它问题研究
      Gue et al.[42](2014) RMFS机器人系统控制与评估 面向对象建模与仿真
      Yuan et al.[43](2016) 评估RMFS的性能, 主要关注机器人数量、速度优化 开放排队网络模型
      Lee et al.[44](2018) 变形RMFS的拣货流程优化 混合整数规划模型、Gurobi
      Bozer et al.[45](2018) RMFS系统与miniload系统对比 仿真方法
      Wang et al.[46](2019) 机器人搬运货架的运行周期问题 旅行时间模型
      Zhang et al.[47](2019) RMFS快递分拣仓库布局自动化设计 机器学习与进化计算组合的方法
      Petković et al.[48](2019) RMFS工作人员的意图评估 隐马尔科夫模型和心理理论
      Wang et al.[49](2020) RMFS系统设计框架研究 基于瓶颈的模型和开放排队网络模型
    • 传统意义上的货位指派是指将商品分配到仓库中的合适储位, 使订单分拣过程行走的距离最短[1]. RMFS的货位指派可分为商品储位指派和货架储位动态指派, 商品储位指派是指在考虑商品销售关联性的情况下, 将关联商品指派到同一货架存储, 最终实现货架存储商品的关联度最大, 降低订单拣选搬运的货架总次数, 图5(a)为商品储位指派的示意图; 在构建商品储位指派数学模型时, 需考虑所有商品必须被指派到货架存储、同一类商品可以存储于多个货架以及货架的存储容量等约束条件. 货架储位动态指派是在订单拣选的过程中, 为搬运货架重新分配储位, 例如将存储畅销商品的货架指派到靠近拣货站台的储位, 同时将存储滞销商品的货架指派到远离拣货站台的储位, 实现订单拣选过程的机器人行走距离最短, 图5(b)为货架储位动态指派的示意图; 在构建货架储位动态指派数学模型时, 需考虑所有货架必须被指派到储位, 储位的状态(占用储位或开发储位)以及仓库布局的连续动态变化关系等约束条件.

      图  5  RMFS货位指派示意图

      Figure 5.  RMFS location assignment diagram

      货位指派是典型广义指派问题(Generalized Assignment Problem, GAP)[50], 最基本的货位指派的数学模型为:

      $$ {\text{模型一}}\;\;\;\;\min (\max )\sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n {{c_{ij}}{x_{ij}}} } $$ (1)
      $$ {\rm{s}}.{\rm{t}}.\;\;\;\sum\limits_{j = 1}^n {{x_{ij}}} = 1 \;\; i = 1,2, \cdots ,m $$ (2)
      $$\sum\limits_{i = 1}^m {{x_{ij}}} \leq 1 \;\; j = 1,2, \cdots ,n$$ (3)
      $${x_{ij}} \in \{ 0,1\} ,{c_{ij}} > 0 \;\; \forall i = 1, \cdots ,m;j = 1, \cdots ,n$$ (4)

      在模型一中, ${x_{ij}} = 1$ 表示将商品(或货架) $i$ 存储在位置 $j$ , 否则 ${x_{ij}} = 0$ ; ${c_{ij}}$ 表示将商品(或货架) $i$ 存储在货架或位置 $j$ 的拣货代价(或收益); 式(1)为目标函数, 根据选取的 ${c_{ij}}$ 不同, 可分为求最小值或最大值(例如拣货时间或距离最小、拣货效率最大等); 式(2)和(3)为约束条件, 表示商品(或货架)与储位之间的存储关系; 式(4)为变量及取值范围.

      科学的货位指派方法可以缩短行走距离、降低搜寻时间、减少工作量以及提高仓库拣货效率[5152]. Hausman[53]最早提出定位存储、随机存储和分类存储三种基本的货位指派策略, 随后的文献分别从需求相关性[5455]、出货量[56]、COI[57]、周转率[58]以及需求和结构相关性[5960]等方面对货位指派问题进行了研究, 根据问题类型、指派策略以及优化目标的不同, 大量文献基于模型一进行了深入广泛的研究.

      RMFS与传统拣货系统的货位指派问题不同在于: (1)传统拣货系统的货位指派与路径策略密切相关[61], RMFS的货位指派则与路径策略没有必然联系. (2)指派目的地不同: 传统货位指派只需将商品指派到某一分区或巷道, RMFS既要将商品指派到具体的货架, 还需考虑将关联商品指派到同一货架来降低拣货成本. (3)优化目标不同: 传统拣货系统将拣货行走的时间或距离作为货位指派问题的优化目标, RMFS则可将货架搬运次数、机器人利用率等作为优化目标[23]. (4)指派复杂度不同: 传统拣货系统的货位指派只需对商品进行储位指派, RMFS则还需考虑货架的储位指派(即货架在仓库中的位置), 这是一个更加复杂的动态指派问题. (5)静态与动态指派的不同: 传统货位指派基于“一次指派、分批出库”的思路, RMFS的货位指派过程是一种“动态优化、逐步求精”的过程.

      RMFS的货位指派可从以下几个方面借鉴传统货位指派问题的研究理论和方法: (1)考虑商品需求关联性和频率: 传统拣货系统考虑商品需求关联性、频率等因素进行货位指派研究[5455], RMFS也需考虑此类因素对商品和货架储位指派优化的影响. (2)考虑逐步求精的动态货位调整: 动态货位调整比一次性长远规划的货位指派更为简单有效[62], 可基于逐步求精、渐进式优化的思路研究RMFS的商品和货架的动态调整问题. (3)考虑人因及设备等因素: 传统拣货系统中人的因素对订单拣选效率影响巨大[63], 货位指派需考虑人员的工作负荷[64]、技能[65]以及拥堵[66]等因素, RMFS货位指派优化过程中也应考虑机器人拥堵、空闲率、电量以及作业人员技能、效率等因素. (4)借鉴已有研究方法: 譬如可用动态规划[67]、启发式[68]、数据挖掘[69]和聚类分析[70]等方法来研究RMFS货位指派问题.

      RMFS的货位指派研究可分为商品储位指派研究和货架储位指派研究, 现有文献主要利用排队论、整数规划、仿真、启发式规则以及智能优化等方法进行建模和求解. 研究文献根据问题和方法分类综述如下:

      (1)商品储位指派研究

      1)利用排队论方法

      Lamballais[3]构建了RMFS系统效能评估的排队网络模型, 分别以最大订单吞吐量、平均订单拣选周期以及机器人利用率等指标评价了不同存储策略的系统绩效, 结果表明采用基于货架周转率的商品分区存储策略可使系统的最大吞吐量提高50%左右, 不足之处是文中假设每个货架只存储一种商品. 在此基础上, Onal[15]提出了一种爆炸存储的商品储位指派策略, 构建了商品储位指派的排队论模型, 结果表明随着爆炸水平的提高, 订单拣选时间最多可降低16%.

      2)利用混合整数规划方法

      Xiang[20]在考虑爆炸存储策略和商品关联性的情况下, 构建了RMFS商品储位指派与路径规划协同优化的混合整数规划模型, 设计的变邻域搜索算法在解的质量和求解时间方面比遗传算法分别好6.0%和3.3%, 但未考虑缺货和补货的情况. 蔺一帅[21]也利用改进的协同优化遗传算法对RMFS的商品储位指派和路径规划问题进行了协同优化, 构建了商品储位指派与路径规划协同优化的混合整数规划模型.

      (2)货架储位指派研究

      1)利用排队论方法

      Nigam[4]利用排队论模型研究了RMFS随机空位存储与最近空位存储策略的效率问题, 结果表明随机空位存储的RMFS系统空间利用率较高, 而最近空位存储的RMFS系统吞吐量较高. Rong[17]进一步研究了随机存储、基于速度和基于类的货架储位指派策略, 构建了不同存储策略绩效评估的排队模型, 结果发现基于类的策略鲁棒性较强, 可以适应不同仓库配置、布局的RMFS.

      2)利用(混合)整数规划方法

      在基于策略的货位指派研究中, 文献[24, 71]提出一种可显著提高RMFS拣货效率的共享存储策略, 文献[19]发现分区存储策略也能显著的提高RMFS的拣货效率, 在此基础上, Weidinger[18]对RMFS的货架储位动态指派问题进行了研究, 构建了混合整数规划模型, 并利用自适应规划方法求解模型, 将机器人的拣货总行程和编队数量分别降低了3.49%和2.17%, 提高了RMFS的拣货效率, 但未构建反映货架储位动态变化关系的理论模型, 文献[22]进一步构建了反映货架储位动态变化关系的混合整数规划模型, 该动态优化模型可缩短了30%左右的拣货距离.

      此外也有文献利用仿真来研究RMFS问题, 仿真技术具有可视化效果好、人机交互灵活等优点, 特别适合用于模型和优化效果的验证, 例如Zou[28]利用仿真方法验证了半开放排队网络模型的正确性, Merschformann[29]则在规划模型基础上, 利用仿真平台RAWSim-O对RMFS的随机、固定、最近空位以及基于类这几种典型的货架储位指派策略进行了对比研究, 结果表明基于类的指派策略的效果更加显著.

      综上所述, 有关RMFS货位指派的研究成果显著, 但主要集中在对商品和货架储位指派的系统绩效评估方面, 较少涉及商品储位指派和货架储位指派的协同优化, 并且一般采用仿真验证指派策略的有效性. 由于RMFS与传统拣货系统在货位指派方面存在诸多不同, 建议重点关注: (1)考虑集成多种指派策略、并寻找最优策略的货位指派方法. (2)由于RMFS需要分别对商品和货架存储进行双重指派, 应重点关注商品关联性对商品、货架储位指派的影响, 重点研究商品和货架储位的双重指派这二者之间的内在联系和相关影响. (3)特别关注动态货位指派问题, 可基于逐步求精、渐进式优化的思想研究RMFS的商品与货架的动态储位指派问题. (4)在模型一的基础上, 根据RMFS货位指派问题的特性, 分别对商品和货架的(动态)货位指派模型进行研究, 构建RMFS货位指派问题的理论模型.

    • 订单分批是指为了提高订单拣选效率而把多个订单合并拣选的过程, 其目的是为了降低订单拣选时货架的搬运次数、机器人的行走距离或时间[1]. RMFS的订单分批示意图如图6所示, 在RMFS订单分批优化过程中, 需考虑每个订单 $j$ 只能被指派到一个订单批次 $i$ 、每个批次 $i$ 包含的订单数不能超过规定的数量 $C$ 以及该批次所有商品必须都被拣选等约束条件, 一般将货架搬运次数、机器人行走距离以及同批次内订单关联度等指标作为优化目标.

      图  6  RMFS订单分批示意图

      Figure 6.  RMFS order batching diagram

      最基本的订单分批问题的数学模型为[72]:

      $$ {\text{模型二}}\;\;\;\min (\max )\sum\limits_{i \in I} {{d_i}{a_{ij}}} $$ (5)
      $$ {\rm{s}}.{\rm{t}}.\;\;\;\;\sum\limits_{j \in J} {{a_{ij}}} \leq C \;\; \forall i \in I $$ (6)
      $$\sum\limits_{i \in I} {{a_{ij}}} = 1 \;\; \forall j \in J$$ (7)
      $${a_{ij}} \in \{ 0,1\} ,C \in {N^*},{d_i} \geq 0 \;\; \forall i \in I;j \in J$$ (8)

      在模型二中, $J$ 表示客户订单, $J = \{ 1,2, \cdots ,n\} $ ; $I$ 为订单集合, $I = \{ 1,2, \cdots ,m\} $ ; $C$ 为每批次订单最大容量; ${d_i}$ 表示拣取批次 $i$ 所有商品的代价(例如时间、距离); ${a_{ij}} = 1$ 表示订单 $j(j \in J)$ 被分配到批次 $i(i \in I)$ , 否则 ${a_{ij}} = 0$ ; 式(5)为目标函数, 根据 ${d_i}$ 的不同可取最大值或最小值(例如货架搬运次数最小、系统吞吐量最大等); 式(6)为订单批次合理性约束; 式(7)表示每个订单都必须被指派到一个批次; 式(8)为变量和参数取值.

      订单分批问题最早由Ackerman[73]提出, 相比货位指派, 订单分批优化对拣货效率的提升更加明显[74]. 根据订单信息是否已知, 订单分批可分为在线订单分批和离线订单分批, 其中在线订单分批更加符合实际情况. 订单分批问题为NP难题[75], 一般利用(元)启发式算法[7677]、数据挖掘[78]以及聚类和仿真[79]等方法研究离线订单分批问题, 而在线订单分批问题则利用时间窗、启发式等方法研究[10], 对离线订单分批问题的研究方法进行改进也可用于在线订单分批问题的研究[80], 国内的马士华[81]、李诗珍[79]等也对这方面的问题进行了深入研究.

      RMFS订单分批的目的是使货架搬运次数、订单拣选时间或延迟率等指标最小, 该问题可分为两种情况: 一是先对订单分批处理, 然后将订单批次分配至拣货站台; 二是先将订单分配至拣货站台, 再进行订单分批处理. RMFS与传统拣货系统的订单分批问题的不同表现在: (1)分批对象不同: RMFS既可直接对订单分批, 还可根据待拣商品的存储位置对机器人进行分批. (2)考虑因素不同: 传统拣货系统的订单分批问题一般只考虑拣货车容量、拣货员的工作负荷、拥堵以及路径策略等因素[77, 8283], RMFS则还需要考虑机器人死锁、电量、故障以及利用率等问题. (3)优化目标不同: RMFS一般将商品货架搬运次数、机器人利用率等指标作为优化目标[23]. (4)复杂度不同: RMFS的订单分批需要考虑两种不同的订单分批情况, 问题的复杂度更高.

      RMFS的订单分批可从以下几个方面借鉴传统订单分批问题的研究成果: (1)RMFS订单分批问题为NP难题, 可利用(元)启发式、数据挖掘、聚类等方法对RMFS的订单分批进行研究. (2)考虑拣货人员的影响: 传统拣货系统认为拣货员的技能可提高批次拣货的效率[65], RMFS的订单分批问题研究也需要考虑拣货员的技能、效率以及工作负荷等因素的影响. (3)考虑订单交货期限: 订单交期对订单拣选至关重要, 与传统拣货系统类似[84], 研究RMFS的订单分批问题也应考虑订单交期问题. (4)考虑系统综合优化: 为得到全局最优的订单分批方案, 传统拣货系统将订单分批与路径规划、任务分配等问题进行协同优化研究[85], 综合考虑RMFS多个子问题的协同优化研究将是必然趋势. (5)继续释放约束条件: 与传统拣货系统类似, 考虑拣货过程中出现的突发情况和随机因素(如插单、取消订单等)对RMFS订单分批问题的影响, 使RMFS订单分批的研究更加贴合实际情况.

      现有文献以批次订单关联性最大、货架搬运次数最小等指标为优化目标, 主要利用排队论、(混合)整数规划、聚类等方法研究RMFS订单分批问题, 对RMFS订单分批的文献按照研究方法综述如下:

      (1)利用排队论方法

      Yu[86]在人工拣货作业背景下, 构建了订单分批与拣货分区协同优化的近似排队网络模型, 该近似排队网络模型与仿真结果相比相对误差小于10%. 考虑到订单分批策略对RMFS效率的影响与AS/RS类似, Hur[87]等设计了评估AS/RS系统绩效的排队网络模型, 仿真结果表明其设计的模型的误差在0.1%到8.6%之间, 这些研究为基于排队论方法研究RMFS的订单分批问题提供了理论基础.

      (2)利用(混合)整数规划方法

      Xiang[20]最先研究了RMFS的订单分批问题, 在模型二的基础上构建了RMFS订单分批问题的混合整数规划模型.

      $$ {\text{模型三}}\;\;\;\min \sum\limits_k {\sum\limits_m {{w_{km}}} } $$ (9)
      $$ {\rm{s}}.{\rm{t}}.\;\;\;\;\sum\limits_n {{z_{nk}} = 1 \;\;\; \forall n} $$ (10)
      $$\sum\limits_n {{z_{nk}}} \leq E\;\;\; \forall k$$ (11)
      $$\sum\limits_n {{a_{in}}{z_{nk}}} \leq P*{u_{ik}} \;\;\; \forall i,k$$ (12)
      $$\sum\limits_m {x_{im}^*{w_{km}}} \geq {u_{ik}} \;\;\; \forall i,k$$ (13)
      $${z_{nk}},{w_{km}},{u_{ik}} \in \{ 0,1\} \;\;\; \forall i,m,n,k$$ (14)

      在模型三中, $N$ 为订单总数; $M$ 为货架总数; $P$ 为商品种类总数; $K$ 为订单批次总数; $E$ 为每批次包含的最大订单数; $n$ 表示订单编号, $n = 1, 2, \cdots ,N$ ; $m$ 表示货架编号, $m = 1,2, \cdots ,M$ ; $i,j$ 表示商品种类, $i,j = 1,2, \cdots ,P$ ; $k$ 为订单批次编号, $k = 1,2, \cdots ,K$ ; ${a_{in}} = 1$ 表示订单 $n$ 包括商品 $i$ , 否则 ${a_{in}} = 0$ ; $x_{im}^* = 1$ 表示商品 $i$ 存储在货架 $m$ , 否则 $x_{im}^* = 0$ ; ${z_{nk}} = 1$ 表示订单 $n$ 被分配给批次 $k$ , 否则 ${z_{nk}} = 0$ ; ${w_{km}} = 1$ 表示因拣选批次 $k$ 而搬运货架 $m$ , 否则 ${w_{km}} = 0$ ; ${u_{ik}} = 1$ 表示批次 $k$ 包含商品 $i$ , 否则 ${u_{ik}} = 0$ ; 式(9)为目标函数, 表示批次拣货过程货架搬运次数最小; 式(10)表示每个订单都必须被指派到一个订单批次; 式(11)表示分配到批次的订单总数不能超过规定的最大数量; 式(12)表示商品的批次归属; 式(13)表示被搬运的货架必须存储该批次所有的商品; 式(14)表示变量取值. 此外Xiang[20]还设计了可变邻域搜索算法进行求解, 结果表明货位指派与订单分批的协同优化显著降低了货架的搬运次数. Boysen[24]则将该问题扩展为订单分批、订单排序以及货架在拣货站台排序三个子问题, 结果表明较优的订单调度与货架排序可使机器人运行时间最少可降低21%. AS/RS与RMFS同为“物至人”拣货系统, 在订单分批方面存在诸多相同之处, 王艳艳[88]等对AS/RS和Carousel拣货系统的订单分批问题进行研究, 吴颖颖[23]等在此基础上研究了物至人拣货系统的订单排序问题, 将货架出入库频率作为优化目标, 优化后的系统拣货效率提高了15.9%. 为了提高电商仓库的拣货效率, 王旭坪[74]和Zhang[10]在考虑订单交货期限的前提下对订单分批与排序协同优化问题进行了研究, 构建了协同优化的整数规划模型, 实现了80.365%的订单配送率.

      (3)利用聚类的方法

      订单分批本质上是一个聚类过程, 因而聚类策略是订单分批问题研究的重点, Chen[78]等利用基于关联规则的聚类方法研究了人工拣货系统的订单分批问题, 构建了订单分批的0-1整数规划模型, 利用关联规则算法进行模型求解, 优化效果显著. 与文献[78]不同, Araidah[89]则设计了订单聚类的启发式规则, 最多可减少44%的拣货时间. 这些研究表明利用聚类、关联规则等数据挖掘方法进行RMFS的订单分批研究将是一种有效途径.

      综上, 上述文献对RMFS的订单分批问题做了初步研究, 并取得了一定的优化效果, 特别是AS/RS的订单分批研究对RMFS具有重要的借鉴意义. 但RMFS与传统拣货系统的订单分批问题存在诸多不同, 应重点关注: (1)研究不同分批策略对RMFS订单分批效果的影响, 并比较各分批策略的优劣. (2)RMFS的订单分批应将商品关联性、需求频率以及货架搬运次数作为重要优化指标, 并考虑机器人特性、状态(如电量、路径等)等因素对订单分批的影响. (3)考虑订单取消以及插单等突发情况下的RMFS订单分批问题.

    • 传统拣货系统的任务分配是将拣货任务按一定方式分配给拣货员或堆垛机, 让拣货员或堆垛机将待拣商品从存储位置拣出, 目的是使拣货的总代价最小[1]. 与传统拣货系统不同, RMFS是一个多机器人系统(Multi-robot systems, MRS), 其任务分配是一个典型的多机器人任务分配(Multi-robot Task Allocation, MRTA)问题, 具体包括两个方面, 首先是将任务集分配给机器人群体, 其次是协调机器人群体的行为, 使其高效、可靠地完成任务[90]. 货架与机器人的任务分配示意图如图7所示, 在构建货架与机器人之间的分配模型时, 可将机器人的行走距离、订单拣选效率以及机器人电量消耗等指标作为优化目标, 并将机器人的电量限制、同一时刻货架只能被一个机器人搬运(反之亦然)等作为约束条件. MRTA问题可建模为最优分配、整数规划、调度、网络流等模型[91], 也可将其视为多旅行商问题(Multiple Traveling Salesmen Problem, MTSP). MRTA问题本质上也是一种广义指派问题, 其数学模型为[92]:

      图  7  RMFS的货架与机器人分配示意图

      Figure 7.  RMFS shelf and robot distribution diagram

      $$ {\text{模型四}}\;\;\;\min \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n {{c_{ij}}{x_{ij}}} } $$ (15)
      $$ {\rm{s}}.{\rm{t}}.\;\;\;{a_i} \leq \sum\limits_{j = 1}^n {{r_{ij}}{x_{ij}}} \leq {b_i} \;\;\; i = 1,2, \cdots ,m $$ (16)
      $$\sum\limits_{i = 1}^m {{x_{ij}}} = 1 \;\;\; j = 1,2, \cdots ,n$$ (17)
      $$\begin{split} &{x_{ij}} \in \{ 0,1\} ,{c_{ij}} > 0,{r_{ij}} > 0,{a_i} \geq 0,{b_i} \geq 0 \\ &\forall i = 1,2, \cdots ,m;j = 1,2, \cdots ,n \end{split} $$ (18)

      在模型四中, ${x_{ij}} = 1$ 表示将任务 $j$ 分配给Agent $i$ (Agent可为机器人或拣货/补货站台), 否则 ${x_{ij}} = 0$ ; ${c_{ij}}$ 表示将任务 $j$ 分配给Agent $i$ 的工作代价或收益; ${r_{ij}}$ 表示Agent $i$ 完成任务 $j$ 所需要的资源数量; ${a_i}$ ${b_i}$ 分别表示Agent $i$ 完成任务花费的最小和最大资源; 式(15)为目标函数, 根据选取的 ${c_{ij}}$ 不同, 可以取最小值或最大值; 式(16)—(17)为约束条件, 表示任务与Agent之间的分配关系; 式(18)为变量和参数取值.

      多数文献将机器人完成任务的代价最小、利用率或产出率最大等作为优化目标, 并利用基于行为[93]、情感[9495]、市场[9697]和最优化[11, 98]等方法求解MRTA问题. 其中基于市场和最优化的方法应用最为广泛, 基于市场的方法是利用拍卖的思想进行任务分配, 又可分为单物品拍卖和组合拍卖[90]两种, 相比其他拍卖形式, 组合拍卖能够提高拍卖效率, 降低竞标人风险. 由于组合拍卖的胜者决定问题已被证明是NP难题, 大多文献都利用启发式或元启发式算法[11, 99]求解MRTA问题, 也有文献利用聚类[100]和仿真[101]的方法, 值得一提的是陈培友等[102]将混沌理论引入了组合拍卖的任务分配过程.

      RMFS的任务分配问题与传统MRTA问题存在诸多不同, 主要有: (1)任务分配复杂度不同: 相比传统MRTA问题, RMFS是多任务多目标的任务分配, 涉及订单与拣货站台、货架与机器人以及拣货(补货)站台与机器人三个方面[2829], 任务分配的复杂度更高. (2)决策方式不同: RMFS的任务分配采用去中心化的分布式智能体决策方式, 相比传统MRTA的集中决策控制系统鲁棒性更强、效果更好[9, 42]. (3)约束条件不同: RMFS的任务分配需要考虑订单交货时间、服务水平等特殊条件约束. (4)任务分配环境不同: RMFS的任务分配是在动态环境中进行, 比静态环境中的MRTA问题更加复杂.

      RMFS的任务分配问题可以按照广义指派问题进行模型构建, 现有文献主要利用排队论、启发式规则、智能优化算法以及仿真等方法研究MRTA问题, 相关研究文献按照研究方法分类综述如下:

      (1)利用排队论方法

      Zou[28]等以在线零售为背景, 构建了排队网络模型来研究RMFS的任务分配规则问题, 并设计邻域搜索方法寻找最优分配规则, 结果表明基于订单处理速度的分配规则要比随机分配规则更优, 并且邻域搜索方法可以找到接近最优的分配规则, 但文中未对机器人的分配规则进行研究. 在此基础上, Roy[33]等研究了多分区存储模式的RMFS的机器人分配策略, 构建了两阶段排队网络随机模型, 结果表明, 单个存储区应采用按批次分配机器人的方式, 最短队列的分配方式则在多分区存储中系统吞吐量更大, 最多可降低60%的订单拣选时间, 但缺乏对随机模型参数更加广泛的评估研究. Yuan[27]则利用排队网络和共享协议研究了RMFS搬运机器人的任务共享与分配问题.

      (2)利用启发式规则与仿真方法

      Zhou[11]等对RMFS中的MRTA问题进行研究, 提出了同时考虑基于拍卖和聚类策略的平衡启发式机制, 以机器人行走距离最小为目标, 仿真发现平衡启发式机制能缩短机器人行走距离, 提高了机器人利用率, 并且在解的质量相近的情况下, 平衡启发式机制的求解时间降低了5%-15%. 但文献[11]在机器人完全自利、环境已知等条件假设的前提下研究了RMFS的MRTA问题, 与实际RMFS的MRTA问题有一定的差距. Merschformann[29]等则从拣货和补货两方面利用RAWSim-O仿真平台研究了RMFS任务分配, 指出工程人员应该更加注重待拣订单的分配决策问题. Ghassemi[30]则进一步利用仿真的方法对RMFS的任务分配问题进行研究, 比较了分散和集中分配两种任务分配模式, 结果表明, 分散分配在保证解的质量的情况下, 求解速度比集中算法快1-3个数量级. RMFS拣货过程的微观问题同样对拣货效率具有重要影响, Gue[42]利用仿真的方法研究了机器人系统的控制方法, 设计了多机器人分散控制算法, 结果表明分散控制相比集中控制方法更能避免机器人死锁的发生. 值得一提的是, Yoshitake[34]等利用实时全息调度方法研究了RMFS的机器人实时调度问题, 将RMFS的生产率平均分别提高了6.7%(标准仓库)和12.5%(大规模仓库).

      (3)利用智能优化算法

      文献[25]在[11]的基础上研究了RMFS的任务调度问题, 分别利用强化学习和遗传算法进行问题求解. 沈博闻[8]等则利用智能调度算法研究了RMFS的任务分配调度问题, 但对订单的分配处理过于理想化. 袁瑞萍[32]进一步研究了RMFS的任务调度问题, 设计了改进的共同进化遗传算法进行问题求解, 结果表明改进的算法缩短了求解时间(同步拣选模式下算法的求解时间是异步模式下求解时间的50%). 随后的Zhang[35]也利用改进的遗传算法研究了RMFS的机器人分配问题, 与传统的基于规则的调度方法相比, 改进的遗传算法更加有效.

      综上, RMFS的任务分配及调度研究成果丰硕, 主要针对RMFS的MRTA问题的绩效指标评价、策略比较、拣货调度以及任务分配问题进行研究, 但对MRTA与RMFS系统其它问题的协同优化研究不多. RMFS任务分配及调度研究可借鉴传统MRTA问题的研究理论和方法: (1)利用组合拍卖的方法: RMFS中订单、拣选站台、机器人以及货架之间存在复杂的交互关系, 组合拍卖的方法更适合RMFS的任务分配问题[103]. (2)考虑机器人能力: 机器人数量、电量、速度以及停泊点等会影响RMFS的作业效率, 在任务分配及调度研究过程中应予以重点关注, 尤其应考虑机器人电量的影响[2627, 31, 43]. (3)基于机器学习的方法: 强化学习、深度学习等机器学习方法被广泛的用于解决MRTA问题[104], 可将其用于求解RMFS的任务分配及调度问题.

      RMFS的任务分配及调度研究应重点关注以下几个方面的问题: (1)综合研究订单与拣货站台、货架与机器人以及机器人与拣货站台之间的分配, 作为多个双向组合拍卖, 相比传统的拍卖方法更加复杂. (2)考虑订单紧急程度及交货期限, 确定合理的RMFS订单分配及调度规则. (3)考虑特殊情况下RMFS任务分配问题, 如出现订单取消、插单以及紧急订单时的任务动态分配及调度研究, 还应考虑机器人的电量、拥堵等对任务分配及调度的影响. (4)在模型四的基础上构建RMFS任务分配及调度的数学模型, 为RMFS多机器人任务分配及调度研究提供理论基础.

    • 路径规划是为拣货人员规划拣货时的行走路径, 使最终的拣货距离最短. 拣货员的路径规划问题一般视为旅行商问题(Travelling salesman problem, TSP), 人工拣货系统常用穿越、回转、中点、最大间隙等策略规划拣货员的行走路径[1]. 与传统拣货系统不同, RMFS的路径规划是一个多机器人路径规划(Multi-Robot Path Planning, MRPP)问题, 其目的是确保机器人在不发生碰撞、拥堵、死锁以及满足时间约束要求的前提下, 同时对多个机器人进行路径规划, 最终使机器人拣货行走的总距离最短, 从而提高订单拣选的效率[12]. 如图8所示为RMFS的路径规划示意图, 图中以拣货过程(补货过程路径规划类似)为例给出了一条机器人的行走路径, 机器人需要将 $i$ 位置的货架搬运到拣货站台, 然后再将货架送到存储区的 $j$ 位置存储, 再将 $i'$ 位置的货架搬运至拣货站台拣货, 随后再送至 $j'$ 位置存储, 最终回到停泊区等待; RMFS的MRPP问题类似于TSP问题, 需要机器人遍历系统预先分配好的各个位置, 使得机器人行走的路径最短, 此外RMFS的MRPP问题还应考虑机器人避障、电量限制等约束条件.

      图  8  RMFS的路径规划示意图

      Figure 8.  RMFS path planning diagram

      传统的MRPP是一种多旅行商问题(Multi-Travelling salesman problem, MTSP)[105], 其数学模型为:

      $$ {\text{模型五}}\;\;\;\;\min \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{c_{ij}}{x_{ij}}} } $$ (19)
      $$ {\rm{s}}.{\rm{t}}.\;\;\;\;\sum\limits_{j = 2}^n {{x_{1j}} = m} $$ (20)
      $$\sum\limits_{j = 2}^n {{x_{j1}} = m} $$ (21)
      $$\sum\limits_{i = 1}^n {{x_{ij}}} = 1 \;\;\;\;j = 2,3, \cdots ,n$$ (22)
      $$\sum\limits_{j = 1}^n {{x_{ij}}} = 1 \;\;\;\;i = 2,3, \cdots ,n$ $\sum\limits_{i \in S} {\sum\limits_{j \in S} {{x_{ij}}} \leq } \left| S \right| - 1 \;\;\;\;\forall S \subseteq V\backslash \{ 1\} ,S \ne \emptyset $$ (23)
      $${x_{ij}} \in \{ 0,1\} \;\;\;\; \forall (i,j) \in A$$ (25)

      MTSP一般被定义为图 $G = (V,A)$ , $V$ 表示节点集合; $A$ 表示边的集合. 在模型五中, ${c_{ij}}$ 表示旅行所需花费的代价; ${x_{ij}} = 1$ 表示机器人从点 $i$ 到点 $j$ , 否则 ${x_{ij}} = 0$ ; 式(19)为目标函数, 式(20)和(21)表示这 $m$ 个机器人必须回到同一个起始地点; 式(22)、(23)和(25)为分配约束条件; 式(24)为消除子回路的约束条件. MTSP及其各类建模方法可具体参考文献[105].

      MRPP问题的求解方法有精确方法、启发式以及人工智能等[106], 静态路径规划一般利用可视图、Voronoi图、栅格图、人工势场等路径规划方法, 并通过深度优先、广度优先、Dijkstra以及A*和D*等算法求解[107], 动态路径规划一般利用启发式或元启发式[108]、强化学习[109]等智能优化方法求解, 也有学者利用双层模糊逻辑[110]、仿真技术[111]对多机器人路径规划问题进行研究.

      RMFS的路径规划与传统的MRPP问题存在诸多不同, 主要有: (1)复杂程度不同: 传统的MRPP是在开放空间内的路径规划, 较少考虑预设行走路径, RMFS的路径规划分为载货机器人路径规划(在巷道内的路径规划)和空载机器人路径规划(在无限制情况下进行路径规划, 因为空载机器人可在巷道和货架下自由行驶)[3]. (2)约束条件不同: RMFS的路径规划需考虑订单交货时间或优先级等因素. (3)存在任务切换代价: RMFS的路径规划需考虑任务切换的代价, 即机器人存储货架后再搬运下一货架所需行走的时间或距离[3]. (4)优化目标不同: 相比传统的MRPP问题, 可将订单延迟率、任务切换代价等作为优化目标.

      RMFS的MRPP问题可建模为MTSP问题, 已有文献主要利用图论、智能优化、强化学习、精确算法以及启发式方法研究RMFS的路径规划问题, 涉及RMFS的MRPP问题的文献按照研究方法分类综述如下:

      (1)利用图论的方法

      传统拣货系统的路径规划问题通常可利用图论的方法建模[112], 一般是先对RMFS拣货区域进行栅格化的处理, 然后将RMFS的MRPP问题视为栅格地图上的路径规划问题, 例如张丹露[38]针对RMFS的MRPP问题提出了一种基于动态加权地图的方法, 与预约表下改进的A*算法相比, 该方法能够将机器人行走时间降低17.4%.

      (2)利用智能优化算法和强化学习

      由于MRPP问题是NP难题, 一般无法求得最优解, 更多利用智能优化算法求解, 夏清松[39]等利用蚁群算法研究RMFS的路径规划与避障的协同优化问题, 并设计了MRPP的避障规则, 但文中有关机器人转向次数较少的假设不符合实际情况, 且未考虑动态MRPP问题. Lee[44]等对RMFS系统进行了扩展, 用拣取机器人替代拣货员拣取商品, 并将RMFS的拣货过程看作特殊的车辆路径问题(pick, place, and transport vehicle routing problem, PPTVRP)进行了研究, 并利用智能优化算法求解. 值得关注的是Dou[25]等利用强化学习方法研究了RMFS的MRPP问题, 实验结果显示其优化效果与遗传算法相近, 但未进行更广泛的实例测试.

      (3)利用精确算法和启发式规则

      沈博闻[8]和Merschformann[12]利用A*及其改进算法研究了RMFS的MRPP问题, 主要关注生成的路径有无堵塞和死锁, 但未考虑机器人电量对路径规划的影响. Kumar[36]、Zheng[37]、Lee[40]以及于赫年[41]针对无冲突的MRPP问题进行了研究, 主要利用Dijkstra、A*、启发式规则等算法实现了多机器人无冲突的路径规划.

      综上, 上述文献对RMFS的MRPP问题进行了初步研究, 取得了一定的研究成果, 但MRPP与RMFS其它问题的协同优化研究不多, 也很少有文献研究动态情况下RMFS的MRPP问题, 并且当前RMFS的MRPP问题研究一般采用仿真的方法, 没有在理论上给出相应的数学模型.

      RMFS的路径规划研究可借鉴传统MRPP问题的研究理论和方法: (1)利用机器学习方法: 强化学习、神经网络等机器学习方法可将路径规划、避碰、避障、死锁以及协作等问题统一解决, 无须建立路径规划的环境模型和地图[113], 相比传统方法具有更多优势. (2)释放约束条件: 考虑不确定环境及动态情况下的MRPP问题, 即考虑机器人故障、电量、障碍物等因素对MRPP的影响. (3)多类问题协同优化: 将MRPP问题与RMFS的订单分批、任务分配等问题进行协同优化. (4)限定范围的连续路径规划研究: 与传统MRPP问题类似, RMFS的路径规划为一定范围(如图8所示区域)内的连续路径规划问题, 例如Zheng[37]、夏清松[39]等利用栅格图法研究了RMFS在拣货区域内的连续路径规划.

      RMFS路径规划问题在借鉴传统MRPP问题研究的基础上, 应重点关注: (1)设计载货机器人和空载机器人的不同路径规划规则, 尤其考虑空载机器人可在货架下行驶的情况. (2)考虑订单交期、退单、插单、退货以及紧急订单等情况对RMFS的MRPP问题的影响. (3)将强化学习、深度学习等方法用于RMFS的MRPP问题的研究. (4)在模型五的基础上对RMFS的MRPP问题进行研究, 提出符合RMFS实际情况的MRPP理论模型.

    • RMFS系统建模和优化方法主要涉及排队论、图论、机器学习、数据挖掘以及Agent建模等方法, 本节对这些建模和优化方法进行综述, 为RMFS系统的后续研究指明方向.

      (1)排队论方法

      排队论是研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法, RMFS的货位指派、订单分批、任务分配及调度等问题可利用排队论进行研究. 例如Lamballais[3]、Onal[15]、Nigam[4]以及Rong[17]等分别利用排队论对商品和货架的储位指派策略进行了研究; Yu[86]和Hur[87]均构建了传统拣货系统订单分批问题的排队网络评估模型, 为利用排队论研究RMFS的订单分批问题提供了参考; Zou[28]和Roy[33]也都利用排队网络模型研究RMFS的任务分配和机器人分配问题. 在利用排队论方法对RMFS的优化研究中, 主要是针对研究的问题特性构建系统绩效评估的排队网络模型, 并通过仿真对优化策略和排队模型进行有效性验证, 如图9所示为RMFS系统绩效评估的半开放排队网络模型.

      图  9  RMFS绩效评估的半开放排队网络模型

      Figure 9.  Semi-open queueing network for performance estimation of RMFS

      (2)图论方法

      图可直观的表示出事物之间的关系, 传统拣货系统的路径规划问题可利用图论的方式进行表示和研究[1], RMFS的路径规划作为一种多机器人的路径规划问题, 也可利用图论的方法进行研究. 例如张丹露[38]针对RMFS的多机器人路径规划问题提出了一种基于动态加权地图的研究方法, Zheng[37]和夏清松[39]等也利用图的表示方式对多机器人的路径规划问题进行了研究, 如图10为RMFS的路径规划及其图表示.

      图  10  RMFS路径规划及其图表示

      Figure 10.  RMFS path planning and its graph representation

      (3)机器学习方法

      机器学习作为一种基于经验的学习方法, 已经成功地应用于图像识别和自然语言处理等领域, Dou[25]等最先利用强化学习方法研究了RMFS的路径规划问题, 证明了将机器学习方法用于RMFS优化研究的可行性和有效性, Zhang[47]则进一步将强化学习与进化计算组合对RMFS快递分拣仓库布局的自动化设计进行了研究, 此外神经网络[114]、深度学习[115]等机器学习方法也被广泛地用于求解多机器人任务分配、路径规划以及障碍物识别等问题, 例如Li[116]和Zhu[117]分别利用神经网络研究了多机器人的动态路径规划和任务分配问题; Heo[118]等利用深度学习研究工业协作机器人的障碍物识别问题. 基于强化学习的RMFS优化框架如图11所示, 可以看出, RMFS系统中的机器人、货架、商品、订单、拣货/补货站台以及拣货员等要素可视为Agent, 这里的环境为RMFS系统, Agent执行的动作 ${a_t}$ 可以是货位指派、订单分批、任务分配以及路径规划的策略或规则, Agent通过动作 ${a_t}$ 影响环境, 更新环境状态 ${s_t}$ , 并从环境获得反馈 ${r_t}$ [119].

      图  11  基于强化学习的RMFS优化框架

      Figure 11.  RMFS optimization framework based on Reinforcement Learning

      (4)数据挖掘方法

      RMFS的商品和货架储位指派需考虑商品销售的关联关系和畅销程度, 订单分批也需知道商品之间的关联强度, 任务分配和路径规划则需预测任务及资源的可用性, 这些问题均可用聚类、预测等数据挖掘方法进行研究. 例如Chen[78]和Araidah[89]分别利用聚类的方法对订单分批问题进行了研究, Pang[69]则进一步利用关联规则方法挖掘商品之间的需求关系, 最终实现了商品储位指派优化.

      (5)Agent建模方法

      基于Agent的建模方法(Agent-based modeling, ABM)是一种分布式的建模方法, 可对主体的微观行为进行刻画, 并可以观察宏观层面涌现的系统特征, 更适合对复杂系统的建模[120]. RMFS作为分布式多Agent系统, 可利用ABM方法进行建模研究, 将整个拣货系统中的移动货架、机器人、拣选(补货)站台等看作自主决策的Agent, 每个Agent都具有特定的行为规则、特征和属性, 以一定规则在拣货系统中独立决策、自主运行, 并与系统中其它Agent和环境进行交互. ABM的目标是对这些规则和交互关系进行调整和优化, 实现整个拣货系统的状态最优. 基于Agent的RMFS多机器人运作结构如图12所示, ABM可对RMFS的Agent个体与拣货系统整体进行协调优化[121]. 众多文献从建模分析[122]、死锁、路径规划[123]等角度通过ABM方法研究多机器人系统, 利用ABM方法对RMFS进行建模还需考虑机器人之间的协同合作、避障、时间约束等问题. Alphabet Soup[124]、RAWSim-O[125]等开源RMFS仿真平台均基于ABM方法, Bozer[45]等也利用ABM方法验证了RMFS相比传统拣货系统具有更高的拣货效率和柔性. 此外, Swarm、Repast、Netlogo等ABM的建模与仿真平台也为RMFS的优化研究提供了可靠的技术支撑.

      图  12  基于Agent的RMFS多机器人运作结构

      Figure 12.  Agent-based multi-robot operation structure of RMFS

      (6)其它方法

      值得特别关注的是, Petković[48]给出了研究RMFS的全新方法, 文章利用隐马尔科夫模型和心理理论对RMFS拣货过程中人的意图进行评价, 并通过虚拟现实技术验证了模型的有效性, 这涉及到机器学习、心理学等学科, 表明了多学科交叉也是RMFS未来重要的研究方法, 例如Keung[126]等利用基于云的网络物理系统研究了RMFS的避障问题, 进一步说明了学科交叉研究的可行性和必要性.

    • 有关RMFS的研究起步较晚, 现有文献研究主要集中在系统分析、设计优化以及运作规划与控制方面, Azadeh[127]给出了系统分析、设计优化、运作策略以及系统比较四个主要的研究方向, 本文则提出以下更为具体的研究方向.

    • 从提升RMFS系统拣货效率的角度出发, 针对RMFS的仓库布局及配置设计和各种设计方案的系统绩效评估, 提出的进一步的研究方向有: 1)仓库存储区形状对拣货效率的影响研究. RMFS存储区普遍为矩形布置方式(例如图1(b)所示), 在拣货和补货站台位置固定的情况下, 仓库存储区的长宽比一方面可能会影响拣货过程机器人的路径规划和拥堵情况, 导致拣货效率下降; 另一方面当拣货站台一侧对应的存储区宽度较窄时, 将造成较多存储畅销商品的货架只能存储在距离拣货站台较远的储位, 最终导致拣货过程机器人搬运货架的距离加长、拣货效率降低. 因此, 对仓库存储区布局的优化是提升RMFS拣货效率的重要研究方向. 2)拣货站台与补货站台的比例对拣货效率的影响研究. 拣货站台与补货站台的数量比对订单拣选效率、拣货与补货的平衡关系以及拣货/补货员的作业负荷都具有重要影响, 例如拣货站台较少, 则可能出现拣货员作业负荷过大、订单拣选时间长以及部分补货站台空闲的情况; 若补货站台较少, 则会出现补货员作业负荷过大、库存商品短缺、订单拣选时间长以及部分拣货站空闲的情况; 因此, 拣货站台和补货站台比例优化对提升RMFS的拣货效率具有重要意义. 3)机器人数量、速度、利用率、待命停泊点以及充电策略等因素对拣货效率的影响研究. 在拣货过程中, 机器人的数量和速度决定了一次性最多能搬运的货架数量和机器人的行走时间; 机器人停泊点则对连续作业机器人的行走距离具有重要影响; 机器人充电策略则决定了机器人充电过程的调度方式, 对机器人的可用率和货架搬运效率都具有重要影响. 因此, 在考虑拣货成本、资源限制及利用率等因素的情况下, 如何合理配置机器人数量、速度以及规划机器人的充电策略将是未来的重要研究方向. 4)机器人结构设计与操作效能的提升研究. RMFS机器人的结构设计可分为硬件结构设计和控制系统结构设计, 其中硬件结构设计决定了机器人搬运货架的方式、可承载的最大重量、行驶速度以及充电方式, 控制系统结构设计则涉及机器人控制方式(集中控制或分散控制)、避障规则、充电策略以及通信切换等问题. 操作效能的提升涉及货架的一体化设计、拣货/补货人员的技能熟练程度等人因问题研究. 这方面涉及运筹优化、机械设计以及人因工程的交叉学科研究, 对提升RMFS拣货效率具有重要意义.

    • 从减少理想化假设条件、考虑随机因素影响和动态情况出发, 提出的主要研究方向有: 1)考虑动态情况下的货位指派、订单分批、任务分配、路径规划研究. 相比静态问题的研究, 动态货位指派比一次性货位优化更具优势, 更能反映拣货过程随时间的变化规律; 动态货位指派也更加符合实际情况, 例如在线订单分批能根据客户的动态需求进行更加合理的订单分批. 因此, 针对RMFS的商品和货架储位动态指派、在线订单分批、动态任务分配以及动态路径规划等问题的研究将是重要的优化方向. 2)考虑机器人死锁、损坏等突发情况的研究. 在拣货过程中, 机器人出现故障是难免的, 为了保证拣货过程顺利进行并提高机器人的利用率, 对拣货过程机器人死锁、损坏等突发情况的研究十分必要. 3)考虑订单取消、插单、退货等情况的研究. 在电商环境下, 客户可能因多种原因出现取消订单、催单(订单加急)以及退货等情况, 虽然已有文献对RMFS的静态订单分批问题进行了初步研究, 但未考虑订单取消、插单等情况, 建议在RMFS拣货优化过程中考虑订单取消、插单、退货等情况, 此外订单取消、插单对系统绩效的影响评估也可作为一个重点研究方向. 4)考虑拣货和补货人员工作负荷、人因以及技能熟练程度对拣货效率的影响研究. 拣货和补货人员的工作负荷、人因以及技能熟练程度对拣货效率具有重要影响, 例如较少的工作负荷容易造成拣货和补货人员空闲, 较多则会引发疲劳、压力过大等情况的出现; 长时间固定姿势的劳作容易造成人体机能和器官的损伤(例如拣货和补货人员经常弯腰); 拣货人员和补货人员的技能熟练程度决定了拣货站台和补货站台的服务速率, 对站台区域的拥堵情况和拣货效率具有重要影响. 虽然人因、技能熟练程度等指标难以量化, 但这方面的研究却十分必要.

    • RMFS的调度问题涉及货架、机器人、订单、商品、拣货站台以及补货站台等多种资源, 针对RMFS系统的资源调度问题, 提出的主要研究方向有: 1)考虑需求关联性的商品及货架储位调度研究. 将需求关联性强的商品指派到相同货架存储, 可减少货架搬运次数; 将存储畅销商品的货架指派到靠近拣货站台的位置存储, 可降低货架搬运距离, 因此考虑需求关联性的商品及货架的储位调度研究是提高拣货效率的重要优化方向, 这方面研究重点关注商品需求关联性计算, 货架储位动态调度等. 2)订单的分批策略及规则研究. 是采用在线订单分批还是离线订单分批、或者同时考虑这二者的混合策略, 是将订单分配给拣货站台后再分批还是先分批再分配给拣货站台, 是根据订单的相似程度分批还是根据搬运的货架分批, 都是目前RMFS订单分批优化中亟需解决的问题; 并且在线订单分批需考虑订单的动态变化关系, 相比离线订单分批更加复杂. 3)机器人与货架、拣货/补货站台以及充电设施的协同调度策略及规则研究. 机器人是RMFS的主要搬运工具, 在拣货过程中, 机器人与货架、拣货/补货站台以及充电设施之间存在复杂的协同调度关系, 包括机器人任务分配和充电设施分配调度等一系列问题, 因此, 机器人与货架、拣货/补货站台以及充电设施的协同调度策略及规则研究是RMFS系统优化必须面对的问题.

    • RMFS作为复杂决策系统, 货位指派、订单分批、任务分配以及路径规划等问题之间存在紧密的内在联系, 例如任务分配之前必须完成货位指派和订单分批, 路径规划必须考虑商品及货架的存储位置. 因此, 多个问题的协同优化更加符合RMFS的运作过程, 是实现系统全局最优的关键, 将成为RMFS优化研究的重要趋势, 但多个问题的协同优化研究在问题描述、模型构建、算法设计以及问题求解等方面都更加复杂, 后续可重点对多目标(问题)协同优化模型构建、算法设计及问题求解进行深入研究.

    • 针对RMFS的优化方法研究提出两点主要的研究方向: 1)在现有的RMFS仿真软件的基础上应开发新的算法和优化模块. RMFS的系统效能评估、各因素对拣货效率的影响等问题可能无法构建精确的优化模型, 只能通过离散仿真的方法进行研究. 因此, 类似Alphabet Soup、RAWSim-O等仿真软件的开发和应用是必不可少的. 2)设计针对RMFS的求解大规模问题的智能优化算法. RMFS的应用背景通常是大型电商企业(例如亚马逊、京东), 系统所包含的货架、机器人、订单等资源的数量庞大, 尤其在面临类似“双十一”等促销活动时, 对RMFS的运作效率和服务质量都是极大的挑战, 因此, 研究求解大规模问题的智能优化算法尤为重要.

    • 随着通信和信息技术的发展, 人工智能发展进入了新阶段, 2017年7月国务院发布的《新一代人工智能发展规划》将人工智能定位为国家战略, 明确指出“人工智能技术应用成为改善民生的新途径”、“人工智能成为带动我国产业升级和经济转型的主要动力”. 2014年10月国务院发布的《物流业发展中长期规划(2014—2020年)》中将物流业定义为支撑国民经济发展的基础性、战略性产业, 而RMFS作为一种新型的智能物流仓储系统, 是智能物流的一个重要研究方向, 也是我国物流业降本增效、产业升级的主要动力, 其研究和应用离不开机器学习、多智能体、大数据、计算机视觉及自然语言处理等新一代人工智能技术的支撑. RMFS与新一代人工智能交叉的研究方向有: 1)基于深度强化学习(Deep Reinforcement Learning, DRL)的优化研究. 强化学习能够解决无模型序列决策问题, 但在处理高维变量问题时常常会面临巨大挑战, 而深度学习则具备从高维变量中自动学习表征的能力, DRL则将这两者结合起来, 为RMFS这类复杂高维问题的决策和优化提供了端到端的解决方案, 让RMFS在需求多变的复杂环境中高效完成任务; 此外RMFS是一个典型的多Agent系统, 这些Agent之间相互合作或竞争, 单一Agent系统无法满足RMFS系统决策的需要, 因此可进一步基于多主体的深度强化学习(Multi-Agent Deep Reinforcement Learning, MARL)研究RMFS, 对RMFS系统中Agent之间的感知发现、知识获取、竞争合作以及演化进行深入研究, 这将成为RMFS智能优化的研究热点[128]. 2)RMFS机器人操作技能学习研究. RMFS机器人在完成拣货和上架任务时, 需要执行移动、避障、抓取、放置、拆垛与码垛等一系列复杂的动作, RMFS机器人的操作技能、执行动作的精确度和效率是RMFS高效运行的关键, 目前机器人技能大多通过人工预定义的规则实现, 无法应对动态复杂的物流场景, 让RMFS机器人通过与环境交互得到经验数据, 从经验数据中自主学习, 一方面可以让RMFS机器人具有自我优化的能力, 同时让RMFS的任务部署更加灵活和用户友好. RMFS机器人操作技能自主学习涉及构建机器人操作技能模型、设计学习策略等关键问题, 已有文献从动力学与学习算法相结合、DRL等方面开展研究[129], 后续研究可关注RMFS机器人高效学习和模型的可解释, 在此基础上构建RMFS机器人操作技能学习框架. 3)RMFS系统自主学习能力研究. RMFS机器人在高度动态、复杂多变的环境(商品装卸、货架搬运以及各机器人动态移动)下工作, 经常会出现碰撞、失效、电量不足等突发情况, 如何使RMFS机器人在长期运行中与复杂多变的环境相适应是RMFS的一个研究热点, 这方面涉及到RMFS机器人的环境地图构建与动态维护、重定位及动态场景感知与理解等基础任务能力的研究. 在RMFS的环境表征的研究方面, 可基于数据融合与信息增强, 通过多层次传感器数据融合得到的环境信息来提升RMFS环境表征能力, 为RMFS机器人提供更可靠的决策信息, 在此基础上利用DRL的方法在RMFS机器人与环境的交互的基础上进行学习, 提升RMFS机器人自主环境适应能力, 这需要解决机器人基于在线获取的弱标注数据进行学习这一问题, 它是使RMFS机器人具有长期自主环境适应能力的关键; 在场景感知与理解方面建议基于深层次语义信息挖掘来获取RMFS场景中物体间的属性关联, 来提升RMFS移动机器人场景认知能力[130]. 4)基于计算机视觉技术和自然语言处理的优化研究. 近年来, 机器视觉和自然语言处理研究均取得了重大的理论突破, 并分别成功地运用于自动驾驶和机器翻译等领域, 计算机视觉技术可提升RMFS机器人识别商品的准确度; 基于语音识别的人机交互技术可提升拣货效率, 例如RMFS机器人通过语音与拣货员(补货员)交互降低拣货(补货)差错. 5)基于大数据的优化研究. 大数据是实现智能决策的重要支撑, 大数据分析可实现客户画像构建、商品销售分析以及RMFS系统存储决策优化, 因而是RMFS优化研究的重要方向, 例如可利用数据挖掘的聚类和关联规则等算法得到商品销售频率和需求关系性, 来优化RMFS的订单分批和货位指派.

    • RMFS作为一种新型的“物至人”拣货系统, 相比传统拣货系统具有拣货效率高、柔性强等诸多优势, 随着电子商务的迅猛发展, RMFS已在物流行业取得成功的应用, 同时针对RMFS的优化研究已成为热点研究领域. 本文主要针对RMFS的货位指派、订单分批、任务分配、路径规划以及建模方法等问题进行了文献总结和述评, 并给出了未来的研究方向. 以上工作抛砖引玉, 以期促进RMFS拣货效率的进一步提升, 使其更好地为电子商务的订单拣选服务.

WeChat 关注分享

返回顶部

目录

    /

    返回文章
    返回