基于改进遗传算法的货箱机器人拣选路径规划

doi:10.16182/j.issn1004731x.joss.22-0084

摘要/Abstract

摘要：

针对智能仓库中新型“货箱到人”拣选模式下多个货箱机器人拣选路径规划问题，给出了一种新的优化模型和改进遗传算法。基于货箱机器人的拣选方式及特点，将其转化为非对称车辆路径问题，以机器人总拣选路径最短和完成时间最少为双目标建立混合整数规划模型，设计改进的混合遗传算法对模型进行求解，并通过大规模算例验证了算法的有效性与稳定性。算例计算结果表明：所建模型及算法提高了货箱机器人的拣选效率，降低了运行成本。

关键词: 智能仓库, 货箱拣选机器人, 双目标路径规划, 非对称车辆路径问题, 混合遗传算法

Abstract:

Under the new "container-to-person" picking mode in intelligent warehouses, a new optimization model and its improved genetic algorithm are proposed to solve the picking path planning problem of multiple container robots. According to the picking mode and characteristics of container robots, the picking path planning problem is transformed into an asymmetric vehicle routing problem, and a mixed integer programming model is established with bi-objectives of the shortest total picking path and the least completion time. A hybrid genetic algorithm is designed to solve this model, and the effectiveness and stability of the algorithm are verified through large-scale examples. The computational results demonstrate that the picking efficiency of container robots is improved by the proposed model and its algorithm, and their total picking cost is reduced.

Key words: intelligent warehouse, container robots for picking, bi-objective path planning, asymmetric vehicle routing problem, hybrid genetic algorithm

中图分类号:

TP242

吴玉文, 牛智越, 李珍萍. 基于改进遗传算法的货箱机器人拣选路径规划[J]. 系统仿真学报, 2023, 35(5): 1086-1097.

Yuwen Wu, Zhiyue Niu, Zhenping Li. Picking Path Planning of Container Robots Based on Improved Genetic Algorithm[J]. Journal of System Simulation, 2023, 35(5): 1086-1097.

图/表 14

图1

图2

图3

图4

表1

表2

表3

图5

图6

图7

图8

表4

表5

表6

参考文献 17

1	夏清松, 唐秋华, 张利平. 多仓储机器人协同路径规划与作业避碰[J]. 信息与控制, 2019, 48(1): 22-28, 34.
	Xia Qingsong, Tang Qiuhua, Zhang Liping. Cooperative Path Planning and Operation Collision Avoidance for Multiple Storage Robots[J]. Information and Control, 2019, 48(1): 22-28, 34.
2	Jose K, Pratihar D K. Task Allocation and Collision-Free Path Planning of Centralized Multi-robots System for Industrial Plant Inspection Using Heuristic Methods[J]. Robotics and Autonomous Systems (S0921-8890), 2016, 80: 34-42.
3	冯国强, 赵晓林, 高关根, 等. 基于A^*蚁群算法的无人机航路规划[J]. 飞行力学, 2018, 36(5): 49-52, 57.
	Feng Guoqiang, Zhao Xiaolin, Gao Guangen, et al. Path Planning of UAVs Using A^* Ant Colony Algorithm[J]. Flight Dynamics, 2018, 36(5): 49-52, 57.
4	赵萍, 雷新宇, 陈波芝, 等. 基于TI-A^*的多机器人动态规划协调方法研究[J]. 系统仿真学报, 2019, 31(5): 925-935.
	Zhao Ping, Lei Xinyu, Chen Bozhi, et al. TI-A* Based Multi-robot Dynamic Planning and Coordination Method[J]. Journal of System Simulation, 2019, 31(5): 925-935.
5	王志中. 基于改进蚁群算法的移动机器人路径规划研究[J]. 机械设计与制造, 2018(1): 242-244.
	Wang Zhizhong. Path Planning for Molile Robot Based on Improved Ant Colony Algorithm[J]. Machinery Design & Manufacture, 2018(1): 242-244.
6	胡春阳, 姜平, 周根荣. 改进蚁群算法在AGV路径规划中的应用[J]. 计算机工程与应用, 2020, 56(8): 270-278.
	Hu Chunyang, Jiang Ping, Zhou Genrong. Application of Improved Ant Colony Optimization in AGV Path Planning[J]. Computer Engineering and Applications, 2020, 56(8): 270-278.
7	张晓莉, 杨亚新, 谢永成. 改进的蚁群算法在机器人路径规划上的应用[J]. 计算机工程与应用, 2020, 56(2): 29-34.
	Zhang Xiaoli, Yang Yaxin, Xie Yongcheng. Application of Improved Ant Colony Algorithm in Robot Path Planning[J]. Computer Engineering and Applications, 2020, 56(2): 29-34.
8	曹新亮, 王智文, 冯晶, 等. 基于改进蚁群算法的机器人全局路径规划研究[J]. 计算机工程与科学, 2020, 42(3): 564-570.
	Cao Xinliang, Wang Zhiwen, Feng Jing, et al. Global Path Planning of Robots Based on Improved Ant Colony Algorithm[J]. Computer Engineering & Science, 2020, 42(3): 564-570.
9	陶重犇, 雷祝兵, 李春光, 等. 基于改进模拟退火算法的搬运机器人路径规划[J]. 计算机测量与控制, 2018, 26(7): 182-185.
	Tao Zhongben, Lei Zhubing, Li Chunguang, et al. Path Planning of Handling Robot Based on Improved Simulated Annealing Algorithm[J]. Computer Measurement & Control, 2018, 26(7): 182-185.
10	巩敦卫, 曾现峰, 张勇. 基于改进模拟退火算法的机器人全局路径规划[J]. 系统仿真学报, 2013, 25(3): 480-483, 488.
	Gong Dunwei, Zeng Xianfeng, Zhang Yong. Global Path Planning Method of Robot Based on Modified Simulated Annealing Algorithm[J]. Journal of System Simulation, 2013, 25(3): 480-483, 488.
11	Nazarahari M, Khanmirza E, Doostie S. Multi-objective Multi-Robot Path Planning in Continuous Environment Using an Enhanced Genetic Algorithm[J]. Expert Systems with Applications (S0957-4174), 2019, 115: 106-120.
12	裴以建, 杨亮亮, 杨超杰. 基于一种混合遗传算法的移动机器人路径规划[J]. 现代电子技术, 2019, 42(2): 183-186.
	Pei Yijian, Yang Liangliang, Yang Chaojie. Mobile Robot Path Planning Based on A Hybrid Genetic Algorithm[J]. Modern Electronics Technique, 2019, 42(2): 183-186.
13	任剑锋, 叶春明, 杨枫. 带时间窗的车间搬运机器人路径优化建模及算法研究[J]. 运筹与管理, 2020, 29(5): 52-60.
	Ren Jianfeng, Ye Chunming, Yang Feng. Research on Path Optimization Modeling and Algorithm of Workshop Handling Robot with Time Window[J]. Operations Research and Management Science, 2020, 29(5): 52-60.
14	张丹露, 孙小勇, 傅顺, 等. 智能仓库中的多机器人协同路径规划方法[J]. 计算机集成制造系统, 2018, 24(2): 410-418.
	Zhang Danlu, Sun Xiaoyong, Fu Shun, et al. Cooperative Path Planning in Multi-robots for Intelligent Warehouse[J]. Computer Integrated Manufacturing Systems, 2018, 24(2): 410-418.
15	张海军, 张博, 岳溥庥, 等. 基于混合遗传算法的多巷道间移动拣选优化[J]. 计算机工程与应用, 2014, 50(16): 243-249.
	Zhang Haijun, Zhang Bo, Yue Puxiu, et al. Order Picking Optimization in Multiple Aisles Based on Hybrid Genetic Algorithm[J]. Computer Engineering and Applications, 2014, 50(16): 243-249.
16	Vigo D. A Heuristic Algorithm for the Asymmetric Capacitated Vehicle Routing Problem[J]. European Journal of Operational Research (0377-2217), 1996, 89(1): 108-126.
17	李锋, 魏莹. 求解随机旅行时间的C-VRP问题的混合遗传算法[J]. 系统管理学报, 2014, 23(6): 819-825, 831.
	Li Feng, Wei Ying. Hybrid Genetic Algorithm for Capacitated Vehicle Routing Problem with Stochastic Travel Time[J]. Journal of Systems & Management, 2014, 23(6): 819-825, 831.

机器人编号	路径	路径长度/m	完成时间/s
目标值		591	125
1	0-13-6-18-12-1-0	116	116
2	0-17-21-4-3-24-0	116	116
3	0-28-25-8-26-23-0	90	90
4	0-9-10-29-20-16-0	70	70
5	0-11-27-22-15-19-0	74	74
6	0-30-2-14-5-7-0	125	125

算法	机器人编号	路径	路径长度/m	完成时间/s
SA- GA	1	0-6-18-12-8-1-0	140	140
	2	0-27-16-15-20-9-0	94	94
	3	0-10-29-30-2-14-0	101	101
	4	0-28-26-25-24-19-0	108	108
	5	0-11-23-17-21-7-0	88	88
	6	0-22-13-5-4-3-0	140	140
	目标值		671	140
SA	1	0-9-2-25-16-20-0	108	108
	2	0-11-21-14-5-4-0	124	124
	3	0-30-17-6-22-8-0	124	124
	4	0-23-12-28-10-18-0	98	98
	5	0-7-19-13-27-24-0	116	116
	6	0-29-26-31-3-15	123	123
	目标值		693	124
GA	1	0-14-7-19-13-2-0	116	116
	2	0-10-30-21-17-3-0	118	118
	3	0-6-5-15-31-4-0	160	160
	4	0-20-12-28-16-24-0	74	74
	5	0-18-22-8-11-23-0	94	94
	6	0-29-26-9-27-25-0	108	108
	目标值		670	160
CW	1	0-27-9-13-19-2-0	162	162
	2	0-5-3-31-15-7-0	159	159
	3	0-14-25-4-6-17-0	178	178
	4	0-30-21-16-26-29-0	122	122
	5	0-18-22-8-11-10-0	72	72
	6	0-12-28-23-24-20-0	86	86
	目标值		779	178

货箱数量	最大货架命中货箱数量	最大承载货箱数量	目标函数1		目标函数2		Gap1/%	Gap2/%
货箱数量	最大货架命中货箱数量	最大承载货箱数量	算法1(obj1)	算法2 (obj2)	算法1 (obj3)	算法2 (obj4)	Gap1/%	Gap2/%
avg							4.85	1.82
100	1	5	1 599	1 750	122	127	9.44	4.10
110	1	5	1 808	1 894	116	120	4.76	3.45
120	1	5	1 955	1 986	123	124	1.59	0.81
130	1	5	2 118	2 150	124	124	1.51	0
140	1	5	2 257	2 362	119	118	4.65	-0.84
150	1	5	2 418	2 591	118	122	7.15	3.39

货箱数量	最大货架命中货箱数量	最大承载货箱数量	目标函数1		目标函数2		Gap1/%	Gap2/%
货箱数量	最大货架命中货箱数量	最大承载货箱数量	算法1 (obj1)	算法2 (obj2)	算法1 (obj3)	算法2 (obj4)	Gap1/%	Gap2/%
avg							2.12	2.16
100	2	5	1 616	1 637	117	127	1.30	8.55
100	3	5	1 685	1 741	123	153	3.32	24.39
100	4	5	1 762	1 706	124	124	-3.18	0
120	2	5	1 872	1 951	125	120	4.22	-4.00
120	3	5	1 853	1 938	126	114	4.59	-9.52
120	4	5	2 024	2 082	119	119	2.87	0
150	2	5	2 371	2 403	116	116	1.35	0
150	3	5	2 275	2 358	119	119	3.65	0
150	4	5	2 345	2 368	119	119	0.98	0

货箱数量	最大货架命中货箱数量	最大承载货箱数量	目标函数1		目标函数2		Gap1/%	Gap2/%
货箱数量	最大货架命中货箱数量	最大承载货箱数量	算法1 (obj1)	算法2 (obj2)	算法1 (obj3)	算法2 (obj4)	Gap1/%	Gap2/%
avg							4.78	6.37
100	1	6	1 447	1 584	122	136	9.47	11.48
100	1	7	1 363	1 497	121	148	9.83	22.31
100	1	8	1 268	1 364	132	138	7.57	4.55
100	2	6	1 424	1 392	134	134	-2.25	0
100	2	7	1 330	1 417	130	136	6.54	4.62
100	2	8	1 187	1 302	123	134	9.69	8.94
100	3	6	1 440	1 423	117	123	-1.18	5.13
100	3	7	1 354	1 368	122	128	1.03	4.92
100	3	8	1 177	1 204	130	124	2.29	-4.62