关键词: 多机协同, 负载均衡, 时间窗, 作业调度和规划, 改进型多旅行商遗传算法

Abstract:

[Objective] Traditional harvesting processes in large-scale farms still suffer from low scheduling efficiency, uneven workload distribution, and suboptimal path planning, which hinder the realization of intelligent and efficient agricultural production. Multi-machine collaborative operation scheduling and planning has become key technologies in intelligent farming management, aiming to optimize task allocation and path planning among multiple harvesters under time window and workload balance constraints. However, such problems belong to complex combinatorial optimization categories characterized by high dimensionality and nonlinearity. Conventional genetic algorithms (GA) often exhibit premature convergence and weak local search capabilities, resulting in suboptimal scheduling schemes. To address these challenges, this study focused on the collaborative harvesting operations of multiple combine harvesters across several fields and proposed an improved multi-traveling salesman problem genetic algorithm (IMTSP_GA) for integrated multi-machine scheduling and path planning. [Methods] A multi-machine cooperative scheduling model was constructed with the objective of minimizing the total operational time of all harvesters while considering time window and load-balancing constraints. The problem was modeled as a multi-traveling salesman problem (MTSP), in which each harvester was regarded as a traveling salesman responsible for a subset of field tasks. To solve the model, the proposed IMTSP_GA adopted a two-layer chromosome encoding structure: The first layer represented the visiting sequence of all task units, and the second layer defined the segmentation positions that allocated tasks to different machines, thereby forming feasible multi-harvester operation routes. To ensure both initial solution quality and population diversity, a hybrid initialization strategy combining sequential and random initialization was designed. Furthermore, a Q-learning-based adaptive mutation mechanism was introduced into the genetic operation process. By constructing a state–action–reward model based on the variation trend of fitness values, the algorithm dynamically selected mutation operators according to their historical performance, thus balancing global exploration and local exploitation. The overall process included chromosome encoding, fitness evaluation, group-based selection, crossover and mutation operations, and Q-learning-driven adaptive control. Based on the optimized scheduling scheme, the full-path planning for each harvester was divided into two stages: (1) in-field path planning, which used an internal spiral coverage method to reduce turning frequency and non-working time; and (2) road network path planning, which employed the Dijkstra algorithm to obtain globally shortest travel routes between fields. [Results and Discussions] A total of 25 farmlands were divided into 49 task units, and four John Deere 3588 harvesters were used for the simulation. Comparative experiments were performed among IMTSP_GA, standard GA, particle swarm optimization (PSO), and ant colony optimization (ACO). The results showed that the IMTSP_GA significantly outperformed other algorithms in terms of total operation time, convergence speed, and computational efficiency. Specifically, the total operational time was reduced by 4.48%, 5.32%, and 9.87% compared with GA, PSO, and ACO, respectively. The average runtime was 5.82 s, which was substantially shorter than that of the GA (11.55 s) and PSO (10.70 s). The algorithm exhibited fast early convergence and effectively avoided premature stagnation. To further evaluate generalization capability, five classical traveling salesman problem (TSP) datasets, Berlin52, Eil76, Bier127, CH150, and KroB200, were tested. IMTSP_GA consistently achieved superior average solutions and shorter runtimes across all datasets, confirming its robustness and adaptability to different problem scales and complexities. Finally, full-process path planning was visualized based on the optimized scheduling results. The generated harvester routes were continuous and compact, ensuring reasonable task allocation and efficient transitions between fields, thereby validating the effectiveness of the proposed model. [Conclusions] By integrating a Q-learning-based adaptive mutation mechanism, IMTSP_GA autonomously selects effective mutation strategies to enhance search performance and convergence stability. Meanwhile, the hybrid initialization strategy maintains population diversity and improves the quality of initial solutions. IMTSP_GA surpasses traditional GA, PSO, and ACO in solution quality, convergence performance, and computational efficiency. The method effectively reduces total operation time, optimizes harvester task allocation, and improves the coordination and efficiency of multi-machine operations. In future work, the research will be extended to more complex scenarios involving multi-region cooperation, task prioritization, and dynamic environmental factors. Reinforcement learning and online optimization techniques will be incorporated to achieve real-time scheduling and intelligent decision-making, thereby enhancing the adaptability and engineering applicability of the proposed method in large-scale intelligent agricultural systems.

Key words: multi-machine collaboration, load balancing, time window, operation scheduling and planning, improved multi-traveling salesman problem genetic algorithm