AGV Scheduling Optimization of Automated Port Based on Disruption Management

Ching-Kuei Kao^1*, Qi-Er Ke², King-Zoo Tang³, Peng-Jung Lin⁴

¹Key Laboratory of LNG Industry Chain, Fujian University of Technology, Fuzhou.
²Department of Logistics Management, Fujian University of Technology, Fuzhou.
³Department of Information Management, Taiwan Chung Cheng University, Chiayi.
⁴Metaverse and New Media College, Yango University, Fuzhou.

DOI: 10.4236/jtts.2024.143025                

Abstract

The recent rapid development of China’s foreign trade has led to the significant increase in waterway transportation and automated container ports. Automated terminals can significantly improve the loading and unloading efficiency of container terminals. These terminals can also increase the port’s transportation volume while ensuring the quality of cargo loading and unloading, which has become an inevitable trend in the future development of ports. However, the continuous growth of the port’s transportation volume has increased the horizontal transportation pressure on the automated terminal, and the problems of route conflicts and road locks faced by automated guided vehicles (AGV) have become increasingly prominent. Accordingly, this work takes Xiamen Yuanhai automated container terminal as an example. This work focuses on analyzing the interference problem of path conflict in its horizontal transportation AGV scheduling. Results show that path conflict, the most prominent interference factor, will cause AGV scheduling to be unable to execute the original plan. Consequently, the disruption management was used to establish a disturbance recovery model, and the Dijkstra algorithm for combining with time windows is adopted to plan a conflict-free path. Based on the comparison with the rescheduling method, the research obtains that the deviation of the transportation path and the deviation degree of the transportation path under the disruption management method are much lower than those of the rescheduling method. The transportation path deviation degree of the disruption management method is only 5.56%. Meanwhile, the deviation degree of the transportation path under the rescheduling method is 44.44%.

Keywords

Automated Port, Disruption Management, Automated Guided Vehicle Scheduling, Dijkstra Algorithm

1. Introduction

China initially had a slow start in building automated container terminals. Nonetheless, with the vigorous implementation of China’s “One Belt, One Road” policy, automated container ports have become a crucial element of the strategic layout and will become the primary focus of the future port development. China is currently progressing toward to a strong maritime nation. To address the issue of shortage of fully automated container terminal numbers, China has expressed in policies, such as the “Construction Outline of a Strong Transportation Nation”, that they will establish an information infrastructure based on 5G, Beidou, and IoT. Moreover, the country will strengthen the development and promotion of the automated container terminal operating system. The goal is to basically complete the construction of the container hub port intelligent system by 2035, become a world-class port, and promote the construction of a strong transportation nation [1]. Automated guided vehicles (AGV) play a significant role in automated ports during the horizontal transportation. In the future, port operations must be safer, more energy-efficient, and have improved loading and unloading efficiency. Given that automated container terminals encompass these features, future terminal construction will be automated moving forward. Horizontal transport AGVs in automated container terminals typically use navigation devices to obtain and perceive environmental information to perform automatic driving and navigation, making it more efficient to load, unload, and transport goods. However, the pressure on horizontal transportation has been growing due to the development of the economy and the continuous growth of port transportation. In the limited container horizontal transportation paths, problems, such as path conflicts and road lock-outs, have become increasingly prominent in horizontal transportation AGV systems [2]. Ignoring the aforementioned disturbances will have a direct effect on the horizontal transportation system and may even result in system paralysis and stagnation, reducing the overall efficiency of the automated port.

Self-driving technology is used to schedule AGVs in an automated dock. Accordingly, the main factors that commonly interfere with AGV scheduling are as follows: 1) Information interference, such as traffic signs, pedestrians, vehicles, and static objects; 2) route interference, mainly involving path conflicts and road lock issues; 3) data processing, including signal data loss and changes in loading plans; and 4) vehicle control, including hardware and software control. The concept of disruption management will be used in this work to quantify the effect of disturbance on the system and how to restore regular operation after a disruption occurs. A new adjustment plan will be developed after a disturbance to minimize the effect of disturbance based on the initial goal. The basic idea of disruption management is to use models and solution algorithms to develop an initial operation plan at the beginning of the project. However, disturbances occur during a plan’s implementation due to various uncertain factors, making the original plan infeasible. At this time, a new plan must be generated in real-time. The new plan not only needs to consider the original optimization goals but also needs to minimize the negative effects brought by the disturbance [3].

When encountering disruptive events with uncertain factors in automated port-horizontal transportation, we should first determine if it affects AGV scheduling, specifically, if AGV scheduling is disturbed, and then examine whether the relevant theories of disruption management can be used to solve the problem. Currently, several scholars determined the disturbance based on subjective judgment [4] (i.e., an extremely serious disturbance event that affects the implementation of the original plan can be considered a disturbance). In other areas, the concept of disruption management is typically applied to certain situations, such as weather-related vehicle obstructions or short-term flight changes. After clarifying that disruption management-related theories can be used, the disturbance caused by the disturbance event must be measured. Then, the effect of the disturbance event on the entire system must be analyzed and evaluated. Finally, a disturbance recovery model is established, and the reasonable algorithms are combined to give feasible solutions in real-time and minimize the disturbance caused by the disturbance. In summary, the optimization of automated port AGV scheduling can be achieved by establishing a disturbance recovery model and judging the system’s disturbance based on the specific conditions to be minimized, which is of great significance for the normal operation of the automated port, energy conservation and emission reduction, and improvement of port operation efficiency.

This work first studied the various disturbance factors in AGV scheduling in automated ports, such as path conflicts, road lockouts, mechanical failures, AGV information loss, and changes in cargo plans, to determine the main disturbance factors that cause AGVs to be unable to execute the original dispatch plan. Once the main disturbance factors in AGV scheduling have been identified, the objective is to minimize the disruptions in the AGV transportation path. Thereafter, an AGV scheduling disturbance recovery model is constructed, and the Dijkstra algorithm is used to solve the disturbance recovery model, resulting in an optimal model optimization plan for minimizing system side effect conflicts in the AGV path. Finally, the Xiamen Yuanhai automated container terminal is selected as the object, and the container transportation volume of the port in 2021 is gathered to examine the overall layout of the horizontal transportation in combination with related literature. This work will simplify the layout of AGV horizontal transportation to provide data support for the AGV scheduling disturbance recovery model. A case analysis is conducted based on this information, and solutions are proposed based on the analysis results.

2. Literature Review

Automated terminal AGV scheduling and disruption management are two important aspects in the design and operation of an automated terminal AGV system. The basic theory of AGV scheduling in automated docks involves the allocation of tasks to AGVs, such as transporting containers or cargo to and from designated locations, in an efficient and optimized manner. This task can be achieved through various optimization algorithms, such as mathematical programming or heuristics, that consider certain factors, such as AGV availability, cargo type, transportation distance, and handling times. Disruption management in AGV systems refers to the ability to effectively handle and overcome any unexpected events or obstacles that may affect the normal operation of AGVs, such as congestion, breakdowns, or changes in production demand. This approach enables real-time monitoring and adjustment of AGV scheduling based on demand changes, congestion, or other disruptions to ensure smooth and efficient operations of AGV scheduling. The relevant studies on an automated terminal AGV scheduling and disruption management are sorted out in detail as follows.

2.1. Automated Terminal AGV Scheduling

Currently, researchers are exploring AGV dispatch optimization in automated terminals from three main perspectives: first, path optimization is developed, mainly using time windows, mixed integer programming, and static path planning methods that allow AGVs to run on pre-planned paths. Zheng [5] complied a summary of the factors that affect the AGV execution and waiting times in the field of AGV path optimization. These factors include the efficiency of the cranes at both ends of the operating chain, the scheduling of the track cranes, and the factors from the storage and loading plans. Fan [6] considered the AGV scheduling optimization under the factor of path conflict, proposed a segmented scheduling strategy, and established a dual-objective scheduling optimization model to minimize the maximum completion time and AGV idle and waiting times. Li [7] considered the charging factor for AGV task optimization and established an AGV task optimization allocation and charging timing model to minimize the AGV transportation costs. He used the Dantzig-Wolfe principle to decompose the model into a main problem based on path set partitioning and a sub-problem with resource-constrained shortest paths and solved different attribute constraints separately in the main problem and sub-problem to reduce the complexity of the model solution. Kang et al. [8] proposed a real-time task allocation method for dual-loading AGVs under the dynamic change of urgency of goods in logistics warehouses. The delivery time of AGVs is calculated based on the urgency of goods, the position and working status of AGVs, and whether the goods are in the same vehicle, and the transportation tasks are allocated based on decision trees. Although these scholars have considered different influencing factors in AGV scheduling optimization and proposed their own model methods, they have not fully considered the sudden situations generated by various uncertain factors under interference.

Second, the superiority of algorithms, such as genetic algorithms and ant colony algorithms, in solving complex problems is evident in their ability to find better solutions. Yu [9] proposed a two-stage scheduling optimization model. The first stage aims to minimize the cost of container operation at quay cranes, whereas the second stage focuses on reducing the cost of AGV transportation. The optimization is performed by using a hybrid intelligent algorithm based on genetic algorithms and heuristics. Zhang [10] proposed using a dynamic window method for the static movement of AGV in the port. The effectiveness of this method was verified by simulation experiments, and a combined algorithm of the dynamic window method and the A* algorithm was proposed. Chen [2] improved the traditional ant colony algorithm by integrating it into a multi-agent system to improve collision avoidance and road unlocking abilities, thereby enhancing the AGV transportation efficiency. Chen et al. [11] used an embedded tabu search algorithm and a real-time monitoring system to schedule AGV transportation and reduce the overall logistics cost.

Finally, from the perspective of dispatch strategies, such as random work center strategies, minimum transportation time/distance strategies, maximum transportation time/distance strategies, modified first-come-first-serve strategies, and random vehicle strategies, human traffic rules are introduced into the AGV operations to make AGV dispatch run in an orderly manner. However, despite significant transportation demands, instances of route conflicts and problems in effectively resolving them may still arise [2].

2.2. Disruption Management

Disruption management refers to the process of dealing with unexpected events that occur while a system operates based on its initial plan under normal circumstances. When a disturbance event occurs and affects the initial plan, even to the point of rendering it unworkable, optimization measures are employed to adjust the initial plan while minimizing the negative effect on the system. Accordingly, the effectiveness of any mitigation plan depends on the characteristics of the disturbance event and the initial plan. Ding et al. [12] aimed to address the delay caused by disruptions and established a logistics delivery disruption management model based on minimizing the deviation cost, taking into account the customer lifetime value. The model effectively improves the logistics delivery system’s response to disruptions under delay conditions and promotes cross-penetration between marketing and disruption management fields. Zhang and Zhu [13] explored customer relationships, cloud models, and disruption management and classified target customers based on cloud models. On this basis, they established a vehicle routing problem delivery management model. The model was solved using the immune algorithm and the tree-seed algorithm. The effectiveness of the algorithms was verified through simulations. The results provided new clues for the routing of delivery vehicles during disruptions. Dekker et al. [14] applied disruption management to railway management. They proposed a new framework for managing disruptions that emphasized three key concepts: predicting disruptions using early warning signals, isolating disrupted areas, and using decentralized decision-making. This mechanism offered new ideas for using disruption management. Jiang [15] applied the theory of disruption management to logistics delivery vehicle failures and established a vehicle failure rescue model, which was verified by simulation case studies. On this basis, a dynamic adjustment vehicle dispatch method based on genetic algorithm optimization was proposed and applied in a case study of a logistics company. The experimental data and vehicle dispatch strategies were compared and demonstrated that the model is effective in solving delivery vehicle failures and has significant implications for reducing delivery reserve vehicles and controlling the decline in delivery service levels.

When a disturbance event occurs, a model is created based on the characteristics of the disturbance event and the initial plan to minimize the deviation between the disruption management plan and the initial plan, thereby minimizing system disturbance. Network graph and mathematical models are commonly used to construct a disturbance recovery model. At present, mathematical models are more commonly used by many researchers. Ning et al. [16] used multi-objective planning methods to establish a multi-objective optimization model for disturbed vehicles, introducing the idea of step-by-step optimization of objectives. They obtained a solution that minimizes the time deviation and delivery cost after interference and proposed an improved multi-objective quantum particle swarm algorithm to optimize the disruption management model and find better solutions for multi-objective optimization problems. In comparison with existing classical algorithms, this algorithm is proven to be effective in solving the problem of disturbed vehicles. Gao [17] pointed out the drawbacks of current research and believed that existing studies only considered one interference factor, whereas in reality, a combination of multiple factors is more in line with real-world needs, and simple mathematical models may not be sufficient to accurately address the problem. Shi [18] addressed the disruption management of dangerous goods vehicle scheduling caused by traffic congestion and established a disruption management model for dangerous goods vehicle scheduling by using a disturbance recovery disaster genetic algorithm to solve the model.

Eglese et al. [19] asserted that the concept of disruption management has matured and can be applied in the routing and scheduling of road freight delivery vehicles, providing better decision support for those who manage road vehicle distribution businesses. In the AGV scheduling of the automated terminal, the ubiquitous interference factors include information interference, route interference, data processing, and vehicle control. When the AGV scheduling is affected by interference factors, a new and reliable AGV scheduling plan must be developed. If the AGV is rescheduled, it may cause greater disturbance to the AGV scheduling plan. However, the use of disruption management is to optimize and adjust the original plan according to the state of interference factors. The goal is to minimize disturbance and save costs appropriately [4]. Therefore, this work adopts the theory of disruption management to reasonably construct an AGV dispatch disturbance recovery model.

3. Analysis and Evaluation of Xiamen Yuanhai Automated Container Terminal

3.1. Automated Container Terminal at Xiamen Yuanhai

In 2012, the Xiamen government collaborated with COSCO and China Communications Construction Company to introduce a full automation transformation at Xiamen Yuanhai container terminal. This terminal was China’s first fully automated container terminal, and it has gained significant industry recognition for its remote operations, intelligence, safety, and sustainability since its launch in March 2016. This container terminal is situated in Berths 14 - 17 at Haicang Port of Xiamen, and it features a 100,000 ton berth and is designed to accommodate 150,000 ton container ships. Furthermore, this terminal is 1508 m long and reached an annual handling capacity of 2.6 million TEUs on December 28, 2021. The construction of Xiamen Yuanhai’s automated container terminal began in March 2013, and it comprises three double-berth gantry cranes, 16 rail-mounted gantry cranes, 18 AGVs, and an automated terminal operating system. The terminal has been constructed and is undergoing trial operations. As global economic integration and trade liberalization trends continue to strengthen, countries around the world are focusing on the logistics industry. Moreover, the international port and shipping industry, a critical component of the modern logistics system, is receiving even more attention.

From 2018 to 2020, Xiamen Yuanhai automated container terminal transitioned from automation to intelligent automation. In 2017, China’s economy entered a new normal, and the global shipping market slowly recovered. This situation led to an excess of capacity on major international shipping routes, resulting in a trend toward larger ships. Xiamen Yuanhai Container Terminal Co., Ltd. actively transformed and upgraded to reduce its operating costs and improve economic efficiency. The proportion of automated terminals/traditional terminals for loading and unloading ships significantly increased between 2018 and 2020, and the dwell time of trailers at automated terminals considerably decreased. On December 21, 2021, the “Smart Port 2.0”, jointly created by China Ocean Shipping, China Mobile, and East Wind, officially commenced commercial operation.

3.2. Layout of the Automated Container Terminal at Xiamen Yuanhai

Xiamen Yuanhai automated container terminal has a total coastline length of 447 m, covers an area of 1.22 million·m², and has one berthing position. This terminal uses the “double-gantry automated quay crane + automatic guided vehicle + automated rail mounted gantry crane” loading and unloading process, and it is equipped with 18 automatic guided vehicles, 16 automated rail mounted gantry cranes, and 3 automated gantry cranes. Moreover, this terminal implements a parallel arrangement of yard and terminal, and the specific layout is shown in Figure 1 [20].

Figure 1. Layout of Xiamen Yuanhai automated container terminal.

The yard of Xiamen Yuanhai automated container terminal has a scale of 225 m × 237.261 m, including 8 yards and 1904 box positions. This automated yard stores ordinary empty and full containers, refrigerated containers, and hazardous containers, while non-automated yards are designated for dangerous goods containers. The entire automated container terminal is divided into six functional areas: foreshore operating area, horizontal transportation area (AGV operating area), AGV exchange area, truck exchange area, yard operating area, and truck buffer area.

This work primarily focuses on the optimization of AGV dispatch, and the horizontal transportation area is described in detail. The horizontal transportation area is a dedicated roadway surface made by special technology, equipped with navigation magnetic pegs and wireless control landing network system. This area is controlled by the back-end control system, and AGV vehicles can automatically run on the quay crane and AGV exchange area. The imported containers can be automatically transported to the automated storage area and then to the bottom of the quay crane and automatically complete the container positioning and movement.

3.3. Units Analysis of the Horizontal Transportation at Xiamen Yuanhai Automated Container Terminal

3.3.1. Dock Loading and Unloading Techniques

The automated container terminal at Xiamen Yuanhai adopts the loading and unloading process system with the strongest application, maturity, and universality in the world, namely, the “quay crane + AGV + AGV partner + ARMG (automated rail mounted gantry crane)” loading and unloading process system. This loading and unloading process is composed of a shore side loading and unloading system, a horizontal transportation system, a yard loading and unloading system, and a collection and transportation system [4].

3.3.2. Situation of Equipment Resource Allocation

The automated container terminal at Xiamen Yuanhai is the first fully automated container terminal in China, and its various loading and unloading equipment is a crucial asset and the core of the terminal’s independent shore-side loading, horizontal transportation, and independent yard loading operations. The configuration and reliability of this equipment directly affects the terminal’s loading and unloading capacity, service level, and operating efficiency. With the rapid development of container transportation business at Xiamen Yuanhai automated container terminal, it imposes higher demands for containerized logistics services.

Therefore, improving the comprehensive management level of container terminals and resolving potential route conflicts have become a pressing issue that needs to be addressed. Based on the experience of foreign automated terminal equipment applications and considering its own practical situation, automated container terminal at Xiamen Yuanhai adopts an efficient and reasonable equipment configuration plan that provides high-efficiency, reliable, and cost-effective equipment support for loading and unloading operations. This feature is an important guarantee for this terminal to achieve good investment returns in the international port competition. The automated equipment of this automated terminal was independently developed by Shanghai Zhenhua Heavy Industries. The main components of the terminal automation equipment include automated gantry cranes, automated yard cranes, AGV, and AGV partner, with a total of 45 units currently in use. The main equipment configuration of this automated terminal is shown in Table 1.

3.3.3. Problems Analysis of AGV Horizontal Transportation

The horizontal transportation system serves as the bridge between the shore-side loading and unloading system and the yard loading and unloading system and consists of a road network from the front of the terminal to the front end of the container area and horizontal transportation equipment. The AGV used at the Xiamen Yuanhai automated container terminal is a fully electric drive AGV developed by Shanghai Zhenhua Heavy Industries Co., Ltd. To address the connection issue between the AGV and the yard gantry crane, an AGV partner is specially set up in the yard seaside transfer area. The AGV partner can actively load and unload containers. This partner can either lift the container from the AGV or place it on top of the AGV so that the AGV does not have to wait for the ARMG to operate and can enter the container area. The AGV partner forms a buffer between horizontal transportation and yard operations.

If information interference, route interference, data interference, or other issues occur in the horizontal transportation system, the operation of the AGV and its efficiency of the port operation will be affected. The layout of the remote port terminal’s horizontal transportation system adopts an “L” shape. During the unloading process, the AGV has to pass through at least three turns, which not only increases the distance of each transportation operation but also augments the number of times the AGV must avoid other vehicles, resulting in a decline in the efficiency of automated container terminal unloading. Accordingly, the problems of route conflicts and road blockages are even more pronounced [4]. The AGV’s operating route during the loading and unloading of the ship is shown in Figure 2.

4. AGV Dispatch Optimization Considering Path Conflict Interference

AGV scheduling is similar to the scheduling of conventional cargo vehicles and uses automated control. During the AGV scheduling, the terminal typically makes transportation plans based on the ship loading plan and its own operational situation. However, disruptions, such as information interference, route interference, data processing interference, and vehicle control, can affect the original transportation plan and reduce the efficiency and safety of AGV scheduling due to the influence of uncertain factors. Therefore, this section focuses on researching the AGV scheduling problem and takes the Xiamen Yuanhai automated container terminal as an example to analyze the main disruption factors of path conflicts. Based on the AGV scheduling strategy and simplified terminal layout, following the shortest distance principle, the initial path is planned using the Dijkstra algorithm combined with time window planning and analyzed for path conflicts. If no conflict arises, then the transportation task is executed. If a path conflict disruption factor exists, then the disturbance is identified and measured while considering the original transportation plan to minimize the disturbance. A path optimization for AGV scheduling considering path conflicts is established to plan a transportation path without conflicts, ensuring that the task is successfully completed.

4.1. Initial Plan of AGV Dispatch

4.1.1. Problem Description

In the horizontal transportation at the seaport, the AGV control center allocates tasks to the corresponding idle AGV based on the nearest destination principle when receiving the container inbound scheduling instructions [4]. The AGV exchanges containers to the AGV exchange area of the yard through the AGV partner and then transport containers to the yard shelves in random order through the yard bridge. Meanwhile, the following assumptions are made on the model built based on the horizontal transportation layout of the container terminal:

Table 1. Main components of the terminal automation equipment.

Terminal automation equipment	Efficiency	Unit of measurement	Equipment power
Automated gantry cranes	30 move/h	3 units	Electricity
Automated yard cranes	24 move/h	16 units	Electricity
AGV	7.2 km/h	18 units	Electricity
AGV partner	-	8 units	Electricity
Terminal automation equipment	Efficiency	Unit of measurement	Equipment power

Figure 2. AGV transportation path during loading and unloading operations.

1) For convenience of calculation, the entities at the container terminal, such as AGVs, AGV partners, quay cranes, and magnetic nails, are set as masses, and the routes of the AGVs operate between masses with equal distances between them.

2) The model simplifies the size of the container and assumes it to be a standard container.

3) The AGV operates at a constant speed and is not related to the load or empty load.

4) In AGV scheduling control, tasks are assigned to the AGV closest to the destination, following the principle of the shortest distance. The AGV is responsible for carrying out the container transport operation.

4.1.2. Generation of the Initial Transport Path

The dispatch strategy of the AGV at Xiamen Yuanhai automation container terminal follows the shortest distance principle. The Dijkstra algorithm is used in conjunction with time window planning to produce the initial path and analyze if any path conflicts are present. The steps are as follows [21] [22]:

Step 1. Based on the horizontal transportation layout of Xiamen Yuanhai automation terminal, set the position of the quay crane and yard points, and randomly generate the starting point of the AGV (V = (x_i, y_j)).

Step 2. Use the Dijkstra algorithm to generate the shortest path.

Step 2.1. Initialize by adding the starting point of the AGV (V = (x_i, y_j)) to the set S and marking it.

Step 2.2. Find the points that are directly connected to the starting point of the AGV (V₀) in the set S, select the point i with the shortest distance, and mark it. Add point i to set S.

Step 2.3. Use point i as the new starting point, and find the point j directly reachable from point i with the shortest distance in the set S. If DIST[j] > DIST[i] + C(i, j), where C(i, j) represents the distance from i to j, then the current distance from the original point V₀ to point j through point i (DIST[i] + C(i, j)) is shorter than the direct distance from the original point V₀ to point j (DIST[j]), so update DIST[j] to DIST[i] + C(i, j) and add point j to the set S.

Step 2.4. Repeat Steps 2.2 and 2.3 until the shortest distance from the original point V₀, through the quay crane, to the yard is determined.

Step 2.5. Output the AGV path formed by the source, intermediate, and target points.

Step 3. Generate time windows for each path in the AGV shortest path set.

Step 4. Select a path from the AGV shortest path set, and check for any a conflict with the time window of other planned paths. If no conflict exists, then generate the AGV dispatch path. If a conflict exists, then select a path from the conflict path set, adopt the re-dispatch strategy, and set the conflicting AGV’s point as the starting point to recalculate the new path by using the Dijkstra algorithm in Step 2 until a conflict-free path is planned.

4.2. Identification of Disturbance after a Path Conflict Occurs

4.2.1. Analysis of Path Conflict Time

Let the transportation network graph be G = (V), where the nodes in the graph are V = {0, 1, 2, ···, n}, the departure time at node i is T₁, the time taken to travel from i to j without a path conflict is T_(ij), the time of the path conflict is ${t^{\prime }}_i$ , and the time required to change the transportation path during the path conflict is ${t^{\prime }}_{ij}$ .

Assuming that t_i is the departure time at node i when AGV travels from node i to node j, if the AGV is traveling along some edge, then the time when path conflict occurs (${t^{\prime }}_i$ ) is in $t_i<{t^{\prime }}_i<t_i+T_{\left(ij\right)}$ , indicating that the path conflict will affect the AGV as it travels from node i to node j, and the time required to change the transportation path during the path conflict is ${t^{\prime }}_{ij}=\theta$ .

4.2.2. Detection of Disruption

In the initial transportation plan, the transportation time threshold is (0, T]. During the process of AGV carrying out the transportation task, the total transportation time is $T_{\left(N\right)}=T_1+T_2+\cdot \cdot \cdot +T_n$ , and $T_{\left(N\right)}\le T$ . The delay in driving time caused by path conflicts is $\theta$ . When AGV is affected by path conflicts, new total transportation time is $T_{\left(N\right)}^{new}=T_1+T_2+\cdot \cdot \cdot +T_n+\theta =T_{\left(N\right)}+\theta$ .

If $T_{\left(N\right)}^{new}=T_{\left(N\right)}+\theta >T$ , then path conflicts cause disturbances, and the original AGV scheduling plan must be adjusted. In other cases, no disturbance caused by path conflicts arises, and the original scheduling plan of the AGV does not need to be adjusted.

4.3. Measurement of Disturbance after Path Conflict Occurrence

When AGV executes the initial transportation plan, a route conflict may occur, which can result in disruptions in the transportation path. An accurate measurement must be made based on the basic principles of disturbance management to accurately measure the deviation of the transportation path and minimize the disruption after the path has been disturbed.

This work mainly uses the deviation amount of the transportation path and the deviation degree of the transportation path to represent to facilitate calculation and a more intuitive representation of the disturbance degree. The deviation amount and the deviation degree of the transportation path are closely related to the increase and decrease in the adjustment plan relative to the initial transportation plan path. This work paper describes the travel path using a point-line method, and the deviation amount of the transportation path is measured by the addition or reduction of transportation nodes. Figure 3 illustrates the path deviation if the dispatching method is used to solve the path conflict by changing the travel path in the form of detours.

In Figure 3, the upper line represents the initial transportation plan of AGV, which is 1-2-3-4-5. When AGV drives from node 3 to node 4, it encounters a path conflict and meets another AGV, which requires adjusting the route. The adjusted route is shown in the transportation line at the bottom of Figure 3. In the adjustment plan, the new route increases 3-6, 6-7, 7-8, 8-5 and decreases 3-4, 4-5, resulting in the new transportation path 1-2-3-6-7-8-5 with the addition of nodes 6, 7, and 8, and the reduction of node 4.

Assuming that the set of transport routes in the initial transport plan is S₀ and after encountering traffic congestion interference and undergoing disruption management, the new set of transportation paths in the adjusted plan is S. Parameter r⁺ is defined as the route node that does not belong to the initial transportation plan S₀, but to the path set S of the disruption management adjustment plan. Meanwhile, parameter r⁻ is defined as the route node that does not belong to the path set S of the disruption management adjustment plan, but to the initial transportation plan S₀. The deviation of transportation paths can be measured using the deviation amount of transportation path and the deviation degree of transportation path. The deviation amount of the transportation path is shown in Equation (1), and the deviation degree of the transportation path is expressed in Equation (2).

$D\left(k\right)={\displaystyle \sum _k\left(\left|r^{+}\right|+\left|r^{-}\right|\right)}$ (1)

$P\left(k\right)=\frac{\text{Deviation amount of transportation path}}{\text{ Path amount of initial transportation plan}}\times 100\%$ (2)

Figure 3. Change of the driving path under path conflicts.

4.4. AGV Dispatch Disturbance Management Model with Path Conflict Considerations

Based on the idea of disruption management, the objective of minimizing the AGV transportation path deviation must be considered when a path conflict occurs. When a path conflict occurs in the initial transportation plan, the path must be adjusted according to the disturbance. The specific steps are as follows:

Step 1. Identify the node and time of the path conflict.

Step 2. Consider the minimum disturbance, adopt the appropriate waiting strategy, or change the path strategy.

Step 3. Generate a new transportation path.

Step 4. Determine if a path conflict exists in the new path.

Step 5. Calculate the total transportation time T_(N).

4.5. Data Acquisition and Model Calculation

4.5.1. Data Acquisition

Based on the review of relevant literature and search for relevant information, combined with the actual situation and the fit of the model, this work takes the horizontal transportation structure of Xiamen Yuanhai automation container terminal as an example and randomly generates the initial starting points V₁ = (x₁, y₁), V₂ = (x₂, y₂), and V₃ = (x₃, y₃) of three AGVs. To simplify the calculation and be consistent with the layout of Xiamen Yuanhai automation container terminal’s horizontal transportation, this work sets up three quay cranes: Quay crane 1 (3, 1), Quay crane 2 (5, 1), and Quay crane 3 (7, 1) and three AGV partners: AGV partner 1 (6, 7), AGV partner 2 (6, 8), and AGV partner 3 (6, 9) and lays out 67 magnetic pins as nodes for the AGV transportation path. The starting points of the three AGVs are randomly generated among the 67 magnetic pins. The AGVs can only transfer the containers to the corresponding container companions for loading and unloading when they reach nodes 34, 35, and 36. The specific setting is shown in Figure 4.

Figure 4. Entity position setting of the AGVs and quay cranes.

4.5.2. Dijkstra Algorithm Combined with Time Window Planning for Pathfinding

After randomly generating the initial positions of three AGVs, the initial driving path of the AGVs can be calculated using the Dijkstra algorithm based on the principle of shortest distance, as shown in Table 2. The results show that the initial driving path of AGV (1) is 45-44-43-42-41-40-39-38-Quay crane 3-29-30-31-32-33-34-35-36-AGV partner 3, the initial driving path of AGV (2) is 31-27-22-21-20-Quay crane 2-20-21-22-27-28-32-33-34-35-AGV partner 2, and the initial driving path of AGV (3) is 18-13-12-11-Quay crane 1-11-12-13-14-19-23-28-32-33-34-AGV partner 1. A conflict was found in the route at nodes 32, 33, and 34 for AGV (1) and AGV (3), as shown in Table 2. In response to the route conflicts, the rescheduling method and disruption management are adopted for path planning to generate new transport paths for comparison, according to the results in Table 2.

Table 2. Initial driving list with time windows.

AGV (1)		AGV (2)		AGV (3)
Path sequence	Time sequence	Path sequence	Time sequence	Path sequence	Time sequence
45	0	31	0	18	0
44	1	27	1	13	1
43	2	22	2	12	2
42	3	21	3	11	3
41	4	20	4	Quay crane 1	4
40	5	Quay crane 2	5	11	5
39	6	20	6	12	6
38	7	21	7	13	7
Quay crane 3	8	22	8	14	8
29	9	27	9	19	9
30	10	28	10	23	10
31	11	32	11	28	11
32	12	33	12	32	12
33	13	34	13	33	13
34	14	35	14	34	14
35	15	AGV partner 2	15	AGV partner 1	15
36	16	-	-	-	-
AGV partner 3	17	-	-	-	-

First, the rescheduling method is considered and aims to achieve the minimum travel distance and resolve path conflicts. In AGV (1), node 32, node 33, and node 34 are removed by using a bypass method, and then the new planned path of AGV (1) is obtained by using the Dijkstra algorithm, as shown in Table 3. In the adjustment plan, the new route increases 31-41, 41-42, 42-43, 43-44, 44-45, 45-35 and decreases 31-32, 32-33, 33-34, 34-35, resulting in the new transportation path 45-44-43-42-41-40-39-38-Quay crane 3-29-30-31-41-42-43-44-45-35-36-AGV partner 3 with the addition of nodes 41, 42, 43, 44, and 45, and the reduction of nodes 32, 33, and 34. Thus, the parameters r⁺ and r⁻ in Equation (1) are equals to 5 and 3, respectively. The results show that the new planned path of AGV (1) has no path conflict with the initial paths of AGV (2) and AGV (3). Then, the deviation amount and the deviation degree of the transportation path under the rescheduling plan can be calculated by using Equations (1) and (2) and are shown as in Table 4.

Table 3. New driving list with time windows under the rescheduling plan.

AGV (1)		AGV (2)		AGV (3)
Path sequence	Time sequence	Path sequence	Time sequence	Path sequence	Time sequence
45	0	31	0	18	0
44	1	27	1	13	1
43	2	22	2	12	2
42	3	21	3	11	3
41	4	20	4	Quay crane 1	4
40	5	Quay crane 2	5	11	5
39	6	20	6	12	6
38	7	21	7	13	7
Quay crane 3	8	22	8	14	8
29	9	27	9	19	9
30	10	28	10	23	10
31	11	32	11	28	11
41	12	33	12	32	12
42	13	34	13	33	13
43	14	35	14	34	14
44	15	AGV partner 2	15	AGV partner 1	15
45	16
35	17
36	18	-	-	-	-
AGV partner 3	19	-	-	-	-

Table 4. Paths under rescheduling plan.

	Transportation path	D (k)	P (k)
AGV (1)	45-44-43-42-41-40-39-38-Quay crane 3-29-30-31-41-42-43-44-45-35-36-AGV partner 3	8	44.44%
AGV (2)	31-27-22-21-20-Quay crane 2-20-21-22-27-28-32-33-34-35-AGV partner 2	0	0
AGV (3)	18-13-12-11-Quay crane 1-11-12-13-14-19-23-28-32-33-34-AGV partner 1	0	0

Subsequently, AGV (1) employs a waiting strategy at node 31 and waits for one unit of time by utilizing the idea of disruption management to minimize disturbance. Thereafter, the Dijkstra algorithm is used again to plan a new path of AGV (1), as shown in Table 5. In the adjustment plan, the new route increases 31-31, resulting in the new transportation path 45-44-43-42-41-40-39-38-Quay crane 3-29-30-31-31-32-33-34-35-36-AGV partner 3 with the addition of nodes 31. Thus, the parameters r⁺ and r⁻ in Equation (1) are equals to 1 and 0, respectively. The results showed that the new planned path of AGV (1) has no path conflict with the initial paths of AGV (2) and AGV (3). Then, the deviation amount and the deviation degree of the transportation path under the disruption management plan can be calculated by using Equations (1) and (2) and are shown as in Table 6.

4.6. Comparison of Results

The comparison between the results of the disturbance management method and the re-dispatch method is shown in Table 7. The comparison of the results of the disruption management method and the rescheduling method shows that the disruption management method is superior to the rescheduling method.

Table 5. New driving list with time windows under disruption management plan.

AGV (1)		AGV (2)		AGV (3)
Path sequence	Time sequence	Path sequence	Time sequence	Path sequence	Time sequence
45	0	31	0	18	0
44	1	27	1	13	1
43	2	22	2	12	2
42	3	21	3	11	3
41	4	20	4	Quay crane 1	4
40	5	Quay crane 2	5	11	5
39	6	20	6	12	6
38	7	21	7	13	7
Quay crane 3	8	22	8	14	8
29	9	27	9	19	9
30	10	28	10	23	10
31	11	32	11	28	11
31	12	33	12	32	12
32	13	34	13	33	13
33	14	35	14	34	14
34	15	AGV partner 2	15	AGV partner 1	15
35	16	-	-	-	-
36	17	-	-	-	-
AGV partner 3	18	-	-	-	-

Table 6. Paths under disruption management plan.

	Transportation path	D (k)	P (k)
AGV (1)	45-44-43-42-41-40-39-38-Quay crane 3-29-30-31-31-32-33-34-35-36-AGV partner 3	1	5.56%
AGV (2)	31-27-22-21-20-Quay crane 2-20-21-22-27-28-32-33-34-35-AGV partner 2	0	0
AGV (3)	18-13-12-11-Quay crane 1-11-12-13-14-19-23-28-32-33-34-AGV partner 1	0	0

Table 7. Comparison of the results between the disruption management method and the rescheduling method.

Adjustment method	Transportation time	D (k)	P (k)
Disruption management	51	1	5.56%
Rescheduling method	52	8	44.44%

First, in terms of transportation time, the transportation time under the rescheduling method is higher than that under the disruption management method. Reducing transportation time is a crucial aspect of AGV scheduling because it can greatly enhance scheduling management and transportation efficiency. Second, the deviation amount and the deviation degree of the transportation path under the disruption management method are far lower than those under the rescheduling method. The deviation degree of the transportation path under the disruption management method is only 5.56%, while that under the rescheduling method is 44.44%. Therefore, the disruption management method can greatly reduce the disturbance caused by interference events to the system, the deviation of the AGV vehicle transportation path, and the mileage, and it is favorable for the long-term development of the port.

5. Conclusion and Future Research

5.1. Conclusions

The automation of terminals can significantly improve the efficiency of container terminal loading and unloading while ensuring the quality of cargo handling and increasing port throughput. This mechanism has become an inevitable trend in the development of ports in the future. However, the continuous growth of port throughput has led to increased operating pressure for automated terminals, and problems, such as AGV route conflicts and road deadlocks, are becoming increasingly prominent. Accordingly, this work takes AGV scheduling as the research object and carries out research on AGV scheduling disruption management that considers route conflicts. The transportation time, deviation of the transportation path, and degree of deviation of the transportation path were analyzed from different perspectives, and the deviation caused by interference factors on the transportation path was measured. An AGV scheduling disruption management program that minimizes system disturbance while considering route conflicts was constructed.

Based on the horizontal transportation layout of Xiamen Yuanhai automated container terminal, the layout was simplified, and a model was constructed. The Dijkstra algorithm was used to solve the problem. Finally, the Dijkstra algorithm with disturbance recovery was used to solve the simplified disturbance management problem of the Xiamen Yuanhai automated container terminal. The superiority of the disturbance management method was determined by comparing it with the rescheduling method. This work proposed a disturbance measurement method for the AGV scheduling disturbance management problem considering path conflicts, enriching the theory and methods of disturbance management and providing a new approach to solving the AGV scheduling disturbance management problem. The AGV scheduling disturbance was measured from the perspective of transportation time, transportation path deviation, and transportation path deviation degree, and a disturbance management model considering path conflicts was constructed. This work provided an effective method for real-time adjustment of transportation plans and improves the efficiency of AGV scheduling.

5.2. Future Research

The study mainly investigated the AGV scheduling and disturbance management problem considering path conflicts and established a disturbance management AGV scheduling model. The Dijkstra algorithm with disturbance recovery is used to solve the model. The research results are limited to the optimization suggestions for the automated container terminal of the Yuanhai in Xiamen. In the future, research can be pursued from the following perspectives: 1) The actual situations, such as driving speed, loading and unloading times, and different container types, were not considered in this work. Additional parameters will be incorporated in future research to align with reality. 2) This work studied AGV scheduling in ports, while coordination of multiple systems must be considered in actual port operations. A more realistic simulation environment can be provided for the planning and design, layout, and other transformations of automated terminals by researching relevant simulation platforms.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Editorial Department of Railway Quality Control (2019) Outline of Building a Strong Transportation Country. Railway Quality Control, 47, 1-4. https://d.wanfangdata.com.cn/periodical/tdjsjd201910001
[2]	Chen, J.W. (2020) Research on AGV Route and Scheduling Optimization in Auto-Mated Container Terminal. Master Thesis, Jimei University.
[3]	Yu, G. and Qi, X. (2004). Disruption Management—Framework, Models and Applications. World Scientific Publishing. https://doi.org/10.1142/9789812561701
[4]	Hu, X.P., Ding, Q.L., Zhang, Y. and Wang, X.P. (2007) A Review on Disruption Management. Journal of Management Science, 2, 2-8.
[5]	Zheng, Z. (2021) AGV Scheduling and Path Optimization in Automated Container Terminal. China Ports, 3, 34-36.
[6]	Fan, H.M., Yue, L.J., Li, D. and Ma, M.Z. (2020) Optimization of AGV Dispatching and Configuration Considering Path Conflict. Operations Research and Management Science, 29, 43-51.
[7]	Li, M.Z. (2020) Research of AGV Assignment Considering Charging Factors at Automated Container Terminals. Master Thesis, Dalian Maritime University.
[8]	Kang, Y., Feng, G., Wang, Z. and Sun, J. (2020) Real-Time Task Assignment Method of Two-Load AGV under Dynamic Change of Goods Urgency in Logistics Warehouse. Journal of Physics: Conference Series, 1576, Article 012055. https://doi.org/10.1088/1742-6596/1576/1/012055
[9]	Yue, L., Fan, H. and Zhai, C. (2020) Joint Configuration and Scheduling Optimization of the Dual Trolley Quay Crane and AGV for Automated Container Terminal. Journal of Physics: Conference Series, 1486, Article 072080. https://doi.org/10.1088/1742-6596/1486/7/072080
[10]	Zhang, X.Y. (2019) Research on Port AGV Path Planning Method Based on Dynamic Window Approach Integrated with A* Algorithm. Master Thesis, Beijing Jiaotong University.
[11]	Chen, J., Du, W., Wang, H. and Guo, D. (2020) Research on Integrated Scheduling Optimization of Double-Trolley Quay Crane and AGV in Automated Terminal. IOP Conference Series: Materials Science and Engineering, 790, Article 012071. https://doi.org/10.1088/1757-899x/790/1/012071
[12]	Ding, Q.L., Hu, X.P., Qi, F. and Jiang, Y., (2021) Disruption Management Model Based on Customer Lifetime Value under Travel Time Delay in Distribution. Operations Research and Management Science, 30, 6-12.
[13]	Zhang, X. and Zhu, W. (2019) Disruption Management for Vehicle Routing Problem Based on Consumer Value and Improved Tree-Seed Algorithm. IEEE Access, 7, 122019-122027. https://doi.org/10.1109/access.2019.2938407
[14]	Dekker, M.M., van Lieshout, R.N., Ball, R.C., Bouman, P.C., Dekker, S.C., Dijkstra, H.A., et al. (2021) A Next Step in Disruption Management: Combining Operations Research and Complexity Science. Public Transport, 14, 5-26. https://doi.org/10.1007/s12469-021-00261-5
[15]	Jiang, L., Ding, B. and Zang, X.N. (2010) The Model of Vehicle Breakdown Rescue Based on Disruption Management. Systems Engineering, 28, 111-116.
[16]	Ning, T., Wang, X.P. and Hu, X.P. (2019) Disruption Management Decision Model for Vehicle Scheduling under Traffic Disruption Delay. Systems Engineering-Theory & Practice, 39, 1236-1245.
[17]	Gao, Y.W. (2020) Research on the Disruption Management Problem of Multi-Depot Vehicle Scheduling and Its Algorithms. Management & Technology of SME, 35, 148-149.
[18]	Shi, S.K. (2020) Disruption Management for Hazardous Materials Transportation Vehicle Scheduling with the Traffic Congestion. Master Thesis, Hebei University of Engineering.
[19]	Eglese, R. and Zambirinis, S. (2018) Disruption Management in Vehicle Routing and Scheduling for Road Freight Transport: A Review. TOP, 26, 1-17. https://doi.org/10.1007/s11750-018-0469-4
[20]	Chen, S.Q. (2017) Research on Optimization Layout and Equipment Configuration of Xiamen Ocean Automation Terminal. Master Thesis, South China University of Technology.
[21]	Chen, Y., Shen, S., Chen, T. and Yang, R. (2014) Path Optimization Study for Vehicles Evacuation Based on Dijkstra Algorithm. Procedia Engineering, 71, 159-165. https://doi.org/10.1016/j.proeng.2014.04.023
[22]	Sun, Y., Fang, M. and Su, Y. (2021) AGV Path Planning Based on Improved Dijkstra Algorithm. Journal of Physics: Conference Series, 1746, Article 012052. https://doi.org/10.1088/1742-6596/1746/1/012052