Tandem Configurations for Automated
Guided Vehicle Systems and the
Analysis of Single Vehicle Loops
Yavuz A. Bozer
Mandyam M. Srinivasan
Department of
Industrial and Operations Engineering
The University of Michigan
Ann Arbor, MI 48109-2117
February 1988
Technical Report 88-3

Tandem Configurations for Automated Guided Vehicle
Systems and the Analysis of Single Vehicle Loops
Abstract
Automated Guided Vehicle (AGV) systems continue to play a significant role in
many low to medium flow manufacturing operations, including Flexible
Manufacturing Systems (FMS) and other applications. The relatively inexpensive
guide path, coupled with the high degree of flexibility and control offered in
vehicle routing, has made AGV systems a proven and viable handling technology
of the 80's.
Traditionally, AGV systems have been implemented and analyzed assuming that
every vehicle is allowed to visit any pickup/deposit point in the system. We
introduce a radically different, yet conceptually simple and intuitive approach where
the system is decomposed into non-overlapping single vehicle loops operating in
tandem. In this paper, we also develop an analytical model to study the throughput
performance of a single vehicle loop. The resulting expressions are the first closed
form analytical expressions that have been obtained to estimate the throughput
capacity for AGV systems in a non-deterministic environment.

TANDEM CONFIGURATIONS FOR AUTOMATED GUIDED VEHICLE
SYSTEMS AND THE ANALYSIS OF SINGLE VEHICLE LOOPS
1. Introduction
Automated Guided Vehicle (AGV) systems continue to play a significant role in many low to
medium flow manufacturing operations, including Flexible Manufacturing Systems (FMS) and
other applications. The relatively inexpensive guide path which does not interfere with other
material flow systems in the facility, coupled with the high degree of flexibility and control the
system offers in vehicle routing, has made AGV systems a proven and viable handling technology
of the 80's.
Although an increasing number of AGV vendors continue to develop more advanced vehicles
and sophisticated control systems, progress in basic academic research has been quite slow (except
for certain initiatives taken to develop guide path free or "self-guided" vehicles). Consequently,
many vendors and potential users continue to employ simulation as a primary tool in AGV system
design and evaluation.
Articles that describe successful industrial applications and those that review the state-of-the-art
in AGV systems quite often appear in trade journals such as Modern Materials Handling and
Material Handling Engineering. (The interested reader may refer to [4], [8], and [11], among
others for up-to-date reviews.)
In this paper we introduce a radically different and quite promising approach - one that is based
on a "tandem configuration" - to design AGV systems. Following a brief literature survey, in
section 3 we define tandem configurations for AGV systems and subsequently we discuss their
advantages and limitations. In section 4 we develop an analytical model to predict the throughput
capacity of a single vehicle operating in a closed loop. (As shown later, such a configuration
defines the basic "building block" of tandem AGV systems.)
In section 5 we present a set of simulation results to numerically verify the analytical model and
demonstrate soe of the insight we gain from it. Lastly, in section 6 we state our conclusions and
define future studies we intend to perform on tandem AGV systems.
1

2. Literature Review
Throughout the paper, including the literature review, we will assume that the reader is familiar
with generally accepted basic terminology used for AGV systems. Readers who are not familiar
with such terminology may refer to the AGV handbook published by the Material Handling
Institute (MHI) [14] or Koff's article [7].
To the best of our knowledge, the tandem configuration is a novel concept and all studies
(refereed or otherwise) in the open literature on AGV systems are concerned with "conventional"
systems where each vehicle is allowed to service any station in the system. Consequently, our
literature search is limited to a brief overview of technical papers concerned with conventional
AGV systems.
Studies concerned with conventional AGV systems generally address one or more of the
following issues: path configuration, location of pick-up/deposit (P/D) points, throughput capacity
estimation, number of vehicles required, and empty vehicle dispatching.
A design methodology with general applicability is presented by Maxwell and Muckstadt [9]
who study systems with unit load carriers operating on a unidirectional path. The authors develop
a deterministic model to derive a lower bound on the number of required vehicles and to determine
vehicle routes for given path layouts and flow data. They also present guidelines for locating P/D
points along certain segments of the guide path.
Studies concerned with empty vehicle dispatching policies are reported by Newton [10], Egbelu
and Tanchoco [3], Hodgson et al. [5], and King et al. [6]. The dispatching policy developed by
Hodgson et al. and King et al. is based on certain characteristics they observed in an analytical
model that was developed for very simple systems (with one or two vehicles and few P/D points).
However, in all of the above studies, for reasonably complex systems the primary tool used for
evaluating the impact of alternative policies is simulation.
A simple but efficient dispatching policy, namely, First-Encountered-First-Served (FEFS), is
presented by Bartholdi and Platzman [2]. The authors show that the FEFS policy (which was
presented by Stone and Fuller [12] for retrieving records from a rotating drum) can be applied to
the case where a single vehicle operates in a closed loop. (With certain restrictions, the results
presented by Bartholdi and Platzman also extend to multiple vehicles operating in a single closed
loop.)
2

For the static case of the problem, the authors show that the FEFS policy generates nearoptimum results in terms of minimizing the number of vehicle revolutions required to move a predetermined set of loads. For the same objective function, they also obtain a bound to show that the
FEFS policy would still perform reasonably well in a dynamic environment where some loads
arrive while the vehicle attempts to move loads that are currently in the system.
Note that Bartholdi and Platzman [2] use the FEFS policy for a single vehicle operating in a
closed loop which was noted earlier to be the basic "building block" of tandem AGV systems. It
must be stressed that, although we intend to use the FEFS policy in our study, Bartholdi and
Platzman had conventional systems in mind when they presented this policy. There is absolutely
no reference to a tandem (or similar) configuration in their paper and their concern for extending
the results to multiple vehicles operating in a closed loop clearly reflects their focus on conventional
AGV systems.
The studies cited above are concerned with "pick & drop" systems. As the name implies, such
AGV systems can be employed in all cases where loads are picked up at certain points and
delivered via AGVs to their destination points. The alternative concept, where each AGV functions
as a work platform on which a job remains until all processing operations are completed, is known
as the "stop & go" system. The "pick & drop" system can be used in both warehousing and
manufacturing while the "stop & go" system is most appropriate for manufacturing operations such
as fabrication and assembly. As seen in the next section, the tandem AGV system is envisioned as
a "pick & drop" system.
3. Tandem AGV Systems
Although the tandem configuration defined below can be used in both warehousing and
manufacturing applications, we will motivate the concept and develop the throughput capacity
estimation model for the latter. Consider first a conventional "pick & drop" AGV system used in
manufacturing. A typical application is illustrated in Figure 1 where each node represents a station
and the solid line represents the guide path. As described later in section 4, each station in Figure 1
may either represent a processor station (with one or more machines) or it may be used strictly as
an entry and exit point for loads entering or leaving the system, that is, an Input/Output (I/O)
station.
3

The system shown in Figure 1 is defined here as a conventional system since each AGV
operating in this system can pick-up a load from any station and deliver it to any other station.
That is, each vehicle has access to all stations. Note that each station has an input buffer and an
output buffer. The former is used for holding loads dropped off at that station while the latter is
used for holding loads that are waiting to be picked up by the AGV. Hence, the input and output
buffers represent the "drop" and "pick" points, respectively. By assumption, the input buffer
precedes the output buffer as shown in Figure 1.
Since each vehicle has access to all stations, conventional AGV systems generally require
extensive control systems for vehicle dispatching, vehicle routing, and traffic management. The
vehicle dispatching system is concerned with assigning the next task to empty vehicles. As can be
seen from several articles published in this area (see, for example, [3] and [5]), methods used for
dispatching empty vehicles in conventional systems can be quite complex. The vehicle routing
system, on the other hand, assures that full vehicles follow the right path to reach their proper
destinations. Depending on the type of system used (that is, single frequency versus multiple
frequency), the hardware associated with the routing system becomes rather complicated or
expensive as more segments (such as short-cuts and side spurs) are added to the guide path.
Lastly, the traffic management system is primarily concerned with avoiding collisions at
intersections, P/D points, and other segments on the guide path. Aside from several types of
sensors installed on the vehicles, most conventional systems use the "zone blocking" concept
where the entire system is divided into zones. The control system (centralized or dedicated to each
zone) allows only one vehicle in each zone at one time. Consequently, a vehicle will not be
allowed to proceed to the next segment of the guide path if another vehicle is present in that zone.
Needless to say, certain delays and slow-downs are encountered by the vehicles as a result of such
traffic management techniques that one is forced to use in conventional systems.
In short, as described in Koff [7] and numerous other articles, the vehicle dispatching system,
the vehicle routing system, and the traffic management system in conventional AGV systems can
be quite complex. This results not only in higher control system development costs, but it also
hinders the installation phase since debugging the control system and making the entire system
operate flawlessly as an integrated unit typically defines the critical path today. Moreover,
conventional systems are prone to congestion if "too many" vehicles are used due to poor planning
and/or increased material flow requirements.
4

The tandem configuration, on the other hand, is an application of the "divide and conquer"
principle to AGV systems. It is based on partitioning all the stations into non-overlapping, single
vehicle closed loops with additional P/D points provided as an interface between adjacent loops.
An example of a tandem AGV system is shown in Figure 2 where station locations are identical to
those shown earlier in Figure 1. Note that each station is assigned to only one loop and that each
loop has only one AGV.
Vehicle dispatching in tandem AGV systems is significantly less complicated than conventional
systems. This is primarily due to the fact that only a single vehicle is dispatched over a smaller
number of stations. Also note that traffic management problems within each loop is essentially
eliminated since there are no other vehicles to cause interference. However, in tandem AGV
systems, a load may be handled by several vehicles before it reaches its destination. In the
following two sections, we will attempt to further clarify the advantages and limitations of tandem
AGV systems.
3.1 Advantages of the Tandem Configuration
The following list is intended to outline the advantages of tandem AGV systems:
o Eliminates congestion (such as slow-down or blocking at intersections and P/D points).
o Yields a significantly less complicated control system (vehicle dispatching and traffic
management) for each loop.
o Allows one to use the same control system in each loop. This would reduce development cost
and installation effort.
o Supports "distributed processing" or "distributed control" since each loop, by construction, is a
natural control component of the system.
o Facilitates centralized control since individual "loop controllers" can be interfaced with a single
central processor.
o Facilitates future expansion since one or more loops (along with the corresponding new
stations) may be added to the system with minimal or no disruptions to most (or all of the)
existing loops.
5

o Within one system, it allows the use of "different" vehicles from the same supplier or several
suppliers. That is, all the AGVs need not be identical in control system requirements and/or
physical configuration as long as they can all use the P/D points provided as an interface
between adjacent loops. Such flexibility may play a critical role in system up-grade or in using
specially equipped vehicles in some loops.
o Supports the effective use of bi-directional vehicles without the usual problems such vehicles
generate in conventional systems.
o Supports the effective implementation of "group technology" since each loop (or a group of
loops) may be viewed as a "cell."
o Facilitates determining the optimum location of each station since the analyst can more easily
capture the material handling impact of alternative arrangements around a loop.
3.2 Limitations of the Tandem Configuration
A number of limitations can be observed for the tandem configuration. They are outlined as
follows:
o A load is likely to be handled by two or more vehicles before it reaches its destination.
o Requires additional space and guide path (due to non-overlapping loops) and additional P/D
points to interface adjacent loops.
o Less flexible in tolerating vehicle break-downs. A subset of stations cannot be accessed if a
vehicle is down. (May therefore require one or more "stand-by" vehicles.)
o Requires balanced workloads among the loops to avoid creating bottleneck loops.
o For loads that traverse several loops, it generates the load routing problem (as opposed to the
full vehicle routing problem in the conventional system).
Note that the first limitation does not necessarily imply that the throughput capacity of a tandem
system would always be worse than that of a conventional system. The additional "transit time"
6

incurred by loads that are handled by several vehicles under the tandem system would be traded-off
against time delays that occur due to congestion and/or operational inefficiencies (stemming from
complicated dispatching problems) in the conventional system.
For a given problem, if little or no congestion is anticipated in the proposed conventional
system, it may very well be the case that it would require a smaller number of vehicles than the
corresponding tandem system with the same throughput capacity. However, as pointed out by a
long-time consultant in the field (Apple [1]), the number of vehicles alone does not dictate the
preferred system since substantial savings incurred in the control system cost may make the tandem
configuration the most economical approach.
Obviously, further analysis is required to fully explore the relative strengths and weaknesses of
the two concepts from a cost and performance standpoint. However, since the tandem
configuration is a new concept, substantial work is necessary to analyze and design tandem AGV
systems before one can make a fair and quantitative comparison with conventional systems.
Hence, at this point we are not proposing tandem AGV systems as a substitute for conventional
systems. We rather view it as a very promising alternative which would outperform the
conventional system in certain cases.
In the following section we will develop an analytical model to study the throughput capacity of
a single vehicle operating in a closed loop. Note that such a system represents the basic "building
block" for tandem AGV systems since the overall throughput performance of the system, to a large
extent, depends on the performance of the individual loops. Further, in order to obtain an
algorithm to partition the system into single vehicle loops, one must first analyze the performance
of such a loop with a given set of P/D station locations and flow requirements. The main concern
at this point is to predict whether the vehicle will meet the throughput requirement imposed by
these stations.
It must be stressed that the term "loop" is not used in a strict sense. The user may specify any
set of appropriate travel times to be used for loaded vehicle travel; that is, one may use "short-cuts"
to reduce loaded vehicle travel time as long as the empty vehicle visits each station in a certain
sequence. One may also specify loaded vehicle travel times for a bi-directional AGV.
Note that a single vehicle operating in a closed loop can be considered as a single-server polling
system, where the server polls the queues in a non-deterministic order. This order will be
determined by the presence/absence of loads in the output queues of the stations as they are polled
by the vehicle. Although there is considerable literature on polling systems where the server polls
the queues in a deterministic sequence, to the best of our knowledge, the method of polling that is
7

being considered in this paper has not been studied previously. For an excellent review on polling
systems, the reader may refer to Takagi [13].
4. Throughput capacity analysis for a single vehicle loop
Let M denote the number of stations in a loop. The stations where the loads are processed will
be termed as the processor stations. Let e denote the set of processor stations, and let Q denote
the set of Input-Output (I/O) stations in the loop. Recall that every station in the loop is assumed to
have both an input and an output buffer. The output buffers of I/O stations receive loads from
outside the loop, while the output buffer of a processor station receives loads that are processed at
that station. In general, let Xi denote the rate at which loads arrive to the output buffer of station i.
The AGV picks up a load from the output buffer of a station and delivers it to the input buffer of
some other station. Let Ai denote the rate at which the vehicle delivers loads to the input buffer of
station i. For ease of exposition, we assume that Ai equals i in steady state at the processor
stations. On the other hand, for loops with multiple I/O stations, Ai need not equal ki in general.
When a load is delivered to the input buffer of an I/O station, it is assumed to exit from the loop.
Note that from conservation of flow, provided that the vehicle is able to meet the demand placed on
it, it must be true that X Ai = S Xi.
ie Q ieQ
Let pij denote the probability that a load, which is picked up by the AGV from the output buffer
of station i, is delivered to the input buffer of station j. Note that the Pij terms can be easily
computed from the problem description, as will be demonstrated in section 5. (It is implicit that pii
= 0.) The values for Ai are then obtained from the unique solution to the system of equations:
M
Ai = jPjji, (4.1.a)
j=l
with
Ai = Xi, ie 3. (4.1.b)
The time taken by the vehicle to pick up a load from the output buffer of station i, transport it
from station i to station j, and unload it at station j, is collectively assumed to be a random variable
with mean Tij. We assume that each station has ample input and output buffers, so that no
blocking of any form can occur.
For convenience, whenever an empty vehicle checks the output buffer of a station, we say that
the vehicle'inspects' station i. Based on the FEFS dispatching rule, it is assumed that when the
vehicle becomes empty, it always follows the same route until it picks up the next load. Without
8

loss of generality, this route is assumed to be 1,2,..,i,i+l,..,M,1,2,... (It is implicit in the
discussion that i+1 = 1, when i=M.) The resulting empty vehicle travel time between stations i and
i+1 is a random variable with mean ai,+1, which includes the time taken to inspect station i+l. Let
Ci denote the expected time between two successive inspections by the vehicle at station i. This
term plays an important role in determining the throughput capacity of the loop, and we show
below how this may be obtained.
For ease of exposition, we will assume, without any loss of generality, that station 1 is an I/O
station, and we will refer to C1 as the'cycle time.' Let vi denote the'visit ratio' for station i,
which is the expected number of times that the vehicle inspects the output buffer of station i during
the cycle time C1. Note that, by this definition, vl = 1. Suppose that we can determine the values
of C1 and the visit ratios, vi, for i=2,..,M. Then we can determine Ci, for any other station i
(including VO stations) from the identity
viCi = viC1. (4.2)
Let qi denote the probability that the output buffer of station i is empty at the instant that the
vehicle inspects the station. The probability of a service (i.e., that a load is picked up) at station i
when the vehicle inspects it is then given by (1-qi), and the expected number of loads picked up
from the output buffer of station i in a cycle is thus equal to (l-qi)vi. For stability of the system,
this should equal XiC1, which is the expected number of loads arriving at the output buffer of
station i during the cycle time C1. Equating these two terms, and using equation (4.2), we obtain
Property 1:
qi = 1- kii. (4.3)
Since qi is non-negative, Property 1 shows that if the vehicle is to meet the demand placed on it
by the arrivals to any /VO station i, then we must have Ci < lAi. In other words, every time the
vehicle inspects the output buffer of station i it removes a load if it finds one. If no load is found it
departs empty. In either case, however, it returns to re-inspect the output buffer of this station Ci
minutes later, on the average. Hence, as long as the time between inspections is less than the time
between arrivals at an output buffer, the vehicle will be able to meet throughput as far as that
station is concerned.
Consider, next, the transition matrix R =r(ij)}, i,j=,..M, which specifies the movement of
the vehicle between the stations. Suppose that the vehicle is currently at station i. Then, with
9

probability qi, the next station visited is station i+l, while with probability (l-qi)pij, the next
station visited is station j. Hence, the elements of this transition matrix are given by
r(i,j) = qi + (1-qi)ii+l j = i+1 (44)
(1-qi)pij j i+l.
Let v = (vi}, i=l,..,M. Noting that vl=l, the visit ratios are uniquely obtained from the set of
equations
vR = v, with
Vl = 1.
Thus,
M
vi = ~ (l-qj)Pjivj + qi-lvi-l, i=2,..,M. (4.5)
j=l
Let
M
vif = I (l-qj)pjivj, (4.5.a)
j=1
and
vie = vi-qi-1. (4.5.b)
Equations (4.5), (4.5.a) and (4.5.b) have the following interpretation. The term vi denotes the
expected number of times that the vehicle inspects station i in a cycle. This is the sum of two
components: (i) the expected number of inspections, vif, at station i in a cycle time C1, where the
vehicle arrived loaded at station i, and (ii) the expected number of inspections, vie, in a cycle time
C1, where the vehicle arrived empty at station i.
Using Property 1 and equation (4.2), equation (4.5) can be rewritten as
M
vi = XSjClpji + vi- -.i- C1,
j=l
M
and noting from equation (4.1) that X Xjpji = Ai, we obtain
j=l
vi = vi-1 + (Ai - i-1)C1. (4.6)
Consider the state of the output buffer of an arbitrary station i at the instant that the vehicle just
inspects it. Let Ti denote the expected time from this instant, until the instant when the next
inspection occurs at some station. With probability qi, the vehicle does not find a load waiting in
the output buffer of station i, and in this case, the next station inspected is station i+l. Hence, the
expected time until the instant when the next inspection occurs is ai,i+l. With probability (1-qi),
10

however, the vehicle finds a load waiting in the output buffer of station i and with probability Pij
the destination of this load is station j. Hence, for this case, the expected time until the instant
when the next inspection occurs is ij. The term Ti is thus given by
M
Ti = qi oij+l + (1-qi) ZPijij- (4.7)
j=1
Observe that in a cycle, station i is visited vi times. So, from equations (4.7) and (4.3), the cycle
time C1 is obtained as
M M M
C1 = viTi = ~ vi ( qi ii+l + (1-qi) XPijtij),
i=l i=l j=1
M M
E (oi,+l(vi-XiC1) + Cli pijxij). (4.8)
i=l j=l
Collecting terms involving C1 in equation (4.8), and setting
M M
af = ~ Xi ~ ijqij,
i=1 j=l
we have
M
~ ViGii+l
C1 M (4.9)
1 - af + ~,Xii,i+l
i=1
Note that the term af represents the proportion of time that the vehicle travels loaded, servicing the
loads that arrive at the output buffers of the stations. From equation (4.6), substituting i-1 in place
of i,
vi1 = Vi2 + (Ai-1 - Xi-2)C1
and so, we can write
i
vi = vi-2+ I (Aj- j.1)Ci.
j=i-1
Continuing to express vi, recursively, in terms of vi-3,..., vl, we obtain
i
vi = Vl + I (Aj-h j-1)C1. (4.10)
j=2
11

M
Let X = Oi,+l.- From equations (4.9) and (4.10), after some algebraic manipulation, we obtain
i=l
C1.= (4.11)
M i
1 - af+.lX - X (Aj-ij)oi,i+l
i=2 j=2
In equation (4.11), set
M i
P1P = Y. z (Aj-kj)i,i+.
i=2 j=2
Interchanging the order of summation, and noting that i+l=l when i=M, the term (p1 is rewritten as
M M M
Pq) = z (Aj-Xj) o ii+l = X (Aj-)j) aj,1, (4.12)
j=2 i=j j=2
k-1
where ajk = aoi,i+ denotes the expected empty vehicle travel time from station j to station k,
i=j
jek. The resulting expression for the cycle time is then stated as
Propertv 2:
C1 = (4.13)
1 - acf- (1+ lX
From equation (4.12), for the special case where Aj = Xj for all stations, we have
Corollary 1:
If the rate of arrivals of loads to the loop via I/O station i equals the rate of departures of loads
from the loop via VO station i for each i e Q, then
vi = v1 + (i - x1)C1, (4.14.a)
and
C1 = (4.14.b)
1 - af+ iX1
/
12

Corollary 1 has the following important interpretation: recall that in order for the AGV to
service all the loads that arrive at the output buffer of I/O station 1, we required that XlC1 < 1.
Applying this condition to equation (4.14.b), we obtain
IC1 = X< 1.
1 - af+ XiX
On simplifying the above inequality, we obtain the following condition for meeting throughput:
(f < 1. (4.15)
Thus, with the FEFS discipline, when the arrival rate at each I/O station is equal to its departure
rate, the only condition for the AGV to meet the throughput demand at any I/O station is that the
proportion of time that the AGV travels loaded be less than 1. In other words, it implies that for
this special case of the FEFS discipline, the empty vehicle travel times between stations do not
affect the throughput capacity of the AGV.
Also, note that from equations (4.14.a), and (4.3), it is easily seen that
viqi = viql. (4.16)
Hence, from equations (4.5.b) and (4.16), we have the following property stated as
Corollary 2:
If the arrival rates of loads to the loop via /O station i equals the rate of departures of loads
from the loop via I/O station i for each i e Q, then
vie = vie, i=2,..,M,
in other words, the empty vehicle travel is evenly distributed between all stations.
In general, from Property 2 we can obtain the condition for the AGV to meet the throughput
requirements at any I/O station. Applying the requirement that XC1 < 1 to equation (4.13), we
need the following condition:
f + (Pi < 1. (4.17)
Comparing equation (4.17) with equation (4.15), note that the term (pi acts as a correction factor.
Equation (4.17) can be interpreted as follows: in order for the AGV to meet the demand placed on
it by station 1, it has to undergo some "mandatory" empty vehicle travel, in addition to the loaded
vehicle travel. The term (pi represents the proportion of time that the vehicle is performing such
13

mandatory empty travel, as far as station 1 is concerned. Note that the correction factor could be
negative in some cases. We also present below, a relation between the (p terms, which is obtained
after some straightforward algebra:
k
(Pk- Pn = I (j- Aj). (4.18)
j=n+l
Note that for any processor station j, we have assumed that j = Aj. Consider any I/O station n,
and let m be index of the next I/O station, with m>n. Equation (4.18) states that for any processor
station having an index k between n and m, we must have
(pk = (Pn, k=n+l,..,m- 1.
Hence, from equations (4.17) and (4.18), it is clear that in order to check whether the vehicle
meets the throughput requirement for the loop, it is enough to check whether the vehicle meets the
throughput requirements at the I/O stations alone.
5. Numerical Examples and Discussions
In this section, using four numerical examples, we will demonstrate the use of the analytical
model and some of the insight we gained. We will also show how the pij values are computed (see
equation 4.1.a). The first two problems represent a "balanced" loop where the arrival rate at each
I/O station is equal to the departure rate. Hence, to a large extent they are used to demonstrate
Corollary 1. The last two problems are not balanced; they are used primarily to demonstrate the
results obtained from the analytical model and the impact of "mandatory" empty vehicle travel. In
each case, the results obtained from the analytical model are also numerically verified via
simulation.
Consider a hypothetical problem with eight stations numbered one through eight. Suppose that
stations 1, 3, 6, and 7 are I/O stations while the remaining stations are processor stations. As
shown in Figure 3, further suppose that the stations are arranged around a circle that resembles the
face of a clock. Empty travel time between each position on the "clock" is assumed to be constant
and equal to one time unit, say, one minute. Loaded travel time between a pair of stations is
obtained by adding one minute to the empty travel time between the pair. The unidirectional
vehicle is assumed to travel clockwise around the loop.
In the simulation model, on the other hand, we assume that interarrival times to the /O
stations, and the processing times at the processor stations are exponentially distributed. The
14

processing capacity of the processor stations are selected such that the expected utilization of each
processor is equal to 75%, provided that the vehicle meets throughput. (Any value for the mean
processing capacity may be used as long as it exceeds the required processing rate defined by Ai,.)
All travel times, empty or otherwise, are assumed to be constant. (Note that the analytical model
would work with any distribution for interarrival, processing, and travel times as long as their first
moment is defined )
In the above system, five types of jobs (labeled A through E) are processed. For each job
type, it is assumed that the number of units produced per hour and the routing (that is, the
sequence of stations they visit) are specified.
5.1 Balanced Systems
For the first numerical example, suppose that each job type is processed according to the data
shown in Table 1. Note that job type E represents all "transit" jobs; that is, those that use the loop
only as a transit loop between their origin and destination loops. Also, note that each job type
enters and leaves the loop through one of the I/O stations.
The data given in Table 1 represents a balanced system since the total rate at which jobs enter
through an I/O station is equal to the total rate at which they leave the loop through that station.
That is, X1=A1=0.875, sX=A3=0.375, X6=A6=0.250, and X7=A7=0.500 jobs per hour. It is
straightforward to compute the pij values from the flow data. For example, job types A, B, and D
require processing at station 8. Also, of the 1.25 jobs per hour that leave station 8, 0.375 are
destined to station 2 while the remaining 0.875 are destined to station 5. Hence, P82 = 0.375/1.25
= 0.30 and P85 = 0.875/1.25 = 0.70.
Using the above data we obtain af = 0.73125 and X = 12/60 = 0.20. Subsequently, using the
expressions derived earlier we obtain the following results: C1=27.0423, C3=34.9091,
C6=37.6471, and C7=32.5424 minutes per inspection. (The above results were obtained by first
computing C1 from equation (4.11). Subsequently, the vi value for i=3,6,and 7 was obtained
from equation (4.10). Using each vi value in equation (4.2) yields the corresponding Ci values of
interest.)
Thus, stations 1, 3, 6, and 7 are inspected at a rate of 2.2187, 1.7187, 1.5937, and 1.8437
times per hour, respectively. Since the rate at which the vehicle inspects stations 1, 3, 6, and 7
exceeds the rate at which loads arrive at these stations, we conclude that the system would meet the
required throughput. Note that the difference between the above two rates dictates the rate at which
the vehicle would depart empty from a station.
15

For example, consider station 1. Loads arrive at a rate of 0.875 per hour. The vehicle inspects
the output buffer of station 1 at a rate of 2.2187 times per hour. Hence, (2.2187 - 0.875) =
1.3437 times out of 2.2187, on the average, the vehicle will depart empty from station 1. In other
words, the probability of an empty departure from station 1 is equal to 1.3437/2.2187 = 0.6056.
Note that using equation (4.3) to obtain ql yields the same result.
The Ci and qi values obtained above were numerically verified using 99% confidence intervals
obtained from the simulation model. The results are shown in Appendix 1.
For the second numerical example, in order to demonstrate Corollary 1, we simply double the
empty travel time between all the stations while maintaining the original loaded travel times. That
is, empty travel time between each position on the "clock" in Figure 3 is assumed to be constant
and equal to two minutes.
Since the same travel times are used for loaded travel, the fraction of time that the vehicle
travels loaded remains the same; that is, af = 0.73125. However, the following values are
obtained for the cycle times: C1=38.7879, C3=57.3130, C6=65.0847, and C7=51.2000 minutes
per inspection. As expected, the vehicle still meets the required throughput since the time between
inspections is less than the time between arrivals at each I/VO station. (The Ci and qi values obtained
for the second problem were also numerically verified using 99% confidence intervals obtained
from the simulation model. The results are shown in Appendix 2.)
In the above two examples, no change occurs in af. Therefore, from Corollary 1 and equation
(4.15), it can be seen that the vehicle still meets throughput in the second problem although the
empty travel times were doubled. To further explore the relationship between the two problems,
consider the number of empty trips performed. In both problems the vehicle is empty 26.875% of
the time. Hence, given a run length of, say, 1000 minutes, the vehicle will be traveling empty for
268.75 minutes in both cases.
From Corollary 2, the empty vehicle travel is evenly distributed between all the stations, that is,
vi qi = vj qj for all i and j. Hence, in 268.75 minutes, the vehicle will make 268.75/12 = 22.4
revolutions around the loop in the first problem while it will make 11.2 revolutions in the second
problem. In other words, in the first problem, during a 1000 minute interval, one would observe a
vehicle, on the average, traveling empty 22.4 times between any two adjacent stations. For the
same time interval, one would observe 11.2 empty vehicles in the second problem.
Naturally, if the empty travel time was increased three times, then the vehicle would still have
met the required throughput, but the number of empty trips observed between adjacent stations
16

would have been three times less. (The above results were numerically verified through simulation
with substantially longer simulations runs.)
5.2 Unbalanced Systems
For the third numerical example, suppose that the five job types (labeled A through E) are
processed according to the data given in Table 2. As before, each job type enters and leaves the
loop through one of the I/O stations; that is, station 1, 3, 6, or 7. However, no job enters the loop
through station 6 while no job leaves the loop through station 7. As before, job type E represents
all "transit" jobs.
Given the above data, one may compute the job arrival rate for I/O stations 1, 3, 6, and 7,
respectively, as 1i=0.875, X3=1.000, X6=0.0, and X7=0.250 jobs per hour. Likewise, the job
departure rates are computed as 0.250, 0.750, 1.125, and 0.0 jobs per hour, respectively. Note
that while the total job arrival rate is equal to the total job departure rate, at indiviual I/O stations the
two are not equal in this example.
Using the above data we obtain af = 0.6896 and X = 12/60 = 0.20. Subsequently, using the
expressions derived earlier we obtain the following results: C1=27.1698, C3=28.8000,
C6=27.1698, and C7=27.1698 minutes per inspection. That is, stations 1, 3, 6, and 7 are
inspected at a rate of 2.2083, 2.0833, 2.2083, and 2.2083 times per hour, respectively. Since the
rate at which the vehicle inspects stations 1, 3, and 7 exceeds the rate at which loads arrive at these
stations, we conclude that the system would meet the required throughput. (The Ci and qi values
obtained for this problem were numerically verified using 99% confidence intervals obtained from
the simulation model. The results are shown in Appendix 3.)
The fourth and last numerical example is similar to the previous one except for job type E
which still enters the loop through station 3 but departs through station 7 (instead of station 6). All
the other routing information and the production rates remain the same as they were initially shown
in Table 2.
The following Ci values can be computed for the fourth problem: C1=27.1698, C3=28.8000,
C6=37.8947, and C7=27.1698 minutes. Since the time between inspections at each /VO station is
less than the time between load arrivals, once again we can conclude the vehicle will meet the
required throughput. (The 99% confidence intervals constructed for this problem are presented in
Appendix 4.)
17

The two problems presented above may also be used to provide further insight into empty
vehicle travel in unbalanced systems. Consider the first unbalanced problem. Using the Ci and qi
values obtained for this problem, one may compute the following empty vehicle trips that would be
observed in a time interval of, say, 1000 minutes:
vlql= 22.2232 V5q5= 18.0568
V2q2= 22.2232 v6q6= 36.8056
v3q3= 18.0568 V7q7= 32.6389
v4q4= 18.0568 vgqg= 32.6389 (5.1)
That is, 22.2232 empty vehicles would be observed between stations 1 and 2, while 18.0568
empty vehicles would be observed between stations 3 and 4, and so on.
The above results can be intuitively interpreted as follows. Consider the input rate, Xi and the
output rate, Ai given for each I/O station i (see Table 3). The third column in Table 3 shows the
difference between these two rates. If the difference is positive, then one may say that empty
vehicles are "generated" at that station. If the difference is negative, however, it indicates that
empty vehicles are "consumed" at that station. (Since the overall flow is conserved, the total of
this column would sum up to zero.)
Hence, "mandatory" empty vehicle may be interpreted as the flow of empty vehicles from
positive labeled I/O stations to negative labeled I/O stations. In our example problem, we have
0.625 empty trips per hour from station 6 to station 1, and 0.250 empty trips per hour from station
6 to station 3 and to station 7. Given the empty travel time between the above stations, it is
straightforward to compute the fraction of time the vehicle would be performing a mandatory
empty trip between a pair of VO stations.
For example, from station 6 to station 1, (0.625 trips/hr x 5 min/trip) 3.125 min/hr or
5.20833% of the time the vehicle would be performing an empty trip. Likewise, 3.33333% of the
time it would be performing an empty trip from station 6 to station 3, and 0.83333% of the time it
would be from station 6 to station 7. Furthermore, given a time interval of, say, 1000 minutes we
can compute the number of empty trips performed. From station 6 to station 1, for instance, the
vehicle would perform (0.625/60) x 1000 = 10.4167 trips in 1000 minutes.
Consequently, 9.375% of the time the vehicle would be performing "mandatory" empty travel.
Adding this value to the percentage of loaded travel yields 68.95833 + 9.37500 = 78.3333%. The
remainder of the time would then be devoted to "non-mandatory" empty travel which would be
distributed evenly between all the stations. That is, 21.66666% of the time the vehicle would
18

perform "non-mandatory" empty travel and in an interval of 1000 minutes the vehicle would make
0.216666 x 1000 / 12 = 18.0556 revolutions around the loop. Note that 18.0556 vehicles would
be observed between all adjacent stations; hence, let us label it the "base flow."
The resulting empty vehicle trips between all the stations can now be obtained by adding the
above "base flow" to "mandatory" empty travel performed. That is, using the following values
Base flow = 1-2-3-4-5-6-7-8-1 = 18.0556
6tol = 6-7-8-1 = 10.4167
6 to 3 = 6-7-8-1-2-3 = 4.1667
6 to 7 = 6-7 = 4.1667, (5.2)
we can compute the empty travel between any pair of stations. For example, from station 7 to
station 8 one would observe 32.6390 empty trips in a 1000 minute interval. Adding the
appropriate numbers for each pair yields the same result shown earlier by equation (5.1). (Some
minor numerical differences exist due to round-off errors.)
A similar interpretation may be constructed for the second unbalanced problem where two
positive labeled stations (6 and 7) "supply" two negative labeled stations (1 and 3) with empty
vehicles. The amount of empty vehicle flow from a positive labeled station to a negative labeled
station is proportional to the rate at -which empty vehicles are generated and consumed at each
station.
In addition to the empty trips predicted above, the analytical model was numerically tested (via
simulation) for those cases where the throughput demand placed on the vehicle exceeds its
capacity. In such cases the analytical model not only correctly predicts that the throughput
requirement is too high but it also indicates which I/O stations would start to "back up." This is
possible because the analytical model allows one to compare the cycle time obtained for each I/O
station with the interarrival time to that station. Hence, those I/O stations that exceed the vehicle
capacity can be quickly identified.
6. Conclusions and Future Work
The tandem configuration for AGV systems is a promising concept. It derives much of its
strength from the simplicity of the resulting system and the additional flexibility it offers.
However, as remarked earlier, the tandem configuration has some limitations and further work is
necessary to compare it to traditional systems from a cost and performance standpoint.
19

The analytical model developed in this study for a single vehicle loop is easy to implement and
straightforward to use. Its primary purpose is to determine whether the vehicle will meet the
required throughput imposed by a given set of P/D station locations and flow requirements. One
can also use the model to measure the impact of: using a bi-directional vehicle, adding new stations
or deleting some of the existing ones, changing the location of the stations around the loop, and
changing the flow values (either in magnitude or in terms of the production routing.)
As part of our current research effort, we are using the results from the analytical model to
develop a partitioning heuristic that would enable one to construct single vehicle loops from a given
set of P/D station locations. Subsequently, using a simulation model, we intend to compare
tandem configurations with their traditional counterparts.
20

7. References
1. Apple, J., Personal Communication, 1988.
2. Bartholdi, J. J., II and L. K. Platzman, "Decentralized Control of a Fixed Route Automatic
Guided Vehicle System," TR-85-05, Material Handling Research Center, Georgia Institute of
Technology, Atlanta, GA, February 6, 1985.
3. Egbelu, P. and J. M. A. Tanchoco, "Characterization of Automatic Guided Vehicle
Dispatching Rules," The International Journal of Production Research, Vol. 22, No. 3, pp.
359-374.
4. Gould, L., "Automated Docks, AGVs Drive 99.9% Delivery Accuracy," Modern Materials
Handling, Vol. 43, No. 1, pp. 72-75, 1988.
5. Hodgson, T. J., R. E. King, S. K. Monteith, and S. R. Schultz, "Developing Control Rules
for an AGV using Markov Decision Processes," to appear in Material Flow.
6. King, R. E., T. J. Hodgson, and S. K. Monteith, "Extracting Heuristic Control Rules for
AGV's Using Markov Decision Processes, Unpublished Working Paper, Department of
Industrial Engineering, North Carolina State University, Raleigh, NC.
7. Koff, G. A., "Automatic Guided Vehicle Systems: Applications, Controls and Planning,"
Material Flow, Vol. 4, 1987, pp. 3-16.
8. Lindsay, B., "Warehouse Business Systems and 60 AGVs Track and Route Products at
Kodak," Industrial Engineering, Vol. 20, No. 5, pp. 50-54, 1988.
9. Maxwell, W. L. and J. A. Muckstadt, "Design of Automatic Guided Vehicle Systems," lIE
Transactions, Vol. 14, No. 2, 1982, pp. 114-124.
10. Newton, D., "Simulation Model Helps Determine How Many Automated Guided Vehicles
Are Needed," Industrial Engineering, Vol. 17, No. 2, 1985, pp. 68-78.
11. Schwind, G. F., "AGV's: Creative Solutions Go Looking for Problems," Materials
Handling Engineering, Vol. 43, No. 9, pp. 44-47, 1988.
12. Stone, H. S. and Fuller, S. H., "On the Near Optimality of the Shortest-Latency-Time-First
Drum Scheduling Discipline," Communications of the ACM, Vol. 16, No. 6, pp. 352-353,
1973.
13. Takagi, H., "Queueing Analysis of Polling Models," ACM Computing Surveys, Vol. 20,
No. 1, pp. 5-28, 1988.
14. Considerations for Planning and Installing Automatic Guided Vehicle Systems, Prepared by
the AGVS section of the Material Handling Institute, Document #101, 1980.
21

Table 1. Hourly production rates and routing data
first balanced problem
by job type for the
Job Type
A
B'
C
D
E
Routing
1-5-8-2-3
1-4-8-5-7
6-2-6
3-8-5-4-2-1
7-1
Jobs/Hour
0.375
0.500
0.250
0.375
0.500
2.000
TOTAL
Table 2. Hourly production rates and routing data
first unbalanced problem
by job type for the
Job Type
A
B
C
D
E
Routing
3-5-8-2-3
1-4-8-5-6
7-2-1
1-8-5-4-2-3
3-6
Jobs/Hour
0.375
0.500
0.250
0.375
0.625
2.125
TOTAL
Table 3. Hourly
input and output rates at I/O
first unbalanced problem
stations for the
/O Station
1
3
6
7
TOTAL
A
0.875
1.000
0.000
0.250
2.125
0.250
0.750
1.125
0.000
2.125
A-A
- 0.625
- 0.250
+ 1.125
- 0.250
0.000
22

APPENDIX
The confidence intervals shown below for each problem were obtained through a simulation
code. Ten replications were made for each problem. Starting with an empty system and an empty
vehicle, each replication was "warmed-up" for 4,000 loaded vehicle trips followed by 36,000
loaded vehicle trips for data collection.
Appendix 1: First balanced problem
Theoretical
value
Theoretical
value
99% CI
99% CI
C1 [26.6247,27.0774]
C3 [34.1668,34.7864]
C6 [36.8204,37.6669]
C7 [31.9501,32.7219]
27.0420
34.9091 *
37.6471
32.5423
ql [0.6075,0.6144]
q2 [0.5724,0.5815]
q3 [0.7790,0.7876]
q4 [0.6072,0.6164]
q5 [0.5191,0.5285]
q6 [0.8389,0.8468]
q7 [0.7267,0.7346]
q8 [0.5164,0.5290]
0.6056
0.5733
0.7818
0.6056*
0.5181*
0.8431
0.7288
0.5181
Appendix 2: Second balanced problem
Theoretical
value
Theoretical
value
99% CI
99% CI
C1 [38.4381,38.8371]
C3 [56.3814,57.2972]
C6 [63.8279,65.6286]
C7 [50.6890,51.5472]
38.7879
57.3130*
65.0847
51.2000
ql [0.4341,0.4417]
q2 [0.4012,0.4076]
q3 [0.6345,0.6517]
q4 [0.4347,0.4455]
q5 [0.3470,0.3594]
q6 [0.7223,0.7333]
q7 [0.5698,0.5850]
q8 [0.3476,0.3580]
0.4343
0.4019
0.6480
0.4343*
0.3496
0.7288
0.5733
0.3496
23

Appendix 3: First unbalanced problem
Theoretical
value
Theoretical
value
99% CI
99% CI
C1 [26.7828,27.7038]
C3 [28.4582,29.3926]
C6 [26.8057,27.7293]
C7 [26.8057,27.7293]
27.1698
28.8000
27.1698
27.1698
ql [0.5918,0.6098]
q2 [0.5586,0.5786]
q3 [0.5120,0.5296]
q4 [0.5406,0.5626]
q5 [0.4512,0.4760]
q6 [1.0000,1.0000]
q7 [0.8827,0.8897]
q8 [0.6013,0.6169]
0.6038
0.5714
0.5200
0.5532
0.4643
1.0000
0.8868
0.6104
Appendix 4: Second unbalanced problem
Theoretical
value
Theoretical
value
99% CI
99% CI
C1 [26.9851,27.8589]
C3 [28.5142,29.6000]
C6 [37.4455,38.9853]
C7 [26.9424,27.8734]
27.1698
28.8000
37.8947
27.1698
qi [0.5894,0.6102]
q2 [0.5567,0.5769]
q3 [0.5101,0.5241]
q4 [0.5369,0.5583]
q5 [0.4474,0.4698]
q6 [1.0000,1.0000]
q7 [0.8818,0.8890]
q8 [0.5978,0.6148]
0.6038
0.5714
0.5200
0.5532
0.4643
1.0000
0.8868
0.6104
24

rmO rrn
S)
EmEEOm
Skh
r
A
Ii'
E rl l
J
0
6.4
A
k<
V
J
Em Em Em Em
Em Em [EQ m
0
Figure 1:
Traditional AGV System
0
0rllI
0r r
Emm - %
Er-1 c rO r
0
mT1 m
r
U
_ 4
0
0
0
Figure 2:
Tandem AGV System
25

1
8
7
2
6
3
5
Figure 3:
Layout for example problem
26