Grid-Map-Based Path Planning and Task Assignment for Multi-Type AGVs in a Distribution Warehouse

Abstract

In an intelligent distribution warehouse, latent AGVs are used for horizontal handling, and forklift AGVs are used for horizontal or vertical handling. Studying the path planning and task assignment problem when the two types of AGVs are mixed can help improve the warehouse operation efficiency and reduce the warehouse operation cost. This paper proposes a two-stage optimization method to solve this problem. In the first stage, the warehouse plan layout is transformed into a raster map, and the shortest path between any two points of the warehouse without conflict with fixed obstacles is planned and stored using the A* algorithm combined with circular rules, and the planned shortest path is called directly in the subsequent stages. In the second stage, to minimize the task completion time and AGV energy consumption, a genetic algorithm combining penalty functions is used to assign horizontal handling tasks to submerged AGVs or forklift AGVs and vertical handling tasks to forklift AGVs. The experimental results show that the method can meet the 24 h operation requirements of an intelligent distribution warehouse and realize the path planning and task assignment of forklift AGVs and latent AGVs. And furthermore, the number of AGVs arranged in the warehouse can be further reduced.

1. Introduction

With the opening of the Industry 4.0 era, AGV, IoT, cloud computing, AR, and other technologies continue to be put into practical application. In 2012, the application of Amazon Kiva was a successful example of the Industry 4.0 era. In the Kiva system, many AGVs carried shelves to pick-up stations, replacing the traditional manual pick-up using trolleys. This led to the massive use of AGVs in the warehousing sector. Multi-AGV systems in warehousing have been widely recognized as a practical means of improving productivity while significantly reducing operating costs [1]. The AGV operation optimization problem has also gradually become a research hotspot, mainly including task assignment, path planning, and joint optimization [2,3], which will be categorized and reviewed below.

AGV task assignment problem refers to assigning multiple tasks to multiple AGVs and determining the order in which each AGV performs the tasks. As shown in

Table 1. Studies related to AGV task assignment.

	Optimization Objective			Solution Algorithms			Other Factors
	Minimum Completion time	Minimum Number of AGVs	Maximum AGV Utilization	Genetic Algorithm	Ant Colony Algorithm	Particle Swarm Optimization	Charging	Layout
Tang et al. [7]	√	——	——	√	——	——	——	√
Xu et al. [8]	√	√	——	√	√	——	——
Udhayakumar et al. [9]	√	——	√	√	√	——	——	——
Liu et al. [10]	√	√	——	√	——	——	√	——
Mousavi et al. [11]	√	√	——	√	——	√	√	——
Li et al. [12]	√	——	——	√	——	——	√	——
Liang et al. [13]	√	——	——		√	——	——	——

, most of the existing studies focus on multiple numbers and single types of AGVs, mainly using completion time, number of AGVs, and AGV utilization as the optimization objectives of task assignment and solving them with the targeted improvement of genetic algorithms and ant colony algorithms. A small portion of the literature also combines problems such as charging and picking station layout with AGV task assignments. With the increasing complexity of AGV application scenarios, a small portion of the literature has begun to research multiple types of AGVs. Zhou et al. [4] divided the parts needed by automobile production lines into light materials and heavy materials and proposed and solved the material handling problem with a time window for two types of AGV; light materials were transported via multi-load AGV, and heavy materials were transported via single-load AGV. There are also a few studies on the joint optimization of AGVs and associated equipment. Aziez et al. [5] modeled the dual optimization of AGVs and trolleys for the actual situation of using trolleys to move materials and AGVs to move trolleys in hospitals and proposed an adaptive large domain search algorithm for fast response to dynamic demands. Hu et al. [6] studied the problem of task assignment for AGVs and automated crane trucks in automated container terminals.

AGV path planning is finding a path that allows AGV to reach the destination quickly without interference. The existing research can be divided into traditional and bionic intelligent path planning. Traditional path planning includes the artificial potential field method, Dijkstra’s algorithm, and the A-star algorithm. Khatib [14] first proposed a real-time obstacle avoidance method for robotic arms based on the concept of artificial potential field, assuming that the robotic arms are in a virtual force field, in the attraction generated via the target point and the repulsion generated via the obstacle. However, the traditional artificial potential field method is easily limited to local information, resulting in congestion, locking, and so on. However, the traditional, artificial, potential field method is easily limited by the localization of information, which leads to congestion and lock up, etc. The subsequent studies focus on achieving conflict-free path planning for robots by improving the local minimum problem [15,16,17]. Dijkstra algorithm is a classical path search algorithm for global path search in a static environment, which is fast and accurate in the case of a few nodes and is mainly used in topological maps. Kim et al. [18] combine the Dijkstra algorithm and time window to realize the conflict-free shortest path of AGV in a bidirectional flow network. The A-star algorithm is a heuristic search algorithm that combines the advantages of the Dijkstra algorithm and Breadth First Search. Due to its high efficiency, the A-star algorithm is widely used in real-time systems, artificial intelligence, and other fields, mainly in grid-based maps. Chiddarwar et al. [19] use the A-star algorithm to obtain the path without conflict between the robot and static obstacles, then dynamically adjust the robot sequence to resolve the conflict between multiple robots. Tang et al. [20] propose an improved geometric A-star algorithm for path planning to form smoother paths. Fransen et al. [21] improve the A-star algorithm to find the least-cost path with turn cost. The intelligent bionic algorithm mainly includes the genetic algorithm, ant colony algorithm, particle swarm algorithm, whale algorithm, and so on. Intelligent bionic algorithms are often appropriate for path planning when the operating environment is complex. Faridi et al. [22] propose to combine improved artificial swarm neighborhood search planning with evolutionary planning to solve multi-robot, multi-objective navigation problems in unknown dynamic environments. There are also studies using the ant colony algorithm [23] and the sheep flock heredity algorithm [24] for multi-robot path planning. With the complexity of the operating environment, path planning is often combined with dynamic obstacle avoidance problems. Zhong et al. [25] add time conflict-free constraints to the path planning model to obtain conflict-free scheduling of AGVs. In the field of intelligent vehicles, Gao et al. [26,27] predict the trajectories of potentially conflicting objects or intelligent vehicles, which also has some reference value for AGV dynamic obstacle avoidance.

Due to the importance and urgency of task assignment and path planning of AGVs, the joint optimization problem of the two is also a hot research topic. Most of the early research focused on exact algorithms. Krishnamurthy et al. [28] construct a mixed integer programming model to describe the DCFRP (dispatching and conflict-free route problem) and solve it using a column generation algorithm. Desaulniers et al. [29] developed exact methods combining column generation, greedy search heuristics, and branch-and-cut algorithms. As the solution size becomes larger, solution methods such as space–time networks, double-layer programming, and phased methods have been proposed one after another. Murakami [30] and Nishida et al. [31] solved the AGV path planning and task assignment problem by constructing space–time network models. Nishi et al. [32], Yang et al. [33], and Ji et al. [34] solved the problem using a two-layer planning approach, with the upper layer solving for AGV task assignment and the lower layer solving for AGV path planning. Hu et al. [35] and Liang et al. [36] proposed three-staged methods of solving path planning, task assignment, and conflict resolution sequentially.

Existing literature shows fruitful research results on AGV task assignment, path planning, and joint optimization. However, they mainly focus on operation workshops or automated terminals. Scenarios are mostly abstracted as topological maps, often ignore fixed obstacles in operation scenarios, and need to consider AGV simulation paths, which are less applicable in warehouse environments with a high density of facilities and equipment. Most of the existing research focuses on single-type AGVs. With the strengthening of intelligent requirements of warehousing, the demand for mixed operations of multiple types of AGVs, such as latent AGVs and forklift AGVs, becomes more significant. It is necessary to combine the scenario characteristics of intelligent distribution warehouses, to make targeted expansion of the research on AGV path planning and task assignment, and to realize the integration and optimization of multiple types of AGVs.

To solve the path planning and task assignment problem of latent AGVs and forklift AGVs in an actual intelligent distribution warehouse to achieve warehouse operation efficiency improvement and warehouse operation cost reduction, a two-stage optimization method combining offline planning and online planning is proposed. The first stage is offline shortest path planning, constructing the determined warehouse layout as a grid map, using the A-star algorithm for shortest path planning, and storing the shortest path and distance between any two grids as offline data, which can directly call the offline data to determine the travel path when the tasks in different planning cycles change, which can greatly reduce the repeated planning in practical application. The second stage is online multi-type task assignment, obtaining real-time updated task data, using the genetic algorithm to solve the problem with the goal of minimum task completion time and energy consumption of AGVs, and assigning two types of handling tasks to corresponding types of AGVs.

The rest of this paper is organized as follows: Section 2 performs the problem description; Section 3 constructs the mathematical model; Section 4 presents the proposed solution method; Section 5 conducts a case study; Finally, Section 6 concludes the paper.

2. Problem Description

A distribution warehouse is important for consolidating and distributing goods, mainly for short-term storage and rapid transit. Therefore, it is often necessary to put both latent AGVs and forklift AGVs in the warehouse. Latent AGVs can only realize the horizontal handling of palletized goods, while forklift AGVs can realize vertical or horizontal handling of palletized goods. The research problem is shown in Figure 1. It can be formulated as follows: in a certain planning cycle, there are multiple pallets to be handled in the distribution warehouse generated at different times, divided into horizontal handling tasks and vertical handling tasks according to whether they need to go up and down the shelves. The AGV parking area houses many latent AGVs and forklift AGVs. The scheduling system needs to arrange for the AGVs to visit all tasks’ pickup and delivery points along the shortest path at a limited time and finally return to the AGV parking area. AGV movement process has no conflict with the fixed facilities in the warehouse. Latent AGVs or forklift AGVs can perform horizontal handling tasks, while vertical handling tasks can only be performed using forklift AGVs. This study needs to abstract the warehouse as a grid map, and the fixed facilities are represented as inaccessible grids. The following two core problems are solved: multi-type task assignment based on assignment principle and shortest path planning based on static obstacle avoidance.

In addition to the above description, the following assumptions are considered in this paper:

• AGV runs at a constant speed without considering the influence of full load/no-load and turning;
• No additional loss time for AGV operation regardless of AGV starting, braking, forking, and so on;
• Regardless of the size difference of AGV, the two types of AGV all occupy one grid;
• AGV charging is not considered;
• The operating environment is a static network, dynamic situations such as conflicts between AGVs and sudden obstacles are not considered.

3. Mathematical Modeling

Two models are involved in this study. Model 1 is the path planning model, the input is the raster map, and the outputs are the shortest path and distance between any two grids. Model 2 is the task assignment model, the shortest path distance derived from Model 1, the set of AGVs and the set of tasks are the input data, and the output is the schedule of tasks and AGVs.

3.1. Path Planning Model

The solution goal of this stage is to obtain the shortest path and path distance between any two passable grids. The parameters of the path planning model are defined as shown in

Table 2. The parameters of the path planning model.

Symbol	Description
Set
$W$	$\mathrm{Set} \mathrm{of} \mathrm{all} \mathrm{grids}, W=G\cup O$
$G$	Set of passable grids
$O$	Set of obstacle grids
Parameter
$\left(x_g,y_g\right)$	$\mathrm{X}-\mathrm{coordinate} \mathrm{value} \mathrm{and} \mathrm{Y}-\mathrm{coordinate} \mathrm{value} \mathrm{of} \mathrm{grid} g$
$D_{ij}$	$\mathrm{The} \mathrm{distance} \mathrm{of} \mathrm{the} \mathrm{path} \mathrm{of} \mathrm{the} \mathrm{AGV} \mathrm{from} \mathrm{the} \mathrm{starting} \mathrm{grid} i$$\mathrm{to} \mathrm{the} \mathrm{ending} \mathrm{grid} j$
Variable
$R_{g{g}^{\prime }}^{ij}$	$\mathrm{Decision} \mathrm{variables}. \mathrm{Takes} 1 \mathrm{if} \mathrm{the} \mathrm{path} \mathrm{of} \mathrm{AGV} \mathrm{from} \mathrm{the} \mathrm{starting} \mathrm{grid} i$$\mathrm{to} \mathrm{the} \mathrm{ending} \mathrm{grid} j$$\mathrm{passes} \mathrm{through} \mathrm{two} \mathrm{different} \mathrm{grids} g$$\mathrm{and} g^{\prime }$ consecutively and 0 otherwise.

.

In order to reduce the computational effort, the definition can be given directly for the particular case where path planning is not required, as shown in Equation (1). When the starting and ending grids are the same, the shortest path is empty, and the path distance is 0. When there is an obstacle grid in the starting or ending point, and the starting and ending points are different, the shortest path is empty, and the path distance is infinite.

$$D_{ij}=\left\{\begin{array}{cc}0& \forall i\in W,j\in W,i=j\\ \infty & \forall i\in O or j\in O,i\ne j\end{array}\right.$$

(1)

When the start and end points are located in different passable grids, the shortest path is solved by constructing the path planning model.

$$D_{ij}=min\sum _{g\in G}\sum _{g^{\prime }\in G}\left(R_{g{g}^{\prime }}^{ij}\times \sqrt{{\left(x_g-x_{g^{\prime }}\right)}^2+{\left(y_g-y_{g^{\prime }}\right)}^2}\right),\forall i,j\in G,i\ne j$$

(2)

$$R_{g{g}^{\prime }}^{ij}\times \left|x_g-x_{g^{\prime }}\right|\le 1,\forall i,j,g,g^{\prime }\in G,i\ne j$$

(3)

$$R_{g{g}^{\prime }}^{ij}\times \left|y_g-y_{g^{\prime }}\right|\le 1,\forall i,j,g,g^{\prime }\in G,i\ne j$$

(4)

$$\sum _{g\in G}{R}_{ig}^{ij}=1,\forall i,j,g\in G,i\ne j$$

(5)

$$\sum _{g\in G}{R}_{gj}^{ij}=1,\forall i,j,g\in G,i\ne j$$

(6)

$$\sum _{g\in G}{R}_{g{g}^{\prime }}^{ij}=\sum _{g^{\prime \prime }\in G}{R}_{g^{\prime }{g}^{\prime \prime }}^{ij},\forall i,j,g,g^{\prime }\in G,i\ne j,g^{\prime }\ne i,g^{\prime }\ne j$$

(7)

$$R_{g{g}^{\prime }}^{ij}=\left\{\mathrm{0,1}\right\},\forall i,j,g,g^{\prime }\in G,i\ne j$$

(8)

The Objective Function (2) represents the minimized path distance D_ij. Constraints (3) and (4) represent movement constraints, which restrict the AGV to move only in 8 adjacent grids in the grid map and gradually approach the ending point. Constraint (5) indicates that the AGV must start from the starting grid. Constraint (6) indicates that the AGV must reach the ending grid. Constraint (7) indicates the other grids except the starting and ending grids to keep the inflow and outflow equal. Constraint (8) represents variable value constraint.

3.2. Task Assignment Model

The task assignment model has to consider both the efficiency and cost of AGV operation, so the optimization objectives are chosen to minimize task completion time and AGV energy consumption. The parameters of the task assignment model are defined as shown in

Table 3. The parameters of the task assignment model.

Symbol	Description
Set
$M$	Set of tasks
$K$	Set of AGVs
Parameter
$i_m$	Pickup grid number of task m
$j_m$	Delivery grid number of task m
$p_m$	$\mathrm{Type} \mathrm{of} \mathrm{task} m. \mathrm{If} p_m=1$$, \mathrm{it} \mathrm{means} \mathrm{vertical} \mathrm{handling} \mathrm{task}. \mathrm{If} p_m=0$, it means the horizontal handling task
$t_m^1$	Generation time of task m
$t_m^2$	Deadline of task m
$u_k$	$\mathrm{Type} \mathrm{of} \mathrm{AGV} k. \mathrm{If} u_k=1$$, \mathrm{it} \mathrm{means} \mathrm{latent} \mathrm{AGV}. \mathrm{If} u_k=0$, it means forklift AGV
$f_k$	Starting grid number of AGV k
$V_k$	Running speed of AGV k, related to the type of AGV, m/s
$D_{i_m{j}_m}$	$\mathrm{Path} \mathrm{distance} \mathrm{from} \mathrm{pickup} \mathrm{grid} i_m$$\mathrm{to} \mathrm{delivery} \mathrm{grid} j_m$, obtained from the path planning model, m
$e_k$	Power consumption factor of AGV k, related to the type of AGV, kWh/(s·tons)
$W_k$	Weight of AGV, related to AGV type, tons
$w$	Weight of goods, tons
$D_k$	Path distance of AGV k completing all assigned tasks, m
$T_k$	Time for AGV k to complete the assigned task, s
$T_{km}^s$	$\mathrm{The} \mathrm{time} \mathrm{when} \mathrm{AGV} k \mathrm{starts} \mathrm{task} m, \mathrm{i}.\mathrm{e}., \mathrm{the} \mathrm{time} \mathrm{when} \mathrm{it} \mathrm{is} \mathrm{ready} \mathrm{to} \mathrm{leave} \mathrm{the} \mathrm{pickup} \mathrm{grid} i_m$
$T_{km}^e$	$\mathrm{The} \mathrm{time} \mathrm{when} \mathrm{AGV} \mathrm{k} \mathrm{finishes} \mathrm{task} m, \mathrm{i}.\mathrm{e}., \mathrm{the} \mathrm{time} \mathrm{when} \mathrm{it} \mathrm{is} \mathrm{ready} \mathrm{to} \mathrm{leave} \mathrm{delivery} \mathrm{grid} j_m$
Variable
$X_{mm\prime }^k$	Decision variables. Takes 1 if AGV k performs task m and task m’ consecutively and 0 otherwise
$Y_{km}$	Decision variables. Takes 1 if task m is executed using AGV k and 0 otherwise.

.

Optimization Objective 1 is the minimum task completion time, as shown in Equation (9), in which its calculation is related to the AGV moving distance, AGV running speed, and task generation time. Equation (10) represents the time when AGV k starts to perform task m. It is necessary to consider whether the task is generated when AGV reaches the task pickup grid, which can be discussed in two cases: if task m is the first task performed via AGV k, compare the time when AGV reaches the pickup grid of task m along the shortest path from the starting point and the generation time of task m, and take the larger of the two; if task m is the task after the first task executed using AGV k, compare the time of the shortest path from the front task delivery grid to the pickup grid of task m and the generation time of task m, and take the larger of the two. Equation (11) indicates the time for AGV k to end the execution of task m. The value is taken as the time for AGV k to start execution of task m plus the time to reach the task delivery grid along the shortest path from the task m pickup grid. Equation (12) indicates that the task completion time of AGV k is the time to return to the starting point along the shortest path after AGV k has completed the last task assigned.

$$f_1=\mathit{min}max\left\{T_k\right\},k\in K$$

(9)

$$T_{km}^s=\left\{\begin{array}{ccc}\hfill max\left\{\frac{D_{f_k{i}_m}}{V_k},t_m^1\right\},& \hspace{1em}& \forall k\in K,m\in M,Y_{km}=1,\sum _{m^{\prime }\in M}{X}_{m^{\prime }m}^k=0\\ max\left\{{(T}_{k{m}^{\prime }}^e+\frac{D_{j_{m^{\prime }}{i}_m}}{V_k}),t_m^1\right\},& \hspace{1em}& \forall k\in K,m\in M,\sum _{m^{\prime }\in M}{X}_{m^{\prime }m}^k=1\hfill \end{array}\right.$$

(10)

$$T_{km}^e=T_{km}^s+\frac{D_{i_m{j}_m}}{V_k},\forall k\in K,m\in M,Y_{km}=1$$

(11)

$$T_k=T_{km}^e+\frac{D_{j_m{f}_k}}{V_k},\forall k\in K,m\in M,Y_{km}=1,\sum _{m^{\prime }\in M}{X}_{m{m}^{\prime }}^k=0$$

(12)

Optimization Objective 2 is the minimum total energy consumption of the AGVs, as shown in Equation (9). The existing literature has modeled AGV power consumption, and Zhou et al. [4] proposed that AGV power consumption is proportional to AGV weight and travel distance. In this paper, we optimize the existing model by considering the weight difference between the two states of AGV handling pallets and no load. Equation (14) represents the travel distance of AGV k, consisting of three parts. Equation (15) represents the travel distance of AGV k when performing the first task, taking the value of the shortest path distance of “AGV starting point → task pickup point → task delivery point”. Equation (16) represents the travel distance of AGV k when performing intermediate tasks, taking the value of the sum of the shortest path distance of “before the task delivery point → task pickup point → task delivery point”. Equation (17) represents the travel distance of AGV k after performing the last task to return to the starting point, taking the value of the shortest path distance of “task delivery point → AGV starting point”.

$$f_2=\mathit{min}\sum _{k\in K}\left(e_k\left(W_k+w\right)\sum _{m\in M}{Y}_{km}{D}_{i_m{j}_m}+e_k{W}_k\left(D_k-\sum _{m\in M}{Y}_{km}{D}_{i_m{j}_m}\right)\right)=\mathit{min}\sum _{k\in K}\left(e_k{W}_k{D}_k+e_{k}w\sum _{m\in M}{Y}_{km}{D}_{i_m{j}_m}\right)$$

(13)

$$D_k=D_1^k+D_2^k+D_3^k,\forall k\in K$$

(14)

$$D_1^k=D_{f_k{i}_m}+D_{i_m{j}_m},\forall k\in K,m\in M,Y_{km}=1,\sum _{m^{\prime }\in M}{X}_{m^{\prime }m}^k=0$$

(15)

$$D_2^k=\sum _{m\in M}\sum _{m^{\prime }\in M}{X}_{m{m}^{\prime }}^k\left(D_{j_m{i}_{m^{\prime }}}+D_{i_{m^{\prime }}{j}_{m^{\prime }}}\right),\forall k\in K$$

(16)

$$D_3^k=D_{j_m{f}_k},\forall k\in K,m\in M,Y_{km}=1,\sum _{m^{\prime }\in M}{X}_{m{m}^{\prime }}^k=0$$

(17)

Equation (18) indicates the service relationship constraint, the constraint that each task must be served via an AGV. Equation (19) indicates that the equipment selection constraint that constrains the vertical handling task cannot be completed using latent AGV. Equation (20) indicates that the time window constraint, to avoid congestion in the warehouse, constrains the start time of AGV k execution task m between the generation time and deadline of task m. Equation (21) indicates that the time order constraint, to avoid long waiting times for tasks, constrains the AGV in the execution of multiple tasks, the task with the earlier generation time is executed first. Equations (22) and (23) represent variable value constraints.

$$\sum _{k\in K}{Y}_{km}=1,\forall m\in M$$

(18)

$$\sum _{k\in K}\sum _{m\in M}{Y}_{km}{u}_k{p}_m=0$$

(19)

$$t_m^1\le T_{km}^s\le t_m^2,\forall k\in K,m\in M,Y_{km}=1$$

(20)

$$T_{km}^s\le T_{k{m}^{\prime }}^s,\forall k\in K,Y_{km}=Y_{k{m}^{\prime }}=1,t_m^1\le t_{m^{\prime }}^1$$

(21)

$$Y_{km},X_{mm\prime }^k=\left\{\mathrm{0,1}\right\},\forall k\in K,m\in M,m^{\prime }\in M$$

(22)

$$Y_{km}\ge X_{m{m}^{\prime }}^k,\forall k\in K,m\in M,m^{\prime }\in M$$

(23)

4. Solution Algorithms

The grid-map-based multi-type AGV path planning and task assignment are essentially two problems, and we design two algorithms to solve them separately. In the first stage, we use the A-star algorithm combined with the cyclic rule to solve the path planning model to obtain the shortest path planning scheme for AGVs. In the second stage, we use the genetic algorithm to solve the task assignment model with the shortest path of the first stage as known information.

4.1. A-Star Algorithm for Path Planning Model

The A-star algorithm is the most effective heuristic search algorithm to solve the shortest path search problem. The basic idea is to use the evaluation function to determine the search direction. Starting from the starting point and expanding to the surrounding nodes, the cost value of each surrounding node is calculated using the evaluation function, and the least costly node is selected as the next expansion node. This process is repeated until the target point is reached and the final path is generated.

The A-star algorithm’s evaluation function f(n) is calculated, as shown in Equation (24). g(n) indicates the actual distance moved from the starting point to node n, and h(n) indicates the estimated distance from node n to the target point. Since the avoidance between AGV and fixed obstacles must be considered, AGV cannot travel along a straight line, the Manhattan distance is chosen as the heuristic function., as shown in Equation (25).

$$f\left(n\right)=g\left(n\right)+h\left(n\right)$$

(24)

$$h\left(n\right)=\left|x_1-x_2\right|+\left|y_1-y_2\right|$$

(25)

The existing A-star algorithm mainly solves the shortest path between known points A and B. In this paper, we improve the A-star algorithm by setting the cyclic rules to continuously solve the shortest path between any two points in the warehouse. Assuming that there are m elements in the set G of passable grids, the logic of the loop calls the A-star algorithm in this paper is shown in Algorithm 1.

Algorithm 1. Framework for recurring A-star algorithm

1:  Initialize: Set of passable grids G, position of the starting grid in the set G o, position of the ending grid in the set G d, starting grid number G(o), ending grid number G(o)  2:  for o = 1:(m−1) do  3:  while d ≤ m do  4:  Shortest path search from G(o) to G(d) using A-star algorithm  5:  d = d + 1  6:  end while  7:  end for  8:  for o = 2:m do  9:  while d > 0 do  10:   Shortest path search from G(o) to G(d) using A-star algorithm  11:   d = d − 1  12:   end while  13:   end for

The steps for solving the shortest path with known starting and ending points using the A-star algorithm are:

Step 1: Add the starting point to the Open list (list of nodes to be examined).

Step 2: Check if the Open list is empty. If empty, the retrieval fails, and the input solution is not feasible; otherwise, execute Step 3.

Step 3: Examine the Open list, find the node n with the smallest value of f(n), and move it to the Close list (list of nodes that have been inspected).

Step 4: Determine whether node n is the target point. If yes, complete the shortest path search and execute Step 7; otherwise, execute Step 5

Step 5: Check the eight squares around node n. If it is not passable or already in the Close list, ignore it and return to Step 2; otherwise, execute Step 6.

Step 6: Determine if the eight squares around node n are in the Open list.

If not, add the surrounding squares to the Open list and set the current node as the parent node, record the values of f(n), g(n), and h(n) of the surrounding squares, and return Step 2.

If in, determine whether the path from the current node to the surrounding nodes already in the Open list is closer (judged via g(n), the smaller, the closer). If closer, set the current node as the parent node and recalculate the values of f(n) and g(n) of the surrounding squares and return Step 2; if not closer, return Step 2 directly.

Step 7: Complete the shortest path search, backtrack the Close list, and record the shortest path and distance of AGV from the starting point to the ending point.

Since the two-stage scheduling method proposed in this paper requires solving the shortest path between any two points in the warehouse first, the computational complexity of the path planning process is related to the number of grids. The number of times the A-star algorithm needs to be called during path planning for a map with n grids is n(n−1)/2; the time complexity of the A-star algorithm is O(nlog(n)) [37]. Therefore, the time complexity of the path planning algorithm proposed in this paper is O(n³log(n)). The time complexity of the path planning algorithm is verified using Matlab2021 on a laptop computer equipped with an AMD R5 5600H processor and 16 GB of RAM. The path planning time was 2.6 s and 70238.9 s for a grid size of 100 and 2500, respectively. As the map size (number of grids) increases, the path planning time increases rapidly. The A-star algorithm can be optimized in the future, thus further improving the path planning efficiency.

4.2. Genetic Algorithm for Task Assignment Model

4.2.1. Encoding Operation

We use the real number coding method to represent the chromosomes. The number position indicates the task number, and the number indicates the AGV number to which the task matches. To meet the time sequence constraint, the tasks are numbered according to the task generation time (the task number generated first is smaller), and the AGV executes the task with the smaller number first. The chromosome shown in Figure 2 represents the AGV task assignment scheme as follows: AGV1 executes tasks 6 and 10 in order, AGV2 executes Task 7, AGV3 executes Tasks 1, 2, 4, and 9 in order, and AGV4 executes Tasks 3, 5 and 8 in order.

4.2.2. Population Initialization

The goal of population initialization is to generate a population number of individuals, and the feasible initial solution in this paper is affected by service relationship constraints, equipment selection constraints, and time window constraints. To generate a better initial population, the initial population is constructed in this paper by the following three steps:

Step 1: Generate the initial solution that satisfies the service relationship constraint and the equipment selection constraint. Firstly, form an all-zero array of task numbers. Secondly, assign vertical handling tasks to forklift AGVs. Thirdly, assign horizontal handling tasks to latent AGVs or forklift AGVs. As shown in Figure 3, suppose there are four tasks in the warehouse, Tasks 1 and 3 are vertical handling tasks, Tasks 2 and 4 are horizontal handling tasks; there are 3 AGVs, in which AGV1 is a latent AGV, AGV2 and 3 are forklift AGVs.

Step 2: Generate the initial solution that satisfies the time window constraint. Determine whether the solution formed in the first step satisfies the time window constraint. If it satisfies, the solution is feasible; if not, it is discarded.

Step 3: Repeat Steps 1 and 2 until the initial solution for the number of populations is generated.

4.2.3. Fitness Function

Fitness is used to judge the quality of individuals in the population. The higher the fitness value, the better the corresponding optimization result. In this paper, to solve the minimum value problem, the inverse of the objective function can be used as the fitness function. The coding method used in this paper cannot ensure that the newly generated individuals meet the time window constraints after crossover and mutation. To solve the problem of violation of constraints simply, this paper uses the penalty function to improve the genetic algorithm.

$$fitness=\frac{1}{f_1{f}_2+f}$$

(26)

$$f=\left\{\begin{array}{cc}\alpha ,& \mathrm{The} \mathrm{time} \mathrm{window} \mathrm{constraint} \mathrm{is} \mathrm{not} \mathrm{satisfied}\hfill \\ 0,& \mathrm{The} \mathrm{time} \mathrm{window} \mathrm{constraint} \mathrm{is} \mathrm{satisfied}\hfill \end{array}\right.$$

(27)

Equation (26) is the formula for calculating the fitness function. Equation (27) indicates that the penalty function f takes a larger positive integer when the task assignment scheme exceeds the time limit, eliminating the scheme.

4.2.4. Selection Operation

The selection operation is selecting good individuals as parents to enter the next generation for genetic operation. In this paper, we choose the binary tournament method. Compare the parent population two by two, select the individuals with more excellent fitness, and put them into the offspring population. Assuming that the population size is N, N comparisons are required, and two individuals are randomly selected for comparison in each cycle. The one with more excellent fitness is selected. There may be duplicates among the newly selected individuals, and only one is retained.

4.2.5. Crossover Operation

In this paper, we use the two-point crossover. Choose the same two positions X₁ and X₂ of two individuals (A and B) at random, and exchange the parts of X₁ and X₂ of two individuals, as shown in Figure 4.

4.2.6. Mutation Operation

The second step of changing individual genes is to perform a mutation operation. In this paper, we use positional mutation, that is, we randomly select one gene position X₁, and then randomly select one gene position X₂ (X₁ is not equal to X₂) from other genes corresponding to the same task type as X₁ to avoid getting individuals that do not satisfy the equipment selection constraint, and exchange the X₁ and X₂, as shown in Figure 5.

4.2.7. Recombination Operation

The number of offspring individuals obtained after the above selection, crossover, and mutation may be less than the population number, and a certain number of offspring individuals need to be supplemented to complete the update of the parent population. In this paper, we adopt the idea of an elite retention strategy to rank the parent population according to fitness. If there are n individuals in the offspring, and the population number is N, then we select the top (N−n) individuals in the parent population and add them to the offspring population. A new parent population is formed using the above steps as the population for the next selection operation.

5. Analysis of Case Study

To verify the model’s and algorithm’s performance, the A-star algorithm and genetic algorithm are implemented using MATLAB programming to solve the multi-type AGVs path planning and task assignment problems. We construct a real intelligent distribution warehouse operation scenario as a grid map of 50 m in length and 50 m in width, as shown in Figure 6, with the grid codes increasing from left to right and from bottom to top, numbered from 1 to 2500, respectively. White grids are passable passages, and black grids are impassable barriers. The analysis of experimental results, such as path planning, task assignment, and marginal cost, are completed sequentially based on the grid map.

5.1. Parameter Setting

The population size of the genetic algorithm is 100, the number of iterations is 5000, the crossover probability and variation probability are 0.9 and 0.1, respectively, and the penalty function coefficient is 1000. We collected 900 pieces of data on 24 h operation of the above intelligent distribution warehouse, and some of the data are shown in

Table 4. Task parameters of the intelligent distribution warehouse.

Task Number	Task Type	Pickup Grid	Delivery Grid	Task Generation time	Task Deadline
1	Horizontal handling task	1	510	0:06:14	0:08:14
2	Horizontal handling task	7	825	0:06:14	0:08:14
3	Vertical handling task	13	963	0:08:06	0:10:06
4	Horizontal handling task	19	371	0:08:59	0:10:59
5	Vertical handling task	25	979	0:08:59	0:10:59
…	…	…	…	…	…
898	Horizontal handling task	32	1580	23:23:47	23:27:47
899	Vertical handling task	25	2325	23:23:47	23:27:47
900	Horizontal handling task	49	1448	23:25:47	23:29:47

. The weight of the goods handled in this warehouse is 1 ton. Currently, two latent AGVs and three forklift AGVs are put in to complete the handling tasks, and the AGV parameters are shown in

Table 5. AGV parameters of the intelligent distribution warehouse.

AGV Number	AGV Type	Starting Grid	Running Speed (m/s)	Weight (t)	Power Consumption Factor (Wh/m·t)
1	forklift AGV	2103	1.2	0.755	0.102
2	forklift AGV	1703	1.2	0.755	0.102
3	forklift AGV	1253	1.2	0.755	0.102
4	latent AGV	853	1.5	0.165	0.043
5	latent AGV	453	1.5	0.165	0.043

.

5.2. Analysis of Results

(1)

Path planning results

The calculations are performed in Matlab 2021a. We use the A-star algorithm to solve the path planning model to plan the shortest path between any two grids in the grid map, which finally forms a distance matrix with a scale of 2500 × 2500. Some data are shown in

Table 6. Distance matrix (partial).

Distance	Grid1	Grid2	Grid3	Grid4	Grid5	Grid6	Grid7	Grid8	Grid9	Grid10	…	Grid2500
Grid1	0	1	2	3	Inf	Inf	6.8	7.8	Inf	Inf	…	86
Grid2	1	0	1	2	Inf	Inf	5.8	6.8	Inf	Inf	…	83.2
Grid3	2	1	0	1	Inf	Inf	4.8	5.8	Inf	Inf	…	82.2
Grid4	3	2	1	0	Inf	Inf	3.8	4.8	Inf	Inf	…	81.2
Grid5	Inf	Inf	Inf	Inf	0	Inf	Inf	Inf	Inf	Inf	…	Inf
Grid6	Inf	Inf	Inf	Inf	Inf	0	Inf	Inf	Inf	Inf	…	Inf
Grid7	6.8	5.8	4.8	3.8	Inf	Inf	0	1	Inf	Inf	…	78.2
Grid8	7.8	6.8	5.8	4.8	Inf	Inf	1	0	Inf	Inf	…	77.2
Grid9	Inf	Inf	Inf	Inf	Inf	Inf	Inf	Inf	0	Inf	…	Inf
Grid10	Inf	Inf	Inf	Inf	Inf	Inf	Inf	Inf	Inf	0	…	Inf
…	…	…	…	…	…	…	…	…	…	…	…	…
Grid2500	86	83.2	82.2	81.2	Inf	Inf	78.2	77.2	Inf	Inf	…	0

. There are three cases of the shortest path in the grid map. In the first case, when i and j represent the same grid, the shortest path is empty, and the distance is 0, such as the diagonal elements in the distance matrix. In the second case, when there are impassable grids in i and j, the shortest path is empty, and the distance is infinite, such as the elements in rows and columns 5, 6, 9, and 10 in the distance matrix. In the third case, when both i and j are passable grids, the shortest paths are obtained using the A-star algorithm, and the distances are the length of the shortest path. As shown in Figure 7, the shortest path between grid 1 and grid 7 is {1,2,3,4,55,56,7}, and the distance is 6.8 m.

(2)

Results of task assignment

To verify the effectiveness of the multi-type AGV task assignment model constructed in this paper, we first conduct ablation experiments on the assignment relationship constraint. We select the first ten tasks in Table 4 (Tasks 3 and 5 are vertical handling tasks, and the rest are horizontal handling tasks) and the five AGVs shown in Table 5 (AGV 1, 2, and3 are forklift AGVs, and AGV2 and 4 are latent AGVs), and assign them using the multi-type AGV task assignment model and the multi-AGV task assignment model that without considering Equation (18), respectively. The experimental results are shown in the following

Table 7. The results of ablation experiments on the assignment relationship constraint.

Task	Multi-Type AGV Task Assignment Model	Multi-AGV Task Assignment Model without Considering Equation (18)
Task 1	AGV5	AGV4
Task 2	AGV5	AGV5
Task 3	AGV3	AGV4
Task 4	AGV5	AGV4
Task 5	AGV3	AGV4
Task 6	AGV5	AGV4
Task 7	AGV5	AGV4
Task 8	AGV4	AGV4
Task 9	AGV5	AGV5
Task 10	AGV4	AGV4
Task Completion Time (h)	0.5839	0.5839
Total Energy Consumption (KW·h)	0.0522	0.0372

, from which it can be seen that the multi-type AGV task assignment model assigns vertical handling Tasks 3 and 5 to forklift AGV3, and the multi-AGV task assignment model without considering Equation (18), assigns vertical handling Tasks 3 and 5 to latent AGV4 because latent type AGVs consume less energy, and the objective function2 of assigning vertical handling tasks to latent AGVs can achieve better results. However, this aligns differently from the actual situation because the latent AGVs cannot perform the up-and-down motion required for vertical handling tasks. This proves the validity and necessity of the task assignment constraint proposed in this paper, which can make the multi-type AGV task assignment model more compatible with the simultaneous operation of latent AGVs and forklift AGVs.

The genetic algorithm is used to solve the task allocation model with the scale of two latent AGVs, three forklift AGVs, and 900 tasks, and the iteration curves are shown in Figure 8. Both objective functions are constantly decreasing, proving the method’s effectiveness. In addition, planning the 24 h AGV task assignment scheme took about 178.7 s, which proved the practicality and efficiency of the algorithm.

The maximum task completion time (objective 1) is optimized from 23.4510 h to 23.4475 h, and a part of the task assignment scheme is shown in

Table 8. Task assignment scheme (partial).

Task Number	Assigned AGV	Task Generation Time	Task Deadline	AGV Arrival Time	Task Start Time	Task End Time
1	5	0.1039	0.1372	0.0020	0.1039	0.1066
2	4	0.1039	0.1372	0.0034	0.1039	0.1094
3	3	0.1350	0.1683	0.0070	0.1350	0.1394
4	3	0.1497	0.1831	0.1446	0.1497	0.1515
5	3	0.1497	0.1831	0.1537	0.1537	0.1584
…	…	…	…	…	…	…
898	5	23.3964	23.4631	23.3217	23.3964	23.4023
899	2	23.3964	23.4631	22.8391	23.3964	23.4135
900	5	23.4297	23.4964	23.4103	23.4297	23.4475

. It can be found that AGVs usually have arrived at the task pickup point for waiting before task generation, so the time to start performing tasks is limited by the task generation time, and there is little room for optimization of the maximum task completion time. At the same time, this reflects that the AGV waiting time is too long, and the utilization rate is not high, indicating that the number of AGVs put into operation in this warehouse is on the high side, and there may be room for optimization of quantity and type.

The energy consumption of AGVs (Objective 2) decreases from 10.9044 kWh to 6.7981 kWh, which shows a better optimization effect, indicating that the proposed method can greatly reduce the energy consumption of AGVs and the operating cost of the warehouse. To further analyze the effect of AGV type on energy consumption, we obtain the optimal scheduling scheme when the number of iterations is 500, 1000, 2000, 3000, 4000, and 5000. The results are shown in Figure 9 and Figure 10, the total energy consumption of AGVs is gradually optimized as the number of iterations increases, but the energy consumption of latent AGV4 and latent AGV5 gradually expands, indicating that more horizontal handling tasks are assigned to latent AGVs. The reason is that latent AGVs have a lower self-weight and energy consumption factor, and the energy consumption when moving goods across the same distance is lower than that of forklift AGVs. Therefore, it is recommended to use a latent AGV instead of a forklift AGV whenever possible when performing horizontal handling in actual operation.

To confirm the superiority of the multi-type AGV task assignment model in practical applications, we compare it with a common strategy in intelligent distribution warehouses, which is to assign idle AGVs to complete handling randomly, and the results are shown in the figure below. Figure 11 shows that the proposed multi-type AGV task assignment model can reduce the task completion time and total energy consumption by 0.04% and 40.41%, respectively, indicating that the method can optimize both efficiency and cost in practical application. The late generation of the final task mainly limits the low task completion time optimization level. The high optimization level of total energy consumption indicates that the proposed method can significantly reduce the energy loss of AGVs, which aligns with the future development trend of low carbonization.

(3)

Marginal cost analysis

Using the method proposed in this paper to optimize the AGV path and task assignment in the warehouse, AGVs spend much time waiting for task generation, indicating that putting in two latent AGVs and three forklift-type AGVs is too redundant. To improve the utilization rate of AGVs and reduce the cost of purchasing equipment for enterprises, we configured different numbers and types of AGVs located at the same starting point based on the same task conditions and conducted a comparative analysis of the maximum task completion time and AGV energy consumption.

Figure 12 shows the effect of the type and number of AGVs on the task completion time. It can be found that when one forklift AGV is put in, all the tasks in the warehouse can be completed under the condition that the time windows are satisfied. Moreover, when one latent AGV is added, the maximum task completion time can be optimized to a small extent (about the 80 s). The reason is that the latent AGVs run faster, and assigning the latest generated tasks to the latent AGVs can reduce the maximum task completion time.

Figure 13 shows the impact of the type and number of AGVs on the total energy consumption. It can be found that the scheme of “forklift AGV + 1 latent AGV” can significantly reduce the total energy consumption, and the continued investment in latent AGVs has little effect on the optimization of total energy consumption but will lead to a rapid increase in equipment acquisition costs. Therefore, it is recommended that the warehouse reduce the original two latent AGVs to one. When the number of latent AGVs is one, putting in one forklift AGV can already meet the demand of vertical handling tasks, and increasing the number of forklift AGVs has little impact on the total energy consumption, which also leads to a significant increase in cost. Therefore, it is recommended that the warehouse reduce the original three forklift AGVs to one.

According to this study, the AGV configuration of the warehouse can be optimized from the original “2 latent AGVs + 3 forklift AGVs” to “1 latent AGV + 1 forklift AGV”, and the equipment acquisition cost will be significantly reduced. This shows that this study can not only realize the path planning and task assignment of multi-type AGVs, improve operation efficiency, and save equipment energy consumption but also provide a more suitable AGV configuration solution for the warehouse and reduce operation cost.

6. Conclusions

This paper conducts an optimization study on the task assignment and path planning problem for the hybrid operation of latent AGVs and forklift AGVs in intelligent distribution warehouses, proposes a two-stage optimization model containing path planning and task assignment, and proposes the A-star algorithm combining cyclic rules and the genetic algorithm using penalty function. The effectiveness of the proposed method is verified using the 24 h operation data of an intelligent distribution warehouse. Firstly, the task assignment of multiple types of AGVs is realized, and the shortest path without conflict with fixed obstacles is planned for each AGV. Secondly, the original AGV configuration scheme of the warehouse is optimized, further reducing the warehouse’s cost. The limitations of this paper are as follows: (1) this paper’s path planning only considers static obstacle avoidance, temporarily ignoring the dynamic conflicts existing in the warehouse, such as conflicts between AGVs, sudden obstacles, etc.; (2) to simplify the model, temporarily ignoring the impact of AGV charging on AGV driving. Therefore, future research can try to add the AGV charging problem to improve the task assignment model while adding the third stage of optimization, calculating the time window of each AGV passing through each grid when completing the assigned task along the shortest path, and achieving dynamic conflict resolution via speed regulation.