# Impact Analysis of Travel Time Uncertainty on AGV Catch-Up Conflict and the Associated Dynamic Adjustment

Authors: Jun-jun Li; Bo-wei Xu; Octavian Postolache; Yong-sheng Yang; Hua-feng Wu
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

In automated logistics systems, travel time uncertainty can severely affect automated guided vehicle (AGV) conflict and path planning. Insight is required into how travel time uncertainty affects catch-up conflict, the main AGV conflict in one-way road networks. Under normal circumstances, the probability formula for catch-up conflict is deduced based on an analysis of AGV catch-up conflict. The vertex, monotonicity, and symmetry of catch-up conflict probabilities are developed, for symmetrical AGV travel time distribution densities. A dynamic adjustment method based on conflict probability for AGVs is designed. The probability features of catch-up conflicts and the performance of the associated dynamic adjustment are simulated and validated for AGVs at an automated container terminal. The simulation results show that the impact analysis of travel time uncertainty on AGV catch-up conflict is correct, and the dynamic adjustment is effective.


---

## Body

## 1. Introduction

Automated guided vehicles (AGVs) participate in unmanned transport systems for material handling [1]. In automated logistics systems, such as automated container terminals and automated warehouses, conflicts may arise when several AGVs run along a narrow lane or pass crossing roads [2]. AGV conflict (which can significantly affect actual AGV speeds, expected travel time, and automated logistic system throughput) has been a key issue in AGV path planning [3]. Many studies have focused on conflict avoidance strategies when studying AGV path planning [1, 4, 5]. Smolic-Rocak et al. used time window insertion in vector form and performed window overlapping tests to dynamically solve the shortest path problem for the supervisory control of AGVs traveling within the layout of a given warehouse [4]. Saidi-Mehrabad et al. considered a conflict-free routing problem (CFRP) for AGVs, as well as a basic job shop scheduling problem (JSSP) to minimize total completion time (make-span). They proposed a two-stage ant colony algorithm (ACA) for this problem, especially for large-size problems [1]. Hidalgo-Paniagua et al. proposed a new multiobjective evolutionary approach based on a variable neighborhood search to produce good paths with shorter lengths, improved safety, and smoother mobile robot movements [5]. However, AGV transportation systems are subject to a high degree of uncertainty [6]. The above references simplified AGV conflict avoidance strategies for deterministic conditions, which might lead to suboptimal or even infeasible solutions.In the real world, AGV conflict on road networks is highly affected by AGV travel times, which are very uncertain because of roadway capacity variations and traffic demand fluctuations [7, 8]. Therefore, the on-time arrival probability of AGVs in automated logistics systems cannot be ensured, especially for a large number of AGVs operating in a limited area. An interesting queuing approach is used to model routing problems with time-dependent travel time [9]. Strategies have been proposed to avoid stochastic travel time influence against unpredictable and random conflicts [10, 11]. Shao et al. used a two-stage traffic control strategy to resolve conflicts and deadlock problems in AGV systems. Specifically, a traffic controller is employed to operate each moving AGV online after utilizing an A∗ algorithm to offline construct an optimal path set for AGVs [10]. Zhang et al. formulated on-time shipment delivery problems as stochastic vehicle routing problems with soft time windows under travel and service time uncertainties and proposed a new stochastic programming model for finding a good trade-off between the total cost borne by carriers and customer service levels [11]. However, measures such as scheduling methods and control strategies, which can temporarily prevent conflicts, may reduce the efficiency of AGV systems. Exclusive dependence on these measures easily leads to queuing and congestion in heavy traffic. Therefore, reasonably preanalyzing AGV conflicts under random circumstances can facilitate shorter travel times and higher AGV utilization rates. However, there is not a way to compute the probability of AGV conflicts under uncertainty.Dynamic adjustment is a key measure to deal with conflicts in the operations management of AGV systems. Lee et al. employed ak-shortest path search algorithm to construct a path set and performed online motion planning operation in real time [12]. Li et al. proposed a set of real-time implementable traffic rules to ensure the completion of all jobs with the absence of vehicle deadlocks and collisions [13]. Hoo-Lim et al. proposed a genetic algorithm to continuously optimize and adjust the traffic flow of AGVs for keeping up with the dynamically changing operational condition [14]. Different adjust strategies may result in different running state and different productivity. It is better to analyze conflict probabilities and perform associated dynamical adjustment, rather than employ traditional adjustment as passive response measures to avoid conflicts among AGVs. Furthermore, many methods mentioned in the literature did not consider conflict probabilities in advance of dynamic adjustment, which might bring high frequency of control action, high operational cost, low efficiency, and service ability of automated logistics systems.After studying the current literature, it is clear that the analysis of AGV conflicts under uncertainty has received less attention from the research community. In this work, catch-up conflict (the main type of AGV conflict in a one-way road network) probability and the associated dynamic adjustment are studied. Compared with the existing literature, the main contributions of this work are elucidated as follows. First, to meet the needs of operation management, AGVs’ travel times are set to random values and the AGV catch-up conflict problem in one-way and single lane road networks is described. Second, the catch-up conflict probability features are analyzed in detail in a situation where the probability density function for the times of AGVs passing through each node is symmetrical. Finally, the dynamic adjustment based on the conflict probability for AGVs is presented in order to reduce catch-up conflicts among AGVs.


## 2. AGV Catch-Up Conflict Probability and Uncertain Travel Time

### 2.1. AGV Catch-Up Conflict Probability

A one-way and single lane road network for an automated logistic system is denoted by a graph withN nodes (A1,A2,…,AN) and B links. Ak and Al are the kth and lth nodes, respectively, and they are consecutive. There are P AGVs (AGV1,AGV2,…,AGVP). The start node and end node of the pth AGV (denoted as AGVp) are Sp and Ep, respectively.Assume thatAGVp passes through node Ak at time tp,k. The probability density function and cumulative distribution function for time tp,k are φp,k(t) and Fp,k(t), respectively. ∀t∈(-∞,+∞), φp,k(t)<+∞. Once tp,k≤tq,k and tp,l≥tq,l, or tp,k≥tq,k and tp,l≤tq,l, catch-up conflicts occur between AGVp and AGVq (the qth AGV). A situation where two AGVs repeatedly catch up with one another is not considered here.Assuming that the movements of AGVs are mutually independent, the eventstp,k≤tq,k and tp,l≥tq,l are independent of one another. Additionally, tp,k≥tq,k and tp,l≤tq,l are independent events. The probability of AGV catch-up conflict event ς is P(ς). It can be shown that(1)Pς=Ptp,k≤tq,k·Ptp,l≥tq,l+Ptp,k≥tq,k·Ptp,l≤tq,l,where P(tp,k≤tq,k) is shown in(2)Ptp,k≤tq,k=∫-∞+∞φq,kτ∫-∞τφp,ktdtdτ=∫-∞+∞φq,kτFp,kτdτ∵∀t∈(-∞,+∞),φp,k(t)<+∞,∴∫ττφp,k(t)dt=0.∴P(tp,k=tq,k)=∫-∞+∞φq,k(τ)∫ττφp,k(t)dtdτ=0.In this case,P(ς) is shown in (3)Pς=Ptp,k≤tq,k·1-Ptp,l≤tq,l+1-Ptp,k≤tq,k·Ptp,l≤tq,l=Ptp,k≤tq,k+Ptp,l≤tq,l-2Ptp,k≤tq,k·Ptp,l≤tq,l.Let the times at whichAGVq passes through nodes Ak and Al be tq,k+x and tq,l+x, respectively, where x indicates the change in departure time for AGVq. Meanwhile, let g1(x)=P(tp,k≤tq,k+x), g2(x)=P(tp,l≤tq,l+x) and z(x)=P(ς). From (3), it is determined that (4)zx=g1x+g2x-2g1x·g2x.


### 2.2. Uncertain Travel Time

#### 2.2.1. Travel Time Is Random

In an automated logistic system, some AGVs may have the same design speed. If an AGV travels exactly at the design speedv0, then its arrival time at a node is t=t0. In practice, because of uncertainty (e.g., speed fluctuations and operating environment disturbances), the actual arrival time is a random variable. Assuming that the various uncertainties are arbitrary, the probability density function of the random variable would be symmetrical about t=t0.Two probability distribution functions (uniform distribution [8, 15] and normal distribution [15, 16]) widely used in engineering are specified in (5) and (6), respectively. (5)φt=0.5δ,t∈t0-δ,t0+δ0,else,(6)φt=12πσe-t-t02/2σ2,where δ>0, σ>0.


#### 2.2.2. Travel Speed Is Random

When the speeds of AGVs change randomly, the times at which the AGVs pass through nodes become random. Here,vp denotes the actual speed of AGVp. Similar to (5) and (6), the uniform and normal distributions of vp are given in (7) and (8), respectively.(7)ϕv=0.5δ′,v∈v0-δ′,v0+δ′0,else(8)ϕv=12πσ′e-v-v02/2σ′2, where δ′>0, σ′>0. If the departure time of AGVp is x, then the time at which it passes through node k is tp,k=x+Lp,k/vp, where Lp,k is the distance traveled by AGVp from node Sp to node k. If the probability density function of vp is ϕp(v), then the probability density function of tp,k is (9)φp,kt=Lp,kt-x2ϕpLp,kt-x.In Section3, the impact of travel time uncertainty on catch-up conflict described in Section 2.1 is analyzed; subsequently, catch-up conflicts caused by uncertain travel time described in Section 2.2 are simulated in Section 5.


## 2.1. AGV Catch-Up Conflict Probability

A one-way and single lane road network for an automated logistic system is denoted by a graph withN nodes (A1,A2,…,AN) and B links. Ak and Al are the kth and lth nodes, respectively, and they are consecutive. There are P AGVs (AGV1,AGV2,…,AGVP). The start node and end node of the pth AGV (denoted as AGVp) are Sp and Ep, respectively.Assume thatAGVp passes through node Ak at time tp,k. The probability density function and cumulative distribution function for time tp,k are φp,k(t) and Fp,k(t), respectively. ∀t∈(-∞,+∞), φp,k(t)<+∞. Once tp,k≤tq,k and tp,l≥tq,l, or tp,k≥tq,k and tp,l≤tq,l, catch-up conflicts occur between AGVp and AGVq (the qth AGV). A situation where two AGVs repeatedly catch up with one another is not considered here.Assuming that the movements of AGVs are mutually independent, the eventstp,k≤tq,k and tp,l≥tq,l are independent of one another. Additionally, tp,k≥tq,k and tp,l≤tq,l are independent events. The probability of AGV catch-up conflict event ς is P(ς). It can be shown that(1)Pς=Ptp,k≤tq,k·Ptp,l≥tq,l+Ptp,k≥tq,k·Ptp,l≤tq,l,where P(tp,k≤tq,k) is shown in(2)Ptp,k≤tq,k=∫-∞+∞φq,kτ∫-∞τφp,ktdtdτ=∫-∞+∞φq,kτFp,kτdτ∵∀t∈(-∞,+∞),φp,k(t)<+∞,∴∫ττφp,k(t)dt=0.∴P(tp,k=tq,k)=∫-∞+∞φq,k(τ)∫ττφp,k(t)dtdτ=0.In this case,P(ς) is shown in (3)Pς=Ptp,k≤tq,k·1-Ptp,l≤tq,l+1-Ptp,k≤tq,k·Ptp,l≤tq,l=Ptp,k≤tq,k+Ptp,l≤tq,l-2Ptp,k≤tq,k·Ptp,l≤tq,l.Let the times at whichAGVq passes through nodes Ak and Al be tq,k+x and tq,l+x, respectively, where x indicates the change in departure time for AGVq. Meanwhile, let g1(x)=P(tp,k≤tq,k+x), g2(x)=P(tp,l≤tq,l+x) and z(x)=P(ς). From (3), it is determined that (4)zx=g1x+g2x-2g1x·g2x.


## 2.2. Uncertain Travel Time

### 2.2.1. Travel Time Is Random

In an automated logistic system, some AGVs may have the same design speed. If an AGV travels exactly at the design speedv0, then its arrival time at a node is t=t0. In practice, because of uncertainty (e.g., speed fluctuations and operating environment disturbances), the actual arrival time is a random variable. Assuming that the various uncertainties are arbitrary, the probability density function of the random variable would be symmetrical about t=t0.Two probability distribution functions (uniform distribution [8, 15] and normal distribution [15, 16]) widely used in engineering are specified in (5) and (6), respectively. (5)φt=0.5δ,t∈t0-δ,t0+δ0,else,(6)φt=12πσe-t-t02/2σ2,where δ>0, σ>0.


### 2.2.2. Travel Speed Is Random

When the speeds of AGVs change randomly, the times at which the AGVs pass through nodes become random. Here,vp denotes the actual speed of AGVp. Similar to (5) and (6), the uniform and normal distributions of vp are given in (7) and (8), respectively.(7)ϕv=0.5δ′,v∈v0-δ′,v0+δ′0,else(8)ϕv=12πσ′e-v-v02/2σ′2, where δ′>0, σ′>0. If the departure time of AGVp is x, then the time at which it passes through node k is tp,k=x+Lp,k/vp, where Lp,k is the distance traveled by AGVp from node Sp to node k. If the probability density function of vp is ϕp(v), then the probability density function of tp,k is (9)φp,kt=Lp,kt-x2ϕpLp,kt-x.In Section3, the impact of travel time uncertainty on catch-up conflict described in Section 2.1 is analyzed; subsequently, catch-up conflicts caused by uncertain travel time described in Section 2.2 are simulated in Section 5.


## 2.2.1. Travel Time Is Random

In an automated logistic system, some AGVs may have the same design speed. If an AGV travels exactly at the design speedv0, then its arrival time at a node is t=t0. In practice, because of uncertainty (e.g., speed fluctuations and operating environment disturbances), the actual arrival time is a random variable. Assuming that the various uncertainties are arbitrary, the probability density function of the random variable would be symmetrical about t=t0.Two probability distribution functions (uniform distribution [8, 15] and normal distribution [15, 16]) widely used in engineering are specified in (5) and (6), respectively. (5)φt=0.5δ,t∈t0-δ,t0+δ0,else,(6)φt=12πσe-t-t02/2σ2,where δ>0, σ>0.


## 2.2.2. Travel Speed Is Random

When the speeds of AGVs change randomly, the times at which the AGVs pass through nodes become random. Here,vp denotes the actual speed of AGVp. Similar to (5) and (6), the uniform and normal distributions of vp are given in (7) and (8), respectively.(7)ϕv=0.5δ′,v∈v0-δ′,v0+δ′0,else(8)ϕv=12πσ′e-v-v02/2σ′2, where δ′>0, σ′>0. If the departure time of AGVp is x, then the time at which it passes through node k is tp,k=x+Lp,k/vp, where Lp,k is the distance traveled by AGVp from node Sp to node k. If the probability density function of vp is ϕp(v), then the probability density function of tp,k is (9)φp,kt=Lp,kt-x2ϕpLp,kt-x.In Section3, the impact of travel time uncertainty on catch-up conflict described in Section 2.1 is analyzed; subsequently, catch-up conflicts caused by uncertain travel time described in Section 2.2 are simulated in Section 5.


## 3. Impact of Travel Time Uncertainty on Catch-Up Conflict

The catch-up conflict between two AGVs is the basis for catch-up conflicts among multiple AGVs. Catch-up conflict probabilities betweenAGVp and AGVq are analyzed here.First, on the basis of distribution characteristics ofP(tp,k≤tq,k+x) and P(tp,l≤tq,l+x), the symmetry and monotonicity of P(ς) are analyzed by Theorem 1 and Inference 2, respectively. Second, according to the symmetries of φp,k(t) and φq,k(t), the symmetry of P(tp,k≤tq,k+x) is analyzed using Theorem 3. Finally, the distribution characteristics of P(ς) are comprehensively analyzed using Inference 4.Theorem 1.
IfP(tp,k≤tq,k+x) and P(tp,l≤tq,l+x) are symmetric about point (x0,0.5), then P(ς) is symmetric about x=x0 and z(x0)=0.5.Inference 2.
If bothP(tp,k≤tq,k) and P(tp,l≤tq,l) are symmetric about point (x0,0.5), and both g1(x) and g2(x) monotonically increase (or monotonically decrease), then P(ς) is an increasing function when x≤x0, or vice versa.Theorem 3.
Ifφp,k(t) and φq,k(t) are symmetric about t=t1 and t=t2, respectively, then P(tp,k≤tq,k+x) is symmetric about point (t1-t2,0.5).Inference 4.
If the following conditions are met inAGVp and AGVq:
(1) the times at whichAGVp and AGVq pass through node Ak are tp,k and tq,k+x, respectively. The times at which AGVp and AGVq pass through node Al are tp,l and tq,l+x, respectively.
(2)φp,k(t), φq,k(t), φp,l(t), and φq,l(t) are the interval distributions(10)φp,kt>0,t∈cp,k,dp,k,φp,kt=0,t∉cp,k,dp,k,φq,kt>0,t∈cq,k,dq,k,φq,kt=0,t∉cq,k,dq,k,φp,lt>0,t∈cp,l,dp,l,φp,lt=0,t∉cp,l,dp,l,φq,lt>0,t∈cq,l,dq,l,φq,lt=0,t∉cq,l,dq,l,respectively. cp,k, dp,k, cq,k, dq,k, cp,l, dq,l, cq,l, and dq,l are all real numbers. cp,k<dp,k, cq,k<dq,k, cp,l<dq,l, and cq,l<dq,l.
(3)φp,k(t), φq,k(t), φp,l(t), and φq,l(t) are symmetric about t=t1,t2,t3 and t4, respectively, where t1-t2=t3-t4.
Thence,P(ς) is symmetric about x0=t1-t2, and P(ς) conforms to Formula (11), where Sk=[cp,k-dq,k,dp,k-cq,k], Sl=[cp,l-dq,l,dp,l-cq,l], Sk∪Sl=[a,b].(11)Pς=zxis0.5,x=x0monotonically  increasing,x∈a,x0monotonically  decreasing,x∈x0,b0,x∈-∞,a∪b,+∞.Similarly, if some intervals of(cp,k,dp,k), (cq,k,dq,k), (cp,l,dp,l), and (cq,l,dq,l) change to closed intervals, Inference 4 is true; if one of these intervals is adjusted to (-∞,+∞) (such as cp,k,dp,k→-∞) Inference 4 remains true.The above analysis can provide premise and basis for dynamic adjustment and help to reduce catch-up conflicts among AGVs.


## 4. Dynamic Adjustment Based on Conflict Probability

Dynamic adjustment based on conflict probability may change the traditional passive response mode to taking the initiative in avoiding conflicts among AGVs. This could provide substantial productivity improvement for AGV transportation systems.If all catch-up conflict probabilities are considered, the difficulty and complexity of AGVs planning will increase and the process would involve more calculation. Hence, based on the catch-up conflict probability features revealed in Inference4, a catch-up conflict probability threshold Tccp (0<Tccp<0.5) is considered for improving the efficiency of AGVs planning. If the catch-up conflict probability is larger than Tccp, then the AGVs with low priority replan their paths; else, the AGVs with low priority simply slow down or wait to avoid conflicts once the potential catch-up conflicts happen. When the AGVs with low priorities replan their paths, the links with “P(ς)>Tccp” in path preplanning are eliminated from their optional links in the corresponding time windows. Checking “P(ς)>Tccp” and path replanning by the AGVs with low priorities are executed until “P(ς)>Tccp” does not exist. Then all catch-up conflict probabilities are lower than Tccp. Low conflict probabilities would result in few conflicts, which will greatly reduce the negative impact of conflicts on AGVs operation.Details are as follows.The dynamic adjustment flow of AGVs is given in Figure1. First, the priorities of AGVs are set, and the catch-up conflict probability threshold Tccp is given. The steps of dynamic adjustment are listed below.Figure 1
Dynamic adjustment based on conflict probability.Step 1.
After path preplanning based on Dijkstra’s algorithm for each AGV, it can be known whether different AGVs will pass through the same nodes. If such nodes do not exist, the AGVs will move according to their path plan; else, turn to Step2.Step 2.
Calculate the catch-up conflict probabilityP(ς). If P(ς)>Tccp, the AGVs with low priorities replan their paths based on Dijkstra’s algorithm with time window and recheck whether the catch-up conflict probability exceeds Tccp until the catch-up conflict probability is lower than Tccp; else, turn to Step 3.Step 3.
AGVs travel according to their path planning. In the process of AGVs traveling, the potential catch-up conflicts are detected by sensors on AGVs. If a catch-up conflict is predicted to occur, the AGVs with low priorities slow down or wait to avoid conflicts; else, AGVs move on.In the dynamic adjustment based on conflict probability, it is important to check “P(ς)>Tccp.” However, it is different from detecting potential conflicts. On the one hand, “P(ς)>Tccp” is checked by calculation, while potential conflicts are detected by sensors. On the other hand, checking “P(ς)>Tccp” is just after AGVs path preplanning and before AGVs starting to move, whereas, detecting potential conflicts is ahead of the node that AGVs will reach and in the process of AGVs moving.


## 5. Simulations on Catch-Up Conflict

### 5.1. Simulation Settings

Automated container terminals are typical automated logistics systems. Because of the notable uncertainty characteristics at automated container terminals, conflicts among AGVs are particularly common, resulting in new bottlenecks of loading and unloading operations. Therefore, it is extremely important to take AGVs at automated container terminals as an example for analyzing catch-up conflict probabilities, using simulations to enhance the operational abilities of AGVs and improve the overall efficiency of automated container terminals. Figure2 shows the road network of an automated container terminal. Roads in the network are one-way and single lanes. “QC” and “YC” indicate the quay crane and yard crane, respectively. v0 is 5 m/s. The horizontal and vertical path lengths are 260 and 90 m, respectively. Nodes 1–63 are road network nodes. Nodes A–C are quay cranes. Nodes a–g are yard cranes. The following parameters are defined based on the statistics of an actual automated container terminal with annual throughput capacity of 5 million TEU.Figure 2
Road network layout and AGVs’ paths at an automated container terminal.The red and purple lines denote the travel paths ofAGVp and AGVq, respectively. Both AGVp and AGVq pass through link (28,29), which may cause catch-up conflict. It can be calculated that t1 = 20 s, t3 = 26 s, t2 = 4 s, and t4 = 10 s. If the departure time of AGVp and AGVq is both 0 s, let tp,28 and tp,29 denote the actual times at which AGVp reach nodes 28 and 29, respectively, and let tq,28 and tq,29 denote the actual times at which AGVq reach nodes 28 and 29, respectively. The departure time of AGVq changes to x s; the actual times at which AGVq reach nodes 28 and 29 are tq,28+x and tq,29+x, respectively. Here, P(ς)=z(x) is simulated to verify the impact analysis of travel time uncertainty on catch-up conflict in Section 3.φ ( t ) in (5) and (6) are employed in φp,28(t), φq,28(t), φp,29(t), and φq,29(t). For the convenience, δp and σp denote δ and σ in φp,28(t) and φp,29(t), respectively, while δq and σq denote δ and σ in φq,28(t) and φq,29(t), respectively.Inference4 in Section 3 is a summary of the conflict probability characteristics. Therefore, only Inference 4 is verified in Section 5. Both “Conditions of Inference 4 are exactly met” and “Conditions of Inference 4 are approximately met” are simulated with MATLAB.


### 5.2. Conditions of Inference4 Are Exactly Met

#### 5.2.1.φ(t) Is Unrelated to Travel Distance

δ and σ in (5) and (6) remain constant. Generally, the times at which an AGV passes through adjacent nodes obey the same type of probability distribution. According to different combinations of uniform and normal distributions, there are three situations (①, ②, and ③) in which the distributions and parameters are set according to Table 1.Table 1
Distributions and parameters inφ(t).
φ p , 28 ( t ), φp,29(t) φ q , 28 ( t ), φq,29(t) ① Distribution Uniform Uniform δ 1 or 2.5 0.25 or 1 ② Distribution Normal Normal σ 0.5 or 1 0.25 or 0.5 ③ Distribution Uniform Normal δ/σ 1 or 2 0.25 or 0.5Through simulation, catch-up probabilities changing withx in the three situations in Table 1 are shown in Figures 3(a), 3(b), and 3(c), respectively. Four curves in each figure stand for four cases.Figure 3
Catch-up conflict probability changes in Section5.2.1.
(a) (b) (c)


#### 5.2.2.φ(t) Is Related to Travel Distance

δ and σ in (5) and (6) change with travel distance. Here, L denotes the travel distance from the start point to the current node. There are three situations in which the distributions of φp,28(t), φq,28(t), φp,29(t), and φq,29(t) are the same as shown in Table 1. The parameters are shown in Table 2.Table 2
Parameters inφ(t).
φ p , 28 ( t ), φp,29(t) φ q , 28 ( t ), φq,29(t) ① δ 0.01 L or 0.025L 0.01 L or 0.025L ② σ 0.00 5 L or 0.015L 0.00 5 L or 0.015L ③ δ/σ 0.0 1 L or 0.025L 0.0 1 L or 0.015LSimulated catch-up probabilities changing withx in the three situations in Table 2 are shown in Figures 4(a), 4(b), and 4(c), respectively.Figure 4
Catch-up conflict probability changes in Section5.2.2.
(a) (b) (c)


### 5.3. Conditions of Inference4 Are Approximately Met

#### 5.3.1.φ(t) Is Related to Travel Distance and x

For example, the value ofδq or σq in φq,28(t) and φq,29(t) is related to L+v0x. In this case, it does not exactly meet the conditions of Inference 4. However, if φq,28(t) and φq,29(t) do not change significantly with x, the conditions of Inference 4 are met approximately. There are three situations in which the distributions of φp,28(t), φq,28(t), φp,29(t), and φq,29(t) are the same as shown in Table 1. The parameters are shown in Table 3.Table 3
Parameters inφ(t).
φ p , 28 ( t ), φp,29(t) φ q , 28 ( t ), φq,29(t) ① δ 0.01 L or 0.025L 0.01 ( L + v 0 x ) or 0.025(L+v0x) ② σ 0.00 5 L or 0.015L 0.005 ( L + v 0 x ) or 0.015(L+v0x) ③ δ/σ 0.0 1 L or 0.025L 0.01 ( L + v 0 x ) or 0.015(L+v0x).Simulated catch-up probabilities changing withx in the three situations in Table 3 are shown in Figures 5(a), 5(b), and 5(c), respectively.Figure 5
Catch-up conflict probability changes in Section5.3.1.
(a) (b) (c)


#### 5.3.2. Travel Speed Is Random

When the probability density function of travel speed has symmetric distribution,φ(t) often is not strictly symmetric distribution. But if φ(t) has an approximately symmetric distribution and φq,28(t) and φq,29(t) change little with x, it can also be approximately consistent with the conclusions of Inference 4.Let the probability density function of travel speed be of both uniform and normal distributions.ϕ(v) in (7) and (8) are employed in ϕp(v) and ϕq(v). For convenience, δ′p and σ′p denote δ′ and σ′ in ϕp(v), respectively, and δ′q and σ′q denote δ′ and σ′ in ϕq(v), respectively. Similarly, according to different combinations of travel speed in uniform and normal distributions, there are three situations shown in Table 4.Table 4
Distributions and parameters inϕ(v).
ϕ p ( v ) ϕ q ( v ) ① Distribution Uniform Uniform δ ′ 0.25 or 0.5 0.25 or 0.5 ② Distribution Normal Normal σ ′ 0.2 or 0.4 0.2 or 0.4 ③ Distribution Uniform Normal δ ′ / σ ′ 0.3 or 0.6 0.3 or 0.6Simulated catch-up probabilities changing withx in the three situations in Table 4 are shown in Figures 6(a), 6(b), and 6(c), respectively.Figure 6
Catch-up conflict probability changes in Section5.3.2.
(a) (b) (c)


### 5.4. Discussions

#### 5.4.1. Discussions about Section5.2

In the situations in Sections5.2.1 and 5.2.2, x0=t1-t2=t3-t4=16 s. In Figures 2 and 3, they are all symmetrical about x = 16 s; when x = 16 s, P(ς)=z(x) reaches its maximum value (0.5). In accordance with the cases in Sections 5.2.1 and 5.2.2, monotonically increasing and decreasing intervals of P(ς)=z(x) obtained by simulations are shown in Tables 5 and 6, which are consistent with Inference 4.Table 5
x’s intervals of P(ς)=z(x) in situation ① of Section 5.2.1.
Monotonicity of interval δ p = 1, δq = 0.25 δ p = 1, δq = 1 δ p = 2.5, δq = 0.25 δ p = 2.5, δq = 1 Increasing [ 14.75,16 ] [ 14,16 ] [ 13.25,16 ] [ 12.5,16 ] Decreasing [ 16,17.25 ] [ 16,18 ] [ 16,18.75 ] [ 16,19.5 ]Table 6
x’s intervals of P(ς)=z(x) in situation ① of Section 5.2.2.
Monotonicity of interval δ p = 0.0 1 L, δq=0.01L δ p = 0.0 1 L, δq=0.025L δ p = 0.02 5 L, δq=0.01L δ p =  0.02 5 L, δq=0.025L Increasing [ 14.2,16 ] [ 13.45,16 ] [ 12.25,16 ] [ 11.5,16 ] Decreasing [ 16,17.8 ] [ 16,18.55 ] [ 16,19.75 ] [ 16,20.5 ]In situation ② of Sections5.2.1 and 5.2.2, cp,28,cp,29,cq,28,cq,29→-∞ and dp,28,dp,29,dq,28,dq,29→+∞. In situation ③ of Sections 5.2.1 and 5.2.2, cp,28, cp,29, dp,28, and dp,29 are limited real numbers, cq,28,cq,29→-∞, dq,28,dq,29→+∞. In these four situations, S28=(-∞,+∞), S29=(-∞,+∞), and Sk∪Sl=(-∞,+∞). Therefore, P(ς)=z(x) monotonically increases in (-∞,16] and decreases in [16,+∞), which is consistent with Figures 3(b), 3(c), 4(b), and 4(c).In summary, the simulation results are consistent with the conclusions in Inference4.


#### 5.4.2. Discussions about Section5.3

In Figures5(a)–5(c), the vertexes of the all curves are all (16.00,0.50). From the simulation results, the monotonically increasing and decreasing intervals for P(ς)=z(x) in situation ① of Section 5.3.1 are shown in Table 7. “[13.52,16.00],2.48” indicates that the increasing interval is [13.52 s, 16.00 s], and the length of this interval is 2.48 s. Although there are some differences among the lengths for increasing and decreasing intervals in each situation, it can be seen from Figure 5 that the catch-up probabilities are all approximately symmetrical about x = 16 s.Table 7
x’s intervals of P(ς)=z(x) in situation ① of Section 5.3.1.
Monotonicity of interval δ p = 0.0 1 L, δq=0.01(L+v0x) δ p = 0.0 1 L, δq=0.025(L+v0x) δ p = 0.02 5 L, δq=0.01(L+v0x) δ p = 0.02 5 L, δq=0.025(L+v0x) Increasing [ 13.52,16.00 ] , 2.48 [ 11.96,16.00 ] , 4.04 [ 11.67,16.00 ] , 4.33 [ 10.22,16.00 ] , 5.78 Decreasing [ 16.00,18.64 ] , 2.64 [ 16.00,21.10 ] , 5.10 [ 16.00,20.62 ] , 4.62 [ 16.00,23.24 ] , 7.24In Figure6(a), the vertexes of the four curves are all (15.99,0.50). The monotonically increasing and decreasing intervals for P(ς)=z(x) situation ① of in Section 5.3.2 are shown in Table 8. The indication of “[14.24,15.99], 1.75” is the same as Table 7. It can be seen that the catch-up probabilities are also approximately symmetrical about x = 16 s.Table 8
x’s intervals of P(ς)=z(x) in situation ① of Section 5.3.2.
Monotonicity of interval δ ′ p = 0.25, δ′q = 0.25 δ ′ p = 0.25, δ′q = 0.5 δ ′ p = 0.5, δ′q = 0.25 δ ′ p = 0.5, δ′q = 0.5 Increasing [ 14.24,15.99 ], 1.75 [ 13.66,15.99 ], 2.33 [ 13.12,15.99 ], 2.87 [ 12.53,15.99 ], 3.46 Decreasing [ 15.99,17.72 ], 1.73 [ 15.99,18.27 ], 2.28 [ 15.99,19.18 ], 3.19 [ 15.99,19.79 ], 3.8From Figures5(b), 5(c), 6(b), and 6(c), it can be seen that, in each situation, the vertex of the catch-up probabilities is approximately (16.00,0.50); P(ς)=z(x) is approximately symmetrical about x = 16 s; P(ς)=z(x) monotonically increases in (-∞,16] and decreases in [16,+∞), approximately.In summary, the probabilities of catch-up conflict changes in Section5.3 are similar to the conclusions of Inference 4.


### 5.5. Simulation Conclusions and Time Window Setting

From simulation results of catch-up conflict probability, it is known that the catch-up conflict probability reaches its maximum whenx=x0. When x gradually decreases or increases from x0, the catch-up conflict probability gradually decreases. At last, the catch-up conflict probability is 0, or is close to 0. These probability features of AGV catch-up conflicts provide references for time window setting of the dynamic adjustment under uncertain travel time.In the dynamic adjustment as detailed in Section4, it is necessary to calculate the time windows. However, it is complicated to calculate them precisely according to Section 2. In contrast, it is simple and practical to apply Inference 4 and simulation conclusions of Section 5 to approximate calculation of time windows in AGVs operation. This feasible and beneficial strategy is as follows: for the link with “P(ς)>Tccp” after path preplanning, the corresponding x is initially recorded. And then the x which makes x-x0 be the historical maximum is set as xm, followed by the corresponding time window [x0-|xm-x0|,x0+|xm-x0|]. Finally, in the process of path replanning, if x is in the range [x0-xm-x0,x0+xm-x0], logistics manager can determine that the corresponding path is unacceptable (because of “P(ς)>Tccp,” which can be seen from Inference 4 and simulation conclusions of Section 5). Else, calculate the catch-up probability according to Section 2. After the calculation, if “P(ς)>Tccp” still holds, update xm and the corresponding time window. Although this strategy cannot obtain the precise time windows at once, it is very favorable for AGV transportation systems since high time savings and improved efficiency encourage logistics managers to implement effectively. Therefore, this strategy is employed in Section 6.


## 5.1. Simulation Settings

Automated container terminals are typical automated logistics systems. Because of the notable uncertainty characteristics at automated container terminals, conflicts among AGVs are particularly common, resulting in new bottlenecks of loading and unloading operations. Therefore, it is extremely important to take AGVs at automated container terminals as an example for analyzing catch-up conflict probabilities, using simulations to enhance the operational abilities of AGVs and improve the overall efficiency of automated container terminals. Figure2 shows the road network of an automated container terminal. Roads in the network are one-way and single lanes. “QC” and “YC” indicate the quay crane and yard crane, respectively. v0 is 5 m/s. The horizontal and vertical path lengths are 260 and 90 m, respectively. Nodes 1–63 are road network nodes. Nodes A–C are quay cranes. Nodes a–g are yard cranes. The following parameters are defined based on the statistics of an actual automated container terminal with annual throughput capacity of 5 million TEU.Figure 2
Road network layout and AGVs’ paths at an automated container terminal.The red and purple lines denote the travel paths ofAGVp and AGVq, respectively. Both AGVp and AGVq pass through link (28,29), which may cause catch-up conflict. It can be calculated that t1 = 20 s, t3 = 26 s, t2 = 4 s, and t4 = 10 s. If the departure time of AGVp and AGVq is both 0 s, let tp,28 and tp,29 denote the actual times at which AGVp reach nodes 28 and 29, respectively, and let tq,28 and tq,29 denote the actual times at which AGVq reach nodes 28 and 29, respectively. The departure time of AGVq changes to x s; the actual times at which AGVq reach nodes 28 and 29 are tq,28+x and tq,29+x, respectively. Here, P(ς)=z(x) is simulated to verify the impact analysis of travel time uncertainty on catch-up conflict in Section 3.φ ( t ) in (5) and (6) are employed in φp,28(t), φq,28(t), φp,29(t), and φq,29(t). For the convenience, δp and σp denote δ and σ in φp,28(t) and φp,29(t), respectively, while δq and σq denote δ and σ in φq,28(t) and φq,29(t), respectively.Inference4 in Section 3 is a summary of the conflict probability characteristics. Therefore, only Inference 4 is verified in Section 5. Both “Conditions of Inference 4 are exactly met” and “Conditions of Inference 4 are approximately met” are simulated with MATLAB.


## 5.2. Conditions of Inference4 Are Exactly Met

### 5.2.1.φ(t) Is Unrelated to Travel Distance

δ and σ in (5) and (6) remain constant. Generally, the times at which an AGV passes through adjacent nodes obey the same type of probability distribution. According to different combinations of uniform and normal distributions, there are three situations (①, ②, and ③) in which the distributions and parameters are set according to Table 1.Table 1
Distributions and parameters inφ(t).
φ p , 28 ( t ), φp,29(t) φ q , 28 ( t ), φq,29(t) ① Distribution Uniform Uniform δ 1 or 2.5 0.25 or 1 ② Distribution Normal Normal σ 0.5 or 1 0.25 or 0.5 ③ Distribution Uniform Normal δ/σ 1 or 2 0.25 or 0.5Through simulation, catch-up probabilities changing withx in the three situations in Table 1 are shown in Figures 3(a), 3(b), and 3(c), respectively. Four curves in each figure stand for four cases.Figure 3
Catch-up conflict probability changes in Section5.2.1.
(a) (b) (c)


### 5.2.2.φ(t) Is Related to Travel Distance

δ and σ in (5) and (6) change with travel distance. Here, L denotes the travel distance from the start point to the current node. There are three situations in which the distributions of φp,28(t), φq,28(t), φp,29(t), and φq,29(t) are the same as shown in Table 1. The parameters are shown in Table 2.Table 2
Parameters inφ(t).
φ p , 28 ( t ), φp,29(t) φ q , 28 ( t ), φq,29(t) ① δ 0.01 L or 0.025L 0.01 L or 0.025L ② σ 0.00 5 L or 0.015L 0.00 5 L or 0.015L ③ δ/σ 0.0 1 L or 0.025L 0.0 1 L or 0.015LSimulated catch-up probabilities changing withx in the three situations in Table 2 are shown in Figures 4(a), 4(b), and 4(c), respectively.Figure 4
Catch-up conflict probability changes in Section5.2.2.
(a) (b) (c)


## 5.2.1.φ(t) Is Unrelated to Travel Distance

δ and σ in (5) and (6) remain constant. Generally, the times at which an AGV passes through adjacent nodes obey the same type of probability distribution. According to different combinations of uniform and normal distributions, there are three situations (①, ②, and ③) in which the distributions and parameters are set according to Table 1.Table 1
Distributions and parameters inφ(t).
φ p , 28 ( t ), φp,29(t) φ q , 28 ( t ), φq,29(t) ① Distribution Uniform Uniform δ 1 or 2.5 0.25 or 1 ② Distribution Normal Normal σ 0.5 or 1 0.25 or 0.5 ③ Distribution Uniform Normal δ/σ 1 or 2 0.25 or 0.5Through simulation, catch-up probabilities changing withx in the three situations in Table 1 are shown in Figures 3(a), 3(b), and 3(c), respectively. Four curves in each figure stand for four cases.Figure 3
Catch-up conflict probability changes in Section5.2.1.
(a) (b) (c)


## 5.2.2.φ(t) Is Related to Travel Distance

δ and σ in (5) and (6) change with travel distance. Here, L denotes the travel distance from the start point to the current node. There are three situations in which the distributions of φp,28(t), φq,28(t), φp,29(t), and φq,29(t) are the same as shown in Table 1. The parameters are shown in Table 2.Table 2
Parameters inφ(t).
φ p , 28 ( t ), φp,29(t) φ q , 28 ( t ), φq,29(t) ① δ 0.01 L or 0.025L 0.01 L or 0.025L ② σ 0.00 5 L or 0.015L 0.00 5 L or 0.015L ③ δ/σ 0.0 1 L or 0.025L 0.0 1 L or 0.015LSimulated catch-up probabilities changing withx in the three situations in Table 2 are shown in Figures 4(a), 4(b), and 4(c), respectively.Figure 4
Catch-up conflict probability changes in Section5.2.2.
(a) (b) (c)


## 5.3. Conditions of Inference4 Are Approximately Met

### 5.3.1.φ(t) Is Related to Travel Distance and x

For example, the value ofδq or σq in φq,28(t) and φq,29(t) is related to L+v0x. In this case, it does not exactly meet the conditions of Inference 4. However, if φq,28(t) and φq,29(t) do not change significantly with x, the conditions of Inference 4 are met approximately. There are three situations in which the distributions of φp,28(t), φq,28(t), φp,29(t), and φq,29(t) are the same as shown in Table 1. The parameters are shown in Table 3.Table 3
Parameters inφ(t).
φ p , 28 ( t ), φp,29(t) φ q , 28 ( t ), φq,29(t) ① δ 0.01 L or 0.025L 0.01 ( L + v 0 x ) or 0.025(L+v0x) ② σ 0.00 5 L or 0.015L 0.005 ( L + v 0 x ) or 0.015(L+v0x) ③ δ/σ 0.0 1 L or 0.025L 0.01 ( L + v 0 x ) or 0.015(L+v0x).Simulated catch-up probabilities changing withx in the three situations in Table 3 are shown in Figures 5(a), 5(b), and 5(c), respectively.Figure 5
Catch-up conflict probability changes in Section5.3.1.
(a) (b) (c)


### 5.3.2. Travel Speed Is Random

When the probability density function of travel speed has symmetric distribution,φ(t) often is not strictly symmetric distribution. But if φ(t) has an approximately symmetric distribution and φq,28(t) and φq,29(t) change little with x, it can also be approximately consistent with the conclusions of Inference 4.Let the probability density function of travel speed be of both uniform and normal distributions.ϕ(v) in (7) and (8) are employed in ϕp(v) and ϕq(v). For convenience, δ′p and σ′p denote δ′ and σ′ in ϕp(v), respectively, and δ′q and σ′q denote δ′ and σ′ in ϕq(v), respectively. Similarly, according to different combinations of travel speed in uniform and normal distributions, there are three situations shown in Table 4.Table 4
Distributions and parameters inϕ(v).
ϕ p ( v ) ϕ q ( v ) ① Distribution Uniform Uniform δ ′ 0.25 or 0.5 0.25 or 0.5 ② Distribution Normal Normal σ ′ 0.2 or 0.4 0.2 or 0.4 ③ Distribution Uniform Normal δ ′ / σ ′ 0.3 or 0.6 0.3 or 0.6Simulated catch-up probabilities changing withx in the three situations in Table 4 are shown in Figures 6(a), 6(b), and 6(c), respectively.Figure 6
Catch-up conflict probability changes in Section5.3.2.
(a) (b) (c)


## 5.3.1.φ(t) Is Related to Travel Distance and x

For example, the value ofδq or σq in φq,28(t) and φq,29(t) is related to L+v0x. In this case, it does not exactly meet the conditions of Inference 4. However, if φq,28(t) and φq,29(t) do not change significantly with x, the conditions of Inference 4 are met approximately. There are three situations in which the distributions of φp,28(t), φq,28(t), φp,29(t), and φq,29(t) are the same as shown in Table 1. The parameters are shown in Table 3.Table 3
Parameters inφ(t).
φ p , 28 ( t ), φp,29(t) φ q , 28 ( t ), φq,29(t) ① δ 0.01 L or 0.025L 0.01 ( L + v 0 x ) or 0.025(L+v0x) ② σ 0.00 5 L or 0.015L 0.005 ( L + v 0 x ) or 0.015(L+v0x) ③ δ/σ 0.0 1 L or 0.025L 0.01 ( L + v 0 x ) or 0.015(L+v0x).Simulated catch-up probabilities changing withx in the three situations in Table 3 are shown in Figures 5(a), 5(b), and 5(c), respectively.Figure 5
Catch-up conflict probability changes in Section5.3.1.
(a) (b) (c)


## 5.3.2. Travel Speed Is Random

When the probability density function of travel speed has symmetric distribution,φ(t) often is not strictly symmetric distribution. But if φ(t) has an approximately symmetric distribution and φq,28(t) and φq,29(t) change little with x, it can also be approximately consistent with the conclusions of Inference 4.Let the probability density function of travel speed be of both uniform and normal distributions.ϕ(v) in (7) and (8) are employed in ϕp(v) and ϕq(v). For convenience, δ′p and σ′p denote δ′ and σ′ in ϕp(v), respectively, and δ′q and σ′q denote δ′ and σ′ in ϕq(v), respectively. Similarly, according to different combinations of travel speed in uniform and normal distributions, there are three situations shown in Table 4.Table 4
Distributions and parameters inϕ(v).
ϕ p ( v ) ϕ q ( v ) ① Distribution Uniform Uniform δ ′ 0.25 or 0.5 0.25 or 0.5 ② Distribution Normal Normal σ ′ 0.2 or 0.4 0.2 or 0.4 ③ Distribution Uniform Normal δ ′ / σ ′ 0.3 or 0.6 0.3 or 0.6Simulated catch-up probabilities changing withx in the three situations in Table 4 are shown in Figures 6(a), 6(b), and 6(c), respectively.Figure 6
Catch-up conflict probability changes in Section5.3.2.
(a) (b) (c)


## 5.4. Discussions

### 5.4.1. Discussions about Section5.2

In the situations in Sections5.2.1 and 5.2.2, x0=t1-t2=t3-t4=16 s. In Figures 2 and 3, they are all symmetrical about x = 16 s; when x = 16 s, P(ς)=z(x) reaches its maximum value (0.5). In accordance with the cases in Sections 5.2.1 and 5.2.2, monotonically increasing and decreasing intervals of P(ς)=z(x) obtained by simulations are shown in Tables 5 and 6, which are consistent with Inference 4.Table 5
x’s intervals of P(ς)=z(x) in situation ① of Section 5.2.1.
Monotonicity of interval δ p = 1, δq = 0.25 δ p = 1, δq = 1 δ p = 2.5, δq = 0.25 δ p = 2.5, δq = 1 Increasing [ 14.75,16 ] [ 14,16 ] [ 13.25,16 ] [ 12.5,16 ] Decreasing [ 16,17.25 ] [ 16,18 ] [ 16,18.75 ] [ 16,19.5 ]Table 6
x’s intervals of P(ς)=z(x) in situation ① of Section 5.2.2.
Monotonicity of interval δ p = 0.0 1 L, δq=0.01L δ p = 0.0 1 L, δq=0.025L δ p = 0.02 5 L, δq=0.01L δ p =  0.02 5 L, δq=0.025L Increasing [ 14.2,16 ] [ 13.45,16 ] [ 12.25,16 ] [ 11.5,16 ] Decreasing [ 16,17.8 ] [ 16,18.55 ] [ 16,19.75 ] [ 16,20.5 ]In situation ② of Sections5.2.1 and 5.2.2, cp,28,cp,29,cq,28,cq,29→-∞ and dp,28,dp,29,dq,28,dq,29→+∞. In situation ③ of Sections 5.2.1 and 5.2.2, cp,28, cp,29, dp,28, and dp,29 are limited real numbers, cq,28,cq,29→-∞, dq,28,dq,29→+∞. In these four situations, S28=(-∞,+∞), S29=(-∞,+∞), and Sk∪Sl=(-∞,+∞). Therefore, P(ς)=z(x) monotonically increases in (-∞,16] and decreases in [16,+∞), which is consistent with Figures 3(b), 3(c), 4(b), and 4(c).In summary, the simulation results are consistent with the conclusions in Inference4.


### 5.4.2. Discussions about Section5.3

In Figures5(a)–5(c), the vertexes of the all curves are all (16.00,0.50). From the simulation results, the monotonically increasing and decreasing intervals for P(ς)=z(x) in situation ① of Section 5.3.1 are shown in Table 7. “[13.52,16.00],2.48” indicates that the increasing interval is [13.52 s, 16.00 s], and the length of this interval is 2.48 s. Although there are some differences among the lengths for increasing and decreasing intervals in each situation, it can be seen from Figure 5 that the catch-up probabilities are all approximately symmetrical about x = 16 s.Table 7
x’s intervals of P(ς)=z(x) in situation ① of Section 5.3.1.
Monotonicity of interval δ p = 0.0 1 L, δq=0.01(L+v0x) δ p = 0.0 1 L, δq=0.025(L+v0x) δ p = 0.02 5 L, δq=0.01(L+v0x) δ p = 0.02 5 L, δq=0.025(L+v0x) Increasing [ 13.52,16.00 ] , 2.48 [ 11.96,16.00 ] , 4.04 [ 11.67,16.00 ] , 4.33 [ 10.22,16.00 ] , 5.78 Decreasing [ 16.00,18.64 ] , 2.64 [ 16.00,21.10 ] , 5.10 [ 16.00,20.62 ] , 4.62 [ 16.00,23.24 ] , 7.24In Figure6(a), the vertexes of the four curves are all (15.99,0.50). The monotonically increasing and decreasing intervals for P(ς)=z(x) situation ① of in Section 5.3.2 are shown in Table 8. The indication of “[14.24,15.99], 1.75” is the same as Table 7. It can be seen that the catch-up probabilities are also approximately symmetrical about x = 16 s.Table 8
x’s intervals of P(ς)=z(x) in situation ① of Section 5.3.2.
Monotonicity of interval δ ′ p = 0.25, δ′q = 0.25 δ ′ p = 0.25, δ′q = 0.5 δ ′ p = 0.5, δ′q = 0.25 δ ′ p = 0.5, δ′q = 0.5 Increasing [ 14.24,15.99 ], 1.75 [ 13.66,15.99 ], 2.33 [ 13.12,15.99 ], 2.87 [ 12.53,15.99 ], 3.46 Decreasing [ 15.99,17.72 ], 1.73 [ 15.99,18.27 ], 2.28 [ 15.99,19.18 ], 3.19 [ 15.99,19.79 ], 3.8From Figures5(b), 5(c), 6(b), and 6(c), it can be seen that, in each situation, the vertex of the catch-up probabilities is approximately (16.00,0.50); P(ς)=z(x) is approximately symmetrical about x = 16 s; P(ς)=z(x) monotonically increases in (-∞,16] and decreases in [16,+∞), approximately.In summary, the probabilities of catch-up conflict changes in Section5.3 are similar to the conclusions of Inference 4.


## 5.4.1. Discussions about Section5.2

In the situations in Sections5.2.1 and 5.2.2, x0=t1-t2=t3-t4=16 s. In Figures 2 and 3, they are all symmetrical about x = 16 s; when x = 16 s, P(ς)=z(x) reaches its maximum value (0.5). In accordance with the cases in Sections 5.2.1 and 5.2.2, monotonically increasing and decreasing intervals of P(ς)=z(x) obtained by simulations are shown in Tables 5 and 6, which are consistent with Inference 4.Table 5
x’s intervals of P(ς)=z(x) in situation ① of Section 5.2.1.
Monotonicity of interval δ p = 1, δq = 0.25 δ p = 1, δq = 1 δ p = 2.5, δq = 0.25 δ p = 2.5, δq = 1 Increasing [ 14.75,16 ] [ 14,16 ] [ 13.25,16 ] [ 12.5,16 ] Decreasing [ 16,17.25 ] [ 16,18 ] [ 16,18.75 ] [ 16,19.5 ]Table 6
x’s intervals of P(ς)=z(x) in situation ① of Section 5.2.2.
Monotonicity of interval δ p = 0.0 1 L, δq=0.01L δ p = 0.0 1 L, δq=0.025L δ p = 0.02 5 L, δq=0.01L δ p =  0.02 5 L, δq=0.025L Increasing [ 14.2,16 ] [ 13.45,16 ] [ 12.25,16 ] [ 11.5,16 ] Decreasing [ 16,17.8 ] [ 16,18.55 ] [ 16,19.75 ] [ 16,20.5 ]In situation ② of Sections5.2.1 and 5.2.2, cp,28,cp,29,cq,28,cq,29→-∞ and dp,28,dp,29,dq,28,dq,29→+∞. In situation ③ of Sections 5.2.1 and 5.2.2, cp,28, cp,29, dp,28, and dp,29 are limited real numbers, cq,28,cq,29→-∞, dq,28,dq,29→+∞. In these four situations, S28=(-∞,+∞), S29=(-∞,+∞), and Sk∪Sl=(-∞,+∞). Therefore, P(ς)=z(x) monotonically increases in (-∞,16] and decreases in [16,+∞), which is consistent with Figures 3(b), 3(c), 4(b), and 4(c).In summary, the simulation results are consistent with the conclusions in Inference4.


## 5.4.2. Discussions about Section5.3

In Figures5(a)–5(c), the vertexes of the all curves are all (16.00,0.50). From the simulation results, the monotonically increasing and decreasing intervals for P(ς)=z(x) in situation ① of Section 5.3.1 are shown in Table 7. “[13.52,16.00],2.48” indicates that the increasing interval is [13.52 s, 16.00 s], and the length of this interval is 2.48 s. Although there are some differences among the lengths for increasing and decreasing intervals in each situation, it can be seen from Figure 5 that the catch-up probabilities are all approximately symmetrical about x = 16 s.Table 7
x’s intervals of P(ς)=z(x) in situation ① of Section 5.3.1.
Monotonicity of interval δ p = 0.0 1 L, δq=0.01(L+v0x) δ p = 0.0 1 L, δq=0.025(L+v0x) δ p = 0.02 5 L, δq=0.01(L+v0x) δ p = 0.02 5 L, δq=0.025(L+v0x) Increasing [ 13.52,16.00 ] , 2.48 [ 11.96,16.00 ] , 4.04 [ 11.67,16.00 ] , 4.33 [ 10.22,16.00 ] , 5.78 Decreasing [ 16.00,18.64 ] , 2.64 [ 16.00,21.10 ] , 5.10 [ 16.00,20.62 ] , 4.62 [ 16.00,23.24 ] , 7.24In Figure6(a), the vertexes of the four curves are all (15.99,0.50). The monotonically increasing and decreasing intervals for P(ς)=z(x) situation ① of in Section 5.3.2 are shown in Table 8. The indication of “[14.24,15.99], 1.75” is the same as Table 7. It can be seen that the catch-up probabilities are also approximately symmetrical about x = 16 s.Table 8
x’s intervals of P(ς)=z(x) in situation ① of Section 5.3.2.
Monotonicity of interval δ ′ p = 0.25, δ′q = 0.25 δ ′ p = 0.25, δ′q = 0.5 δ ′ p = 0.5, δ′q = 0.25 δ ′ p = 0.5, δ′q = 0.5 Increasing [ 14.24,15.99 ], 1.75 [ 13.66,15.99 ], 2.33 [ 13.12,15.99 ], 2.87 [ 12.53,15.99 ], 3.46 Decreasing [ 15.99,17.72 ], 1.73 [ 15.99,18.27 ], 2.28 [ 15.99,19.18 ], 3.19 [ 15.99,19.79 ], 3.8From Figures5(b), 5(c), 6(b), and 6(c), it can be seen that, in each situation, the vertex of the catch-up probabilities is approximately (16.00,0.50); P(ς)=z(x) is approximately symmetrical about x = 16 s; P(ς)=z(x) monotonically increases in (-∞,16] and decreases in [16,+∞), approximately.In summary, the probabilities of catch-up conflict changes in Section5.3 are similar to the conclusions of Inference 4.


## 5.5. Simulation Conclusions and Time Window Setting

From simulation results of catch-up conflict probability, it is known that the catch-up conflict probability reaches its maximum whenx=x0. When x gradually decreases or increases from x0, the catch-up conflict probability gradually decreases. At last, the catch-up conflict probability is 0, or is close to 0. These probability features of AGV catch-up conflicts provide references for time window setting of the dynamic adjustment under uncertain travel time.In the dynamic adjustment as detailed in Section4, it is necessary to calculate the time windows. However, it is complicated to calculate them precisely according to Section 2. In contrast, it is simple and practical to apply Inference 4 and simulation conclusions of Section 5 to approximate calculation of time windows in AGVs operation. This feasible and beneficial strategy is as follows: for the link with “P(ς)>Tccp” after path preplanning, the corresponding x is initially recorded. And then the x which makes x-x0 be the historical maximum is set as xm, followed by the corresponding time window [x0-|xm-x0|,x0+|xm-x0|]. Finally, in the process of path replanning, if x is in the range [x0-xm-x0,x0+xm-x0], logistics manager can determine that the corresponding path is unacceptable (because of “P(ς)>Tccp,” which can be seen from Inference 4 and simulation conclusions of Section 5). Else, calculate the catch-up probability according to Section 2. After the calculation, if “P(ς)>Tccp” still holds, update xm and the corresponding time window. Although this strategy cannot obtain the precise time windows at once, it is very favorable for AGV transportation systems since high time savings and improved efficiency encourage logistics managers to implement effectively. Therefore, this strategy is employed in Section 6.


## 6. Simulation on Dynamic Adjustment

The dynamic adjustment in Section4 is verified by ten AGVs at an automated container terminal as shown in Figure 1. The priority of AGVs is set as AGV1>AGV2>⋯>AGV10. Tccp=0.25, which is half of the maximum of the probability of catch-up conflict. The design speeds of AGVs are all 5 m/s, and the departure times of AGVs are random values in [0s,10s]. The starting nodes and final nodes are random in quayside cranes and yard cranes. The probability density functions for times AGVs passing through nodes are related to travel distance and x, and they are random probability density functions in Sections 5.2 and 5.3. The data about catch-up conflicts of AGVs are shown in Table 9.Table 9
Comparisons of adjustment effectiveness.
Adjustment strategy Number of “P(ς)>Tccp” Maximum conflict probability Average conflict probability Number of conflicts Average travel time Sensor detection 23 0.43 0.24 13 46.58 Conflict probability 0 0.23 0.13 2 38.17The data in the second row of Table9 are referencing AGVs which avoid conflict only by sensor detection. In this mode, AGVs with low priority slow down or wait once conflicts happen, and no dynamic adjustment is executed. The data in the third row of Table 9 are with reference to AGVs with dynamic adjustment detailed in Section 4. From Figure 1, it can be seen that some events of “P(ς)>Tccp” might occur in the process of the dynamic adjustment, although “P(ς)>Tccp” can be avoided after the dynamic adjustment. Here, in the third row of Table 9, “Number of ‘P(ς)>Tccp’” is the number of “P(ς)>Tccp” after the dynamic adjustment. “Number of conflicts” is the number of catch-up conflicts that have occurred after the dynamic adjustment.From Table9, it can be observed that the number of “P(ς)>Tccp,” maximum conflict probability, average conflict probability, number of conflicts, and average travel time of AGVs adjustment strategy based on conflict probability are quite smaller than those of AGVs adjustment strategy based on sensor detection.The number of “P(ς)>Tccp” about AGVs adjustment strategy based on conflict probability is 0, whereas the number of catch-up conflicts is more than 0. This is because the situation in which P(ς)≤Tccp has not been dealt with in dynamic adjustment.Although the catch-up conflict cannot be eliminated completely in the execution of the dynamic adjustment strategy based on conflict probability, the number of conflicts has been greatly reduced. Such few potential conflicts will not cause serious problems in AGVs, because AGVs with low priorities can slow down or wait to avoid conflicts.In brief, the dynamic adjustment based on conflict probability is superior to the traditional adjustment based on detection using sensors. The proposed method lowers the frequency of control action and brings higher efficiency and service ability of AGVs. The proposed method is suitable for the adjustment of path planning with uncertain travel time and has a high accuracy and practicability.


## 7. Conclusion

Travel time is crucial for the execution of transportation tasks. However, travel time uncertainty is one of the main defects of the loading and unloading operations often used in AGVs. This uncertainty affects AGV conflict and inevitably increases the variability in automated logistics systems. Higher travel time uncertainty leads to more difficult and complex path planning for AGVs.To meet the demands of practical applications, this work considers the travel time uncertainty of AGVs, studies the impact of travel time uncertainty on AGV catch-up conflict, and designs the dynamic adjustment based on conflict probability for AGVs. The probability features of catch-up conflicts and the performances of the associated dynamic adjustment are simulated and validated for AGVs at an automated container terminal. The simulation results show that the conclusions proposed in this work are correct, and the dynamic adjustment is effective. Moreover, the findings of the present work provide theoretical and decision-making bases for the improvement of automated logistics systems efficiency.In the future, related work in different areas will be extended. First, the impact of other uncertainties, such as task arrival time and task assignment, on AGV conflict will be analyzed and verified in real automated logistics systems. Second, intelligent algorithms based on conflict probability for AGVs conflict-free path planning under uncertain environments will be designed.



---

*Source: 4037695-2018-04-19.xml*