Research on Path Optimization Modeling and Algorithm of WorkshopHandling Robotwith Time Window

doi:10.12005/orms.2020.0118

Abstract

Abstract: This paper takes the workshop handling robot as a research object, and solves the path optimization problem of pickup and delivery with the time window. This paper proposes a method of reinforcement learning genetic-ant colony hybrid algorithm(RLGA). Firstly, the number of initial handling robots is solved by scanning method, and the geometric center of sub-path nodes is set as virtual node. The ant colony algorithm embedded with genetic operator is used to solve the optimal connection virtual node. Secondly, the optimal sub-path is solved by using the algorithm of reinforcement learning.Finally, the weighted sum of the basic cost, transportation cost and time penalty cost is taken as the target solution, and the optimal solution satisfying the constraint condition is obtained. The superiority of the reinforcement learning genetic-ant colony hybrid algorithm is verified by comparing with the results of the benchmark problem.

Key words: handling robot, reinforcement learning genetic-ant colony hybrid algorithm, path optimization

摘要： 本文以车间搬运机器人为研究对象,在考虑时间窗的前提下,求解机器人进行物料配送和成品回收场景下的路径优化问题。提出一种强化学习遗传蚁群算法,首先利用扫描法求解初始搬运机器人的数量,并将子路径节点的几何中心设置为虚拟节点,利用嵌入遗传算子的蚁群算法求解连接虚拟节点的最优路径,再利用强化学习算法求解子路径的最优结果;最后将基本成本、运输成本和时间惩罚成本的加权和作为目标解,并最终求出满足约束条件的最优解。通过与基准问题求解结果对比,验证了强化学习遗传蚁群算法的优越性。

关键词: 搬运机器人, 强化学习遗传蚁群算法, 路径优化

CLC Number:

TP18

REN Jian-feng, YE Chun-ming, YANG Feng. Research on Path Optimization Modeling and Algorithm of WorkshopHandling Robotwith Time Window[J]. Operations Research and Management Science, 2020, 29(5): 52-60.

任剑锋, 叶春明, 杨枫. 带时间窗的车间搬运机器人路径优化建模及算法研究[J]. 运筹与管理, 2020, 29(5): 52-60.

References

[1] 周济.智能制造——“中国制造2025”的主攻方向[J].中国机械工程,2015,26(17):2273-2284.
[2] Panchu K P, Rajmohan M, Sumalatha M R, et al. Route planning integrated multi objective task allocation for reconfigurable robot teams using genetic algorithm[J]. Journal of Computational and Theoretical Nanoscience, 2018, 15(2): 627-636.
[3] 李妍峰,高自友,李军.动态网络车辆路径派送问题研究[J].管理科学学报,2014,17(8):1-9.
[4] Baizid K, Chellali R, Yousnadj A, et al. Genetic algorithms based method for time optimization in robotized site[C]//Intelligent Robots and Systems (IROS), 2010 IEEE/RSJ International Conference on. IEEE, 2010: 1359-1364.
[5] Baizid K, Yousnadj A, Meddahi A, et al. Time scheduling and optimization of industrial robotized tasks based on genetic algorithms[J]. Robotics and Computer-Integrated Manufacturing, 2015, 34: 140-150.
[6] Qian Z, Wang G, Wang J, et al. Route planning of uav based on improved ant colony algorithm[C]// Internationnal Conference on Longistics Engineering, Management and Computer Science(LEMCS 2015).2015.
[7] 徐林,范昕炜.基于改进遗传算法的餐厅服务机器人路径规划[J].计算机应用,2017,37(07):1967-1971.
[8] 梁凯,陈志军,闫学勤.移动机器人路径规划仿真研究[J/OL].现代电子技术,2018(17):167-172.
[9] Gang L I, Jia-xin Y U, Dao-tong G U O, et al. ROBOT route planning and simulation based on improved genetic algorithm[J]. Computing Technology and Automation, 2015, 2: 006.
[10] 裴振兵,陈雪波.改进蚁群算法及其在机器人避障中的应用[J].智能系统学报,2015,10(1):90-96.
[11] 赵宏才,郭佳乐,徐肖鲸,刁少文.基于模糊蚁群算法的移动机器人轨迹规划研究[J].计算机仿真,2018,35(5):318-321.
[12] Lu E H C, Yang Y W, Su Z L T. Ant colony optimization solutions for logistic route planning with pick-up and delivery[C]//Systems, Man, and Cybernetics(SMC), 2016 IEEE International Conference on. IEEE, 2016: 000808-000813.
[13] 王辉,王景良,朱龙彪,邵小江,王恒.基于改进蚁群算法的泊车系统路径规划[J].控制工程,2018,25(2):253-258.
[14] 张建同,宋玉坚,叶春明.多堆场集装箱卡车路径规划的混合蚁群算法[J].工业工程与管理,2017,22(2):89-96.
[15] 王春颖,刘平,秦洪政.移动机器人的智能路径规划算法综述[J/OL].传感器与微系统,2018(8):5-8.
[16] Kober J, Peters J. Reinforcement learning in robotics: asurvey[J]. International Journal of Robotics Research, 2013, 32(11): 1238-1274.
[17] 于乃功,默凡凡.基于深度自动编码器与Q学习的移动机器人路径规划方法[J].北京工业大学学报,2016,42(5):668-673.
[18] 高乐,马天录,刘凯,张宇轩.改进Q-Learning算法在路径规划中的应用[J].吉林大学学报(信息科学版),2018,36(4):439-443.
[19] 陈自立,徐娅萍,顾立彬.基于模糊Q学习算法的AGV路径规划研究[J].制造业自动化,2012,34(11):4-6,16.
[20] 王付宇,叶春明,王涛,赵晶晶.震后伤员救援车辆两阶段规划模型及算法研究[J].管理科学学报,2018,21(2):68-79.
[21] 符卓,刘文,邱萌.带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法[J].中国管理科学,2017,25(5):78-86.
[22] 马华伟,范奉伟,胡笑旋.基于禁忌搜索算法的甩挂运输路径规划问题研究[J].中国管理科学,2016,24(S1):194-198.
[23] Polydoros A S, Nalpantidis L. Survey of model-based reinforcement learning: applications on robotics[J]. Journal ofIntelligent & Robotic Systems, 2017, 86: 1-21.
[24] Duguleana M, Mogan G. Neural networks based reinforcementlearning for mobile robots obstacle avoidance[J]. Expert Systemswith Applications An InternationalJournal, 2016, 62: 104-115.
[25] Wang H F, Chen Y Y. A genetic algorithm for the simultaneous delivery and pickup problems with time window[J]. Computers& Industrial Engineering(S0360-8352), 2012, 62(1): 84-95.
[26] Wang C, Zhao F, Mu D, et al. Simulated annealing for a vehicle routing problem with simultaneous pickup-delivery and time windows[C]// Ifip International Conference on Advances in Production Management Systems. Springer, Berlin, Heidelberg, 2013.