Optimal Design Methodology

for an AGV Transportation System

by Using the Queuing Network Theory
Satoshi Hoshino1 , Jun Ota1 , Akiko Shinozaki2 , and Hideki Hashimoto2
1
2

Dept. of Precision Engineering, School of Engineering The University of Tokyo

Bunkyo-ku, Tokyo 113-8656, JAPAN {hosino, ota}@prince.pe.u-tokyo.ac.jp
Mitsubishi Heavy Industries, LTD. Sagamihara-shi, Kanagawa 229-1193, Japan

Abstract. In this paper, we propose an optimal design methodology for an AGV

transportation system by using the queuing network theory. In this study, we deal
with an actual transportation system as a combinatorial optimization problem.
Therefore, some kind of paths and working multi-agents, such as Automated Guided
Vehicles (AGVs), Automated Transfer Cranes (ATCs), and container cranes, are included in this system as design objects. We describe how to derive these design
parameters (i.e., design solutions) by the performance evaluation of an AGV transportation system.

1 Introduction
In an automated port transportation system, timeliness is always an important constraint. Therefore, this system oers improvements in eciency. In
this paper, we propose an optimal design methodology for a transportation
system with AGVs. This design problem can be considered as combinatorial optimization problem. Therefore, it is necessary to consider the following
design elements: (1) an optimal number of working agents to satisfy the requirement, and (2) an optimal number of paths between agents.
Conventional researches relating to the design of transportation systems
are generally divided into two categories: (1) A method based on the analysis
of the local aspects of the transportation system [1][2], and (2) A method
based on solving problems with simulation [3][4]. Abe et al. [1][2] proposed a
design method using the open queuing network for optimal system design. In
this method, a belt conveyor was used at a coaling wharf. However, a transportation system using a transport agent, such as a belt conveyor, which may
move constantly, is inadequate for a multi-agent transportation system that
includes AGVs. On the other hand, Chiba et al. [3] proposed an integrated design methodology in AGV transportation systems. In this study, they designed
an optimal number of AGVs and transport routes based on a simulation. Liu
et al. [4] developed a microscopic simulation model for the purpose of designing, analyzing, and evaluating some dierent Automated Container Terminals
(ATCs).However, these two design methodologies are called simulation-based
optimization; therefore, they sometimes need a signicant amount of computational time to achieve an optimal design.
For this study, an AGV transportation system shown in Fig.1 was designed.
An objective of this study is to establish a specic methodology with the
following eects:

Satoshi Hoshino, Jun Ota, Akiko Shinozaki, and Hideki Hashimoto

Fig. 1. Vertical layout of AGV transportation system

1. It is possible to model and design the transportation system as a multiagent system, globally and optimally.
2. The computational time deriving the design solutions is less than that
required in the simulation-based optimization method.
3. It is possible to evaluate and analyze the system proposed here.
To achieve the eects outlined above, we applied a closed queuing network,
which is used to analyze and design large-scale computer systems for transportation systems. However, because the transportation time changes when
the number of AGVs in the system changes, the following problem arises when
only the queuing network theory is used.

It is impossible to design the system by using only the queuing network

theory.

For this challenging point, we aim to integrate the queuing network theory
into the simulation-based method and iterate a design process; then, we will
propose a methodology which can exactly simulate the transportation delay
and thus estimate the eciency of the proposed methodology.

2 Transportation System in a Port Container Terminal

2.1 AGV transportation system
In this study, the AGV transportation system is divided into three areas,
namely, the quay, transport, and container yard areas (Fig.1). In this system,
AGVs continue to circulate until they successfully complete all tasks by the
following procedure:
step1 The Container cranes working in the quay area load a container on the
AGVs from the container ship.
step2 A location is assigned as the destination in the container yard area at
the time when the AGV leaves the quay area.

Optimal Design Methodology for an AGV Transportation System

step3 The AGV arrives at the assigned location. If it encounters another

AGV in its working path, this AGV goes onto the passing path; then, this
passing path becomes a working path.
step4 If the ATC is already at the handling point, the AGV will transfer the
container to ATC. Otherwise, if the ATC is already engaged, the AGV
will wait at this point.
step5 The ATC goes to storage point in the assigned location to store the
container.
step6 The AGV that has handled a container goes back to the quay area.
(back to step1)
In this system, two dierent types of ATCs are working at the same location. Therefore, they can cross each other with working.
2.2 Combinatorial optimization problem
Design objects
The parameters of the design object in this study are described as the following:
- The number of AGVs
- The number of ATCs
- The number of passing paths (buers)
All containers should successfully be transported from the container ship to
the container yard area within a limited amount of time. In these constraints,
the minimum number of agents that satisfy the requirement is used as a
performance function.
Assumption of the transportation system
In this study, each location becomes the destination of a container by a certain probability for the sake of simplicity. As the assignments are made, any
location without an engaged ATC becomes the priority destination. Additionally, the general working time of each container crane depends on the position
allocated to each container in the container ship. However, we provide a xed
working time for the sake of simplicity. Moreover, three xed container cranes
are used due to the xed scale of a berth.

3 Queuing Network Theory

3.1 Cyclic queuing network
In the closed queuing network, the number of agents is constant since agents
can neither arrive nor leave the system, but, rather, circulate repeatedly
through the various nodes at all times [5]. Thus, a closed queuing network,
which includes N queues in tandem, i.e., a series of N queues arranged cyclically in such a way that agents proceed sequentially through the cycle, returning to the rst node after being serviced at node N , is called a cyclic queuing
network [6]. Fig.2 indicates the state of transition in the system from step n
(Fig.2a) to step n + 1 (Fig.2b).

Satoshi Hoshino, Jun Ota, Akiko Shinozaki, and Hideki Hashimoto

Fig. 2. A state transition diagram in the cyclic queuing network composed of a

single server. Only the rst agent proceeds to the next node; then, the next queuing
agent (the second agent in that queue) goes into the single server, and the third and
fourth agents proceed forward in the queue.

3.2 Performance evaluation method

Ottjes et al. and Duinkerken et al. used some performance indicators when
they designed the ACTs using a specic transport simulator [7][8]. Similarly
in our study, working AGVs in the system are dened as network agents.
The number of nodes, the service time at each node, the number of servers in
the nodes, the trac parameter, and the number of relative arrivals of AGVs
at the node are input parameters. After that, (a) trac intensity(Eq.1), (b)
throughput(Eq.2), and (c) the average number of AGVs at the node(Eq.3,
4) are obtained. The following are the performance evaluation criteria: (a) is
used to locate bottlenecks in the system, (b) is used to determine whether or
not the system satises the requirement, and (c) is used to design the number
of buers.

j1 (K) =
G[j] (K) =

j1 (K) = j1

G(K 1)
G(K)

(1)

j1 (K) = hj1

G(K 1)
G(K)

(2)

j1 (K) = hj1

G(K 1)
G(K)

(3)

xj qj (xj )G[j] (K xj )

(4)

1
G(K)

0xj K

N


qi (xi )

x1 ++xj1 +xj+1 ++xN =K i=1,i=j

where,
K: The Number of AGVs
j1 : The trac parameter
hj1 : The number of relative arrivals of AGVs
G(K): Normalization constant
G[j] (K): Normalization constant of j-complement in the network
N : The number of nodes
xj : The number of AGVs around the nodej

(5)

Optimal Design Methodology for an AGV Transportation System

qj (xj ): Convolution parameter

where the j1 is given by {the number of relative arrivals of AGVs at a
certain node j} {the service time at a certain node j} and the hj is the
number of relative arrivals of AGVs at node j. In this study, the number of
relative arrivals of AGVs is the same for each node because the design object
is modeled by a single cyclic queuing network (Fig.2). Therefore, the number
of tasks is equal to the number of relative arrivals of AGVs. These parameters
can be obtained from the system specications. The function G(K) is dened
so that all the P (x1 , x2 , ..., xN ) add up to one. The j-complement network is
equal to the normalization constant given by removing the jth node in the
closed queuing network, that is, G[j] (K) is obtained by procedure of the G(K)
described below [5]:
Dene the G(K) and q(K) arrays; then, execute the following procedure
after initializing these arrays:

1, x = 0
G(x) 0, x = 0
1 for (j = 1; j <= N; j++) {
2
for (x = 0; x <= K; x++) {
3
x
hj ,

x Sj

x!
x
q(x)
h
x
j

, Sj < x

xSj x!
Sj !Sj
4
5
6

}
for (k = K; k >= 0; k ) {
G(k)

7
}
8 }

q(y)G(k y)

0yk

where, Sj is the number of servers working at each node.

4 System Design
4.1 Modeling of the transportation system
Fig.1 is modeled as shown in Fig.3 based on the cyclic queuing network. The
three areas in Fig.1 are assigned from nodes 1 to 4, and the number of cranes
and ATCs in the quay area and container yard area are the number of servers
at nodes 1 and 3. AGVs circulate through those nodes in the network until
their transportation tasks are completed.

Satoshi Hoshino, Jun Ota, Akiko Shinozaki, and Hideki Hashimoto

Fig. 3. Modeling the transportation system

4.2 Transport specications of AGV and ATC

Table1 indicates the specications for the AGV and ATC. Fig.4 is the transportation route for the AGVs. It is assumed that the AGVs go through the
central path in the quay area for the sake of simplicity. Thus, in cases in which
there is no trac congestion, the time at node2 (A to B) and node4 (B to A)
is calculated: 165 [s] and 122 [s], respectively. On the other hand, the loading/unloading and handling time of the container crane and ATCs is xed
because of the above assumption; therefore, in this study, the time at nodes
1 and 3 are given as 60 [s] and 30 [s], respectively. However, if the ATC is not
at the handling point when the AGV arrives, the AGV will need to wait at
this point.
Table 1. Specication of the AGV and ATC
Max. velocity [m/s]
Rotational velocity [m/s]
Acceleration [m/s2 ]
Deceleration [m/s2 ]

AGV(full) AGV(empty) ATC(full) ATC(empty)

5.56
6.94
2.25
2.0
1.39
1.39
0.15
0.15
0.1
0.1
0.63
0.63
0.4
0.4

4.3 Design algorithm

Fig.5 indicates the design algorithm that we propose. In this design algorithm,
a transportation simulator is used to (1) simulate a designed system, and (2)
calculate the transportation delay by the AGV friction.
The service time at each node and the number of the container cranes
and ATCs are inputted as initial parameters. After that, the throughput is
obtained by the eq.(2). The throughput is evaluated based on certain requirements. If the throughput satises the requirements, the minimum number of
AGVs is derived as the optimal number of AGVs based on the performance
function. However, if it does not satisfy the requirement, the number of ATCs
is increased by two, and the design process is then iterated. In this study, the
number of AGVs is designed not to exceed 30 in order to avoid adding the
AGVs recklessly.

Optimal Design Methodology for an AGV Transportation System

Fig. 4. Modeling of transport routing

Fig. 5. Design algorithm by using the queuing network theory

The transportation simulator then operates based on the derived number

of AGVs to evaluate whether or not this theoretical result also satises the
requirement. If the simulation result also satises the requirement, the combination of optimal design parameters is obtained, as well as a design process in
which the number of ATCs is changed and the process is iterated. Otherwise,
the time at nodes 2, 3, and 4 are calculated by a simulator, and then the
calculated time can be used as input parameters.
This design process will be iterated until the derived number of AGVs in
step n is not lower than the derived number of AGVs in step n 1.
4.4 Requirement setting
In this study, one of the constraints is the time of berthing at a port container
terminal; this time is equal to the time required to complete the transport.
This is, {Transporting Requirement} {System Throughput}. In this design
process, the number of transportation tasks is 600, and the required throughput is 120, i.e., the system has to successfully complete all tasks within 5
hours.

Satoshi Hoshino, Jun Ota, Akiko Shinozaki, and Hideki Hashimoto

4.5 The combination of design solutions

Table2 indicates the number of AGVs at each node in the case of the design
solutions are obtained. The average number of AGVs at node3 is less than the
number of locations (6 and 7). Therefore, the number of buers is designed
as 0 (See Table3).
Table 2. Average number of AGVs at each node
Case Node1 Node2
Node3
Node4
a
6
4
3 < Location:6
4
b
5
4
3 < Location:7
4

Table3 indicates each combination of optimal design solutions and time

cost at each node (See the case a and b). The increase in the time is noticeable as the number of AGVs increases. Here, there is a trade-o between the
throughput that depends on the number of AGVs and the time needed by
the node. Therefore, there are cases in which increasing the number of AGVs
worsens the transport eciency.
Table 3. The combination of design parameters and time cost at each node
Case ATC AGV Buer Transporting time
Node2, 3, 4 [s]
a
12
17
0
178, 45, 144
b
14
16
0
170, 36, 140

4.6 Consideration
Consideration of design solutions by the throughput
Fig.6 indicates the throughput obtained by this design result. It can be conrmed that more than the optimal number of AGVs derived by this proposed
design algorithm could satisfy the requirement. From the simulation result,
the throughput is conrmed to be (a) 120.1 and (b) 126.6. From this result,
we consider that the proposed design methodology is available.

Fig. 6. System throughput

Optimal Design Methodology for an AGV Transportation System

Consideration of computational cost

If we solve this combinatorial optimization problem by using the all search
algorithm of the simulation-based optimization method, we must consider all
the combinations of design solutions: 30 AGVs 10 ATCs 2 buers equal
to 600 times of simulation cost is needed. Correspondingly, in our proposed
method, the total simulation cost required until the solutions are derived is
just 15 times. From this result, this proposal design methodology is able to
derive the solutions with a few simulations.

5 System Performance Evaluation

5.1 Trac intensity
The trac intensity at nodes 1 and 3 are evaluated in each design solutions.
As shown in Table4, in the system which is designed by the derived solution,
it can be located that bottleneck is in the quay side.
Table 4. Trac Intensity at Nodes 1 and 3
Case Node1 [%] Node3 [%]
a
92.4
44.5
b
91.9
33.7

Fig.7 indicates the trac intensity curve at nodes 1 and 3 while the number of AGVs in the system increases. It has been conrmed that the trac
intensity of node 1 approximates 100 [%] faster than that of node 3. This shows
that more container cranes are needed to obtain much more throughput.

Fig. 7. Performance evaluation by the trac intensity curve

5.2 Average number of AGVs at each node

Fig.8 indicates the average number of AGVs at each node while the number
of AGVs increases. Thus, Fig.8 indicates the rough behavior of AGVs. From
Fig.8(b) and (d), we can derive the number of transporting AGVs at nodes 2
and 4. From Fig.8(a) and (c), we can derive the number of loading/unloading
and handling AGVs and of queuing AGVs at nodes 1 and 3. This shows that
adding more AGVs to obtain more throughput leads the system to breakdown
due to the existence of bottleneck.

10

Satoshi Hoshino, Jun Ota, Akiko Shinozaki, and Hideki Hashimoto

Fig. 8. The number of AGVs at each node

6 Conclusion and Future Work

In this paper, the design methodology and performance evaluation of an actual
AGV transportation system are described. For this purpose, we integrated
the queuing network theory into the simulation-based optimization method.
The methodology was then proposed, which can simulate the transport delay
exactly and evaluate the eciency of the proposed methodology.
As future work, it would be necessary to design actual multi-agent transportation systems by modeling agents other than AGVs on the basis of a
certain probabilistic distribution of the rough behavior of such agents. In addition, this methodology will be applied at actual container terminals so that
the eciency of the system can be veried.

References
1. Abe M. et al. : The Optimum Design for Materials Handling-Carrying System in
Coaling Wharf (1st Rep), Proc. of Int. Conf. on Materials-Handling Equipment
and Logistics, pp. 133-143, 1991.
2. Abe M. et al. : The Optimum Design for Materials Handling-Carrying System in
Coaling Wharf (2nd Rep), Proc. of Int. Conf. on Materials-Handling Equipment
and Logistics, pp. 144-157, 1991.
3. Chiba R. et al. : Integrated Design with Classication of Transporter Routing
for AGV Systems, Proc. 2002 IEEE/RSJ Int. Conf. Intell. Robots and Systems,
pp. 1820-1825, 2002.
4. Liu C.-I. et al. : Design, Simulation, and Evaluation of Automated Container
Terminls, IEEE Tran. on Intelligent Transportation Systems, Vol. 3, No. 1, pp.
12-26, 2002.
5. Buzen J.P. : Computational algorithms for closed queueing networks with exponential servers, Comm. ACM, 16, 9, pp. 527-531, 1973.
6. Gordon W.J. et al. : Closed queuing systems with exponential servers, Oper.
Res. 15, 2, pp. 254-265, 1967.
7. Ottjes J.A. et al. : Simulation of a New Port-Ship Interface Concept for Inter
Modal Transport, Proc. of the 11th European Simulation Symposium, 1999.
8. Duinkerken M.B. et al. : A Simulation Model for Automated Container Terminals, Proc. of the Business and Industry Simulation Symposium, pp. 134-149,
2000.