Multi-agricultural Machinery Collaborative Task Assignment Based on Improved Genetic Hybrid Optimization Algorithm Haohao Du , Huicheng Lai, Guxue Gao, Xiaopeng Wen, Yifei Li, Haidong Wang, Guo Zhang 1 College of Information Science and Engineering, Xinjiang University, Urumqi 830017, China 2 Key Laboratory of Signal Detection and Processing, Xinjiang University, Urumqi 830017, China Correspondence: Huicheng Lai. Email: lai@xju.edu.cn Abstract: Agricultural machinery collaboration technology is crucial in improving the efficiency of agricultural machinery utilisation and enhancing the benefits of large-scale production of machinery fleets. To address the challenges of delayed scheduling information, heavy reliance on manual labour, and low operational efficiency in traditional large-scale agricultural machinery operations, this study proposes a method for multi-agricultural machinery collaborative task assignment based on an improved genetic hybrid optimisation algorithm. The proposed method establishes a multi-agricultural machinery task allocation model by combining the path pre-planning of a simulated annealing algorithm and the static task allocation of a genetic algorithm. By sequentially fusing these two algorithms, their respective shortcomings can be overcome, and their advantages in global and local search can be utilised. Consequently, the search capability of the population is enhanced, leading to the discovery of more optimal solutions. Then, an adaptive crossover operator is constructed according to the task assignment model, considering the capacity, path cost, and time of agricultural machinery; two-segment coding and multi-population adaptive mutation are used to assign tasks to improve the diversity of the population and enhance the exploration ability of the population; and to improve the global optimisation ability of the hybrid algorithm, a 2-Opt local optimisation operator and an Circle modification algorithm are introduced. Finally, simulation experiments were conducted in MATLAB to evaluate the performance of the multi-agricultural machinery collaborative task assignment based on the improved genetic hybrid algorithm. The algorithm's capabilities were assessed through comparative analysis in the simulation trials. The results demonstrate that the developed hybrid algorithm can effectively reduce path costs, and the efficiency of the assignment outcomes surpasses that of the classical genetic algorithm. This approach proves particularly suitable for addressing large-scale task allocation problems. Keywords: Agricultural machinery; Task assignment; Genetic algorithm; Adaptive crossover operator; Adaptive mutation operator 1. Introduction With the continuous advancement of science and technology, our country's mechanisation level in agriculture has significantly improved. Automation technology has become a key area in the development of modern agriculture. Agricultural machinery automatic navigation technology is crucial for implementing precision agriculture [1] and enables efficient and accurate agricultural machinery operations. Integrating farm machinery and information technology has become inevitable in developing modern agricultural machinery in China. Leveraging information technology to promote agricultural machinery development can maximise information technology's guiding role, enhance agricultural production efficiency, and hold significant importance for promoting the high-quality and efficient development of agricultural machinery in our country [2]. Smart agriculture plays a crucial role in economic development, and a range of innovations are already being applied in developed countries that enable farmers to reduce resource consumption and increase agricultural production effectively[3]. [4]Research has explored the master-slave navigation system of two agricultural machines, and experimental results demonstrate that these two agricultural machines can collaborate safely, with a 95.1% increase in efficiency compared to traditional single-machine operations. Additionally,[5]proposed a novel agricultural master-slave navigation system where the slave machine tracks the operation of the master machine, achieving preliminary collaborative navigation. Multi-machine collaboration technology in agricultural machinery is crucial for enhancing the efficiency of machinery utilisation and improving the benefits of large-scale production of machinery fleets. Task allocation is also a significant evaluation metric for collaborative operations within agricultural machinery fleets. The challenge lies in allocating each task to the most suitable agricultural machinery unit before commencing operations, thereby maximising the overall benefits of the machinery fleet. Multi-machine collaborative task allocation has been extensively researched in logistics distribution, drones, and robotics. The integration of robotics and automation technology has significantly transformed the landscape of agriculture. The emergence of automated agriculture and the utilisation of robotics and sensors[6-9]aim to accomplish agricultural tasks more efficiently, thereby increasing production efficiency, reducing manual operations, cutting labour costs, and executing functions like field management, crop cultivation, and harvesting with greater precision. The primary goal is to address issues related to agricultural machinery's production efficiency and crop yield. Furthermore, unmanned driving technology has led to the development of high-precision autonomous driving tractors, which have applications in various agricultural activities such as ploughing and harvesting[10-11].Rational task allocation in multi-machine operations can accelerate the execution speed of fleet tasks and reduce system consumption[12], primarily aimed at minimising production costs.[13]introduced a solution utilising a dual-layer distributed Multi-Agent System (MAS) framework. They employed an iterative auction approach at the production planning layer and a distributed Hungarian method at the scheduling layer to address the multi-robot task allocation problem.[14]introduced a hybrid particle swarm optimisation and simulated annealing algorithm to find high-quality workshop scheduling solutions within reasonable computational time.[15]proposed a distributed auction algorithm based on the distance between robots and target tasks and the matching degree between robot capabilities and functions. They established a multi-robot collaborative task allocation model in a heterogeneous environment, effectively addressing the task allocation problem among heterogeneous robots. To manage the scheduling of multi-robot collaborative navigation task planning,a method based on ant colony algorithms was proposed for multi-robot collective navigation operations in agricultural fields [16]. Subsequently, a remote management platform for multi-robot coordinated navigation operations was designed and developed[17]. This platform can monitor real-time trajectories and operational information of multi-robot collaborative navigation operations and facilitate remote scheduling and management, thereby preliminary meeting the requirements of multi-robot collective navigation operations and reducing costs.[18]developed a multi-UAV task allocation algorithm based on an improved particle swarm optimisation algorithm. This algorithm builds upon the traditional particle swarm optimisation by introducing partial matching crossover and second-order swap mutation. These enhancements effectively enhance the efficiency of UAV task allocation in maritime environments and optimise navigation paths. [19]presented a multi-UAV integrated scheduling optimisation method that divides the problem into task allocation and individual UAV scheduling stages. This approach achieves task allocation among multiple UAVs.[20]proposed a solution to the task allocation problem in multi-machine collaborative agricultural machinery operations. They devised a method based on the multi-mutated grouping genetic algorithm for assigning static tasks when similar farm machines must work together. They constructed the multi-mutated grouping genetic algorithm and designed a two-stage encoding, grouping crossover operator, and multiple mutation operators. They established a static task allocation model for multi-machine collaborative agricultural machinery operations, meeting the requirements of practical task allocation in collaborative scenarios. The research was done on multi-agricultural machinery cooperative task allocation based on an improved ant colony algorithm in agricultural field environments [21]. This was done to help manage operations involving multiple machines working together. This study laid the foundation for addressing task scheduling and management in complex agricultural operational environments that involve multi-machine collaboration. While significant progress has been made by scholars both domestically and internationally in the field of multi-machine collaborative task allocation, there are still several limitations that need to be addressed. Firstly, a large portion of research has been applied to areas such as multi-robot systems,multi-UAVs, and multi-autonomous underwater vehicles, with only a few studies focusing on integrating agricultural machinery into the context of farming applications. Secondly, in solving task allocation problems using various algorithms, past research has mainly concentrated on optimising the algorithms' performance, such as improving efficiency and addressing issues related to local optima [22-23]. However, task allocation is a multi-constrained optimisation problem in practical agricultural field operations. Beyond minimising path costs, other factors must be considered, including supply-demand matching, agricultural machinery performance parameters, fuel consumption, and time constraints. Agricultural machinery often needs comprehensive information-gathering and scientific decision-making methods for field collaborative management. In agricultural machinery operations, there is usually an asymmetry in supply and demand information, and management authorities frequently need more scientifically rational scheduling and management plans, along with efficient and sensible task allocation strategies. Addressing these issues is essential in achieving successful multi-machine collaborative operations in agricultural fields. Therefore, it is necessary to study the agricultural machinery static task of agricultural machinery. The innovations and contributions of this research are as follows: (1) This paper proposes a path pre-planning model based on a simulated annealing algorithm and a static task assignment model based on a genetic algorithm. (2) The tournament selection method can avoid the problem of early convergence to the local optimal solution, keep the population's diversity, and increase the algorithm's global search ability. (3) The adaptive crossover operator and adaptive mutation operator are designed. The two-segment coding method is used to optimise the objective function. A multi-crossover operator and multi-population mutation method are constructed to improve population diversity and enhance population exploration's ability to achieve multi-machine cooperative static task allocation. (4) To optimise the path further, a 2-opt local optimisation mutation operator and an improved circle algorithm are used to optimise the path better. The rest of this paper is as follows: the second section introduces the cooperative operation model, the third section presents the task assignment model, the fourth section designs the algorithm, the fifth section provides the simulation results, and the sixth section discusses the conclusion. 2. Problem formulation Task allocation refers to the process of assigning feasible tasks to suitable performers. It involves determining the nature, requirements, and priorities of jobs and giving them to a ppropriate individuals or resources to ensure practical task completion, maximizing the ben efits obtained when all tasks are accomplished. Multi-machine collaborative static task allo cation in agricultural machinery refers to establishing a mapping relationship between agric ultural machinery units and multiple sections of cultivated land. Subsequently, before com mencing operations, the farm machinery allocates task assignments and their order to the designated machinery units to maximize their benefits. Consequently, agricultural machinery can operate systematically in cultivated fields, facilitating coordinated scheduling and man aging multiple machinery units within a specific region.Using the set �� ={�1 ,�2 ,⋯, �� }repr esents m operational agricultural machinery units.Using the set �� ={�1 , �2 , ⋯, �� } means n tasks.The parameters of the i-th agricultural machinery are defined as follows �� = {��� , �� , �� , �� , ��� , ��� , ��� },(i = 1,2, ⋯, m).Table 1 lists the main parameters adopted in this st udy. Table 1 the main parameters used in this study Symbols Description vai The average speed (km/h) of operation for the i-th agricultural machinery. di The working width (m) of the i-th agricultural machinery during operation. wi The average operational capacity of the i-th agricultural machinery in terms of area covered (m²/h). vi tti cvi cw i dT j IT j Sj The average speed (km/h) at which the i-th agricultural machinery travels in a non-operational state. The average time (h) taken for the i-th agricultural machinery to perform a turnaround during operation. The average fuel consumption (L/h) of the i-th agricultural machinery while traveling in a non-operational state per unit of time. The average fuel consumption (L/h) of the i-th agricultural machinery per unit of time during operation. The width of the vertical operation path for task �� . The length of the parallel operation path for task �� . The operational area of task �� . For analysis, a section of farmland was selected in the farm testing field. This area was divided into 15 idealized plots based on the requirements. Each parcel of farmland was considered an obstacle, and free traversal was restricted due to the distribution of the farmland. The Ovitalmap was utilized to establish the farmland model, and the model was visualized. In the model, white indicates roads, and blue represents boundaries, as depicted in Fig 1. Fig.1 Model of experimental farmland 2.1.The primary hypothesis of multi-machine cooperative operation Due to the complexity of collaborative operations and to simplify the problem and facilitate computation, the following basic assumptions are made based on standard operational scenarios: ① The performance parameters of agricultural machinery and the positional parameters of farmland are known. Each plot of land is not connected to any other plot.② The number of tasks must be greater than the number of farm machines.③ Each task plot is assigned to only one agricultural machinery unit, with the route planning for each task plot known.④ Agricultural machinery departs from the garage, completes all assigned tasks, and returns to the garage.⑤ The farmland is obstacle-free. The agricultural machinery is in an ideal state. 2.2.Multi-machine cooperative operation model (1) The cost of completing a task for an agricultural machinery unit is calculated as the distance the machinery travels from the garage to the designated task location and back to the garage. Each agricultural machinery unit's overall operational time and fuel consumption are computed. In practical applications, agricultural machinery typically departs from the garage to sequentially visit task areas, each being called only once. The machinery returns to the garage after completing the final task. The cost associated with the path of each machinery unit is as follows: �� = ���� ,�� + 0 1 �� −1 �(��� , ���+1 ) + ���� ,�� �=1 � 0 (1) � � Formula 1.Where �� represents the path cost of agricultural machinery i .Where ���0,��1 represents the distance from the starting point �� to the first task point ��1 for agricultural machinery i .Where DiTi ,si represents the distance from the last task point �� � to the return point ��0 for agricultural ni 0 i � −1 machinery i .Where Tk=1 D(Tik , Tik+1 ) represents the total distance traveled by agricultural � machinery �1 from task e to ��� .The distance is calculated as shown in Formula (2). D (T k ,T k + 1 ) = (xk + 1 - xk )2 + (yk + 1 - yk )2 （2） The objective function is established to minimize the total path cost for all agricultural machinery units,and it is defined as follows: minf总 = min( �� = �，i Î M M (Disi ,Ti + i=1 0 1 Ti −1 D(Tik , Tik+1 ) +DiTi ,si )) k=1 i 0 n （3） （4） Formula (3) represents the minimization of the total path cost between task areas,while Formula (4) represents that all agricultural machinery units need to complete tasks in all task areas. The fuel consumption �� comprises three parts: fuel consumption during travel,fuel consumption for turning during operation,and fuel consumption during operation.This is illustrated in Formula (5). � �� = � ∗ ��� + �� � �_����(��) ∗ �_�(�) ∗ ��� + �=1 � �� ∗ ��� �=1 �� (5) In Formula (5),n_turn(ij) represents the number of U-turns for the i-th agricultural machinery at the j-th task location. (3)The total time �� to complete tasks consists of three components: machinery travel time,machinery in-field turning time,and machinery operation time.This is represented by Formula (6). � �� = � + �� � �_����(��) ∗ �_�(�)+ �=1 � �� �=1 �� (6) 3. Establishment and Process Design of Multi-Machinery Collaborative Task Allocation Model 3.1.Framework for Task Allocation of Multiple Agricultural Machinery The collaboration of various agricultural machinery can be divided into two categories: static task allocation and dynamic task allocation. This article mainly focuses on the static task allocation for multiple agricultural machinery working collaboratively, as illustrated in Fig.2.In static task allocation, tasks are reasonably allocated to each agricultural machine, and an efficient and rational global resource allocation plan is generated based on the known task information. Fig.2 Overall framework of multi-computer cooperative task allocation relationship 3.2 Task Allocation Methods �!(�−1)! There are (�−1)!(�−�)! possibilities to assign n tasks to m-machine in an orderly way.When n is large,we can not use the exhaustive method to get the optimal task assignment.At this time,we often use the heuristic method to get a feasible solution [24-25];in this paper,a simulated annealing algorithm and a genetic algorithm are used to solve the problem. 3.2.1 Path Preplanning Based on Simulated Annealing Algorithm Simulated Annealing is a global optimisation algorithm[26]used to find the optimal solution to a problem within a search space. Inspired by solid-state annealing principles, it simulates a solid object's cooling process from high to low temperature to explore the solution space. This paper employs the Simulated Annealing algorithm for path preplanning to obtain a feasible solution with the lowest cost. The specific process is outlined below: (1) Set the initial value of the iteration count,initial temperature �� ,final temperature t,and the length of the Markov chain. (2) Initialize the current offspring population as route_new=route and set the initial distance matrix and path. (3) Sets the optimal path length to infinity and initializes the current and optimal paths to the initial directions. (4) When the temperature is greater than or equal to the last temperature, perform the following steps: ① The number of iterated Markov chain lengths ② Perform path perturbation to generate a new path route. ③ Calculates the size of the new path. ④ If the length of the new way is less than the length of the current path, the length of the current path is updated to the length of the new path. ⑤ Otherwise, the current new path is updated with a certain probability according to Metropolis criteria. If the new path length is less than the optimal path length, the optimal path and length are updated. (5) Update the temperature. (6) Finally, the optimal path and length are returned as the algorithm's output. 3.2.2.Task Allocation Based on Genetic Algorithm Genetic Algorithm (GA) is a heuristic optimisation algorithm [27] inspired by the principles of biological evolution and genetics in nature. It simulates the process of natural growth and has strong global search capabilities, making it effective in finding better solutions in large search spaces. Genetic algorithms typically involve three basic steps: selection, crossover, and mutation. An adaptive crossover operator and a genetic algorithm with multiple adaptive modifications are proposed. This algorithm employs two-stage encoding and uses tournament selection of chromosomes, effectively addressing the problem of multi-machine collaborative task allocation. 4. Algorithm Design 4.1.Encoding According to reference[28], a two-stage encoding method was employed, as illustrated in Fig.3.The first part represents the task order, with n tasks represented by numbers from 1 to n, utilising n digits. The second part denotes the number of tasks assigned to each agricultural machine (AM) and consists of m digits. For instance, the encoding scheme is applied when n = 8 and m = 3. Fig.3 Two-stage coding 4.2.Selection Tournament selection is simple, effective, and easy to implement. It involves selecting a small group of individuals to compete and selecting the fittest as the winner. This selection method has a low computational cost and is suitable for large-scale problems and complex optimisation tasks. Additionally, it aids in maintaining diversity; tournament selection allows weaker individuals to participate in the competition, increasing the diversity of the selection process. Even if an individual has relatively low fitness, he still has the chance to be selected, thus obtaining the opportunity for survival and reproduction. This helps avoid the problem of early convergence to local optima, maintains population diversity, and enhances the algorithm's global search capability. Define the problem's fitness function, where higher-fitness chromosomes represent better task allocation outcomes. The fitness function is defined as shown in Formula (7): 1 ���� = (7) � 4.3 Adaptive Crossover Operator (1) The sigmoid function is a commonly used logistic function, also called the logistic function. It maps real numbers to the interval (0,1) and is frequently utilized to convert continuous inputs into probability values. Its formula is given by Formula (8): ���� = 1 (8) 1+�−� Where x is the input value,e is the base of the natural logarithm (approximately equal to 2.71828). The output of the function is a value between 0 and 1. (2) In Formula (10). Using the method of adaptive step size, we calculate a relative evolutionary algebraic value according to the number of population (N) so that its range r, Formula (9) is shown. The step size of R will increase with algebra, and the value will rise first and then decrease. This scaling effect can be used to control the genetic algorithm's early exploring ability and later balancing power; this makes evolution more exploratory in the early stages and more balanced in the later stages so that fitness changes over a smaller range. The R trend is shown in Fig.4. � = 2 ∗ ���(�) ∗ �= 1 1+���(−�) ∗ ��� ������ − ���(�) (������−���+1) ������ (9) (10) Where n is the number of population, Gen is the number of current iterations, and MAXGEN is the total number of iterations. Fig.4 Trends in R (3) Overshoot �����ℎ��� = (���(�� )−����(�� )) (11) ����(�� ) In Formula (11),max(�� ) represents the maximum value of the path cost for agricultural machine m(i),and Mean(�� ) represents the average path cost for all agricultural machines m. ��1 = ��2 = (���(��1 )−����(��1 )) (12) (���(��2 )−����(��2 )) (13) ����(��1 ) ����(��2 ) In Formula (12)-(13),to1 and to2 represent the two individuals' overshoot. (4) Definition of adaptive tolerance as shown in Formula (14): the crossover operator can be dynamically adjusted, and in the global search phase, the population diversity can be increased by increasing the crossover probability to explore the solution space better. In the local search phase, the crossover probability can be reduced gradually, which makes the algorithm search the local area near the excellent solution more centralized. �� = ������ + � ∗ ���∗(������ −������ ) (14) ������ Tolmin and Tolmax are two given thresholds representing the parameter's minimum and maximum values, respectively. R is an adaptive step size to achieve dynamic adjustment and optimization of parameters. (5) Based on the new population resulting from the selection of the bidding tournament, two chromosomes are randomly selected in the new population, and the crossover probability is calculated separately for each chromosome. As shown in Formula (15) - (16). ��1 = ����� ∗ (�1_���� − �1_���) + ����� ��2 = ����� ∗ (�2_���� − �2_���) + ����� �1_����−�1_��� (15) �2_����−�2_��� (16) �1_����−�1_��� �2_����−�2_��� Where Pcmax and Pcmin denote two given crossover probabilities,respectively,The average, maximum,and minimum path costs of each agricultural machine among the m agricultural machines in the first chromosome are represented by y1_mean,y1_min and y1_max. The crossover probabilities of the two randomly selected chromosomes are normalised to obtain the crossover probabilities. To ensure that each possibility is correctly considered and applied, the problems associated with inconsistent probability distributions are avoided, thus better achieving the desired effect of the optimisation algorithm. As shown in Formula 17-18. ��2 = ��1 ∗ �1 + ��2 ∗ �2 (17) �1 + �2 =1 (18) 4.3.1Sequential intersections (OX) The crossover process of the sequential crossover operator is shown in Fig.5 ① Selec t two individuals (Dad and Mom) randomly.② Randomly select two crossover points (Cro ssPoint1 and CrossPoint2),such that CrossPoint1 is smaller than CrossPoint2.e.g., CrossPoi nt1=2, CrossPoint2=4.③ The mother's chromosome is passed as it is in the gene section between CrossPoint1 and CrossPoint2.④ The remaining partial gene segments in Mom are inserted into the remaining segments of the offspring (offspring) in the order in which th ey appear in Dad. A random breakpoint is selected for the second part of the chromosom e, and then the two gene segments are reversed in order. Fig.5 Sequential crossover operator 4.3.2 Partially-Mapped Crossover (PMX) The crossover process of the partially mapped crossover operator is shown in Fig.6. ① Two chromosomes are randomly obtained from the selected population.② In the first part of the chromosome, two random numbers are generated to satisfy 0≤k1