基于遗传算法和A*算法的多农机协同作业优化方法

doi:10.16182/j.issn1004731x.joss.24-0453

摘要/Abstract

摘要：

针对多农业机械(简称农机)协同作业中的任务分配不均和农机转向路口较多导致时间成本较大问题，提出一种预热策略改进分组遗传算法(pre-heat multi grouped genetic algorithm， PHMGA)与转向约束A*算法(turn A*， tA*)相结合的任务规划方法。PHMGA基于已知环境为每台农机分配任务，通过考虑行驶、作业及转向距离的代价目标函数确保任务量均衡，并设计多种算子和策略，以搜寻近似最优解。tA*算法则用于选择田间路径，通过转向惩罚规避转向路口较多的复杂区域，进一步缩短作业时间。仿真结果表明：所提算法有效均衡了每台农机的工作量并显著降低了作业时间和等待时间，相比传统算法分别减少了5%和56%~67%。

关键词: 农业机械, 改进分组遗传算法, 改进A*算法, 多机协同作业规划, 任务分配, 路径规划

Abstract:

To address the uneven task distribution among multiple agricultural machines (referred to as farm machinery) and the high time cost due to numerous turning points at intersections, this paper proposes a task planning method that combines a pre-heat multi grouped genetic algorithm (PHMGA) with the turn A* algorithm (tA*). PHMGA allocates tasks to each piece of farm machinery based on the known environment, ensuring balanced workload through a cost objective function that considers travel, operation, and turning distances. It also designs various operators and strategies to search for near-optimal solutions. The tA* algorithm is used to select paths in the fields, avoiding complex areas with many turning points through turning penalties, thereby further reducing operation time. Simulation results show that our proposed method effectively balances the workload among the farm machinery and significantly reduces operation and waiting times, achieving a reduction of 5% and 56%~67% respectively compared to traditional methods.

Key words: agricultural machines, improved multi-group genetic algorithm, improved A* algorithm, multi-machine collaborative operation planning, task assignment, path planning

中图分类号:

TP391.9

于逸然,赖惠成,高古学等 . 基于遗传算法和A^*算法的多农机协同作业优化方法[J]. 系统仿真学报, 2025, 37(9): 2397-2408.

Yu Yiran,Lai Huicheng,Gao Guxue,et al . Optimization Method for Multi Agricultural Machinery Collaborative Operation Based on Genetic Algorithm and A * Algorithm[J]. Journal of System Simulation, 2025, 37(9): 2397-2408.

图/表 17

图1

图2

图3

图4

图5

图6

图7

图8

表1

表2

图9

表3

不同权重的实验结果

权重	任务分配结果				$∑ j = 1 M S j$ /km	R	G
权重	农机1	农机2	农机3	农机4	$∑ j = 1 M S j$ /km	R	G
α=1，β=0，γ=0	0→7→8→0	0→5→9→0	0→2→4→6→ 10→11→12→0	0→1→3→0	22.08	384.291	134.180
α=0，β=1，γ=0	0→12→3→2→0	0→11→5→0	0→10→4→ 7→9→0	0→8→6→1→0	37.255	0.011	8.514
α=0，β=0，γ=1	0→7→10→3→0	0→2→5→9→0	0→1→4→8→0	0→11→6→12→0	34.219	32.813	0.003
α=0.6，β=0.2，γ=0.2	0→12→2→3→0	0→1→4→8→0	0→5→6→ 10→9→0	0→7→11→0	30.977	1.911	0.065
α=0.2，β=0.6，γ=0.2	0→7→5→3→0	0→6→10→ 9→8→0	0→11→4→0	0→12→2→1→0	30.253	0.459	1.703
α=0.2，β=0.2，γ=0.6	0→5→11→0	0→9→10→ 6→4→0	0→1→8→7→0	0→12→2→3→0	29.403	0.015	4.786
α=0.33，β=0.33，γ=0.33	0→5→6→ 10→9→0	0→3→2→12→0	0→8→4→1→0	0→7→11→0	30.977	1.911	0.065

表3

图10

图11

表4

表5

图12

参考文献 25

[1]	国家统计局. 中国统计年鉴——2023[EB/OL]. [2024-04-15]. .
[2]	习近平. 加快建设农业强国推进农业农村现代化[J]. 求是, 2023(6): 4-17.
[3]	刘成良, 贡亮, 苑进, 等. 农业机器人关键技术研究现状与发展趋势[J]. 农业机械学报, 2022, 53(7): 1-22, 55.
	Liu Chengliang, Gong Liang, Yuan Jin, et al. Current Status and Development Trends of Agricultural Robots[J]. Transactions of the Chinese Society for Agricultural Machinery, 2022, 53(7): 1-22, 55.
[4]	韩冷, 何雄奎, 王昌陵, 等. 智慧果园构建关键技术装备及展望[J]. 智慧农业(中英文), 2022, 4(3): 1-11.
	Han Leng, He Xiongkui, Wang Changling, et al. Key Technologies and Equipment for Smart Orchard Construction and Prospects[J]. Smart Agriculture, 2022, 4(3): 1-11.
[5]	张振国, 毛建旭, 谭浩然, 等. 重大装备制造多机器人任务分配与运动规划技术研究综述[J]. 自动化学报, 2024, 50(1): 21-41.
	Zhang Zhenguo, Mao Jianxu, Tan Haoran, et al. A Review of Task Allocation and Motion Planning for Multi-robot in Major Equipment Manufacturing[J]. Acta Automatica Sinica, 2024, 50(1): 21-41.
[6]	陈宝童, 王丽清, 蒋晓敏, 等. 群智协同任务分配研究综述[J]. 计算机工程与应用, 2021, 57(20): 1-12.
	Chen Baotong, Wang Liqing, Jiang Xiaomin, et al. Survey of Task Assignment for Crowd-based Cooperative Computing[J]. Computer Engineering and Applications, 2021, 57(20): 1-12.
[7]	Tang Jun, Liu Gang, Pan Qingtao. A Review on Representative Swarm Intelligence Algorithms for Solving Optimization Problems: Applications and Trends[J]. IEEE/CAA Journal of Automatica Sinica, 2021, 8(10): 1627-1643.
[8]	Chakraa Hamza, Guérin François, Leclercq Edouard, et al. Optimization Techniques for Multi-robot Task Allocation Problems: Review on the State-of-the-art[J]. Robotics and Autonomous Systems, 2023, 168: 104492.
[9]	崔炜, 朱发证. 机器人导航的路径规划算法研究综述[J]. 计算机工程与应用, 2023, 59(19): 10-20.
	Cui Wei, Zhu Fazheng. Review of Path Planning Algorithms for Robot Navigation[J]. Computer Engineering and Applications, 2023, 59(19): 10-20.
[10]	Yao Linhui, Sun Zhongyi. Research Progress of Robot Path Planning Algorithm[J]. Current Journal of Applied Science and Technology, 2023, 42(23): 27-41.
[11]	Chakraborty Suprava, Elangovan Devaraj, Padma Lakshmi Govindarajan, et al. A Comprehensive Review of Path Planning for Agricultural Ground Robots[J]. Sustainability, 2022, 14(15): 9156.
[12]	唐昀超, 祁少军, 朱立学, 等. 移动机器人避障运动研究[J]. 系统仿真学报, 2024, 36(1): 1-26.
	Tang Yunchao, Qi Shaojun, Zhu Lixue, et al. Obstacle Avoidance Motion in Mobile Robotics[J]. Journal of System Simulation, 2024, 36(1): 1-26.
[13]	Hu Kewei, Chen Zheng, Kang Hanwen, et al. 3D Vision Technologies for a Self-developed Structural External Crack Damage Recognition Robot[J]. Automation in Construction, 2024, 159: 105262.
[14]	余翔, 姜陈, 段思睿, 等. 改进A^*算法和人工势场法的路径规划[J]. 系统仿真学报, 2024, 36(3): 782-794.
	Yu Xiang, Jiang Chen, Duan Sirui, et al. Path Planning for Improvement of A^* Algorithm and Artificial Potential Field Method[J]. Journal of System Simulation, 2024, 36(3): 782-794.
[15]	Dam Tuan, Chalvatzaki Georgia, Peters Jan, et al. Monte-Carlo Robot Path Planning[J]. IEEE Robotics and Automation Letters, 2022, 7(4): 11213-11220.
[16]	余翔, 邓千锐, 段思睿, 等. 一种多无人机协同优先覆盖搜索算法[J]. 系统仿真学报, 2024, 36(4): 991-1000.
	Yu Xiang, Deng Qianrui, Duan Sirui, et al. A Multi-UAV Collaborative Priority Coverage Search Algorithm[J]. Journal of System Simulation, 2024, 36(4): 991-1000.
[17]	王伟权, 丁鼎, 曹淑艳. 混合变邻域搜索算法求解大规模电动车辆路径优化问题[J]. 系统仿真学报, 2022, 34(4): 910-919.
	Wang Weiquan, Ding Ding, Cao Shuyan. Hybrid Variable Neighborhood Search algorithm for the Multi-trip and Heterogeneous-fleet Electric Vehicle Routing Problem[J]. Journal of System Simulation, 2022, 34(4): 910-919.
[18]	Zhang Yajia, Sun Hongyi, Zhou Jinyun, et al. Optimal Vehicle Path Planning Using Quadratic Optimization for Baidu Apollo Open Platform[C]//2020 IEEE Intelligent Vehicles Symposium (IV). Piscataway: IEEE, 2020: 978-984.
[19]	张莉, 张惠珍, 刘冬, 等. 考虑紧迫度的应急物资调度及粒子群算法求解[J]. 系统仿真学报, 2022, 34(9): 1988-1998.
	Zhang Li, Zhang Huizhen, Liu Dong, et al. Particle Swarm Algorithm for Solving Emergency Material Dispatch Considering Urgency[J]. Journal of System Simulation, 2022, 34(9): 1988-1998.
[20]	Evans J T IV, Pitla S K, Luck J D, et al. Row Crop Grain Harvester Path Optimization in Headland Patterns[J]. Computers and Electronics in Agriculture, 2020, 171: 105295.
[21]	Zhao Xin, Wang Ke, Wu Sixian, et al. An Obstacle Avoidance Path Planner for an Autonomous Tractor Using the Minimum Snap Algorithm[J]. Computers and Electronics in Agriculture, 2023, 207: 107738.
[22]	Worasan Kongkidakhon, Sethanan Kanchana, Pitakaso Rapeepan, et al. Hybrid Particle Swarm Optimization and Neighborhood Strategy Search for Scheduling Machines and Equipment and Routing of Tractors in Sugarcane Field Preparation[J]. Computers and Electronics in Agriculture, 2020, 178: 105733.
[23]	Wang Ning, Yang Xi, Wang Tianhai, et al. Collaborative Path Planning and Task Allocation for Multiple Agricultural Machines[J]. Computers and Electronics in Agriculture, 2023, 213: 108218.
[24]	Singh Alok, Anurag Singh Baghel. A New Grouping Genetic Algorithm Approach to the Multiple Traveling Salesperson Problem[J]. Soft Computing, 2009, 13(1): 95-101.
[25]	Alaya Ines, Solnon Christine, Ghedira Khaled. Ant Colony Optimization for Multi-objective Optimization Problems[C]//19th IEEE International Conference on Tools with Artificial Intelligence(ICTAI 2007). Piscataway: IEEE, 2007: 450-457.

参数	量值
作业宽幅d/m	2.4
农机轴距L/m	3.5
农机作业平均速度v_w/(km/h)	3.5
农机行驶平均速度v_r/(km/h)	15
农机转向平均速度v_turn/(km/h)	2.5
最大转向角θ_max /rad	0.6

农田序号	长度/m	宽度/m
1	173	100
2	133	92
3	139	52
4	111	42
5	73	58
6	97	90
7	120	66
8	103	127
9	115	98
10	74	44
11	225	94
12	49	134

算法	农机编号	作业距离/km	作业时间/h	完成时间/h	等待时间/h
MGA+A*	农机1 农机2 农机3 农机4	10.094 22.452 14.236 19.410	1.908 3.008 2.105 2.954	3.008	1.100
MGA+tA*	农机1 农机2 农机3 农机4	10.230 22.452 14.236 19.486	1.901 3.008 2.105 2.951	3.008	1.107
MOACO+A*	农机1 农机2 农机3 农机4	14.176 17.787 17.201 17.898	2.395 2.431 2.175 3.018	3.018	0.843
MOACO+tA*	农机1 农机2 农机3 农机4	14.276 17.787 17.201 17.898	2.391 2.431 2.175 3.018	3.018	0.843
PHMGA+A*	农机1 农机2 农机3 农机4	16.270 16.906 21.700 18.544	2.534 2.498 2.856 2.595	2.856	0.358
PHMGA+tA*	农机1 农机2 农机3 农机4	16.270 17.026 21.700 18.544	2.534 2.493 2.856 2.595	2.856	0.363