Design and analysis of AGV-based cross-docking operations using analytical models

ABSTRACT

Cross-docking is important for logistics because it reduces inventory, lead-times, and shipments. However, dynamic imbalances between supply and demand usually results in some inventory being warehoused in cross-docks. Therefore, flexible automation using robots, such as automated guided vehicles (AGV), can be used to improve performance of cross-docking, a trend in industry. This paper focuses on mathematical modeling of cross-docking operations when packages are moved in AGVs. A model based on Mean Value Analysis (MVA) is developed for determining the number of AGVs and estimating the service rate. This service rate is used as a parameter in a fork/join queuing model to characterize the performance of cross-docks in which outbound trucks get their packages directly from in-bound trucks as well as warehouses by estimating the queue lengths and mean sojourn times. The efficacy of the combined MVA and fork/join analytical models is verified using a discrete-event simulation as a case study, which shows that the models are largely in agreement in a test range with difference of 28% at the lowest throughput tested. Future study could use advances in sensors and Industry 4.0 for estimating parameters in the proposed models and improve performance and sustainability.

KEYWORDS:

• AGV
• cross docking
• queueing models
• warehouse design
• queueing networks
• performance analysis

1. Introduction

The Material Handling Industry of America defines cross-docking as ‘the process of moving merchandise from the receiving dock to shipping dock for shipping without placing it first into storage locations’ (Van Belle et al., 2012). With the rapid rise of electronic retailing, the main focus has moved from holding stock to delivering an item rapidly. Therefore, cross-docking is becoming an important distribution strategy to deliver incoming packages directly to outgoing trailers with minimal storage in between. Cross-docking can reduce inventory-holding costs, decrease lead-times, and consolidate shipments. Cross-docking needs close synchronization between in-bound receiving and out-bound shipping operations and has been extensively studied in recent years. Some of these challenges can be addressed by employing flexible automation and mobile robotics in cross-docking which will enable intelligent, dynamic, routing to adapt to changing workload (Fragapane et al., 2021).

As can be seen from published literature, much of the studies have focused on scheduling trucks to essentially address operational issues (Theophilus et al., 2019). Less than perfect synchronization of in-bound and out-bound trucks coupled with dynamic imbalances between supply and demand usually results in some inventory being carried in cross-docks. Therefore, in practice, outbound trailers in cross-docks have to be loaded with a mix of packages picked directly from in-bound trailers and combined with packages from inventory, which is called a warehouse. It is common practice in industry to have such cross-docks where a portion of outbound packages are picked from a warehouse. This is an important issue in practice but has not been studied much in research (A-L. Ladier & Alpan, 2016). More importantly, space for such warehouse needs to be considered at the strategic level when a cross-dock terminal and its layout is being designed.

Another strategic issue that has not received much attention in research studies is the material transfer capacity of a cross-docking terminal. Typically papers that study scheduling of trucks in cross-docking terminals parameterize the material transfer capacity but do not address how to size it and the interaction between choice of this capacity with its warehouse. For instance, A. L. Ladier and Alpan (2018) in their truck scheduling formulation consider the maximum number of pallets that can be moved during one time period inside the cross-dock as an input to their model. Understanding and designing material transfer capacity for automated cross-docks is much more important than manual cross-docks because, once the facility is operational, it is practically difficult to increase the capacity, which has also been reported in literature (A-L. Ladier & Alpan, 2016).Automated cross-docks combined with warehouses are the focus of this paper. Automated Guided Vehicle (AGV) systems have been widely used for material handling in factories and warehouses. Compared to other methods, such as using conveyor belts or forklifts, the main advantage of AGVs in cross-dock applications is to increase the system’s flexibility. There are several theories for controlling AGV systems such as supervisory control theory (Wonham & Ramadge, 1984). Predicitve schedule and real-time re-routing techniques for AGVs to adapt to breakdowns and delays have also been proposed (Breton et al., 2006). Similarly, dispatching rules for AGVs have been studied in manufacturing job shop applications (Egbelu & Tanchoco, 1984). More recently, Lin et al. (2012, June) and Miyamoto and Inoue (2016) have studied dispatching issues that arise in operational control of AGVs. AGV fleet size can be determined using analytical and simulation modeling which involves consideration of load handling requirements, empty travel times, and waiting times. Rajotia et al. (1998) proposed a mixed integer program with an objective of minimizing AGV empty trips. Malmborg (1994) proposed a queuing dynamic model for a fixed number of AGVs in a single loop and used the model to predict material flow rates and vehicle response time from vehicle dispatching under a single loop system. Queuing models for AGVs used in container terminals have been proposed by Roy et al. (2016). Yang et al. (2018) studied integrated scheduling of cranes and AGVs in container terminals.

The main operational sequence in cross-docks is illustrated in Figure 1 and can be summarized as follows:

Figure 1. Process diagram.

1. The incoming packages are unloaded at the strip door (inbound door) and placed at the inbound dock.

2. Then an AGV picks a package from the inbound dock and carries it through the cross-dock networks to the required outbound dock or the warehouse.

3. Concurrently with (2), the packages on the storage shelves in the warehouse are picked and delivered to the outbound dock by AGVs.

4. Finally, all the packages from the cross-dock and warehouse are loaded into the outbound trailers at the stack door.

While unloading and loading operations in Steps 1 and 4 can also be automated using robots, in many industrial settings these are done manually.

Queuing models have been used in a variety of production and logistics applications for strategic design decisions (Shortle et al., 2018). Roy et al. developed a queuing model for an autonomous vehicle-based storage and retrieval system using multiclass open queuing network theory (Roy et al., 2015a). Similarly, a fork-join model has been proposed for such vehicle-based storage retrieval systems (Zou et al., 2016). Lamballais et al. (2017) propose a queuing network model for a robotic warehouse for order picking in e-commerce fulfillment centers by using a queuing network formulation. Another approach has been developed based on semi-open queuing network models to evaluate congestion effects in processing storage and retrieval transactions (Roy et al., 2015b). However, in cross-docks with a warehouse, models need to consider diverging and converging material flows.

The main advantage of using such analytical models based on queuing theory is that they are computationally very efficient and do not require a lot of data or detailed information about probability distributions. This makes them ideally suitable for strategic level design when much of the details are typically not available. Because of the underlying assumptions typically made in such models, the predicted results are not meant to be accurate in an absolute sense but only in a relative sense. Their computational efficiency enables decision-makers to extensively explore the design space and develop a short list of candidate design configurations, which can then be analyzed in greater detail. Usually, discrete event simulations are used detailed analysis.

Fork/join queuing models can be used to analyze cross-docking with warehouses and can be useful in making strategic decisions about material transfer capacity. When an order arrives at the fork node, two independent tasks need to be finished and joined together to complete the order. The two independent tasks are: loading packages from an inbound cross-dock and loading packages from the warehouse. The join node synchronizes the two independent tasks, which means both tasks must be completed for the order to be completed. For cross-docking with a warehouse, orders at the fork node represent packages moved from an inbound dock and packages from a warehouse. Likewise, synchronization from the join node ensures that an outbound truck leaves with all packages from inbound docks and the warehouse.

Generally, there is no closed-form expressions for the fork/join queue lengths, thus several approximation algorithms have been developed. Flatto and Hahn (1984) presented the probability generating function of the two joint queue lengths and their steady-state probabilities. Also, Flatto (1985) went on to further analyze the asymptotic behavior of this distribution. Nelson and Tantawi (1988) derived a simple, closed-form approximation for the mean sojourn time based on a scaling technique for an M/M/1 fork/join system with more than two queues. Baccelli and Makowski (1985) considered a fork/join system with N heterogeneous servers $\left(\mathrm{N}\ge 2\right)$ with general arrival and service process, and they computed steady-state upper bound and lower bound for GI/G/1 and D/G/1 systems. Balsamo et al. (1998) studied general M/G/1 fork/join queue systems by computing the mean sojourn time and its lower and upper bounds. This was based on the use of stochastic comparison methods, but this technique is computationally complex. Varma and Makowski (1994) developed an interpolation approximation for the mean sojourn time of fork/join for N-dimension parallel queue systems with general arrival and service distribution model with $\mathrm{N}\ge 2$ homogeneous servers with a focus on heavy traffic conditions. Kemper and Mandjes (2012) focused on methods to qualify the mean value of the sojourn time in two-queue fork/join systems. They defined $S_i$ as a task’s sojourn time in queue $i$ and a job’s sojourn $S$ as max $\left\{S_1,S_2\right\}$. Raghavan and Viswanadham (2001) have proposed fork/join queuing models for general supply chain networks with service times that have Gaussian distribution to estimate lead times at the supply chain level and analyzed the impact of variance.

In this paper, two approaches from queuing theory are combined in a novel way for modelling cross-docking operations by leveraging the strengths of both techniques. The rest of the paper is organized as follows: In Section 2, the service rates of different type of cross-docks is modelled using MVA. In Section 3, the fork/join queue network (FJQN) model is applied to cross-docking with warehouses system in which the service rate from the MVA model is used as an input. The mean sojourn time for a loading job in FJQN model is estimated along with its upper bound and lower bound in Section 4. Results from detailed simulation model are then used as a case study to verify the efficacy of the combined MVA + FJQN approach in Section 5. Section 6 presents conclusions along with several possible directions for future studies.

2. MVA for cross-dock throughput and AGV fleet sizing

Mean Value Analysis is a recursive technique for obtaining throughput in equilibrium for a closed separable system of queues (Martin & Lavenberg, 1980). Ankem (2017) studied the application of MVA for modelling cross-docking with AGVs without congestion. This work is generalized in this paper. A given cross-dock network is viewed as a set of interconnected nodes, in which each travel segment is a node. There are k such nodes in the network, and each node is modelled as an M/M/1 queue. The objective of the MVA algorithm is to model the performance of the cross-dock network as a function of the number of AGVs, m. The algorithm starts with a network with no AGVs and then increases the number of AGV’s by 1 iteratively until there are the required number of AGVs in the system as follows.

1. For k = 1 … K, the number of nodes, calculating the waiting time at each node using the arrival theorem.

(1) $W_k\left(m\right)=\frac{L_k\left(m-1\right)+1}{{\mu }_k},$(1)

where ${\mu }_k$ is the service rate at node $k$ and m is the number of AGVs.

• (2) Obtaining the throughput

(2) ${\lambda }_m=\frac{m}{{\sum }_{k=1}^K{W}_k\left(m\right)v_k},$(2)

where $v_k$ is the utilization of node $k$.

• (3) Computing the mean queue length for k = 1, … K.

(3) $L_k\left(m\right)=v_k{\lambda }_m{W}_k\left(m\right)$(3)

When warehousing is added to a cross-dock, the AGVs delivering from the warehouses will share the route segments with those from in-bound cross-docks and need to be included in the model to estimate the overall service rate, that is throughput, of the cross-dock. The number of warehouses can also influence the cross-dock throughput. We analyze and compare four types of cross-docks: (i) cross-dock with no warehouse, (ii) cross-dock with one warehouse, (iii) cross-dock with two warehouses, and (iv) cross-dock with four warehouses. Taking a four-door cross-dock with one warehouse as an example, in Figure 2, the cross-dock routes have been divided into 36 segments. A segment is a portion of a path. The arrows in Figure 2 show the direction of movement of AGVs from inbound doors to outbound doors. For example:

Figure 2. Four-door cross-dock with one warehouse.

(1) The route AGVs use from inbound door 1 to outbound door 1 would be: segment 4, segment 5, segment 3 and segment 6;

(2) The route AGVs using from inbound door 1 to warehouse would be: segment 4, segment 35, segment 31, segment 33;

(3) The route AGVs using from warehouse to outbound door 1 would be: segment 34, segment 32, segment 36, segment 3.

Table 1 gives the length of each segment of a different type of cross-dock. For a four-door cross-dock with one warehouse type, the segment number aligns with the number labelled in Figure 2. The area between the in-bound and out-bound doors is approximately 62 ft by 86 ft, which translates to 5,332 sq. ft.

Table 1. Length of Segments of Cross-Dock with Four Warehouses.

Cross-Dock Type	Segment	Length (Feet)
Cross-Dock with no warehouse	1,9,17,25,2,10,18, 26	6
	7,15,23,8,16,24	6
	3,11,19,27,4,12,20,28	9.42
	5,6,13,14,21,22,29,30	86
Cross-Dock with One warehouse	1,9,17,25,2,10,18, 26	6
	7,15,23,8,16,24	6
	3,11,19,27,4,12,20,28	9.42
	5,6,13,14,21,22,29,30	86
	31,32	40
	33,34	4.71
	35,36	6
Cross-Dock with two warehouses	1,9,17,25,2,10,18, 26	6
	7,15,23,8,16,24	6
	3,11,19,27,4,12,20,28	9.42
	5,6,13,14,21,22,29,30	86
	35,36,41,42	6
	31,32,37,38	40
	33,34,39,40	4.71
Cross-Dock with four warehouses	1,9,17,25,2,10,18, 26	6
	7,15,23,8,16,24	6
	3,11,19,27,4,12,20,28	9.42
	5,6,13,14,21,22,29,30	86
	35,36,37,38,44,45,46,47	4.71
	31,32,40,41	6
	33,34,42,43	22
	39,48	30

The most significant factor for a cross-dock is the number of doors. Bartholdi and Gue (2004) analyzed a 10-door cross-dock. However, most industrial cross-docks nowadays have between 50 doors to 300 doors. For this paper, a 100-door cross-dock has been chosen for convenience, but the results can be generalized to any arbitrary number of doors. Table 2 shows all cross-dock parameter values that we use in this paper.

Table 2. Cross-Dock Parameters Consistent with Industrial Practices.

Parameter	Value
Arriving Rate of Demand	Poisson Process with $\lambda =1$
Average Package Volume	$3\mathrm{f}{\mathrm{t}}^3$
Average Trailer Capacity	$3000\mathrm{f}{\mathrm{t}}^3$
Number of Packages Loaded per Trailer	1000 Packages
AGV Speed	4.4 feet/second
AGV Length	3 feet
AGV Capacity	1 package

In the MVA model, the cross-dock track segments are treated as servers, and AGV’s are treated as customers. Service rate at a segment means the rate at which an AGV can travel through that segment. As mentioned in section 1, an AGV is assumed to carry only one package at a time, so the queue length at a segment is equal to the queue length of packages. Take a four-door cross-dock with no warehouse and only one AGV as an example. Segment $k=1,2,\dots ,K=30$, and the number AGV, $m=1$. To start, set the average queue length $L_k\left(m=0\right)=0$ at each track segment. Recall the equations (1)(1) $W_k\left(m\right)=\frac{L_k\left(m-1\right)+1}{{\mu }_k},$(1) , (2(2) ${\lambda }_m=\frac{m}{{\sum }_{k=1}^K{W}_k\left(m\right)v_k},$(2) ) and (3(3) $L_k\left(m\right)=v_k{\lambda }_m{W}_k\left(m\right)$(3) ):

The waiting time at segment for segment $k=1,2,\dots ,30$:

$\left(1\right)W_k\left(m=1\right)=\frac{L_k\left(0\right)+1}{{\mu }_k}=\frac{1}{{\mu }_k},$

where ${\mu }_k=\frac{\mathrm{A}\mathrm{G}\mathrm{V}\mathrm{S}\mathrm{p}\mathrm{e}\mathrm{e}\mathrm{d}}{\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}\mathrm{o}\mathrm{f}\mathrm{e}\mathrm{a}\mathrm{c}\mathrm{h}\mathrm{s}\mathrm{e}\mathrm{g}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}}$, reflects the rate of AGVs delivering packages on each segment. AGV speed and length of each segment are shown in Table 2.

The throughput with only one AGV in the system is given by:

$\left(2\right){\lambda }_{m=1}=\frac{1}{W_1\left(1\right)v_1+W_2\left(2\right)v_2+\dots +W_{30}\left(36\right)v_{30}},$

where $v_k=\frac{\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{o}\mathrm{f}\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{s}k\mathrm{s}\mathrm{e}\mathrm{g}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{s}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{d}}{\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{o}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{b}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}\mathrm{d}\mathrm{o}\mathrm{o}{\mathrm{r}}^2}.$

The segment usage $v_k$ depends on the number of inbound and outbound doors and the number of packages delivered by AGVs. In this paper, usage is calculated based on ‘uniform loading’ assumption in which packages are delivered from every inbound door to every outbound door.

The mean queue length for segment $k=1,2,\dots ,30$ is given by:

$\left(3\right)L_k\left(m=1\right)=v_k{\lambda }_1{W}_k\left(1\right).$

Table 3 shows the inputs used to calculate the system throughput of a four-door cross-dock with no warehouse, and ${\lambda }_{m=1}=$ 0.32. Under the assumption of uniform loading, the throughput of each outbound door is 0.08.

Table 3. Input for Throughput Determination.

Segment	Length (feet)	AGV Speed (feet/second)	${\mu }_k$ (1/second)	The number of times k segment is used	$v_k$	AGV Length (feet)	Maximum number of AGV stay in segment k without congestion
3	9.42	4.4	0.47	4	0.16	3	3
11	9.42	4.4	0.47	4	0.16	3	3
19	9.42	4.4	0.47	4	0.16	3	3
27	9.42	4.4	0.47	4	0.16	3	3
4	9.42	4.4	0.47	4	0.16	3	3
12	9.42	4.4	0.47	4	0.16	3	3
20	9.42	4.4	0.47	4	0.16	3	3
28	9.42	4.4	0.47	4	0.16	3	3
1	6	4.4	0.73	3	0.12	3	2
9	6	4.4	0.73	7	0.28	3	2
17	6	4.4	0.73	7	0.28	3	2
25	6	4.4	0.73	3	0.12	3	2
2	6	4.4	0.73	3	0.12	3	2
10	6	4.4	0.73	7	0.28	3	2
18	6	4.4	0.73	7	0.28	3	2
26	6	4.4	0.73	3	0.12	3	2
7	6	4.4	0.73	6	0.24	3	2
15	6	4.4	0.73	8	0.32	3	2
23	6	4.4	0.73	6	0.24	3	2
8	6	4.4	0.73	6	0.24	3	2
16	6	4.4	0.73	8	0.32	3	2
24	6	4.4	0.73	6	0.24	3	2
5	86	4.4	0.05	7	0.28	3	28
6	86	4.4	0.05	1	0.04	3	28
13	86	4.4	0.05	5	0.2	3	28
14	86	4.4	0.05	3	0.12	3	28
21	86	4.4	0.05	3	0.12	3	28
22	86	4.4	0.05	5	0.2	3	28
29	86	4.4	0.05	1	0.04	3	28
30	86	4.4	0.05	7	0.28	3	28

For a given cross-dock network with various segment lengths and average travel speed for AGVs, cross-dock throughput can be obtained for varied number of AGVs. Figure 3 shows throughput of the four-door cross-dock with different number of warehouses as the number of AGVs are varied.

Figure 3. Throughput of 4-door cross-dock.

In Figure 3, for a given number of AGVs, the throughput increases as the number of warehouses increase. This is because adding warehouses reduces the congestion in the cross-dock. In practice, the cost associated with a warehouse would also be a factor to consider.

As seen in Figure 3, for each of cross-dock and warehouse configuration, the throughput increases rapidly with increasing AGVs initially but eventually is limited by the congestion caused by large number of AGVs in the system. Table 3 shows the maximum number of AGVs that can be in a given segment. By considering the number of AGVs and the capacity of each segment, Table 4 gives a bound on outbound throughput of different type of cross-dock without congestion. The throughput’s unit is in packages/second.

Table 4. Throughput of 4-door cross-dock.

Type	Throughput	Total Number of AGV in the system
Cross-Dock with No Warehouse	0.88	151
Cross-Dock with One Warehouse	1.05	154
Cross-Dock with Two Warehouses	1.19	187
Cross-Dock with Four Warehouses	1.56	197

The throughput of a cross-dock with warehouses is larger than the throughput of a cross-dock with no warehouse. The throughput will increase 0.5 package/second if a cross-dock with four warehouses is chosen instead of a cross-dock with one warehouse but requires 40 additional AGVs.

The throughput of a 100-door cross-dock can also be calculated using MVA analysis by extending the 4 doors model. Figure 4 shows throughput of different types of 100-door cross-docks.

Figure 4. Throughput of 100-door cross-dock.

The throughput has no significant difference among four types of cross-dock with 100 doors. To reduce the cost of building warehouses, a cross-dock with one warehouse could be selected. For the purpose of applying fork/join queuing theory to the cross-dock system, it is reasonable to assume that the throughput or the service rate of the cross-dock follows the exponential distribution with mean $x_2$=3 packages/second.

2.1. The rate of delivering packages from the warehouse

Once the order arrives, some packages are loaded from the warehouse and other packages are loaded from the cross-dock. To maintain a stable system, the service rates of the cross-dock and warehouse should be higher than the overall demand on the system. Therefore, the service rate of the warehouse should be greater than the demand as well as less than the service rate of the cross-dock. In this paper, the service rate of the warehouse is assumed to follow an exponential distribution with a rate between the arrival rate of demand for the overall system and the service rate of the cross-dock. The arrival rate is assumed to follow the Poisson process with rate = 1, and the cross-dock service rate is assumed to follow the exponential distribution with rate = 3. Thus, the warehouse service rate is assumed to follow the exponential distribution with rate between 1 and 3.

2.2. Combining MVA and FJQN model

In this paper, MVA and FJQN are based on M/M/1 queues; and the resulting throughput using MVA model of the cross-dock is exponentially distributed, which can be readily input to the FJQN model. Figure 5 shows the flow chart of applying MVA to FJQN model.

Figure 5. Flow chart combining MVA and FJQN model.

From the FJQN model, the queue length of packages delivered from the cross-dock and the queue length of packages delivered from the warehouse as well as the mean sojourn times, also called the mean waiting time, of one job can be computed. One job here means processing one outbound trailer, that is loading every needed package into one outbound truck from inbound doors or warehouses.

3. The queue length of cross-dock with a warehouse

The two queues for the cross-dock with a warehouse is defined by $x_1$-queue and $x_2$-queue. Here $x_1$ and $x_2$ are the mean service rate of the warehouse and the cross-dock, respectively. $x_1$-queue stands for the queue in which the packages are loaded from the warehouse. $x_2$-queue stands for the queue in which the packages are loaded from the cross-dock. The equation for the equilibrium probabilities $p_{ij}$=P ($i$ packages in $x_1$-queue, $j$ customers in $x_2$-queue) is converted to the generating function $P\left(z,w\right)={\sum }^{p_{ij}}{z}^i{w}^j$, which displays a relation between P(z,0) and P(0,w) on the portion |z|, |w| less than or equal to 1 of S. S is a Riemann Surface of genus 1 that is parameterized by two elliptic functions z = z(t) and w = w(t), and t is referred to as a uniformizing parameter on S.

(4) $S=\{\left(z,w\right):(1+x_1+x_2)zw-x_{1}w-x_{2}z-z^2{w}^2\}$(4)

The functions $p_{ij}\left(t\right)$ satisfy the Kolmogorov forward equation (Feldman & Valdez-Flores, 2009). The equilibrium equations are obtained from these by setting $\frac{d{p}_{ij}}{d_t}=0.$ Using the notation:

$\chi \left(A\right)=\left\{\begin{array}{c}1,ifpropertyAholds\\ 0,otherwise\end{array}\right.$

The equilibrium equations are:

(5) $[1+x_1\chi \left(i\ge 1\right)+x_2\chi \left(j\ge 1\right)]p_{ij}=x_1{p}_{i+1,j}+x_2{p}_{i,j+1}+\chi \left(i\ge 1,j\ge 1\right)p_{i-1,j-1}$(5)

It is converted into the equation for $P\left(z,w\right)$

(6) $Q\left(z,w\right)P\left(z,w\right)=N\left(z,w\right),\left|z\right|,\left|w\right|\le 1,$(6)

where

(7) $Q\left(z,w\right)=\left(1+x_1{x}_2\right)zw-x_{1}w-x_{2}z-z^2{w}^2,$(7)

(8) $N\left(z,w\right)=x_{2}z\left(w-1\right)P\left(z,0\right)+x_{1}w\left(z-1\right)P\left(0,w\right)$(8)

Solving $Q=0$ for either $z,w$:

(9) $w=\frac{\left(1+x_1{x}_2\right)z-x_1\pm \sqrt{D_1\left(z\right)}}{2z^2}$(9)

(10) $z=\frac{\left(1+x_1{x}_2\right)w-x_2\pm \sqrt{D_2\left(w\right)}}{2w^2},$(10)

where

(11) $D_1\left(z\right)=[\left(1+\left(1+x_1{x}_2\right)z-x_1\right]{ }^2-4x_2{z}^3$(11)

(12) $D_2\left(w\right)=[\left(1+\left(1+x_1{x}_2\right)w-x_2\right]{ }^2-4x_1{w}^3$(12)

The functional equations for $P\left(z,w\right)$ are transformed into a set of conditions on $P\left(z\left(t\right),0\right)$ and $P\left(0,w\left(t\right)\right)$ to determine $P\left(z,w\right)$. From this, an asymptotic formula for $p_{ij}$ is obtained, which is used for studying the interdependence queue lengths $X_1,X_2$ where $X_1$ is the expectation of number of packages delivered from the cross-dock conditioned on $X_2,$ which is the queue length of delivering packages from the warehouse under the symmetric case and asymmetric. Furthermore, the expectation and the distribution of either of these random variables $X_1,X_2$ conditioned on the other is derived using the limit laws. The reader who is interested in the details is referred to Flatto and Hahn (1984), Flatto (1985).

(1) For $x_1<x_2,$ then:

(13) $E\left(X_1|X_2=j\right)\sim \frac{x_2-x_1}{x_2-1}\times jasj\to \mathrm{\infty }$(13)

(2) For $x_1=x_2,$ then:

(14) $E\left(X_1|X_2=j\right)\sim 2\sqrt{\frac{x_1\times j}{\left(x_1-1\right)\pi }}asj\to \mathrm{\infty }$(14)

From the previous section, the MVA model for the 100-door cross-dock estimates $x_2$ to be 3 packages/second. To get a stable system, $x_1$ should range between 1 to 3 packages/second. The arrival rate is a Poisson process with a mean of 1 package per second. As shown in Figure 6, if a given system’s queue length is found to be large then another system queue length is bound to be shorter. Therefore, if the total demand for the cross-dock with a warehouse is known, the number of packages loaded from the warehouse and the number of packages loaded from the cross-dock could be obtained as shown in Figure 7.

Figure 6. Queue length of double queue.

Figure 7. Number of packages loaded per trailer under the different service rate.

Symmetric here means the service rate of the cross-dock equals the service rate of the warehouse, which means $x_1=x_2=$ 3 packages/second. Asymmetric means the service rate of loading packages from the warehouse is different from the service rate of loading packages from the cross-dock. Under the symmetric case, the correlation coefficient of double queue,$\rho (X_1,X_2$), can be calculated according to the following equation:

(15) $\rho \left(X_1,X_2\right)=\frac{1}{2}-\frac{1}{8x_1}$(15)

where ${\mathrm{X}}_1$ and ${\mathrm{X}}_2$ are the queue lengths of the packages loaded from the cross-dock and the warehouse. $\hspace{0.17em}{x}_1$ is the service rate of packages loaded from the warehouse. Therefore:

(16) $\rho \left(X_1,X_2\right)=\frac{1}{2}-\frac{1}{8x_1}=\frac{1}{2}-\frac{1}{8\times 3}\approx 0.458$(16)

The result indicates that there is a positive relationship between the queue length of loading packages from the warehouse and the queue length of loading packages from the cross-dock.

3.1. The queue length of loading a trailer from warehouse and cross-dock

The paper assumes that order arrivals is a Poisson process with a mean of 1 package per second, and the service rate has exponential distribution with rates $x_1,x_2$. Recall that in Table 2, a trailer can have 1000 packages in total. For a cross-dock with 100 doors, $x_1$ is AGVs’ service rate delivering packages from the warehouse to outbound docks, and $x_2$ is the service rate of AGVs delivering packages from inbound docks to outbound docks. Several service rate pairs are applied to analyze the queue length of the cross-dock and the queue length of the warehouse. Five pairs of service rates are considered in this paper: $x_1$=1.1, $x_1$ =1.5, $x_1$= 2, $x_1$=2.5 and $x_1$=3 with $x_2$ =3 in each pair (units in package/second).

Based on equation (15)(15) $\rho \left(X_1,X_2\right)=\frac{1}{2}-\frac{1}{8x_1}$(15) , for $x_1=x_2$ = 3:

$\left\{\begin{array}{c}{X}_1=2\sqrt{\frac{x_1\times X_2}{\left(x_1-1\right)\pi }}\\ X_1+X_2=1000\end{array},\right.\left\{\begin{array}{c}{X}_1=50\\ X_2=950\end{array}\right.$

Based on equation (13)(13) $E\left(X_1|X_2=j\right)\sim \frac{x_2-x_1}{x_2-1}\times jasj\to \mathrm{\infty }$(13) and (14(14) $E\left(X_1|X_2=j\right)\sim 2\sqrt{\frac{x_1\times j}{\left(x_1-1\right)\pi }}asj\to \mathrm{\infty }$(14) ), for $x_1<x_2$:

$\left\{\begin{array}{c}{X}_1=\frac{x_2-x_1}{x_2-1}\times X_2\\ X_1+X_2=1000\end{array}\right.$

Table 5 gives the number of packages loaded from the warehouse and the number of packages loaded from the cross-dock for one trailer under the symmetric case and asymmetric case. As the service rate of the warehouse gets closer to the rate of the cross-dock, the queue length of packages in the warehouse gets shorter. The warehouse will have a small inventory if the warehouse has a higher service rate that is close to the service rate of the cross-dock.

Table 5. Number of Packages Loaded per Trailer under the Different Service Rate.

Warehouse Service Rate	$\mathrm{C}\mathrm{r}\mathrm{o}\mathrm{s}$ s-Dock Service Rate	$X_1$	$X_2$
$x_1=1.1$	$x_2=3$	487.18	512.82
$x_1=1.2$	$x_2=3$	473.68	526.32
$x_1=1.3$	$x_2=3$	459.46	540.54
$x_1=1.4$	$x_2=3$	444.44	555.56
$x_1=1.5$	$x_2=3$	428.57	571.43
$x_1=1.6$	$x_2=3$	411.76	588.24
$x_1=1.7$	$x_2=3$	393.94	606.06
$x_1=1.8$	$x_2=3$	375	625
$x_1=1.9$	$x_2=3$	354.84	645.16
$x_1=2.0$	$x_2=3$	333.33	666.67
$x_1=2.1$	$x_2=3$	310.34	689.66
$x_1=2.2$	$x_2=3$	285.71	714.29
$x_1=2.3$	$x_2=3$	259.26	740.74
$x_1=2.4$	$x_2=3$	230.77	769.23
$x_1=2.5$	$x_2=3$	200	800
$x_1=2.6$	$x_2=3$	166.67	833.33
$x_1=2.7$	$x_2=3$	130.43	869.57
$x_1=2.8$	$x_2=3$	90.91	909.09
$x_1=2.9$	$x_2=3$	47.62	952.38
$x_1=3$	$x_2=3$	50	950

4. Mean sojourn time with bounds

The paper assumes the arrival rate, $\lambda$, follows the Poisson distribution, and the service time $\frac{1}{x_1}$, $\frac{1}{x_2}$ follows the exponential distribution that is denoted by $B_1$ and $B_2$. The arriving orders or trailers generate jobs for loading packages from the warehouse and for loading packages from the cross-dock. The job’s sojourn time in $x_1$-queue, $x_2$- queue are denoted by $S_1$ and $S_1$. The sojourn time for an outbound trailer is the total time of staying in the system, which is sum of its waiting time and service time. The FJQN model for an outbound trailer’s sojourn time is S = max {$S_1$, $S_2$} which implies that it will be in the system until all its packages from the warehouse and cross-dock are loaded.

With $\lambda =1$ package/second, the load of node $i$ is defined as $l_i=\lambda E{B}_i$. The mean sojourn time based on the Pollaczek-Khinchine mean formula in each node, $E{S}_i$ gives

(17) $n_i=E{S}_i=\frac{\lambda E[{B_i}^2]}{2\left(1-l_i\right)}+E{B}_i=\frac{{l_i}^2}{2\left(1-l_i\right)}\left(sc{v}_i+1\right)+l_i$(17)

ES can be accurately approximated by the mean sojourn time of the bottleneck queue plus an increment of 10% (Kemper & Mandjes, 2009). By assuming $x_1$ and $x_2$ to be exponentially distributed, their square coefficient of variance (scv) is 1.

Two methods are used to get the lower and upper bound of ES. One is due to the Jensen’s inequality, and another one is presented by Baccelli and Makowski (1985), also see, Baccelli et al. (1989). For convenience, this paper refers to these bounds as ‘simple bounds’ and ‘B-M’ bounds. The assumption behind these bounds is that the variability of the system’s total working time, including waiting time and service time, of parallel queues increases as the variability of the arrival process increases. According to Jensen’s inequality, the lower bound is:

(18) $\mathrm{E}\mathrm{S}\ge max\left\{E{S}_1,E{S}_2\right\}=:\mathrm{l}\mathrm{b}$(18)

and the upper bound is:

(19) $ES\le E{S}_1+E{S}_2=ub$(19)

The B-M bounds could be applied to a more general queuing system. For a GI/G/1 fork-join queue, the upper bound could be computed due to the distribution of the sojourn times of single GI/G/1 queue and the single D/G/1 queue for the lower bound. The lower bound of the sojourn time is calculated under the case of deterministic arrival processes. $\underset{\_}{S}$ is defined as the maximum of $S_1$ and $S_2$.

(20) $E\left[S\right]=\underset{0}{\overset{\mathrm{\infty }}{\int }}y{P}_{\mathrm{D}/\mathrm{G}/1}(S_1\le y)d{P}_{\mathrm{D}/\mathrm{G}/1}\left(S_2\le y\right)+\underset{0}{\overset{\mathrm{\infty }}{\int }}x{P}_{\frac{\frac{\mathrm{D}}{\mathrm{G}}}{1}}\left(S_2\le x\right)d{P}_{\frac{\frac{\mathrm{D}}{\mathrm{G}}}{1}}\left(S_1\le x\right)=:LB$(20)

The two queues are assumed to be independent, according to the independent processes, following by $S_1$ and $S_2$ are also independent. $\bar{S}$, the upper bound of the mean sojourn time, is defined as the maximum of $S_1$ and $S_2$.

(21) $E\left[\bar{S}\right]=\underset{0}{\overset{\mathrm{\infty }}{\int }}y{P}_{\mathrm{G}\mathrm{I}/\mathrm{G}/1}(S_1\le y)d{P}_{\mathrm{G}\mathrm{I}/\mathrm{G}/1}\left(S_2\le y\right)+\underset{0}{\overset{\mathrm{\infty }}{\int }}x{P}_{\frac{\frac{\mathrm{G}\mathrm{I}}{\mathrm{G}}}{1}}\left(S_2\le x\right)d{P}_{\frac{\frac{\mathrm{G}\mathrm{I}}{\mathrm{G}}}{1}}\left(S_1\le x\right)=:UB$(21)

It shows that:

(22) $max\left\{lb,LB\right\}\le ES\le UB\le ub$(22)

Generally, the B-M bounds cannot be calculated explicitly for M/G/1 system, except M/M/1 queue. Also, in some situations, the lb and ub are tighter than B-M bounds. Thus because of the advantage of calculation, lb and ub are considered as the bound of the mean sojourn time rather than B-M bounds.

Under M/M/1 case,

(23) $UB=n_1+n_2-{\left(\frac{1}{n_1}+\frac{1}{n_2}\right)}^{-1}$(23)

It is known that $S_i$ follows the exponential distribution. For ES, having

(24) ${\tau }_i=\frac{l_i}{\left(1-a_i\right)}$(24)

where $a_i$ is the unique solution of –

(25) $a_i=e^{-\left(1-a_i\right)/l_i}$(25)

The lower bound is obtained after the integral calculations –

(26) $LB={\tau }_1+{\tau }_2-{\left(\frac{1}{{\tau }_1}+\frac{1}{{\tau }_2}\right)}^{-1}$(26)

4.1. Mean sojourn time of one job

Recall that the mean sojourn time of one job means loading 1000 packages into an outbound trailer from the cross-dock and the warehouse. With an arrival rate of $\lambda =1$ package/second, Table 3 shows the number of packages loading from the warehouse and the cross-dock for one trailer, respectively, which means the load of parallel queues is known. Then the mean sojourn time of an outbound trailer can be computed. In the following analysis, $x_2$ is fixed to be 3 packages/second and $x_1$ ranges from 1.1 packages/second to 3 packages/second. Table 4 shows the mean sojourn time and bounds of one job in cross-docking with warehouse system for five combinations of service rates.

Table 6 shows the total time of loading 1000 packages in a trailer. The mean sojourn time is very large when the service rate of loading packages from the warehouse is smaller than the service rate of loading packages from the cross-dock. Recall from Table 5 that more packages needed to be loaded from the warehouse at slower service rate. Therefore, it is reasonable to get a large mean sojourn time of one loading task of the warehouse if the service rate is low.

Table 6. Mean Sojourn Time of One Job under Different Service Rate.

Service Rate (package/second)	ES(minutes)	Simple Bounds (minutes)		B-M Bounds (minutes)
		lb	ub	LB	UB
$x_1=1.1$	8.79	11.47	7.99	13.8	9.05
$x_1=1.2$	8.24	11.07	7.49	11.52	8.65
$x_1=1.3$	7.63	10.61	6.94	9.71	8.21
$x_1=1.4$	7.01	10.14	6.37	8.26	7.77
$x_1=1.5$	6.4	9.7	5.82	7.08	7.37
$x_1=1.6$	5.82	9.29	5.29	6.11	7.01
$x_1=1.7$	5.28	8.91	4.8	5.31	6.7
$x_1=1.8$	4.76	8.57	4.33	4.64	6.43
$x_1=1.9$	4.82	8.27	4.38	4.08	6.21
$x_1=2.0$	4.98	8	4.53	3.61	6.03
$x_1=2.1$	5.15	7.76	4.68	3.21	5.9
$x_1=2.2$	5.34	7.55	4.85	2.88	5.82
$x_1=2.3$	5.53	7.37	5.03	2.59	5.77
$x_1=2.4$	5.75	7.22	5.22	2.35	5.77
$x_1=2.5$	5.98	7.09	5.43	2.14	5.82
$x_1=2.6$	6.22	6.98	5.66	1.97	5.91
$x_1=2.7$	6.49	6.9	5.9	1.82	6.05
$x_1=2.8$	6.65	6.84	6.17	1.69	6.24
$x_1=2.9$	6.7	6.8	6.47	1.58	6.48
$x_1=3.0$	6.75	6.79	6.45	1.49	6.47

Figure 8 shows the mean sojourn time of one job steeply declining and then slowly increasing as the service rate of loading packages from the warehouse gets closer to the service rate of loading packages from the cross-dock. When $x_1$ equals 1.8 packages/ second, it takes 4.76 minutes. This is the least time to completely process an outbound trailer. In Table 5, we see that if the service rate of loading packages from the warehouse is 1.8 packages/second, there will be 375 packages loaded from the warehouse and 625 packages loaded from the cross-dock for one trailer. Therefore, compared to the packages loaded from the cross-dock, there are fewer packages stored in and delivered from the warehouse, which can then be used to estimate the warehouse space requirements. The first plot shows the bounds calculated due to Jensen’s inequality, and the second one shows the bounds calculated due to Baccelli and Makowski (1985). By comparing the two plots, the simple bounds give a much better estimation of mean sojourn time range than the B-M bounds in this case. Thus, the simple bounds are used in the following analysis.

Figure 8. Bounds of one job’s mean sojourn time.

5. Cross-dock simulation case study

To test the efficacy of the combined MVA and FJQN models, a discrete-event simulation model of a 100-door cross-dock with warehouse has been developed using Simio simulation software is used as a case study. In this simulation model there are four entities for the cross-dock, which can be summarized as follows:

1. Source: the order arrives in the system following the Poisson distribution with $\lambda =1$ package/second.

2. Server_1: the service rate of delivering packages from the warehouse to outbound doors follows the exponential distribution with ${\mu }_1$ ranges from 1.1 package/second 3 to package/second.

3. Server_2: the service rate of delivering packages from the cross-dock follows the exponential distribution with ${\mu }_2$ = 3 package/second.

4. Sink (departure): one outbound trailer leaves the system after 1000 packages are loaded in the truck.

Table 7 shows the processing time of one package in the system without the waiting time. The waiting time in the system is mainly caused by the synchronization because there is no congestion in the delivering path. The trailer cannot leave until all packages from the corss-dock and warehouse are delivered and loaded.

Table 7. Comparison of Processing Time of One Package.

	Processing Time based on Simio (Seconds)				Processing Time based on FJQN (Seconds)
Service Rate	Average	Maximum	Minimum	Variance	ES	Upper Bound	Lower Bound
$x_1$=1.1	10.98	69.48	0	342.22	15.27	14.59	13.87
$x_1$=1.2	7.92	29.16	0	45.11	7.67	7.71	6.98
$x_1$=1.3	5.04	15.84	0	11.66	5.14	5.41	4.68
$x_1$=1.4	3.24	13.32	0	10.16	3.88	4.26	3.53
$x_1$=1.5	2.16	8.64	0	4.19	3.11	3.56	2.83
$x_1$=1.6	1.80	7.20	0	4.67	2.60	3.10	2.37
$x_1$=1.7	1.44	7.20	0	3.31	2.24	2.77	2.04
$x_1$=1.8	1.26	6.48	0	2.72	1.97	2.58	1.79
$x_1$=1.9	1.08	5.76	0	2.19	1.75	2.32	1.59
$x_1$=2.0	1.08	5.76	0	2.19	1.58	2.17	1.44
$x_1$=2.1	0.90	5.04	0	1.71	1.44	2.04	1.31
$x_1$=2.2	0.90	5.04	0	1.71	1.32	1.93	1.20
$x_1$=2.3	0.72	4.32	0	1.2	1.22	1.84	1.11
$x_1$=2.4	0.72	4.32	0	1.29	1.13	1.76	1.03
$x_1$=2.5	0.72	3.96	0	1.05	1.06	1.70	0.97
$x_1$=2.6	0.72	3.96	0	1.04	1.00	1.64	0.91
$x_1$=2.7	0.72	3.60	0	0.83	0.94	1.58	0.86
$x_1$=2.8	0.72	3.60	0	0.82	0.89	1.54	0.81
$x_1$=2.9	0.72	3.24	0	0.64	0.84	1.50	0.77
$x_1$=3.0	0.72	3.24	0	0.63	0.80	1.45	0.73

Table 7 uses 10 replications of the simulation to estimate the mean, maximum and minimum processing times. These results from simulation are compared with the simple bounds, which are tighter, as discussed in Section 4. From equation 11(11) $D_1\left(z\right)=[\left(1+\left(1+x_1{x}_2\right)z-x_1\right]{ }^2-4x_2{z}^3$(11) , the lower bound of ES should be larger than the maximum of ES1 and ES2. In our case, ES1 is always larger than the ES2 because the service rate of loading packages from the warehouse is larger than the service rate of loading packages from the cross-dock.

Figure 9 shows a comparison of the results for the simulation model and the FJQN model along with the plot of their differences for values of $x_1$ ranging from 1.1 to 3.0. Both models are largely in agreement almost everywhere in the tested range. However, when $x_1$ is 1.1, the processing time based on simulation model is 28% lower than computed using FJQN model package/second. We conjecture that this difference is caused by underlying differences: simulation model is based on M/M/1 queue, but FJQN is based on M/G/1 queue. M/G/1 allows arbitrary service time distribution. Recall in Section 3 when $x_1$ is 1.1 package/second, there would be 487 packages loaded from the warehouse. As $x_1$ increases from 1.1 to 3, the number of packages loaded from the warehouse decreases from 487 to 50, which decreases the processing time. For all other values of $x_1$ the simulation result and the FJQN model agree quite closely in the estimate of average processing times. However, there is considerable difference in variance of the processing time, which is a known limitation of queuing models.

Figure 9. Comparison of processing time from simulation and FJQN model results.

6. Conclusions

This paper proposed the first analytical queuing model that combines MVA and FJQN to model the performance of automated cross-docks with warehouse. In spite of the growing number of publications related to cross-docks, such models have not been developed. The proposed model can be used for strategic decision making in design and analysis of cross-docks, especially those based on AGVs for moving unit packages, which are becoming increasingly important in industry with the growth of electronic-retailing. We first address the issue of determining the number of AGVs and estimate the resulting service rate using Mean Value Analysis (MVA). A given cross-dock network is viewed as a set of interconnected nodes, in which each travel segment is a node. Each segment of the cross-dock network is modelled as an M/M/1 queue. Therefore, the service rate of each segment will also be exponentially distributed and makes it mathematically compatible with the FJQN which also modelled using M/M/1 queues.

The combined MVA and FJQN can be used to analyze the impact of design parameters such as number of AGVs, number of warehouses within the cross-dock network, and the relative service rates of cross-docks and warehouses. A significant use of this model is to efficiently assess how these design parameters influence the average time required to process an outbound trailer (sojourn time in the FJQN), which can be useful for industry practitioners. A detailed simulation model of a 100-door cross has been developed and found to agree with the analytical estimates of average time to process an outbound trailer. Future work should focus to perform a detailed case study in an industrial setting of cross-dock with warehouses to more completely understand the strengths and weaknesses of the proposed MVA/FJQN model. Most of the cross-docks in practice tend to be I-shaped (A-L. Ladier & Alpan, 2016). In particular, the models studied in this paper are agnostic to the specific shape, and the main impact of the shape is the layout of AGV travel paths, and resulting travel times, which the proposed model can readily extended to handle. Future studies could extend the proposed models to a variety of different shapes. Future studies should also consider generalizing beyond M/M/1 queue models that underlie the proposed MVA/FJQN model with the aim of obtaining good estimates of the variance in trailer processing times at least through approximations. A shortcoming of the current work is is lack of verification of results using real industrial data, which should be addressed in future work.

AGVs studied in this paper will be endowed with considerable sensing and intelligence that enables intelligent and dynamic routing, in turn would enable the system to adapt to varying workload. With advances sensors in Industry 4.0, parameters for these proposed models could be estimated automatically and accurately in the future and could open opportunities for improving operational performance and sustainability which are all topics for fruitful future studies.

Abbreviations

AGV Automated Guided Vehicle

D/G/1 Kendall’s notation for deterministic interarrival time, general service time, and single server

FJQN Fork/Join Queue Network

GI/G/1 Kendall’s notation for general (independent) interarrival time, general service time, and single server

M/G/1 Kendall’s notation for exponential interarrival time, general service time, and single server

M/M/1 Kendall’s notation for exponential interarrival time, exponential service time, and single server

MVA Mean Value Analysis

Disclosure statement

No potential conflict of interest was reported by the author(s).