The Shuttle Dispatch Problem with Compound Poisson Arrivals: Controls at Two Terminals Hyo-Seong Lee M. M. Srinirasan Department of Industrial and Operations Engineering The University of Michigan, Ann Arbor 48109-2117 Technical Report 88-6 June 1988

Abstract We consider the control of an infinite capacity shuttle which transports passengers between two terminals. The passengers arrive at each terminal according to a compound Poisson process and the travel time from one terminal to the other one is a random variable following an arbitrary distribution. The following control limit policy is considered: dispatch the shuttle at terminal i, at the instant that the total number of passengers waiting at terminal i reaches or exceeds a predetermined control limit mi. The objective of this paper is to obtain the mean waiting time of an arbitrary passenger at each terminal for given control values mi and m2. We also discuss a search procedure to obtain the optimal control values which minimize the total expected cost per unit time under a linear cost structure.

L Introduction We consider a transportation system in which a single shuttle transports passengers between two terminals. All passengers who arrive at a given terminal are to be transported to the other terminal. We will term the passengers who arrive at terminal i as type i passengers. We assume that type i passengers arrive at terminal i according to an independent compound Poisson process with rate hi (i=1,2). The batch size of each arrival of type i passengers is an independent random variable Xi>l, following an arbitrary discrete distribution. The interterminal travel time from terminal i to the other terminal is a random variable Di having an arbitrary distribution, which is assumed to be independent of the number of passengers carried by the shuttle. We assume that the time needed to board the shuttle is negligible. The capacity of the shuttle is assumed to be infinite so that all the waiting passengers at the terminal can be carried all at once. For this transportation system (see figure 1), we consider the following operating policy, which is usually termed as a control limit policy: dispatch the shuttle at terminal i at the instant that the total number of passengers waiting at terminal i reaches or has exceeded a predetermined threshold value mi (i=1,2); if the number of waiting passengers is equal to or greater than mi when the shuttle arrives at terminal i, the shuttle immediately leaves terminal i for the other terminal. On the other hand, if the number of passengers at terminal i at that time is below mi, the shuttle is held until the number of waiting passengers reaches or exceeds mi. The objective of this paper is to obtain an expression 1

for the mean waiting time of the passengers at each terminal under a given control limit policy. D terminal 1 terminal 2,lXl r2,X2 control limit: mI D control limit: m2 2 Fig. 1. Dispatching of a shuttle with controls at two terminals. A considerable amount of work has been done on the shuttle dispatching problem with one or two terminals. Comprehensive surveys on this problem can be found in the papers by Sim and Templeton(1983) and Teghem(1986). For a single terminal dispatching problem with Poisson arrivals, Weiss(1979) developed an algorithm to find the optimal control value under a linear cost structure assuming that the capacity of the shuttle is infinite. Deb and Serfozo(1973) proved that a control limit policy is an optimal operating policy under a linear cost structure for the case of a single terminal with finite shuttle capacity. Recently, Powell(1985,1986) studied more general strategies for dispatching a shuttle which includes both holding and cancellation strategies. Under an assumption of compound Poisson arrivals, he developed an algorithm to find the mean waiting time of an arbitrary passenger for a given policy. For the shuttle dispatching problem with two terminals, Ignall and Kolesar(1974) and Weiss(1981) studied infinite capacity shuttle dispatching problems assuming that the dispatcher can hold the shuttle for more 2

passengers at only one of the terminals. In their paper, Ignall and Kolesar proved that the optimal policy is to dispatch the carrier if and only if the total number of passengers waiting at both terminals is greater than a threshold value. However, since a shuttle is held only at one terminal, this problem is relatively simple compared to the problem with controls at two terminals. For a shuttle dispatching problem with controls at two terminals, Deb(1978) presented a significant result on the characteristics of the optimal dispatching policy. Under a linear cost structure, he proved that the optimal policy which minimizes the expected total discounted cost over an infinite time horizon has the following form: suppose the shuttle is at one of the terminals with x passengers waiting there and y passengers waiting at the other terminal. Then the optimal policy is to dispatch the shuttle if, and only if, x>G(y), where G(.) is a monotone decreasing control function. Unfortunately, however, the explicit determination of the function G(.) is still not known. Although our operating policy appears to be similar to the policy described by Deb, there is a fundumental difference between our model and Deb's model as explained below: First, our model assumes that arrival of the passengers follows a compound Poisson process and the capacity of the shuttle is infinite while Deb's model assumes that passengers arrive according to a Poisson process and the capacity of the shuttle is finite. Second, in Deb's model, it is assumed that the number of passengers at both terminals is always known, so that the information at both terminals is used to decide whether the shuttle is dispatched or not. Although this 3

assumption gives a natural structure for the dynamic programming modeling, in many cases, the information on the number of passengers at one terminal is not available at the other terminal. In our study, we assume that the number of passengers at a terminal is known only when the shuttle is present at that terminal. Consequently, in our model, only the number of passengers who are waiting at the terminal where the shuttle is present is used to decide whether the shuttle is dispatched to the other terminal or not. Although we use the information only at one terminal in deciding whether the shuttle is dispatched or not, the number of passengers at the other terminal must be implicitly considered in the analysis because the sojourn time of the shuttle at one terminal affects the sojourn time of the shuttle at the other terminal. Due to this consideration, the analysis becomes fairly complicated. One approach to solve the shuttle dispatching problem is to use a semi-Markov decision process. Although this approach has been quite successful in proving the optimality of the control limit policies in some cases(Deb and Serfozo 1973, Deb 1978), it usually needs considerable computational effort. In addition, the Markov decision process approach does not provide some important performance statistics such as the mean waiting time for each type of passenger. Since our objective in this study is to obtain the mean waiting time for each type of passengers, hence in order to solve the problem with controls at two terminals, we adopt a different approach as follows. We decompose the system into two individual terminals and then a t analyze each individual terminal separately as a single terminal shuttle dispatching problem. Thus, in order to solve the problem with two terminals, we must first be able to solve a single terminal 4

dispatching problem. Although the algorithms developed by Powell(1985,1986) solve a very general single terminal problem, for the infinite capacity shuttle dispatching problem described below, the procedure presented in the next section is much more efficient. 2. The single terminal dispatching problem We consider here a shuttle which services passengers who arrive at a single terminal. Passengers arrive at this terminal according to a compound Poisson process with rate X. The batch size of each arriving passenger is a random variable X21, following an arbitrary distribution. To operate the system, we use the following control limit policy: when the shuttle is at the terminal and the number of passengers waiting there is less than the predetermined control limit m, the shuttle waits at the terminal until the total number of waiting passengers reaches or exceeds m. As soon as the number of waiting passengers reaches or exceeds m, the shuttle leaves the terminal to transport the passengers to their destination and then returns to the terminal after a random amount of time V, which we shall call the intervisit time. If the number of passengers waiting at the terminal is equal to or greater than m at the instant the shuttle comes back to the terminal, it leaves the terminal immediately carrying all the waiting passengers. On the other hand, if the shuttle finds less than m passengers, it waits at the terminal until the number of waiting passengers reaches or exceeds m. 5

2.L Notation For analytical convenience, for any discrete random variable (r.v.), A, that is used in the analysis, we adopt the following notation throughout the paper: ai = P{A=i), 00 A(z) = Xai zi, the probability generating function (p.g.f.) of A, i=O a(l) = E(A), a(2) = E(A(A-1)). Let Q = number of batches that arrive during an intervisit time V, r.v., R = number of passengers that arrive during V, r.v., I = total number of passengers at the terminal when the shuttle leaves the terminal, r.v., Jn =number of passengers who arrive during the sojourn time of the shuttle at the terminal if the number of passengers at the shuttle arrival instant is m-n, 0 < n < m, r.v., *(i) xj = P{i-fold convolution of X is j}, L = mean queue length of the waiting passengers at the terminal, W = mean waiting time of an arbitrary passenger at the terminal. 2.2. The Analysis It is shown in Lee and Srinivasan(1987) that if we know the first two moments of I, which is the number of passengers when the shuttle leaves the terminal, the mean waiting time of an arbitrary passenger experienced at the terminal can be obtained as follows: 6

1 i(2) X(2) / ) ( w= ( ix') /x (2.1) To obtain the first two moments of I, however, we must know both rj, which is the probability that j passengers arrive during the intervisit time for j=O,...,m-1, and the first two moments of R. Suppose we know the values of qi. Then, rj can be obtained by J *(i) rj = xj, j=0,1,2,.., (2.2) i=O *(0) where xo =1. To obtain the qi values, note that by definition, 00 qi= e-t dV(t). (2.3) 51! 0 However, for the computation of qi, we use the following equivalent expression: (q'=-iV*(i)(X), (2.4) where V*(i)(0) is the ith derivative of the Laplace Stieltjes Transform (LST) of V with respect to 0. The moments of R are obtained by using the following result, stated as lemma 2.1. Since lemma 2.1 can be easily proved, we omit the proof here. Lemma 2.1. The probability generating function of R is given by R(z) = V*(X-X(z)). (2.5) From equation (2.5), we can obtain the first and second factorial moments of R as r(l) = E(R) = XE(V)x(1), (2.6.a) 7

r(2) = E(R(R-1)) = (Xx(1))2E(V2) + Xx(2)E(V). (2.6.b) We can now obtain an expression for the probability generating function of I from the following result, stated as theorem 2.1. Theorem 2.1 m-1 I(z) = R(z) + rjzi{Jm.j(z) - 1}, (2.7) j=0 where n-I Jn(z) =X(z) + xjzJ{Jn-j(z) - 1). j=l (2.8) Proof By conditioning on the number of passengers who arrive during an intervisit time, we can obtain a recursive equation that yields P{I=k} as m-1 P{I=k} = rk + rjJm-j = k-j}, j=O k-m. (2.9) From equation (2.9), the probability generating function of I can be obtained as 00 I(z) = E P{I=k}zk k=m oo m-1 oo = Z rkzk + rj zi P{Jm-j=k-j}zkj k=m j=O k=m oo m-1 = Z rkzk + rj z Jm.j(z) k=m j=O m-1 = R(z)+ rj z{Jm-j(z) - 1}. j=O (2.10) The term Jn(z), which is used in equation (2.10), can be obtained as follows. Note that, since the number of passengers is m-n when the shuttle arrives at the terminal, the shuttle must stay at the terminal until at least n more 8

passengers arrive. By conditioning on the number of passengers who arrive in the first batch, we can obtain a recursive equation for P{Jn =k} as n-1 P{Jn=k} = I xjP{Jn.j=k-j} + xk, k>n. (2.11) j=1 From (2.11), the p.g.f. of Jn is expressed by oo ~oo n-1 Jn(z)= P{Jn=k)zk = E { E XjP{Jn.j-j=k+xk}zk k=n k=n j=1 n-1 oo o = ~ xjJ P{Jnj=k-j}zk-j+ XkZk j=1 k=n k=n n-1 = ] XjzJ{Jn-j(z)-l}+X(z). (2.12) j=1 From I(z), we can obtain the first and second factorial moments of I as m-1 i() = E(I) = r(l) + rjjm.j, (2.13.a) j=0 m-1 i(2) = E(I(I-1)) = r(2) + Xrj (2jj + (2j), (2.13.b) Jm-j + Jm-j), (2.13.b) j=o.(1) (2) where Jn and jn are obtained from equation (2.8) as n-1 jn = x(1)+ E Xjn, (2.14.a) j=1 n-1 Jn (2() (2) ++ n-j (2.14.b) j=1 By substituting i(l) and i(2) obtained in (2.13) into (2.1), we can find the mean waiting time experienced by an arbitrary passenger at the terminal. 9

3. Analysis for a problem with two terminals 3.1 General Approach Now using the result obtained for the shuttle dispatching problem with a single terminal, we will analyze the problem with two terminals. As shown in section 2, the mean waiting time of an arbitrary passenger at a terminal can be obtained if we know the first two moments for the number of passengers at the terminal at the instant that the shuttle leaves the terminal. It was also observed that in order to obtain these two moments, we must know the probabilities for the number of passengers (from 0 to mi1) present at the terminal when the shuttle arrives at the terminal as well as the first two moments of the number of these passengers. In case of a shuttle dispatching problem with two terminals, however, these values cannot be obtained easily because the sojourn time of the shuttle at one terminal and the travel time from that terminal to the other one affect the sojourn time of the shuttle at the other terminal. To obtain the probabilities for the number of passengers (from 0 to mi1) present at the terminal at the shuttle arrival instant, we will restrict our attention to the following four types of epochs on the path of the shuttle. Let the instant that the shuttle arrives at terminal 1 be an epoch of type 1 and the instant that the shuttle leaves terminal 1 be an epoch of type 2. Similarly, let the instant that the shuttle arrives at terminal 2 be an epoch of type 3 and the instant that the shuttle leaves terminal 2 be an epoch of type 4. Henceforth, we choose to call an epoch of type i as epoch i. Thus, the shuttle moves on from epoch 1 to epoch 4 via epochs 2 and 3, and comes back to epoch 1. At this point, the next cycle is initiated. Note that we must find 10

the steady state probabilities for the number of passengers (from 0 to mi-1) at epochs 1 and 3. However, for this purpose, we will use epochs 2 and 4 instead of epochs 1 and 3 because by doing so we can reduce the number of states, and hence the computational effort significantly. This advantage comes from the observation that the number of type 1 passengers at epoch 2 and the number of type 2 passengers at epoch 4 are always zero. Once we obtain the steady state probabilities for the queue lengths (from 0 to mi-1) at epochs 2 and 4, we can easily obtain the steady state probabilities for the queue lengths (from 0 to mi-1) at epochs 1 and 3. Define the states at epochs 1 and 4 to be k if the number of type 1 passengers is k for k<ml. If the number of type 1 passengers at these epochs is equal to or greater than ml, the state is defined to be mi. Similarly, define the states at epochs 2 and 3 to be k if the number of type 2 passengers at these epochs is k for k<m2. If the number of type 2 passengers is equal to or greater than m2, the state is defined to be m2. Thus, the state space at epochs 1 and 4 is {0,1,...,ml} and the state space at epochs 2 and 3 is {0,1,...m2}. Let us define Is to be the state at epoch s at the tth cycle and define qs(ij) to be t+1 t ql(ij)=PIt jI i), (3.1.a) q2(ij)=PI = j I14 = i}, (3.1.b) t t q3(ij)=P{I3= j I 2 = i), (3.1.c) q4(ij)=P{I4 = j I2 = i). (3.1.d) 11

So, for instance, q4(ij) represents a transition probability that the state at epoch 4 will be j given that the state at epoch 2 is i. Let p2(ij) to be the transition probability, P{I1 = j I I2 = i) and let p4(ij) be the transition probability, P{I4 = j i 14 = i. Then, these probabilities can be obtained from the following equations: P2(ij) = q4(i,k)q2(kj), (3.2.a) k=O m2 P4(iJ) = ~ q2(i,k)q4(kj). (3.2.b) k=0 To represent these equations in a more compact form, we define matrices Qs and Ps such that Qs = ( q(ij)) for s=1 to 4, Ps = (ps(i) ) for s=2 and 4. Then, equation (3.2) can be represented by P2 = Q4Q2, (3.3.a) P4 = Q2Q4. (3.3.b) Suppose we know the matrices Qs for s=1 to 4. Then, we can find matrices P2 and P4 from equation (3.3). Let nik be the steady state probability that the state at epoch i is k and let li be vectors such that i=(o^ic0,,il,...im1) for i=1 and 4, 7i=(7iioil,*...*im2) for i=2 and 3. Since matrices P2 and P4 are ergodic, using the transition probabilities p2(ij) and p4(ij) obtained from (3.3), we can compute Cik for i=2 and 4 by solving the following equations: 12

Ti = tiPi, ei = 1, for i=2,4. (3.4) Recall that we want to find the steady state probabilities n, and 73 using n2o and N4, which can be easily done from 7^ = 14Q1, (3.5.a) 73 = 7t2Q3. (3.5.b) Thus, if we know Qk for k=1 to 4, then 72 and n74 can be obtained from Q2 and Q4, and given n2, N4, Q1 and Q3, then nl and 73 can be obtained. Once nl and 7;3 are obtained, we can also compute the first two moments of the intervisit times, which yield the first two moments of the number of passengers at the shuttle arrival instant. With all this information, we can finally compute the mean waiting time for each type of passenger for given values of ml and m2. Each of these steps will be described below in detail. 3.2. Notation The notation used for a discrete random variable in section 2 will continue to be used in this section. In addition to that, in this section, for any continuous random variable C used in the analysis, C*(.) will denote the LST of C. We define Ii = total number of passengers at terminal i when the shuttle leaves terminal i, r.v., Vi = intervisit time of the shuttle for terminal i in steady state, r.v., Ui = sojourn time of the shuttle at terminal i in steady state, r.v., Uin = sojourn time of the shuttle at terminal i given that the state was mi-n at the time the shuttle arrives to terminal i (i=1,2), r.v., 13

S1 = D1 + U2, r.v., S2 = D2 + U1, r.v., *(k) xij( ) = P{k-fold convolution of Xi is j}, Wi = mean waiting time of an arbitrary passenger of type i. 3.3. The Analysis In this section, we will derive an expression for Wi, the mean waiting time for an arbitrary passenger of type i. As described in section 3.1, to obtain Wi, the transition matrices Qk for k=l to 4 must be computed. While the matrices Qi and Q3 can be easily obtained, the matrices Q2 and Q4 are not easy to obtain because of the interrelationships among the random variables. We now describe how the matrix Q4, namely, each value of q4(ij), can be computed. We will not show how the matrix Q2 is obtained because it can be computed in exactly the same way as Q4 is computed. Note that q4(ij) can be obtained if we can compute the probabilities for the number of type 1 passengers that arrive during S1 given that the state at epoch 2 was i. To obtain this, let us define a random variable S,ij such that P{Sl,i < t} = P{S1 < t I the state at epoch 2 was i}. Since the probability for the number of type 1 passengers that arrive during Si can be obtained if we know the LST of Sij, we will first find an expression for the LST of Sl,i. To this end, we define gin and a new random variable Dl,n as follows: gin = P{number of batches of type 2 which arrive during D1 is n}, P{Dl,n<t) = P{D1< t I n batches of type 2 have arrived during D1). 14

Then, by conditioning on the number of individual passengers of type 2 which arrive during D1, we can express the LST of Sli as m2-i-l m2-i-1 m2-i0 gin n, n*n ) *(n * S,i(0)= gln=[ E x2j {Dl,n(0)U2,m2-(i+j)()}+(l- xjn )Dn(0)] n=O j=n j=n m2-i-1 + (Di(e)- ginD,( ) (3.6) n=0 The explanation of equation (3.6) is as follows: Suppose the number of batches which arrive during D1 is n. Note that this happens with probability gin and the LST of the travel time D1 in this case is * D1, n(). Since the state at epoch 2 is given as i, if n is greater than, or equal to, m2-i, the number of type 2 passengers at epoch 3 will reach or exceed the control limit m2 and hence there will be no sojourn time for the shuttle at terminal 2. This is represented by the second line in equation (3.6). Similarly, suppose the number of batches which arrive during D1 is less than m2-i, i.e., n<m2-i. In this case, if the number of individual passengers, j, who belong to these n batches is less than m2-i-1, the number of passengers of type 2 at epoch 3 will be i+j, and the shuttle must stay at terminal 2 for U2,m2-(i+j). On the other hand, if j is equal to or greater than m2-i-1, since the state at epoch 3 will be m2, the shuttle will not be delayed at terminal 2, which is represented by the first line in equation (3.6). From equation (3.6), we see that S1,i(0) can be obtained if we can compute D and Un( We now eplain how these terms can be compute D1 n(9) and uo n(9). We now explain how these terms can be 15

computed. The following results, stated as lemma 3.1 and theorem 3.1 yield ) and U2,n() respectively. Din(O) and U2,n(9) respectively. Lemma 3.1 The LST of D1,n is expressed by *(n) D * (-X2)" *(n) D1 (e+X2) D1,n(0)= Dl n)(0-, —Dn(O) =glnn! 1 (* (n) D1 (2) (3.7) Proof Let d1(t) be a p.d.f. of D1 and d1n(t) be a p.d.f. of D1,n. By applying Bayes' formula, we can obtain the p.d.f. of Dl,n as 1 e-X2t (X2t)n dln(t) gln n! d1(t). (3.8) 00 From equation (3.8) and using that D1 (0) = J(-t)n e-td(t) dt, the LST of D1,n is expressed by 00 D* n =J00 dCt =(-X2)n * (n) D!,n() = e-st dln(t) dt = glnn! D1 (+X?2). (3.9) Since g n = (-,2)n * (n) n!- D 1 (X2), by substituting this into equation (3.9), we obtain lemma 3.1. Theorem 3.1 * Ui n(0) is expressed recursively as ** * *i Ui n() = Bi(0) xijUi,n-j(0) - 1) +Bi (). j=1. (3.10) 16

* xi where Bi (0) = Proof Let Yi n be the number of batch arrivals of type i during the sojourn time of the shuttle at terminal i given that the state is mi-n at the instant the shuttle arrives at terminal i. Then, P{Yi,n=k) can be expressed by 00 P{Yi,n=k} = xij fork=l, j=n n-1 = ~ xijP{Yi,n-j=k-1} for k>l. (3.11) j=1 Consequently, the p.g.f. of Yi,n can be expressed by oo n n-1 Yi,n(z)= xijz + xij P{Yi,n-j=k-l}zk j=n k=2j=1 oo n-1 n = xijz + xijz ~ PYin-j=k-l}zk-l j=n j=1 k=2 oo n-1 Sxijz + xijzYi,n-j(z) j=n j=l n-1 = z xij{Yi,n-j(z) - 1} +z. (3.12) j=1 Let Bi be a random variable denoting the interarrival time of type i batch arrivals. Since Bi is assumed to follow an exponential distribution with mean 1 -, the LST of Bi is expressed by * Bi)= f ii i=1,2. (3.13) The result now follows by substituting Bi (8) in place of z in equation (3.12). 17

Since we have an expression for S i(O), we can now obtain q4(ij). Let hiin denote the probability that the number of batches of type 1 which arrive during Sl,i is n. Then, in the same manner in which qi was computed in equation (2.4), hlin can be computed from (for n=O,...,ml-j-l), (-Xi)n *(n) hlin = n! i (xi), *(k (3.14) *(k) where Sli (X1) can be obtained as follows: By taking the kth derivative on both sides of equation (3.6) and setting 0=X1, we have m2-i-l Sli (1)= I gln n=O m2-i-l k [(n, (k) *(r j=n r=O *(k-r) 2 m2-(i+j) m2-i-1 +(1- E j )n j=n D*(k) x)] Din l + {(qI*(k) + OII (Xi) m2-i-1 gln n=O *(k)(x) 4n t,) (3.15) where D*(k) Din (Xl) can be obtained from equation (3.7) as ln *(n+k)Xl +X2) D1 (A,+A2) *(k). Xn,,(l) (3.16) D*(n2) 1 (X2) *(k) and U2n (Xi) is obtained from equation (3.10) as n-1 *2(k) j U2n (X1)= j=l k X2j{~ (k) r=Or *(r) ( * (k-r) )} t 1 U2 n-j [ 1 n-1.,*(k)/~ +(1- x2j) B (Xil). j=l (3.17) 18

Since we know hlin, we can finally obtain q4(ij) as *(k) q4(ij)= hlik j, i=0,...m2, j=O,...,ml-l, k=O ml-1 q4(i,ml)=1- q4(iJ), i=O......m2. (3.18) j=0 We have now computed the transition matrix Q4. Since Q2 can be computed in the same way as Q4, we can obtain P2 and P4 using equation (3.3), and then, t2 and;4 using equation (3.4). We are now in a position to find 1n and n3, and from them, W1 and W2. Since n2 and W2 can be obtained in the same way as tn and W1, we will only present how n1 and W1 can be computed. As shown in equation (3.5), to compute i1, we need to know Q1, namely, each value of ql(ij). Let fij be the probability that the number of individual passengers of type 1 who arrive during D2 is j. Then, ql(ij), can be computed as ql(i) = 0 ifj<i = fi j-i if iLj, j<m1 ml-i-1 =1- k f k if ij, j=m1. (3.19) k=0 Since Qi1 has now been obtained, by applying equation (3.5), we can obtain t1. Once it1 has been obtained, the only other information needed to obtain.(1) (2) i( and i) are the first two moments of the number of type 1 passengers at epoch 1. Note that these values can be obtained from equation (2.6) if we know the first two moments of the intervisit time, V1. The first two moments of V1 can be easily obtained because V1 = S1+D2 and S1 and D2 are independent. The independence holds here because in this vacation, D2 19

follows S1. (Note, however, that D2 affects the realization of the S1 which follows D2.) Thus, we have E(V1) = E(S1) + E(D2), (3.20.a) E(V2) = E(S2) + 2E(S1)E(D2) + E(D2). (3.20.b) Since E(D2) and E(D2) are given values, in order to obtain E(V1) and E(V1), 2 we should determine E(S1) and E(S1). This is done as described below. Since t2k is the steady state probability that the state at epoch 2 is k, the LST of S1 is expressed by 2 * (3.21) S1(0) = 2kSl,Ik(0). (3.21) k=O By differentiating S1 () with respect to 0, we obtain m2 *(1) E(S1) =- Z n2kSlk (0), (3.22.a) k=0 2 m2 *(2) E(Sp) = 2kS kS (0), (3.22.b) k=0 *(1) *(2) where Si(k (0) and S1k (0) can be obtained using equation (3.15). Since we now know the first two moments of the intervisit time as well as (1) (2) nlk for k=0,...,m1-l, we can calculate i1 and i1 using the procedure presented in section 2, and hence, can obtain Wi using equation (2.1). Finally, let us analyze the expected length of a cycle when mi and m2 are used as control limits. Obviously, the expected length of a cycle, X, can be obtained by x = E(V1) + E(U1) = E(V2) + E(U2). (3.23) 20

However, since the expected number of type i passengers who arrive during.(1) (1) one cycle is ii and the arrival rate is ix(, we can obtain the expected length of a cycle more simply from.(1).(1) 11 12 %= (1)= (1) (3.24) Xlxl X2x2 4. The Optimization Procedure The motivation for the analysis in this paper comes from studies of the optimal control policies when a cost structure is imposed on our twoterminal shuttle system. Suppose a linear holding cost of ci per unit time is incurred for each passenger of type i (i=1,2) who waits at terminal i and a cost Cs is incurred each time the shuttle leaves a terminal and returns, again, to that terminal. Since the expected length of a cycle is X, the Cs expected operating cost for the shuttle per unit time is expressed as -. X Similarly, from Little's rule, the mean number of passengers of type i waiting at terminal i at an arbitrary time is Xixj Wi. Thus, the expected waiting cost per unit time is ciix W1 + 2 (22 W2. From this, the expected total cost per unit time, C, is calculated as (1) 2lxl cs _X__ CS(1) C = (1) + clXlx )W1 + c2X2x2 W2. (4.1) 1i This expression enables us to search for the optimal control values which minimize the expected cost per unit time in the long run. 21

Due to the complex form of the equations, we could not prove any properties (such as convexity) for the cost function which could be useful in the search procedure. However, our computational experience suggests that for a fixed value of one control variable, the cost function is unimodal with respect to the other control variable. If we make use of this observation and the recursive nature of the functions, we can find the optimal control values with reasonable computational effort. In particular, we observed that, for a symmetric system(in the sense that two queues are same in every respect), the cost function shows a unimodality with respect to the control value mi. The following example illustrates this: <example> X1=X2=0.2, Xll=X21=0.4, x12=x22=0.3, x13=x23=0.3, D1=D2=10, with probability 1, Cs=500, cl=C2=1. The results of the policy comparisons for the example are presented in table 1. In the table, the values of %, Wi and C are shown for each value of mi. Note that in this example, C, which is the expected total cost incurred per unit time, shows a unimodality with respect to mi as was stated. 22

Table 1. Result of the Example mi X Wi C 11 36.105 14.307 24.722 12 38.597 15.083 24418 13 41.129 15.874 24.222 14 43.687 16.676 24119 15 46.264 17.484 24.095 16 48.855 18.297 24.140 17 51.455 19.113 24243 18 54.062 19.931 24.397 19 56.674 20.751 24.593 (* means the optimal policy) 5. Conclusions In this paper, a control limit policy is presented for the shuttle dispatching problem with two terminals. Under the assumptions that controls are made at both terminals and the number of passengers is known only when the shuttle is staying at that terminal, a procedure to calculate the mean waiting time for each type of passenger is presented for given control values. This procedure can be directly extended to the system with more than two terminals. However, since the number of states needed to analyze the system increases with number of terminals, the procedure developed in this paper is not practicable if the number of terminals is greater than two. Thus, for this case, good approximation methods are desired to be developed. 23

References Cooper, R.B., Introduction to Queueing Theory, Second Ed., Elsevier, North-Holland, New York, (1981). Deb, R.K., "Optimal Dispatching of a Finite Capacity Shuttle," Management Science, v 24 (1978), pp. 1362-1372. Deb, R.K. and Serfozo, R.F., "Optimal Control of Batch Service Queues," Advances Appl. Probability,, v 5 (1973), pp. 340-361. Ignall, E and Kolesar, P., "Optimal Dispatching of an Infinite Capacity Shuttle: Control at a single terminal," Operations Research, v 22 (1974), pp. 1008-1025. Lee, H-S and Srinivasan, M.M., " Control Policies for the Mx/G/1 Queueing System," Technical Report 87-20 (1987), Dept. of Industrial and Operations Engr.,The Univ. of Michigan, summitted to Management Science. Powell, W.B., "Analysis of Vehicle Holding and Canellation Strategies in Bulk Arrival, Bulk Service Queues," Transportation Science, v 19 (1985), pp 352-377. Powell, W.B., "Iterative Algorithms for Bulk Arrivals, Bulk Service Queues with Poisson and non-Poisson Arrivals," Transportation Science, v 20 (1986), pp.65-79. Sim, S.H. and Templeton, J.G.C., "Computational Procedures for Steady State Characteristics of Unscheduled Multi-Carrier Shuttle Systems", European Journal of Operations Research, v 12 (1983), pp. 190-202. Teghem, J., Jr., "Control of the Service Process in a Queueing System," European Journal of Operations Research, v 23 (1986), pp. 141-158. Weiss, J., "The Computation of Optimal Control Limits for a Queue with Batch Services," Management Science v 25 (1979), pp. 320-328.,"Further Results on an Infinite Capacity Shuttle with Control at a Single Terminal," Operations Research, v 29 (1981), pp.1212-1217. 24