Sage Journals: Discover world-class research

Abstract

Research on multitask scheduling systems in factory environments is a popular topic in the field of intelligent manufacturing. Existing research mainly focuses on the optimization of automated guided vehicle (AGV) path planning and scheduling, emphasizing on the minimization of conflicts and deadlocks, multi-objective task scheduling, and metaheuristic algorithm optimization, while ignoring path stability and real-time path planning in dynamic environments. Therefore, this paper aims to address these issues to better handle dynamic changes in actual operating environments. This paper establishes a mathematical model with the optimization objective of minimizing the overall running time of material distribution tasks and proposes an improved ant colony algorithm to optimize the model. First, the concept of prior time is introduced to improve the traditional ant colony algorithm. The path of the ongoing task is introduced with a time calculation, and the occupancy time window of each grid point on the path is calculated. Based on this, the initial pheromone distribution on subsequent paths is altered dynamically, which accelerates the convergence of the ants to a collision-free path. Second, in the pheromone update stage, the method of calculating the pheromone increment in the traditional ant colony algorithm is modified. The original distance influence factor is changed to a time influence factor, which ensures that all tasks still have the minimum running time when calculating a collision-free path. Finally, through 30 sets of simulation experiments on material distribution tasks, it is shown that the proposed algorithm shortens the total running time by 15.14%, 12.87%, and 10.59% compared to two ant colony algorithms and one strategic multi-AGV scheduling algorithm, respectively, thus verifying the effectiveness of the proposed method.

Keywords

Multiple automated guided vehicles multitask scheduling ant colony algorithm prior time optimization

Introduction

In the context of warehouses and manufacturing plants, the transportation of materials and goods is crucial.¹ In this context, the unique industrial capabilities of AGVs have been demonstrated.² Through effective scheduling of AGVs, efficient transportation of materials and goods can be achieved, greatly improving production efficiency and reducing distribution costs.³ This facilitates the unmanned transfer of materials in the factory production process, which is also an important way to achieve intelligent manufacturing.

In practical industrial production, a multi-AGV scheduling system for material transfer is an automated system that collaboratively manages multiple AGVs to jointly complete a series of relatively independent, complex, and difficult production processes that cannot be organized through traditional assembly line processes. Coordinated scheduling problems of multiple AGVs (CSMAs) have received close attention in the field of intelligent manufacturing research due to their complexity. In CSMAs, different AGVs undertake various transportation tasks and need to travel efficiently between different starting points to meet the actual needs of factory material transportation.⁴ At the same time, these AGVs need to have the minimum time cost and the highest transportation efficiency. When faced with complex transportation tasks, staggered road networks, and numerous AGVs, a series of complex problems, such as AGV road selection and collision prevention, are encountered, which make it more difficult for a multi-AGV multitask scheduling system to achieve good performance and affect its efficiency and practicality.⁵

In response to these problems, scholars worldwide have conducted extensive research. Deng et al.⁶ effectively addressed the AGV collision and waiting time occupancy problems by introducing an improved genetic algorithm. Zhong et al.⁷ proposed a mixed integer programming model for multidevice integrated scheduling that incorporates path optimization, integrated scheduling, and minimization of conflicts and deadlocks. Jiao⁸ transformed the multi-AGV problem into an occupancy-based multivehicle path planning problem and applied a particle swarm algorithm to effectively solve the AGV scheduling problem. In addition, Ulusoy et al.⁹ attempted to solve the collaborative scheduling problem for machine tools and AGVs in flexible manufacturing systems by combining time windows and genetic algorithms. Udhayakumar et al.¹⁰ designed a hybrid algorithm for the FMS manufacturing environment with the optimization objectives of AGV load balancing, minimum travel time, and maximum utilization rate. This algorithm combines genetic algorithms and ant colony algorithms to solve the multi-objective task scheduling problem for AGVs. Zhao et al.¹¹ developed a multi-AGV scheduling algorithm based on predictive collision avoidance, using the A* algorithm for path planning and providing strategies for dealing with different types of collisions.

Among the numerous algorithms for solving scheduling problems, ant colony optimization (ACO) is an intelligent optimization method that simulates the foraging behavior of ants in nature. It has the advantages of positive feedback, parallel computation, high robustness, and multiple adjustable parameters, making it an effective method for solving multi-task scheduling problems.¹² In particular, in multi-task scheduling problems, the ACO algorithm can quickly converge to an optimal solution through its positive feedback mechanism. Its parallel computing feature allows multiple agents to search the solution space simultaneously, effectively improving the computational efficiency. Despite its strengths, the traditional ACO algorithm still has some notable drawbacks. First, its convergence speed is relatively slow, especially when solving large-scale complex problems, where the convergence time can be quite long. Second, the ACO algorithm is prone to getting stuck in local optima, stagnating near local optimal solutions and making it difficult to explore the global optimal solution. To address these issues, many scholars have proposed improvement strategies from different perspectives, including adjusting the algorithm structure, optimizing parameter selection, and determining the initial pheromone distribution. In terms of algorithm structure, Dorigo et al.¹³ proposed an innovative metaheuristic ant colony optimization method that provides a general algorithm framework for solving complex problems. Relevant studies have also been conducted in China. For instance, Wu et al.¹⁴ introduced rollback and death strategies to reduce the impact of ineffective pheromones on ant colony evolution, optimized the state transition rules, and improved the pheromone composition structure. Liu and Zhang¹⁵ applied the elite strategy and the max-min strategy to the basic ant colony algorithm. By updating the pheromones of elite ants, they successfully balanced the solution speed and optimization ability. From the perspective of parameter optimization, Sahu et al.¹⁶ considered using the length and usage time of the path traveled by the ants to calculate the pheromone increment for autonomous navigation tasks with humanoid robots. They used both static and dynamic path planning to verify the efficiency of this method in path planning problems. Akka and Khaber¹⁷ adopted a new pheromone update rule and dynamically adjusted the evaporation rate to accelerate the convergence speed of the algorithm and expand the search space, thereby preventing premature local optimization. Zhu et al.¹⁸ combined the artificial potential field method with ant colony algorithm, improving the slow convergence speed issue of the ant colony algorithm through the enhancement of heuristic functions and adaptive induced heuristic factors. Xiao et al.¹⁹ combined the dynamic window method with ant colony algorithm and constructed an evaluation function based on an improved dynamic window algorithm, which enhanced the local optimization ability of the dynamic window algorithm. They also developed an efficient fusion algorithm to avoid the limitations of the two algorithms in solving the path. From the perspective of initial pheromone distribution, Ding et al.²⁰ incorporated the path information obtained from genetic algorithms into initial pheromones, achieving satisfactory optimization results. Chen et al.²¹ utilized the guidance effect between a series of jump points obtained by the leapfrogging search algorithm to enhance the early convergence and reduce the search time issues of the ant colony algorithm. Wang et al.²² used the initial path obtained from the artificial potential field method as heuristic information. Based on the zero theorem, they assigned different initial pheromones to grid points with different characteristics and set an iteration threshold to achieve a good global search ability. Deng et al.²³ used the initial results of particle swarm optimization as the initial pheromone distribution of the ACO algorithm and utilized the parallelizability between ant colony algorithms to achieve efficient parallel search among ants via distributed technology.

However, existing algorithms typically modify the initial pheromone distribution based on specific factors only once. This fixed distribution strategy is difficult to dynamically adapt to environmental changes during the path planning process, leading to decreased path stability and increased risk of conflicts. Moreover, they fail to adequately consider the cooperation between different vehicles, especially in dynamic environments, which limits the algorithm's flexibility and real-time performance, potentially causing path delays and inefficiencies.²⁴ To overcome these shortcomings, this paper proposes a strategy that dynamically alters the initial pheromone concentration distribution in the subsequent exploration stages based on prior information. This strategy improves the stability and real-time performance of path planning by dynamically adjusting the pheromone distribution through real-time monitoring of path occupancy times. In addition, the distance influence factor in the heuristic function of the pheromone concentration update stage is changed to a time influence factor so that when calculating collision-free paths, the method can still fully consider time factors to obtain paths with the shortest running time.

The remainder of this paper is organized as follows. Section ‘Problem Description’ introduces the model of the material distribution scenario and establishes a mathematical model for the scheduling system. Section ‘Algorithm Design’ first introduces the basic process of the traditional ant colony algorithm, then introduces the improved pheromone update method and the heuristic function of the improved ant colony algorithm proposed in this paper, and finally gives the basic process of the improved algorithm. Section ‘Simulation Test and Analysis’ first validates the performance improvement of the proposed improved ant colony algorithm through specific task groups that can cause space–time conflicts, and then specifically analyses and compares the total completion times of the proposed algorithm with two ant colony algorithms and one strategic multi-AGV scheduling algorithm under 30 task scenarios. Section ‘Conclusion’ summarizes and concludes the research.

Problem description

Problem scenario model

In an intelligent warehousing system, AGV cars are mainly responsible for material handling in the factory area. For a single AGV multitask scenario, it is only necessary to consider the starting point and the ending point of each task, calculate the shortest path from the starting point to the ending point, and complete the tasks in order. However, for multi-AGV multitask scheduling optimization, the situation becomes more complex and conflicts between vehicles need to be considered.

To quantify this problem, we first divide the factory area to establish a grid map model, as shown in Figure 1. The areas that vehicles cannot reach are represented by black grid cells.

Figure 1.

Factory grid map model.

This grid map model divides the factory area into 20 × 20 units, where a certain number of AGVs are responsible for material handling tasks. When a task is assigned to an AGV car, it will calculate the optimal path based on the task starting point and ending point, and then transport the goods along the optimal path to the task ending point and wait for the next required task. In the case of multiple tasks assigned to multiple AGVs, space–time conflicts may occur when the calculated paths of different AGVs occupy the same grid unit at the same time. This will lead to conflicts between AGVs, forcing other AGVs to stop and wait to avoid collisions, thus it should be avoided as much as possible in practice. However, for a fixed map size, the more AGV cars there are, the more complex the transportation task becomes, and the higher the probability of AGV space–time conflicts, which affects the normal handling efficiency of AGVs.

Mathematical model

To achieve efficient collaborative scheduling of multi-AGV under multitask conditions in factories, it is necessary to establish the corresponding mathematical optimization model. The following are the basic assumptions of the model:

AGVs cannot run along the edge of the grid or into an occupied area of the grid but can only travel from inside the grid to inside the grid.

Each AGV can only transport one object at a time.

All AGVs run at the same speed.

The acceleration during the starting phase and the deceleration during the stopping phase of the AGV are not considered.

The times taken for AGV vehicles to load and unload goods are not considered.

If the AGV moves diagonally, it will occupy two adjacent grids simultaneously, and the occupation time will be the time required to completely leave the current grid unit.

When the AGV changes its direction of travel, due to its structure, it can turn on the spot with a turning radius of zero.

AGVs can reach adjacent unoccupied grids from each grid and can reach up to eight adjacent grids.

Based on the problem scenario model established earlier, let the driving speed of the AGV be v, the side length of each grid point be r, and the length of the AGV be

l (l < r)

. Suppose there are N material distribution tasks, where

T a s k (n)

represents the

n

t h

task. Each task contains a task starting point

S_{n}

and a task ending point

E_{n}

. Suppose there are W AGVs available for use.

T_{n}^{s}

represents the starting time of the

n

t h

task, and

T_{n}^{e}

represents the ending time of the

n

t h

task, which satisfies the following constraint:

T_{n}^{s} = T_{n - 1}^{e}

(1)

That is, the starting time of the current task is equal to the ending time of the previous task.

$T_{n}^{s} (i)$ represents the entry time of the $i$ - $t h$ ( $i$ =1, 2,…, $I$ ) grid point on the travel route of the AGV responsible for the $n$ - $t h$ task, $T_{n}^{e} (i)$ represents the departure time from the $i$ - $t h$ grid point on the travel route of the AGV responsible for the $n$ - $t h$ task, $t_{c}$ is the vehicle turning time, $T_{n}^{d} (i)$ is the occupancy time of the $i$ - $t h$ grid point by the AGV responsible for the $n$ - $t h$ task, and $T_{n}^{g} (i)$ is the time at which the AGV responsible for the $n$ - $t h$ task crosses the $i$ - $t h$ grid boundary. The following constraints are satisfied:

T_{n}^{e} (i) = T_{n}^{s} (i) + T_{n}^{d} (i)

(2)

T_{n}^{e} (i) = T_{n}^{s} (i + 1) + T_{n}^{g} (i)

(3)

T_{n}^{e} = T_{n}^{e} (I)

(4)

The occupation time

T_{n}^{d} (i)

of each grid point varies according to the current position of the vehicle and the way it enters the next grid point, and the possible situations are as follows:

Figure 2 illustrates four scenarios representing the different ways a vehicle can move from the previous grid into the current grid and subsequently enter the next grid. These scenarios correspond to four distinct occupancy times for the vehicle in the current grid, as well as the additional grids occupied. These also apply to motions in opposite directions, that is, for the movement of the vehicle in the reverse direction, the corresponding occupancy times and extra occupied grids remain the same. The grid occupation time $T_{n}^{d} (i)$ of a vehicle within a solid-outline box is as follows:

Figure 2.

Vehicle routes at different locations.

From Table 1 and Formulas (1)–(4), we can calculate the occupancy time $T_{n}^{d} (i)$ of each AGV in each grid point on the travel route and the time $T_{n}^{e}$ for each AGV to complete each assigned task. Let $T (w)$ represent the final time for the $w$ - $t h$ AGV to complete all assigned tasks; then, the mathematical optimization model of the multi-AGV collaborative scheduling system under the multitask conditions established in this paper is:

min {max {T (w) | w = 1, 2, \dots, W}}

(5)

Table 1.

Time taken for different routes.

Situation	Occupied time/s	Additional grid points occupied
1	$\frac{r + l}{v} + t_{c}$
2	$\frac{\sqrt{2} l + \sqrt{2} r}{v}$	2, 4, 6, 8
3	$\frac{r + l}{v}$
4	$\frac{r + \sqrt{2} r + l + \sqrt{2} l}{2 v} + t_{c}$	1, 4

That is, the longest completion time of the AGV is minimized while satisfying the constraints (1)–(4) and the basic assumptions of the model.

Algorithm design

Considering the complexity of the problem model established in the previous section, especially the need to simultaneously handle space–time conflicts between vehicles when solving this optimization problem, this undoubtedly increases the difficulty of solving the problem. The ant colony algorithm has demonstrated significant advantages in solving such problems through distributed collaborative optimization. Based on this advantage, we use the ant colony algorithm as our optimization method and introduce the concept of prior time to effectively improve the algorithm.

Traditional ACO algorithm

The basic idea of the ACO algorithm is to use the foraging behavior of ants as a neighborhood search strategy and optimize the search process of the strategy by simulating the behavior of ants releasing pheromones. Specifically, an ant releases pheromones into its surroundings as it searches the problem space. When other ants search, they will move in directions with high pheromone intensity to find better solutions.

Suppose there are K ants, and each ant needs to traverse different cities until it reaches the destination, here the cities correspond to the grid points in the factory grid map model. Let $τ_{i j}^{t}$ represent the pheromone value between city i and city j at time t. The ants choose the next city to move to based on the state transition probability, that is, $P_{i j}^{k}$ , which is the $k$ - $t h$ ( $k$ =1, 2,…, $K$ ) state transition probability of the K ants transferring from city i to city j. This probability is obtained by combining multiple parameters. The formula is as follows:

P_{i j}^{k} = {\begin{matrix} \begin{matrix} \frac{{(τ_{i j}^{t})}^{α} \times (η_{i j}^{t})^{β}}{\sum_{s = a l l o w_{k}} {(τ_{i s}^{t})}^{α} \times (η_{i s}^{t})^{β}} & s \in a l l o w_{k} \end{matrix} \\ \begin{matrix} 0 & \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix}  \end{matrix} \end{matrix} \end{matrix} \end{matrix} \end{matrix} s \notin a l l o w_{k} \end{matrix} \end{matrix}

(6)

where

α

is the pheromone importance factor, the value of which determines the probability of the subsequent ants following a previously traveled path;

β

is the heuristic function factor, which measures the relative importance of heuristic information in guiding ant colony search;

a l l o w_{k}

represents the set of neighboring cities that are allowed to be accessed by ants. For the neighboring cities visited by the ants,

η_{i j}^{t}

is the reciprocal of the distance between cities i and

j

η_{i j}^{t} = \frac{1}{d_{i j}}

(7)

where

d_{i j}

represents the distance between cities i and j. The larger the value is, the smaller

η_{i j}^{t}

is and the smaller the state transition probability

P_{i j}^{k}

is, and vice versa.

When an iterative process is completed, all ants have reached the destination. To prevent the accumulation of pheromones in the wrong direction, it is necessary to introduce the evaporation factor $ρ$ ( $0 < ρ < 1$ ) to control the dissipation of pheromones.

Formula (8) shows the pheromone update rule:

τ_{i j}^{t + 1} = (1 - ρ) τ_{i j}^{t} + \sum_{k = 1}^{K} Δ τ_{i j}^{k}

(8)

where

τ_{i j}^{t + 1}

represents the pheromone intensity between city i and city j at time

t + 1

;

ρ

is the pheromone volatilization coefficient, reflecting the dissipation rate of the pheromone;

τ_{i j}^{t}

is the pheromone intensity between city i and city j at time t, and

Δ τ_{i j}^{k}

is the intensity of the pheromone left by the k -

t h

ant between city i and city j, which can be expressed as

Δ τ_{i j}^{k} = \frac{Q}{L_{k}}

(9)

where Q is the pheromone increase intensity coefficient and

L_{k}

is the length of the journey of the

k

t h

ant. When all iterative tasks are completed, the optimal path from the task starting point to the task destination can be found.

Prior-time based improved ACO algorithm

Although the traditional ACO algorithm performs well in many optimization problems, it shows limitations in the context of multi-AGV multi-task scheduling. First, it does not account for the time and space occupancy of vehicles during path planning, which can easily lead to space–time conflicts during actual operation, causing collisions or delays. Second, the traditional ACO algorithm primarily focuses on finding the shortest path, failing to adequately consider dynamic changes during task execution, such as real-time path adjustments to avoid potential conflicts. Additionally, the traditional algorithm tends to get trapped in local optima, making it difficult to find the global optimal path in complex multi-task environments.

To address the aforementioned issues of the traditional ACO algorithm in multi-AGV scheduling, this paper proposes an improved ACO algorithm based on prior time information. Unlike the traditional ACO algorithm, the improved version takes into account the operational status of other vehicles during the path planning process. By introducing the concept of prior time, the algorithm calculates and maintains the time windows for grid points occupied by each AGV on their current task routes. This prior information allows dynamic adjustments of the pheromone concentration distribution. When a grid point is already occupied by another AGV and may cause a time conflict, the algorithm will adjust the pheromone concentration on that path based on the severity of the conflict, thereby guiding the path planning of subsequent task-dispatching ants. Specifically, when calculating the path for the first task, the traditional ACO algorithm is used since there are no running vehicles on the map. However, when the algorithm performs path calculations for the $n$ - $t h$ $(n > 1)$ task, considering the running vehicles on the map, it is necessary to consider the occupation time of each grid point on the current travel routes of these vehicles. A $1 \times W$ -dimensional structure array $L i s t$ is defined to maintain the current path information of the vehicles, where $L i s t (w) . p a t h$ records the sequential grid point numbers that AGV w passes through for the current execution task p, and $L i s t (w) . t i m e$ $(1 \leq w \leq W)$ sequentially records the times of entry and departure from each grid point:

\begin{aligned} L i s t (w) . t i m e \\ = [[T_{p}^{s} (1) T_{p}^{e} (1)], [T_{p}^{s} (2) T_{p}^{e} (2)], \dots, [T_{p}^{s} (I) T_{p}^{e} (I)]] \end{aligned}

(10)

Here,

T_{p}^{s} (i)

and

T_{p}^{e} (i)

represent the entry time and departure time of the vehicle for the

i

t h

grid point

(1 \leq i \leq I)

, respectively.

When calculating the path for a new task n, each iteration of the algorithm requires determining which grid points the ant can travel to from the current $i$ - $t h$ grid point. If a grid point is different from the grid points in $L i s t . p a t h$ , there is no spatial conflict, and the path can be calculated based on the original pheromone concentration. If the grid point is the same as a grid point in $L i s t . p a t h$ (assuming it is the same as the $j$ - $t h$ grid point in the path of AGV w who is currently executing task p in $L i s t . p a t h$ ), there may be a temporal conflict, and it is necessary to calculate the time $T_{n}^{s} (i + 1)$ at which the $n$ - $t h$ task vehicle enters the grid point and the time $T_{n}^{e} (i + 1)$ at which it leaves the grid point and then perform a temporal conflict judgment based on the following conditions:

T_{n}^{s} (i + 1) < T_{p}^{e} (j)

(11)

T_{n}^{e} (i + 1) > T_{p}^{s} (j)

(12)

That is, if the time at which the

n

t h

task vehicle enters the grid point is less than the departure time of the AGV w currently executing task p at that grid point and the time at which the

n

t h

task vehicle departs from the grid point is greater than the entry time of AGV w currently executing task p at that grid point, then there is a space–time conflict. In this case, we consider whether to actively affect the pheromone concentration distribution to offset the negative impact of long waiting times caused by space–time conflicts. The probability

P_{c}

is introduced to measure the possibility of changing the concentration:

P_{c} = \frac{T_{p}^{e} (j) - T_{n}^{s} (i + 1)}{T_{p}^{e} (j) - T_{n}^{s} (i + 1) + T_{n}^{d} (i + 1)}

(13)

Formula (13) uses

T_{p}^{e} (j) - T_{n}^{s} (i + 1)

to represent the waiting time of the

n

t h

task vehicle at the

i + 1

t h

grid point due to the occupancy of the grid by the AGV executing task p, and it uses

T_{n}^{d} (i + 1)

to represent the normal passing time of the

n

t h

task vehicle at the

i + 1

t h

grid point. The value of

P_{c}

depends on the ratio of the waiting time of the

n

t h

task vehicle to its original passing time. When the waiting time is relatively long and the value of

P_{c}

is greater than or equal to the decision threshold c, the concentration of pheromone between the

i

t h

grid point and the

i + 1

t h

grid point is reduced to 0, preventing the recalculation of conflicting paths due to multiple iterations. When the waiting time is relatively short and the value of

P_{c}

is less than the decision threshold c, the concentration of pheromone is not altered, and the vehicle will wait for the occupied vehicle executing task p to depart before entering the

i + 1

t h

grid point. This strategy dynamically adjusts the concentration of pheromones based on the distribution of prior time by determining the relationship between

P_{c}

and c. By dynamically reducing the pheromone concentration on conflicting paths, the probability of selecting those paths in subsequent iterations is reduced, thereby avoiding space–time conflicts caused by multiple AGVs choosing the same path.

In the pheromone update stage, the traditional ACO algorithm updates pheromones solely based on distance factors. The newly added pheromone content as shown in Formula (9) is determined by the pheromone constant Q and the travel distance $L_{k}$ . In this way, the information can be changed according to the distance factor. However, in multi-task scenarios within factories, the shortest distance does not necessarily represent the shortest time. To optimize the overall task execution time, this paper replaces the distance factor $L_{k}$ in the heuristic function of the pheromone update phase by a time factor $T_{k}$ , as shown below:

Δ τ_{i j}^{k} = \frac{Q}{T_{k}}

(14)

In the formula, the time used by the

k

t h

ant is taken as a reference factor, effectively reducing the unnecessary waiting time caused by vehicle space–time conflicts. Furthermore, this approach can also avoid calculating paths that consume excessive time by not simply pursuing collision-free paths blindly.

The steps of the prior-time based improved ACO algorithm are as follows:

Step 1: Initialize the task starting point $n_{s}$ and ending point $n_{e}$ . Initialize the ant number $k = 1$ and the iteration number $m = 1$ .

Step 2: Set the algorithm control parameters. Let the total number of ants be K and the maximum number of iterations be M.

Step 3: Start the $m$ - $t h$ iteration:

Step 4: Send the $k$ - $t h$ ant from the starting point $n_{s}$ .

Step 5: Calculate the adjacent grid points that ant k can travel to next, and compare them with the grid points occupied by the vehicles executing the tasks in $L i s t . p a t h$ to determine whether the same grid points exist.

Step 6: If there is no same grid point, then calculate the path directly according to the traditional ant colony algorithm, and go to Step 8; Otherwise, calculate the entry time and departure time of the AGV at that grid point and compare them with the time in $L i s t . t i m e$ to judge whether there is a time conflict. The judgment method is shown in Formulas (11) and (12).

Step 7: If there is a conflict, calculate the probability $P_{c}$ according to Formula (13) and compare it with the decision threshold c, and then dynamically adjust the pheromone concentration between the corresponding grid points; Otherwise, the pheromone concentration is not changed.

Step 8: Calculate the state transition probability $P_{i j}^{k}$ based on the pheromone concentration value, and select the next path point.

Step 9: Check whether the selected next path point is the endpoint $n_{e}$ . If not, return to Step 5; Otherwise, record the current ant's path, update the tabu list, and go to Step 10.

Step 10: Increase k by 1. If $k \leq K$ , return to Step 4; Otherwise, all ants in this iteration have completed their tasks, go to Step 11.

Step 11: Update the pheromone using Formula (14) based on the recorded grid occupancy time.

Step 12: Increase the current iteration number m by 1. If $m \leq M$ , initialize the ant number $k = 1$ and return to Step 3 to start a new iteration; Otherwise, all iterations have been completed and go to Step 13.

Step 13: Output the path with the shortest grid occupation time and update the structure array $L i s t$ .

Simulation test and analysis

To verify the effectiveness of the proposed optimization model and solution algorithm for the multi-AGV multi-task collaborative scheduling system, a series of simulation tests were designed, covering multiple task sets, varying numbers of AGVs, and scenarios with potential space–time conflicts. By comparing the proposed algorithm with the traditional ACO algorithm, the improved ACO algorithm,¹⁹ and the strategic multi-AGV scheduling algorithm which uses A* for path calculation,¹¹ the improvement in task completion time was quantified to validate the effectiveness of the proposed algorithm. The grid map of the factory area in Figure 1 was used as the experimental scene. The grid map was assigned values using a row-major order, meaning that the assignment starts from the first row, with the first grid cell assigned a value of 1, and each subsequent row has 20 more assigned grid cells to fully describe the terrain of the entire factory. MATLAB R2021a was used to write the algorithm code, and the algorithm was run on an Intel Core i5-11320H 3.20 GHz processor (16.00 GB RAM) with Windows 11 as the operating system. The algorithm parameters are set as follows: number of ants $K = 50$ , maximum number of iterations $M = 100$ , pheromone volatility coefficient $ρ = 0.3$ , pheromone importance factor $α = 1$ , heuristic function factor $β = 7$ , pheromone increase intensity coefficient $Q = 1$ , grid side length $r = 1$ , vehicle side length $l = 0.7$ , vehicle turning time $t_{c} = 1$ , vehicle speed $v = 1$ , and decision threshold $c = 0.7$ .

Space–time conflict test

To demonstrate the optimization effect of the improved algorithm, two sets of tasks with intersecting paths in the map in Figure 1 were selected, as shown in Table 2.

Table 2.

Space–time conflict task list.

Task number	Start point	End point
1	181	200
2	10	390

Two AGVs were employed, and the traditional ACO algorithm and the improved ACO algorithm proposed in this paper were used to calculate the scheduling path of each AGV, and a time axis was introduced for the two-dimensional calculation path, allowing a three-dimensional image to visually display the occupancy time at each grid point. The simulation results are shown in Figures 3 and 4.

Figure 3.

Scheduling paths of the traditional ACO algorithm.

Figure 4.

Scheduling paths of the proposed improved ACO algorithm.

By introducing a timeline, we can have a clearer understanding of the occupancy time of each grid point. As shown in Figures 3 and 4, the two paths calculated by the traditional ACO algorithm have a space–time conflict, resulting in vehicles needing to wait. In contrast, the proposed algorithm calculates nonconflicting paths for the two tasks, successfully avoiding waiting and reducing the time consumption of the tasks.

Figures 5 and 6 show the specific position change trends of the AGVs optimized by the two algorithms in the Y-coordinate direction and X-coordinate direction during the travel process. It can be seen that there is a crossing path in Figure 5(a) and (b) at 11.91 s–13.61 s; that is, the overlapping parts of the red line and blue line in (a) and (b) occur in the same time interval. In contrast, in Figure 6(a) and (b), there is no overlap of the red line and blue line in the same time interval. This result intuitively verifies the effectiveness of the proposed improved ACO algorithm in avoiding space–time conflict paths.

Figure 5.

Changes in the AGV positions optimized by the traditional ACO algorithm. (a) Y coordinate change trend. (b) X coordinate change trend.

Figure 6.

Changes in the AGV positions optimized by the proposed improved ACO algorithm. (a) Y coordinate change trend. (b) X coordinate change trend.

Multitask scenario test

To verify the optimization effect of the proposed algorithm under multitask conditions, we simulated 30 different sets of tasks ${T ask (n), n \in (1, 2, \dots, 30)}$ , as shown in Table 3.

Table 3.

Simulation task list.

Task number	Start point	End point	Task number	Start point	End point
1	40	293	16	12	82
2	94	292	17	64	195
3	229	385	18	109	159
4	176	109	19	235	122
5	377	186	20	59	141
6	388	260	21	2	344
7	378	271	22	264	71
8	344	19	23	347	221
9	251	400	24	17	119
10	24	145	25	186	318
11	99	374	26	103	224
12	370	18	27	367	190
13	84	249	28	133	243
14	261	341	29	160	387
15	35	203	30	185	236

We tested and analyzed the impact of changes in the number of AGVs on the scheduling results. Using the traditional ACO algorithm, we adopted a strategy of waiting for the previous vehicle to pass when there was a space–time conflict. The scheduling task allocation scheme was as follows: first, all vehicles were assigned tasks separately, and each vehicle received only one task. Once a task was completed, the vehicle responsible for the task would accept the next unfinished task. Task dispatching continued until all tasks were completed. We conducted scheduling simulations for scenarios where the number of AGVs increased from 1 to 10 and determined the total time required to complete 30 dispatch tasks under different numbers of AGVs. The simulation results are shown in Figure 7.

Figure 7.

Task completion times under different numbers of vehicles.

It can be seen that when the number of AGVs is greater than four, the decrease in the total task completion time gradually slows. This is because the increase in the number of vehicles will lead to an increase in space–time conflicts, thus in the case of 10 vehicles running simultaneously, the total task completion time does not decrease, but rather increases. We summarized the number of space–time conflicts generated under different numbers of AGVs, as shown in Figure 8.

Figure 8.

Number of space–time conflicts under different number of vehicles.

Considering the relationship between the number of AGVs and space–time conflicts, the characteristic that the improvement of task completion efficiency gradually slows down or even deteriorates with the increase of vehicle numbers, and the impact of economic costs on AGV quantity selection, we selected five AGVs for testing, using the traditional ACO algorithm, the improved ACO algorithm,¹⁹ the multi-AGV scheduling algorithm,¹¹ and the prior-time based improved ACO algorithm proposed in this paper. The parameters of each algorithm were set to the same values, and the optimization results are shown in Tables 4 to 7. The middle part of the table shows the task queue for each AGV, while the last column reflects the total time required for each AGV to complete the assigned tasks. This time includes the execution time of each task and the time required for movement between tasks. Here, the method used for calculating the path between tasks is the same as the method used for calculating each task. Through comparative analysis of the experimental results, we can see that both the improved ACO algorithm and the multi-AGV scheduling algorithm have shorter total task completion times than the traditional ACO algorithm under multitask conditions, while the prior-time based improved ACO algorithm proposed in this paper outperforms all three algorithms in improving task execution efficiency and reducing conflict rates.

Table 4.

Optimization results of the traditional ACO algorithm.

AGV number	Task queue	Time taken/s
1	1-8-14-20-26-29	228.09
2	2-9-11-17-21-28	210.92
3	3-10-13-16-24-30	216.85
4	4-6-15-19-23-27	201.98
5	5-7-12-18-22-25	188.29

Table 5.

Optimization results of the improved ACO algorithm.

AGV number	Task queue	Time taken/s
1	1-8-17-22-25	180.75
2	2-9-12-20-24-30	217.75
3	3-10-13-16-18-23-27	200.65
4	4-6-15-19-26-28	202.26
5	5-7-11-14-21-29	222.13

Table 6.

Optimization results of the multi-AGV scheduling algorithm.

AGV number	Task queue	Time taken/s
1	1-9-12-20-22-26	178.12
2	2-8-16-19-25-30	216.48
3	3-7-11-17-23-29	198.08
4	4-6-14-18-24-27	196.96
5	5-10-13-15-21-28	205.05

Table 7.

Optimization results of the proposed algorithm.

AGV number	Task queue	Time taken/s
1	1-7-11-16-19-23-29	188.55
2	2-8-14-18-24-27	181.83
3	3-10-13-20-28	193.07
4	4-6-15-17-22-25	179.86
5	5-9-12-21-26-30	193.55

The experimental results further show that in a typical scenario of 30 tasks and 5 AGVs, the proposed improved ACO algorithm achieves a total task completion time of 193.55 s, which is 15.14%, 12.87%, and 10.59% shorter than the 228.09 s taken by the traditional ACO algorithm, the 222.13 s taken by the improved ACO algorithm, and the 216.48 s taken by the multi-AGV scheduling algorithm, respectively. This is attributed to the consideration of the grids and time periods occupied by other running vehicles during the path calculation process of the proposed algorithm, as well as the adjustment of the pheromone update strategy. The traditional ACO algorithm and the improved ACO algorithm struggle with multi-AGV multi-task scheduling due to their inability to dynamically adjust path planning, which often leads to space–time conflicts and results in longer total task completion times. Although the strategic multi-AGV scheduling algorithm considers various AGV conflicts and their scheduling schemes, it also does not make dynamic path adjustments in advance based on these conflicts. In contrast, the proposed algorithm successfully avoids path conflicts and optimizes scheduling efficiency by introducing prior time and dynamic adjustment strategies, thus showing greater effectiveness and superiority in multi-task scenarios.

Conclusion

This paper investigates the collaborative optimization scheduling problem for multiple AGVs under multiple task conditions in factories and establishes a mathematical model for optimizing the scheduling system. In response to the potential occurrence of space–time conflicts during multitask execution, an optimization based on prior information is introduced on the basis of traditional ACO algorithms. By incorporating the time and space occupancy information of existing paths, the possibility of changing the pheromone concentration for subsequent path calculations is considered to determine whether it is necessary to detour to other paths, thus enabling dynamic adjustments. The introduction of the prior time concept enables the algorithm to dynamically perceive the occupancy status of other AGVs and adjust path planning accordingly to avoid space–time conflicts. This is a factor that existing ACO algorithms have not considered in multi-task scheduling. Moreover, existing ACO algorithms mainly optimize based on path distance, whereas the proposed algorithm in this paper incorporates a time influence factor. This ensures that path selection not only avoids conflicts but also minimizes vehicle travel time. These improvements enable the algorithm to generate paths that occupy less time when scheduling complex tasks.

Through simulation tests under multitask conditions, it is found that the proposed algorithm outperforms two ant colony algorithms and one strategic multi-AGV scheduling algorithm in avoiding space–time conflicts and improving scheduling efficiency, so it can better handle multitask scheduling problems in actual factories. Compared with the above algorithms, the proposed algorithm is more stable and reliable and can better meet the needs of practical applications. Despite these advantages, there are still some limitations in this study. First, the simulation tests were conducted on a simplified 20 × 20 grid map, which, while reflecting some issues present in real-world scenarios, does not encompass more complex factory environments. In more intricate scenarios, such as varying vehicle speeds and load capacities, the adaptability and effectiveness of the algorithm require further verification. Second, although the proposed algorithm has demonstrated high scheduling efficiency in the simulated environment, maintaining the real-time responsiveness of the algorithm and further integrating it with other optimization methods, such as deep learning, are major challenges that need to be tackled in future research when dealing with large-scale, frequently dynamically changing tasks.

Footnotes

Declaration of conflicting interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by Key R&D Program Project of Shandong Province (Grant No. 2024TSGC0012) and Shandong Province Central Guidance Local Science and Technology Development Fund Project (Grant No. YDZX2024125).

ORCID iDs

Yazhen Zhu

Qing Song

References

Sang

Pan

, et al. Dynamic AGV scheduling model with special cases in matrix production workshop. IEEE Trans Ind Inform 2023; 19: 7762–7770.

Krishnamoorthy

Satheesh

Sudha

, et al. Effective scheduling of multi-load automated guided vehicle in spinning mill: a case study. IEEE Access 2023; 11: 9389–9402.

Gao

, et al. Tasks assigning and sequencing of multiple AGVs based on an improved harmony search algorithm. J Ambient Intell Humaniz Comput 2019; 10: 4533–4546.

Lin

Liu

Wang

, et al. A review of path-planning approaches for multiple mobile robots. Machines 2022; 10: 773.

Ren

Shao

, et al. An automated guided vehicle conflict-free scheduling approach considering assignment rules in a robotic mobile fulfillment system. Comput Ind Eng 2023; 176: 108932.

Deng

Jiang

, et al. A hybrid GA approach to the scheduling of machines and automated guided vehicles in flexible job shops. J Sichuan Univ (Nat Sci Ed) 2021; 58: 73–82.

Zhong

Yang

Dessouky

, et al. Multi-AGV scheduling for conflict-free path planning in automated container terminals. Comput Ind Eng 2020; 142: 106371–106371.

Jiao

. Study and realization of AGV scheduling in automatic storage ＆ retrieval system . Master Thesis, Shandong University, China, 2013.

Ulusoy

Sivrikaya-Serifoglu

Ümit

. A genetic algorithm approach to the simultaneous scheduling of machines and automated guided vehicles. Comput Oper Res 1997; 24: 335–351.

10.

Udhayakumar

Kumanan

. Task scheduling of AGV in FMS using non-traditional optimization techniques. Int J Simul Model 2010; 9: 28–39.

11.

Zhao

Liu

Lin

, et al. Design and implementation of a multiple AGV scheduling algorithm for a job-shop. Int J Simul Model 2020; 19: 134–145.

12.

Mavrovouniotis

Yang

Van

, et al. Ant colony optimization algorithms for dynamic optimization: a case study of the dynamic travelling salesperson problem [research frontier]. IEEE Comput Intell Mag 2020; 15: 52–63.

13.

Dorigo

Di Caro

. Ant colony optimization: a new meta-heuristic. In: Proceedings of the 1999 Congress on Evolutionary Computation-CEC99, Washington, DC, USA, 06-09 July 1999, pp.1470–1477: IEEE.

14.

Wei

Song

, et al. Improved ACO-based path planning with rollback and death strategies. Syst Sci Control Eng 2018; 6: 102–107.

15.

Liu

Zhang

. Dynamic schedule method based on improved rolling time domain optimization strategy. J Mech Eng 2013; 49: 182–190.

16.

Sahu

Parhi

Kumar

. An approach to optimize the path of humanoids using adaptive ant colony optimization. J Bionic Eng 2018; 15: 623–635.

17.

Akka

Khaber

. Mobile robot path planning using an improved ant colony optimization. Int J Adv Robot Syst 2018; 15: 1–7.

18.

Zhu

Zhang

, et al. Path planning of lunar robot based on dynamic adaptive ant colony algorithm and obstacle avoidance. Int J Adv Robot Syst 2020; 17: 1–14.

19.

Xiao

Sun

, et al. Multiobjective path optimization of an indoor AGV based on an improved ACO-DWA. Math Biosci Eng 2022; 19: 12532–12557.

20.

Ding

Chen

Yuan

. On the combination of genetic algorithm and ant algorithm. J Comput Res Dev 2003; 09: 1351–1356.

21.

Chen

Zhang

, et al. A jump point search improved ant colony hybrid optimization algorithm for path planning of mobile robot. Int J Adv Robot Syst 2022; 19: 1–9.

22.

Wang

Yang

Zhang

, et al. Robot path planning based on improved ant colony algorithm with potential field heuristic. Control Decis 2018; 33: 1775–1781.

23.

Deng

Zhang

Liu

. Ant colony optimization and particle swarm optimization for robot-path planning in obstacle environment. Control Theory Appl 2009; 26: 879–883.

24.

Zhang

, et al. A scheduling optimization method for multiple automated guided vehicle systems. Int J Adv Robot Syst 2024; 21: 1–13.

Task number	Start point	End point	Task number	Start point	End point
1	40	293	16	12	82
2	94	292	17	64	195
3	229	385	18	109	159
4	176	109	19	235	122
5	377	186	20	59	141
6	388	260	21	2	344
7	378	271	22	264	71
8	344	19	23	347	221
9	251	400	24	17	119
10	24	145	25	186	318
11	99	374	26	103	224
12	370	18	27	367	190
13	84	249	28	133	243
14	261	341	29	160	387
15	35	203	30	185	236

Task number	Start point	End point	Task number	Start point	End point
1	40	293	16	12	82
2	94	292	17	64	195
3	229	385	18	109	159
4	176	109	19	235	122
5	377	186	20	59	141
6	388	260	21	2	344
7	378	271	22	264	71
8	344	19	23	347	221
9	251	400	24	17	119
10	24	145	25	186	318
11	99	374	26	103	224
12	370	18	27	367	190
13	84	249	28	133	243
14	261	341	29	160	387
15	35	203	30	185	236

Multi-AGV multitask collaborative scheduling based on an improved ant colony algorithm

Abstract

Keywords

Introduction

Problem description

Problem scenario model

Mathematical model

Algorithm design

Traditional ACO algorithm

Prior-time based improved ACO algorithm

Simulation test and analysis

Space–time conflict test

Multitask scenario test

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iDs

References

Task number	Start point	End point	Task number	Start point	End point
1	40	293	16	12	82
2	94	292	17	64	195
3	229	385	18	109	159
4	176	109	19	235	122
5	377	186	20	59	141
6	388	260	21	2	344
7	378	271	22	264	71
8	344	19	23	347	221
9	251	400	24	17	119
10	24	145	25	186	318
11	99	374	26	103	224
12	370	18	27	367	190
13	84	249	28	133	243
14	261	341	29	160	387
15	35	203	30	185	236