Research on Multi-AGV Task Allocation in Train Unit Maintenance Workshop

Abstract

In the context of the continuous development and maturity of intelligent manufacturing and intelligent logistics, it has been observed that the majority of vehicle maintenance in EMU trains still relies on traditional methods, which are characterized by excessive manual intervention and low efficiency. To address these deficiencies, the present study proposes the integration of Automatic Guided Vehicles (AGVs) to improve the traditional maintenance processes, thereby enhancing the efficiency and quality of vehicle maintenance. Specifically, this research focuses on the scenario of the maintenance workshop in EMU trains and investigates the task allocation problem for multiple AGVs. Taking into consideration factors such as the maximum load capacity of AGVs, remaining battery power, and task execution time, a mathematical model is formulated with the objective of minimizing the total distance and time required to complete all tasks. A multi-population genetic algorithm is designed to solve the model. The effectiveness of the proposed model and algorithm is validated through simulation experiments, considering both small-scale and large-scale scenarios. The results indicate that the multi-population genetic algorithm outperforms the particle swarm algorithm and the genetic algorithm in terms of stability, optimization performance, and convergence. This research provides scientific guidance and practical insights for enterprises adopting task allocation strategies using multiple AGVs.

1. Introduction

Intelligent manufacturing has emerged as a primary means of enhancing a nation’s industrial competitiveness [1]. Within the framework of “Industry 4.0” and intelligent manufacturing, intelligent logistics is considered a fundamental and crucial component in achieving intelligent manufacturing objectives [2]. In this context, Automated Guided Vehicles (AGVs) are extensively utilized as indispensable material handling equipment to fulfill the objectives of intelligent logistics. Regarding intelligent manufacturing, China has witnessed a continuous elevation in its railway equipment capabilities. Over the span of ten years, from 2012 to 2021, the nationwide inventory of railway passenger cars has increased from 57,700 to 78,000 units, while the number of high-speed train sets has escalated from 825 to 4153 sets [3]. With the ongoing growth in high-speed train sets, a corresponding surge in equipment maintenance has also been observed. The maintenance of high-speed train sets constitutes a critical link in ensuring their seamless operation. The train unit maintenance workshop possesses several significant characteristics that have a crucial impact on its operations and efficiency. Firstly, the workshop is equipped with advanced equipment and technology specifically designed to meet the maintenance needs of high-speed train sets. These technologies cover mechanical, electrical, and electronic systems, enabling comprehensive and efficient repair tasks. Secondly, the workshop faces diverse maintenance tasks that encompass various fields such as mechanical, electrical, and electronic repairs. These tasks require specialized skills and expertise to ensure the effective and reliable operation of the train sets. Thirdly, due to the critical importance of maintenance for ensuring safe operations, the workshop operates under strict time constraints. Timely completion of repair tasks is essential to ensuring the prompt return of train sets to operation. Fourthly, the workshop needs to manage a large number of train sets, which involves effective vehicle allocation, scheduling, and maintenance planning to handle multiple train set repairs simultaneously. Fifthly, the workshop must meet the power demands of train sets and maintenance equipment. A stable and reliable power supply is essential to guaranteeing continuous operation. Sixthly, vehicle scheduling and transportation present significant challenges for the workshop. Proper vehicle scheduling and route planning are crucial for the timely delivery of train sets and transportation to the workshop. Seventhly, safety and quality control are paramount concerns for the workshop. Strict adherence to safety protocols and reinforcement of quality control measures are essential for ensuring operational safety and reliability.

In summary, the train unit maintenance workshop is a complex and efficient system that requires specialized skills and effective management to ensure the safe and reliable maintenance of high-speed train sets. This study explores the multi-AGV task allocation problem in the workshop, addressing challenges related to vehicle management, scheduling, and task assignment, thus improving the operational efficiency and maintenance quality of the workshop. As a result, this research optimizes the workshop’s operations and enhances the overall performance of the maintenance system.

2. Literature Review

The multi-AGV task allocation problem refers to the allocation of tasks to multiple AGVs and scheduling the execution order of tasks, with the objective of maximizing the efficiency and quality of task completion. Due to its complexity and intractability, the multi-AGV task allocation problem is a typical NP-hard problem [4]. In the domain of task allocation models, there are primarily single-objective and multi-objective planning models. Single-objective planning models, such as Lu et al. [5], aim to minimize the total completion time as the objective function to optimize the task allocation and sequencing of mobile robots. Zhuang et al. [6] focus on minimizing the number of shelf transportation operations as the objective, considering handling conflicts in the task allocation model for mobile robots. Li et al. [7] consider minimizing the maximum travel time of AGVs and propose an AGV task allocation algorithm based on shelf priority. Multi-objective planning models, like Li Teng et al. [8], establish a two-level task allocation model, minimizing the total cost at the upper level and minimizing the number of idle robots at the lower level. To mitigate uncertainties and discrepancies between the model and actual operational conditions, a robust optimization model was further developed. Zou et al. [9] design a greedy algorithm to construct a multi-objective task allocation model, optimizing the total energy consumption of AGVs, the number of AGVs used, and the task timeliness that affects customer satisfaction. Li et al. [10] have developed a dual-objective, energy-saving single-load AGV planning model for multiple transportation tasks, aiming to minimize transportation distance and energy consumption. Mousavi et al. [11], considering the battery level of AGVs, optimize AGV task scheduling with the objectives of minimizing completion time and the number of AGVs. Regarding algorithm design, most current studies employ metaheuristic algorithms [12,13,14,15,16] for solving the task allocation problem. In recent years, with the advancement of machine learning and deep learning [17,18,19,20,21], these methods have gradually found applications in addressing task allocation problems. Zou et al. [22] proposed the Discrete Artificial Bee Colony algorithm (DABC) and other novel advanced techniques for task allocation problem-solving. Tang et al. [23] designed a two-layer genetic algorithm, with the inner layer optimizing the task scheduling sequence of AGVs and picking stations and the results being fed back to the outer layer model to optimize equipment configuration and sorting station layout. Yue et al. [24] introduced an enhanced hybrid genetic algorithm and particle swarm optimization algorithm (PSO-GA) to establish multi-AGV task allocation models. Liu et al. [25] proposed an improved particle swarm optimization algorithm to solve multi-objective task allocation models, exhibiting enhancements in population convergence speed and algorithm performance. Tang et al. [26] presented a novel approach based on classical soft Actor-Critic and hierarchical reinforcement learning algorithms, namely the layered soft Actor-Critic algorithm, to address dynamic scheduling problems in order picking. Yang Wei et al. [27] proposed a variable neighborhood simulated annealing algorithm to solve the job scheduling problem of mobile robots in warehousing systems. They designed three types of neighborhood perturbation operations, including insertion, swap, and “2-opt”, to systematically transform the search space and improve the algorithm’s search ability and scope. Yang Zhifei et al. [28] extracted the advantages of different algorithms and proposed an adaptive multi-objective genetic-differential evolution algorithm to address robot dispatching tasks. They introduced a new multi-stage real-number coding rule and incorporated elite and adaptive strategies to enhance the algorithm’s convergence speed. Song Wei et al. [29] applied an ant colony algorithm to process task sequences and then used a genetic algorithm to allocate subsets of tasks for task chaining. Xu Liyun et al. [30] improved the encoding method and genetic operators of the cultural genetic algorithm and demonstrated through simulation experiments that the improved algorithm achieved faster convergence. In terms of applying these algorithms to other research domains, Chen et al. [31] introduced a multi-agent control structure model to solve complex distributed resource planning problems by leveraging the advantages of multi-agent systems. Kler et al. [32] utilized data analysis to optimize inventory and supply chain networks in meat and poultry farms, aiming to achieve the goals of a green supply chain. Ntawuzumunsi et al. [21] proposed an energy-efficient algorithm based on data aggregation technology for communication between intelligent beekeeping devices. Joshi et al. [20] investigated how machine learning techniques can be used to predict phishing attacks in blockchain networks.

Existing research has demonstrated the wide applicability and potential of various intelligent algorithms in different domains, contributing to improved efficiency, resource utilization, and problem-solving capabilities. Regarding the AGV task allocation research, the focus has mainly been on the allocation of only one task per AGV within a certain period. Researchers have constructed single-objective and multi-objective models and made improvements to the original algorithms to enhance their convergence and solution performance. However, some of the improved algorithms have resulted in increased complexity in the theoretical derivation steps and higher computational requirements. In the case of AGVs operating in a single-task mode, system optimization is constrained, and as task volume escalates, task backlog issues can emerge. Increasing the number of AGVs for task execution may exert pressure on traffic, thereby impeding overall system efficiency improvements. Furthermore, existing research has primarily concentrated on algorithmic enhancements while neglecting optimization pertaining to research scenarios and model characteristics. Hence, this paper aims to address these gaps by focusing on the research scenario of a high-speed train maintenance workshop. The objective is to minimize the total distance and time required to complete all tasks while considering constraints such as the AGV’s maximum load capacity, remaining battery level, and time. Multiple population-based genetic algorithms are designed to solve the task allocation model. Theoretical contributions are made to the field of multi-AGV task allocation, and practical implications are expected to enhance the overall efficiency of the logistics system in the high-speed train maintenance workshop.

3. Problem Description and Hypotheses

In the logistics system of a high-speed train maintenance workshop, Automated Guided Vehicles (AGVs) are responsible for the transportation of all raw materials within the workshop. Their primary task involves delivering raw materials from the storage points to the designated maintenance workstation points. Considering the specific characteristics of the high-speed train maintenance workshop, it is worth noting that different systems can undergo maintenance simultaneously at the same workstation. In other words, when repairing a specific section of a train car, there is a unique target maintenance workstation. In a given time period, the high-speed train maintenance workshop generates a set of n delivery tasks, denoted as N = {1, 2, ……n}. These tasks can be grouped as G_k = {i, j ……|i, j ∈ N}. The workshop has a total of m AGVs available for task execution, forming the set K = {1, 2, ……m}. As the AGVs purchased for the workshop are of the same model, each AGV shares the same maximum load capacity and travel distance when fully charged. To closely resemble real-world scenarios, this study considers the delivery tasks performed by AGVs at non-saturated battery levels. With respect to the discharge characteristics of lithium batteries, the remaining travel distance decreases rapidly as battery usage increases. To align with the maintenance rhythm, each task i should be assigned in such a manner that the AGV’s arrival time is no earlier than the task generation time a_i, and the task completion time falls within the task deadline b_i. Given these conditions, how can the task grouping and allocation problem be formulated to maximize the overall system efficiency? Specifically, the optimization objectives are to minimize the total travel distance under the task grouping and to minimize the AGV task completion time. Constraints such as the AGV’s maximum load capacity, remaining battery level, and time availability are taken into consideration. By establishing a mathematical model, an optimal task grouping, and allocation scheme can be derived.

In order to account for the discrepancies between the model’s solution and the actual operational scenario, the following assumptions should be met:

(1)

The maintenance task represents the comprehensive system of the first section of a train car.

(2)

The inventory of raw materials at the storage points adequately meets the requirements of the delivery tasks.

(3)

AGV travel paths can be reliably and consistently planned without encountering conflicts.

(4)

The consideration of raw material volumes and the loading/unloading times of AGVs is omitted.

(5)

Under normal circumstances, all AGVs maintain a uniform speed during travel.

(6)

When executing a task group, each required storage point for a task can be traversed by an AGV only once.

(7)

AGVs start their operations by uniformly parking at a designated location, known as the starting point, with Task 1 assigned as the initial task.

(8)

Upon completion of all tasks within a task group, AGVs park at the target maintenance workstation, referred to as the endpoint, with Task n designated as the final task.

4. Model Establishment

Based on the problem description above, the model parameters and definitions of decision variables are as follows:

Model Parameters:

W: represents the maximum load capacity of each AGV;

w_i: represents the weight of raw materials required for task i;

e_k: represents the remaining battery level of AGV k;

f: represents the safety battery level expressed as a percentage;

L: represents the function that relates the percentage of battery consumption to the remaining travel distance for each AGV;

a_i: represents the generation time of task i;

b_i: represents the deadline time of task i;

v: represents the travel speed of each AGV;

d_i,j,k: represents the shortest distance from task i to task j for AGV k;

$D_{G_k,k}$: represents the shortest total distance for AGV k to complete task group G_k;

t_i,j,k: represents the minimum time from task i to task j for AGV k;

$t_{i,k}^{\prime }$: represents the time required for AGV k to complete task i;

$T_{G_k,k}$: represents the minimum total time for AGV k to complete task group G_k.

Decision Variables:

$$x_{i,j,k}=\left\{\begin{array}{l}1,AGV k travels from task i to task j\\ 0,others\end{array}\right.$$

(1)

$$y_{i,k}=\left\{\begin{array}{l}1,task i is delivered by AGV k\\ 0,others\end{array}\right.$$

(2)

Objective function:

$$Z=\min \left\{D_{G_k,k}+\left(\max T_{G_k,k}\right)\right\}$$

(3)

Constraint function:

$$D_{G_k,k}={\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n{\displaystyle \sum _{k=1}^m{x}_{i,j,k}{d}_{i,j,k}}}}$$

(4)

$$T_{G_k,k}={\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n{\displaystyle \sum _{k=1}^m{x}_{i,j,k}{t}_{i,j,k}}}}$$

(5)

$$t_{i,j,k}=\frac{d_{i,j,k}}{v},\forall i,j\in N,k\in K$$

(6)

$${\displaystyle \sum _{k=1}^m{y}_{i,k}=1},\forall i\in N$$

(7)

$${\displaystyle \sum _{i=1}^n{x}_{i,j,k}=y_{j,k}},\forall j\in N,k\in K$$

(8)

$${\displaystyle \sum _{j=1}^n{x}_{i,j,k}=y_{i,k},\forall i\in N,k}\in K$$

(9)

$${\displaystyle \sum _{k=1}^m{w}_i{y}_{i,k}\le W,\forall i}\in N$$

(10)

$$x_{i,j,k}(t_{{}_{i,k}}^{\prime }+t_{i,j,k}-a_j)\le 0,\forall i,j\in N(i,j\ne 1,n),k\in K$$

(11)

$${\displaystyle \sum _{k=1}^m{x}_{i,j,k}(t_{{}_{i,k}}^{\prime }+t_{i,j,k}+t_{j,k}^{\prime })-b_i\le 0,\forall i,j\in N(i,j\ne 1,n)}$$

(12)

$$L(x)=a{x}^2+bx+c$$

(13)

$${\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n{\displaystyle \sum _{k=1}^m{x}_{i,j,k}{d}_{i,j,k}}}}\le L(1-e_k)-L(1-f)$$

(14)

$${\displaystyle \sum _{j=2}^{n-1}{x}_{1,j,k}=1},\forall k\in K$$

(15)

$${\displaystyle \sum _{i=2}^{n-1}{x}_{i,n,k}=1},\forall k\in K$$

(16)

$$\begin{array}{l}{x}_{i,j,k}\in (0,1),\forall i,j\in N,k\in K\\ y_{i,k}\in (0,1),\forall i\in N,k\in K\end{array}$$

(17)

In the aforementioned model, x_i,j,k and y_i,j,k are binary decision variables taking values of 0 or 1. Equation (3) represents the objective function, which aims to minimize the total distance and time required to complete all tasks. Equations (4) and (5) are utilized to calculate the total distance and total time, respectively, for completing all tasks within each task group. Equation (6) computes the completion time between two tasks based on speed and distance. Constraint (7) ensures that each task is assigned to an AGV. Constraints (8) and (9) guarantee that tasks within the same task group are exclusively assigned to a single AGV. Constraint (10) ensures that the weight of each task group does not exceed the maximum load capacity of the AGV. Constraint (11) guarantees that an AGV, which sequentially performs tasks i and j, arrives at the storage point of task j no earlier than the task generation time of task j after completing task i. Constraint (12) ensures that the total completion time of the task group does not exceed the deadline time of each individual task. Equation (13) expresses the relationship between the AGV’s battery consumption curve and the remaining travel distance [33]. Constraint (14) ensures that each AGV operates within its battery constraint range, with a safety battery level reserved for returning to the charging area. Equation (15) states that each AGV must pass through task 1 and can do so only once. Equation (16) states that each AGV must pass through task n and can do so only once.

5. Algorithm Design

The multi-population genetic algorithm [34,35,36,37] is an optimization algorithm based on the genetic algorithm that enhances search capability and global optimization performance by introducing multiple independent populations. Each population functions as an independent subsystem of the genetic algorithm, possessing its own set of individuals and evolutionary process. Below is a detailed introduction to the main characteristics of the Multi-Population Genetic Algorithm (MGA) and the algorithm design process in this paper, as shown in Figure 1.

5.1. Main Characteristics of the Algorithm

(1)

Multiple Independent Populations: The multi-population genetic algorithm consists of several independent populations, each with its own unique set of individuals and evolutionary process. Each population can be configured with distinct parameters and operational strategies.

(2)

Population Interaction: Information and individuals are shared among multiple populations through exchange strategies, facilitating global search capability. Exchange strategies may include periodic individual migration, sharing of optimal solutions, and exchange operations.

(3)

Parallel Computation: The ability for multiple populations to undergo parallel evolution endows the multi-population genetic algorithm with high computational efficiency and search capability.

5.2. Algorithm Design Process

(1)

Encoding: The encoding process involves generating a sequence of mutually distinct natural numbers from 1 to n, where n represents the number of delivery tasks. This sequence constructs a permutation representing a combination of delivery tasks, with each number denoting a specific task. Each permutation corresponds to a potential task allocation scheme. Adhering to the given constraints, the elements of the solution are systematically assigned to the delivery routes of the respective AGVs. To elaborate, consider the example solution 123456. The first element of the solution represents the first target point for the delivery route of the first AGV. It is then checked whether this allocation adheres to the imposed constraints, including the AGV’s maximum load capacity, remaining battery level, and time requirements. If the constraints are met, the second element of the solution is assigned as the second task point for the first AGV. In cases where the constraints are not satisfied, indicating that the task cannot be assigned to the first AGV, it is then assigned as the first task point for the second AGV, and this process continues iteratively.

(2)

Initializing Populations: In this study, four populations are created, each comprising 20 individuals (solutions). To generate these individuals, 20 randomly generated non-repeating sequences between 1 and n, where n represents the number of delivery tasks, are utilized. Each individual within a population represents a distinct task allocation solution. To promote diversity and facilitate thorough exploration of the search space, unique crossover and mutation probabilities are randomly assigned to each population. The crossover probability ranges from 0.7 to 0.9, while the mutation probability ranges from 0.001 to 0.05. Both probabilities are generated using random number distributions.

(3)

Selection, Crossover, and Mutation: Firstly, fitness evaluation is conducted for each individual within the population, with the fitness function value being the reciprocal of the objective function value. By computing the total distance and time of the corresponding task allocation solution for each individual, their respective fitness values are derived. Lower fitness values indicate more superior task allocation solutions, increasing the likelihood of individuals being selected as parents to produce the next generation. Subsequently, these individuals are randomly paired for information exchange through the crossover operation. This process introduces diversity among individuals within the population, facilitating exploration of a broader solution space. Lastly, following the crossover operation, the genes of the offspring individuals are subjected to mutation with a certain probability. The mutation operation introduces new gene combinations within individuals, further enhancing population diversity and avoiding being trapped in local optima.

(4)

Reverse Evolution: In order to enhance the local search capability of the genetic algorithm, a reverse evolution operation is introduced after the selection, crossover, and mutation operations. The reverse evolution operation randomly selects a gene segment from the parent and performs a reverse order operation on that segment. Subsequently, the fitness value of the parent after the reverse operation is calculated to determine whether to accept the parent with the reverse operation. The reverse operation is only effective if the fitness of the parent improves after the reverse operation, in which case it is included in the next generation of individuals. Otherwise, the reverse operation is considered ineffective.

(5)

Migration Operator: To facilitate information exchange among populations, a strategy of periodically introducing the best individual from one population into another population is employed. Specifically, the best individual from one population is selected to replace the worst individual in another population. Through this information exchange mechanism, the flow and sharing of information among populations are encouraged. Introducing the best individual allows beneficial genetic information to be transmitted to other populations, thereby enhancing their overall fitness. Simultaneously, replacing the worst individual helps prevent populations from prematurely converging to local optima and increases the diversity of the populations.

(6)

Elite Population: To enhance information exchange and sharing among populations, a strategy of selecting the best individuals from other populations and placing them into a special elite population for preservation is adopted. The elite population can be viewed as a collection of the best solutions from each population. By regularly selecting the best individuals from other populations and adding them to the elite population, excellent solutions from various populations can be accumulated and shared with other populations for evolution.

(7)

Termination Criteria: To further enhance the stability and convergence of the algorithm, the best individual in the elite population is required to maintain its status as the best solution for a consecutive number of generations equal to or greater than 10. In other words, when the best individual in the elite population remains unchanged for 10 or more consecutive generations, it can be considered that the algorithm has reached a relatively stable state, and the iteration process can be terminated.

6. Simulation Experiments and Analysis

To verify the correctness of the mathematical model and the effectiveness of the Multi-population Genetic Algorithm (MGA), comparative experiments were conducted in this study. The experiments were designed and implemented using Matlab. The results obtained from Particle Swarm Optimization (PSO) and the Genetic Algorithm (GA) were compared and analyzed against the results of the Multi-Population Genetic Algorithm. Through this comparative analysis, the solving capabilities and performance of each algorithm can be evaluated, confirming the correctness of the mathematical model, and validating the effectiveness of the Multi-Population Genetic Algorithm in problem-solving.

In this study, an 80 × 80 maintenance workshop for high-speed trains was established, with the starting point of tasks set at (1, 1) and the destination point at (80, 80). Randomly generated obstacle distributions were introduced to represent walls, shelves, and other objects within the maintenance workshop. These obstacles contribute to creating a more realistic map of the maintenance workshop, thereby enhancing the authenticity and reliability of the experiments. By incorporating randomly generated obstacle distributions, various constraints and challenges present in real-world scenarios can be considered during the simulation experiments. Consequently, this approach allows for a more comprehensive evaluation and optimization of the operational efficiency within the maintenance workshop.

6.1. Small-Scale Simulation Experiment

Assuming the maintenance workshop is equipped with five Automatic Guided Vehicles (AGVs) capable of executing distribution tasks. Each AGV has a full battery range of 200 km. To ensure the safe operation of AGVs, a safety battery level of 10% of the total battery capacity is set, allowing AGVs to maintain sufficient charge to return to the charging area during their journeys. The remaining battery percentages for each AGV are shown in

Table 1. Remaining Battery Levels of AGVs.

AGV No.	Remaining Battery Percentage
1	67
2	88
3	96
4	78
5	76

. Additionally, each AGV has a maximum load capacity of 100 kg and a travel speed of 20 km/h. For further investigation of the performance of distribution tasks, 20 sets of distribution tasks were randomly selected through code. The locations of these tasks are between the starting point and the destination point, with random coordinates assigned to each task. The dataset includes the coordinates of the task points, task generation times, task completion deadlines, and the weight of the materials, as presented in

Table 2. Task Information.

Task No.	Task Points X	Task Points Y	Material Weight (kg)	Task Generation Time (s)	Task Deadline Time (s)
1	1	1	/	/	/
2	40	48	11	160	170
3	35	16	6	49	59
4	45	55	12	14	114
5	20	55	19	50	160
6	14	29	27	35	45
7	23	30	12	98	108
8	21	51	4	80	90
9	11	44	12	95	105
10	55	60	17	97	107
11	30	60	17	13	133
12	20	60	12	67	77
13	50	35	20	65	74
14	30	25	24	159	169
15	15	10	19	32	42
16	30	5	7	61	71
17	10	20	19	75	85
18	5	30	3	157	167
19	20	40	12	87	97
20	15	55	17	76	86
21	40	60	9	26	136
22	80	80	/	/	/

.

The algorithm was implemented in Matlab2021b with the following parameter settings: Population size n^p = 20 Maximum iteration count I_max = 50. For the Particle Swarm Algorithm (PSO): Inertia weight w = 0.01, Learning factors c₁ = c₂ = 1. For the Genetic Algorithm (GA), the crossover probability p₁ = 0.85 Mutation probability p₂ = 0.1. For the proposed Multi-population Genetic Algorithm (MGA), the number of populations is set to m^p = 4. The simulation results of the three algorithms for the multi-AGV task allocation problem in the maintenance workshop are presented in Figure 2.

In Figure 2, the horizontal axis represents the number of iterations, and the vertical axis represents the fitness value, which corresponds to the objective function in our model, i.e., the total sum of AGV’s running distance and delivery time under the given task allocation. From Figure 2, it can be observed that as the number of iterations increases, the fitness value continuously decreases until it reaches a stable state. Eventually, the optimal task allocation result that minimizes the objective function is obtained. To eliminate the impact of randomness on the experimental results, the algorithm parameters and experimental scenarios were kept unchanged, and the experiment was repeated 50 times. The average optimal results and the number of iterations obtained from the statistical analysis are shown in

Table 3. The average optimal results obtained from the algorithms.

Algorithm	Average Optimal Results	Average Number of Iterations
PSO	542	34
GA	574	48
MGA	528	31

.

According to Table 3, the Particle Swarm Optimization (PSO) algorithm found the average optimal result of 542 in the 34th iteration, the Genetic Algorithm (GA) found the average optimal result of 574 in the 48th iteration, and the Multi-population Genetic Algorithm (MGA) found the average optimal result of 528 in the 31st iteration. Moreover, the MGA achieved a better optimal result than the other two algorithms, indicating that the proposed mathematical model is correct and effective and that the MGA exhibits superior performance in terms of solving ability and efficiency.

From the above 50 experiments, the optimal results obtained from the three algorithms are used for the multi-AGV task allocation search to obtain the task execution sequences, as shown in

Table 4. The optimized task combinations for the three algorithms.

Algorithm	AGV No.	The Task Execution Sequence
PSO	1	1
	2	1-17-7-5-8-9-19-10-22
	3	1
	4	1-6-11-21-4-13-2-22
	5	1-15-16-3-14-18-20-12-22
GA	1	1-17-6-9-20-5-8-22
	2	1
	3	1-15-16-12-11-21-10-4-22
	4	1
	5	1-3-13-2-14-18-19-7-22
MGA	1	1-17-7-14-18-2-10-22
	2	1
	3	1
	4	1-16-3-13-19-9-11-21-4-22
	5	1-15-6-5-12-20-8-22

. In Table 4, Task ID 1 represents the starting point, and Task ID 22 represents the endpoint. When the AGV task execution sequence is 1, it indicates that the corresponding AGV vehicle was not assigned. From the contents of Table 4, it can be observed that by using the multi-population genetic algorithm for the multi-AGV task allocation model, three automatic guided vehicles (AGV1, AGV4, and AGV5) can complete the 20 sets of delivery tasks, achieving dynamic optimality in matching the delivery of raw materials with AGV vehicles.

Based on the multi-AGV task allocation results obtained from the three algorithms, corresponding route maps were generated, denoted as Figure 3a–c, respectively. In the figures, black dots represent randomly generated obstacles. From Figure 3c, it can be observed that the route generated by the multi-population genetic algorithm successfully avoids all obstacles and delivers all target points from the starting point to the endpoint. This visually demonstrates the effectiveness of the multi-population genetic algorithm in optimizing the task allocation order and path selection for the delivery tasks.

6.2. Large-Scale Simulation Experiment

To further investigate the algorithm’s generalization, we increase the number of AGVs to 4 and add 20 additional randomly generated delivery tasks based on the small-scale case. The parameters for the additional AGVs and the information for the new tasks are presented in

Table 5. Additional AGV Battery Residual Capacity.

AGV No.	Remaining Battery Percentage
6	71
7	95
8	88
9	87

and

Table 6. Additional Task Information.

Task No.	Task Points X	Task Points Y	Material Weight (kg)	Task Generation Time (s)	Task Deadline Time (s)
1	1	1	/	/	/
22	45	20	21	7	107
23	45	10	5	62	72
24	55	5	9	68	78
25	65	35	5	3	163
26	65	20	16	172	182
27	45	30	16	132	142
28	35	40	14	37	47
29	41	37	9	39	49
30	64	42	10	63	73
31	10	30	3	71	81
32	5	15	5	111	121
33	24	55	7	36	56
34	35	25	23	55	65
35	13	35	12	45	55
36	40	35	5	8	128
37	40	25	7	4	14
38	25	25	9	56	66
39	30	15	9	48	58
40	30	20	7	88	98
41	5	20	12	43	53
42	80	80	/	/	/

, respectively. The other AGV parameters remain unchanged.

The algorithm in this study was implemented using Matlab2021b. To ensure consistency between the small-scale and large-scale experiments, the algorithm parameters were kept unchanged as specified in Section 5.1. The algorithm was run, and the iterative convergence plot of the best solution was obtained, as shown in Figure 4. Additionally, the optimal solutions and optimized task assignments were compiled and presented in

Table 7. Optimal Results and Optimized Task Assignments for Three Algorithms in Large-Scale Experiment.

Algorithm	Optimal Result	AGV No.	The Task Execution Sequence
PSO	1073	1	1-16-40-32-18-14-2-10-42
		2	1-17-6-31-9-12-11-33-42
		3	1-41-35-5-28-36-22-25-30-42
		4	1-15-3-23-24-27-26-42
		5	1-38-39-7-19-8-20-42
		6	1
		7	1
		8	1
		9	1-37-34-29-4-21-13-42
GA	1099	1	1
		2	1-6-31-17-32-18-14-27-42
		3	1
		4	1-34-24-26-10-42
		5	1-38-40-7-16-39-23-3-13-42
		6	1
		7	1-22-36-29-28-12-20-33-2-42
		8	1-15-41-35-9-19-8-5-21-42
		9	1-37-4-11-30-25-42
MGA	1062	1	1-25-30-10-8-20-11-21-4-42
		2	1-6-17-32-18-9-2-26-42
		3	1-16-3-34-22-13-24-23-39-42
		4	1
		5	1
		6	1
		7	1-15-41-38-7-40-14-27-42
		8	1-37-36-29-28-5-12-33-19-35-31-42
		9	1

.

In the case of large-scale instances, the Particle Swarm Optimization (PSO) algorithm converges to the optimal solution around the 21st iteration, while the Genetic Algorithm (GA) finds the optimal solution around the 18th iteration. On the other hand, the proposed Multi-Group Genetic Algorithm (MGA) obtains the optimal solution around the 41st iteration. In terms of computational efficiency, PSO takes approximately 1.974 s, GA takes about 1.802 s, and MGA requires 6.886 s. Despite MGA’s longer computational time due to its complex structure, it achieves significantly superior optimal results within a reasonable computational time. This demonstrates the enhanced computational performance of MGA, enabling it to generate superior task allocation solutions within a relatively short time. MGA is suitable for multi-AGV task allocation problems because it efficiently generates feasible task allocation solutions. Although its computational time is slightly longer than other algorithms, it can attain significantly better results within the same computational time. This validates the effectiveness and practicality of the proposed Multi-Group Genetic Algorithm in solving multi-AGV task allocation problems.

Based on the results from Table 7, it can be concluded that the multi-population genetic algorithm effectively solves the multi-AGV task allocation problem. Compared to the other two algorithms, the multi-population genetic algorithm reduces the number of deployed AGV vehicles, increases the utilization rate of each AGV, and lowers the total cost of the logistics system. This, in turn, enhances the overall efficiency of the dynamic train maintenance workshop’s logistics system.

Figure 5a–c illustrate the route maps for the three algorithms. In the large-scale scenario, from the route map of the multi-population genetic algorithm, it can be observed that the system successfully avoids all obstacles and completes the delivery of all task groups. This further demonstrates the effectiveness of the multi-population genetic algorithm in improving the system’s operational efficiency.

In conclusion, the multi-population genetic algorithm exhibits excellent optimization, convergence, and stability performance in both large-scale and small-scale scenarios. As the problem size increases, the algorithm produces solutions of higher quality compared to the other two algorithms. Although there is a certain difference in running time, it is within an acceptable range with the improvement of computer performance. Therefore, it can be concluded that the proposed multi-population genetic algorithm is effective in solving the multi-AGV task allocation problem. Specifically, Unique Probability Mechanism: The unique probability mechanism is a crucial component in the multi-population genetic algorithm, aiming to maintain population diversity and avoid premature convergence to local optima. This mechanism assigns a unique probability value to each individual in the population based on its fitness evaluation, where the fitness function value is the objective function value. Individuals with lower fitness values (corresponding to better task allocation solutions) are assigned higher probabilities being selected as parents for reproduction in the next generation. By doing so, the algorithm ensures a balance between exploration and exploitation, allowing the population to thoroughly explore the solution space and prevent getting stuck in suboptimal solutions. Local Search Strategy: The local search strategy is another key element introduced in the multi-population genetic algorithm to enhance its local search capabilities. After performing crossover, the offspring individuals undergo a local search process to fine-tune their solutions within a local neighborhood. This process involves exploring the surrounding solutions and adjusting the genes in a probabilistic manner. The local search strategy promotes intensification around promising regions of the solution space, enabling the algorithm to converge more quickly to good-quality solutions. It effectively improves the exploitation ability of the algorithm and further refines the task allocation solutions. Information Exchange Methods: Information exchange is a significant aspect of the multi-population genetic algorithm, which encourages inter-population cooperation and knowledge sharing. Individuals from different populations are randomly paired for information exchange through crossover, facilitating the integration of diverse genetic information and promoting the global search ability of the algorithm. Additionally, information is also exchanged among individuals within the same population through mutation, which introduces new gene combinations and maintains population diversity. This comprehensive information exchange mechanism ensures that valuable genetic information is propagated effectively throughout the entire population, contributing to a more thorough exploration of the solution space.

In summary, the unique probability mechanism, local search strategy, and information exchange methods synergistically enhance the performance of the multi-population genetic algorithm. The unique probability mechanism maintains population diversity, the local search strategy refines solutions around local optima, and the information exchange methods foster global search and knowledge sharing. The experimental results demonstrate that the multi-population genetic algorithm outperforms other algorithms, such as Particle Swarm Optimization (PSO) and Genetic Algorithm (GA), in terms of stability, optimization performance, and convergence speed, making it a powerful and effective approach to tackle the multi-AGV task allocation problem.

7. Conclusions

The aim of this research is to address the multi-AGV task allocation problem in real maintenance workshops and optimize task assignment using the Multi-population Genetic Algorithm (MGA). Our study primarily focuses on maximizing production efficiency and resource utilization in the workshop, aiming to enhance operational efficiency and reduce costs. Throughout the research process, we developed a comprehensive AGV allocation model that considers constraints such as the AGV’s maximum load capacity, remaining battery power, and time availability to ensure reasonable task distribution and path planning.

The main contribution of this research lies in the introduction of the MGA algorithm, which takes into account factors like task priority, distance between tasks, and proximity to maintenance workstations, resulting in more rational and efficient task allocation. Comparative experiments with traditional Particle Swarm Optimization (PSO) and the Genetic Algorithm (GA) demonstrated that MGA exhibited faster convergence and superior optimal solutions for large-scale instances, highlighting its competitive advantage in multi-AGV task allocation. However, our research also has certain limitations. The algorithm may require longer computation times when dealing with more complex and dynamic operating environments, necessitating further optimization of algorithm parameters and structures to improve efficiency. Additionally, some assumptions made in the algorithm may not entirely align with real workshop conditions, calling for the consideration of additional real-world factors to enhance the model’s practical applicability. Future improvements could involve incorporating factors such as loading and unloading times and raw material volumes to more accurately reflect real workshop scenarios. Further optimization of local search and information exchange methods within the algorithm could enhance convergence and optimization performance. Additionally, exploring the combination of the MGA algorithm with other intelligent techniques could address more complex and diverse industrial scenarios.

Overall, this research offers an efficient and optimized solution for AGV task allocation in practical maintenance workshops and provides valuable references for related research and applications. Continual refinement and optimization will allow these findings to have a greater impact in a broader range of industrial settings, driving advancements in intelligent manufacturing and logistics. We believe that the outcomes of this research will provide robust support in tackling challenges faced in actual maintenance operations and offer new insights and directions for future improvements and adaptations in this field.