ABSTRACT A CONTROLLED ROUTING ALGORITHM FOR A SYNCHRONOUS SLOT HIGHWAY SYSTEM BY Michael Earl Dick Traffic congestion has become a major problem for all metropolitan areas of the world today, and complete solutions using existing highway systems are, at best, only remote possibilities. Thus, it is necessary to develop new and better systems to transport people. One such possible system is a synchronous slot highway (SSH) where vehicles are automatically positioned in slots moving (with a constant velocity) in synchronism. Previous research has centered on algorithms selecting minimum travel time routes through any network. This thesis deve10ps a controlled routing algorithm which considers both minimum and non-minimum travel time routes. The innovation of routing some users over non-minimal travel time routes is justified if this causes sufficient reduction in total user waiting time (in the entrance queues). The route decision is based on minimizing a performance index which is composed of a system (route) cost factor and a user (waiting time) cost factor. 03% Michael Earl Dick The mathematical properties of the system are analyzed with the aid of results from queueing theory. A simulation model is developed, and eXperiments are conducted assuming different vehicular arrival rates to study the effectiveness of the algorithm. Results indicate the controlled routing algorithm is most beneficial as the vehicular arrival rate and/or the average trip length is increased. A CONTROLLED ROUTING ALGORITHM FOR A SYNCHRONOUS SLOT HIGHWAY SYSTEM By Michael Earl Dick A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Electrical Engineering 197# This work is dedicated to my Father and Mother for instilling in me the desire to learn, and my wife, Sue, and our children whose sacrifices allowed the completion of this degree. ii ACKNOWLEDGEMENTS The author wishes to express his appreciation to his major professor, Dr. John B. Kreer, who devoted many hours to technical stimulation, valued encouragement, and finally the complete review of this thesis. Appreciation is also expressed to Dr. R. O. Barr, Dr. J. G. Hocking, and Dr. W. C. Taylor for serving as members of the guidance committee. Financial support was granted by Michigan State University for five terms in the form of a teaching assistantship in the Department of Electrical Engineering and Systems Science and for four terms with a research assistantship through the Division of Engineering Research. This support is gratefully acknowledged. iii TABLE OF CONTENTS Chapter I. INTRODUCTION . . . . . . . . . . II. PROPERTIES OF THE SYSTEM . . . . 2.1 TheHighway....... 2.2 Systems Controlling the SSH 2.3 The Reservation System . 2.3.1 Storing Route Descriptions 2.3.2 Allocating Capacity 2.3.3 Fitting Trips into III. MATHEMATICAL DEVELOPMENT . . . . 3.1 Queueing Characteristics 3.2 Approximations . . . . . 3.3 EXpected Waiting Time . . 3.u Projected Densities . . . 3.5 Performance Index . . . . IV. COMPUTER SIMULATION . . . . . . h.1 Development of the Model Open Slots. h.1.1 Modeling Assumptions A.1.2 The Comparative Reservation Arrangement 0 e e e e e e 0 iv Page \ouoxoxw-r: 11 16 25 28 3h 35 35 35 38 Chapter 4.2 The Network . . . . 4.2.1 4.2.2 Off-Line Storage Arrays “.3 BaSiC F1011! Charts 0 e e e o 4.4 GASP Parameters . . heSRGBultBoeeeeeeeeeee V. CONCLUSIONS AND FUTURE INVESTIGATIONS APPMDICES O O O O O C O O O O O O O O O O A. SUPPLEMENTARY DERIVATIONS B. FLOW CHARTS C. ROUTE INFORMATION . . . . BIBLIOGRAPHY . . . . . . . . . . Selection of Alternate Paths Page 39 39 1.1 1+5 #7 A9 58 6O 6O 63 85 104 Table 4.1 #.2 #.3 hoh #.5 k.6 4.7 B.1 0.1 0.2 LIST OF TABLES Encoding of destinations for trips at entrance1eeeeeeeeeeeeeeeeee Encoding of trip sections for arrivals at entrance 1 O O O O O O O O O O O O O O O O O 0 Average densities on the highway for different arrival rates and average trip length . . . . . Average number in queue for different arrival rates and average trip length . . . . . . . . . Increased travel time (c) . . . . . . . . . . . Increased waiting time multiplied by 2.5 (nc) . The difference (divided by the number of arrivals) between increased travel time (c) and 2.5 times increased waiting time (nc) . . . The average rates of occurrences and corresponding constraints for portions of a reservation list . . . . . . . . . . . . . Destinations from each origin according to lengthoftrip......o........o Pointers in array TRPT used to locate trip information...eeeeeeeeeeeeeee Section for each origin-destination pair . . . vi Page an AA 52 52 55 55 56 61 86 87 88 Figure 2.1(1) 2.1(11) 2.2(i) 2.2(11) 3.1 3.2 3.3(1) 3.3(11) 3.h 3.5(1) 3.5(11) 3.6 3.7(1) 3.7(11) 3.8(1) 3.8(11) LIST OF FIGURES Trip from e3 to B is reserved at slot e1 . . The reserved slot has progressed to BlOt 92 e e e e e e e o e e e e e e e e o e A possible configuration for a general net'ork.OOOOOOOOOOOOOOOOO The reservation list representing section 5. Typical flow-density characteristics of a conventional highway system . . . . . . . . Flow-density characteristics of an SSH . . . Segment of a simple network . . . . . . . . Location of pseudo-queues on the reservation lists a e e e e e e e e e e e e The kth pseudo-queue of a reservation list . Portions defined for reservation list with overlapping Condition 0 e e e e e e e e e e Portions defined for reservation list with gap condition 0 o e e e e e e e e e e e e e The reservation lists required for a trip from A to B O O O O O O O O O O O O O O O 0 Part of the reservation list for section 2 . A sample density curve for section 2 . . . . Part of the reservation list for section 3 . A sample density curve for section 3 . . . . vii Page 8 12 12 15 15 27 3O 3O 3O 32 32 32 32 Figure h.1 h-Z h.3 4.1; 11.5 as #.7 A.8 4.9 B.u 3.5 3.6 3.? B.8(i) 3.8(11) B.9 The Network: Two-way exterior streets with one-way interior streets . . . The destination array . . . . . . . . . . . The pointer array and corresponding trip section array . . . . . . . . . . . . . . . M8111 program flow diagram e e e e e e e e e The event subroutine . . . . . . . . . . . . Location of entrances on the section of thenetwork................ Density plots for various arrival rates and average trip length e e e e e e e e e e Plots of the average number in the queues for variations in the parameters and control.................. Plots of difference between K times expected waiting time (no) and increased travel time (c) divided by the number of arrivals . . . Flow diagram for storing trips and trip Painters O O O O O O O O O O O O O O O O O 0 Flow diagram for decoding sections of a giventripeeeeeeeeeeeeeeeee Flow diagram for storing destinations from each origin in the network . . . . . . . . . Flow diagram of subroutine ARRVL . . . . . . Flow diagram of subroutine BEST . . . . . . Progression of slots in adjacent memory words................... Availability of slots for a vehicle requesting a trip from 1 to A . . . . . . . Status of system before applying shifting algorithm 0 O O O O O 0 O O O O O 0 O O O 0 Status of system after shifting of vehicle and insertion of the scheduled trip . . . . Flow diagram of subroutine UPDATE . . . . . viii Page no #3 #3 #6 #6 A8 53 51+ 57 6A 65 66 68 70 73 73 73 73 76 CHAPTER I INTRODUCTION The traffic problem in the world today has progressed to a point where a complete solution using the existing highway systems seems improbable. The basic problem with surface streets is the bottlenecks encountered at intersections (resulting in lengthy waiting times with a very tedious start and stop procedure), while the problem with the existing freeway systems is the known relationship between flow rate and density, i.e., above a certain density km the flow rate will begin to decrease (3). This is caused by the distance drivers leave between their car and the car ahead to insure suffi- cient reaction time to any changes in the motion of the vehicle ahead. These limitations of the current systems necessitate the development of new transportation systems to handle the projected traffic flows of the future. Many types of systems are being considered and some prototype models have been developed (7, 12, 19, 25). One proposed system is a synchronous slot highway (SSH) where vehicles are automatically positioned into slots moving in synchronism with a constant velocity. The basic aim of the SSH is to increase the flow rate by reducing the effect of the car-gap relationship (existing in conventional traffic systems), making the flow rate directly proportional to the density. Previous research has centered on algorithms selecting minimum travel time routes through any vehicular network to increase efficiency (1, 5, 6, 16). This thesis develops a controlled routing algorithm which considers both minimum and non-minimum paths during SSH network busy periods. The innovation of routing some users over non-minimal travel time routes is justified if this causes sufficient reduction in total user waiting time (in the entrance queues). Thus, the objective of the routing algorithm is to increase efficiency by reducing user waiting time in the entrance queues while still maintaining a reasonable total travel time for each vehicle. Chapter 2 of the thesis discusses the Operation of an SSH system. Requests by users for a given destination are processed by a reservation system. The function of the reservation system is explained with particular attention given to the fundamental properties pertinent to this thesis. Chapter 3 contains the mathematical development of the problem. The properties of the system are studied under the general topic of queueing theory. The expected number of slots filled in any section of the network.is 3 derived and used to compute a system cost for each route. In addition, the expected waiting time for any vehicle is computed as a measure of the user cost for each route. The performance index is the sum of the system cost and the user cost for each vehicle; this performance index is the function minimized for route selection by the control algorithm. Finally, simulation results are given for a sample network. A comparison of density, average queue length, and average waiting time between the controlled routing algorithm and a single minimum time route situation is presented. Results for variations in vehicular arrival rate and average trip length indicate the algorithm is more effective as the average trip length increased and/or average vehicular interarrival time is decreased. Complete flow-charts of the subroutines used in the simulation are given in the Appendix. CHAPTER II PROPERTIES OF THE SYSTEM 2.1 The Highway The primary goal of this thesis is the development of a controlled routing algorithm applicable to an SSH or a system with similar properties. The discussion of the SSH characteristics follows the paper by Louis T. Klauder, Jr. (17) with properties presented only if pertinent to the development of the routing algorithm. The system to be considered is a synchronous slot highway (SSH) where each lane is divided into logical slots moving in synchronism. Each slot is either occupied or unoccupied. The slots are all of identical length (l) and move with a constant velocity (V). A general network for an SSH would be composed of a number of sections linked by inter- sections. Each section would have adjoined to it a number of on-ramps and off-ramps interfacing with conventional traffic systems. For this general network the system would be divided into a number of subsections each having an on-ramp at the beginning and an off-ramp at the end. 4 Fbr simplification of the simulation programming a symmetrical grid network with identical sections is assumed, each having an entrance at the beginning and an exit at the end. The common length of all sections is denoted by the symbol L, and each section contains the same number of slots (m). 2.2 Systems Controlling the SSH There are two fundamental systems which supervise the Operation of the SSH. The Operating system is used to supervise the travel of the vehicles over the system but is not discussed as its Operation is essentially independent of the reservation of trips. The reservation system is the program which selects the slots for any trip and insures no multiple occupancy of the slots. While it is highly correlated with the controlled routing algorithm, no attempt is made to modify the fundamental functions of the reservation system. Instead a reservation system is assumed, incorporating the basic functions of: (i) storing route description, (ii) allocating capacity, and (iii) fitting trips into open slots. 2.3 The Reservation System 2.3.1 Storing Route Descriptions When a vehicle is to be routed through the system, the slots must be chosen so as not to interfere with any previously routed trips. This is insured by scheduling the complete space-time path through the network before the vehicle is allowed to begin the trip. In a realistic system a complete trip description must be stored to guarantee proper handling of each trip. FOr the most general network this would include, the exit number from each section, the previous section used in the route, and the required slot in each section of the trip. However, the simulation of the controlled routing algorithm requires only the knowledge of the state of each slot on any reservation list. For this purpose reservation lists are maintained for each section with a zero indicating an empty status and a one, an occupied status of each slot currently on the section. Each reservation list also includes slots indicating the future status Of the section. These slots represent vehicles currently on other sections of the highway which eventually use the given section. Determination of the maximum length for the reservation lists is possible because of a convention Of the reservation system: a trip cannot be scheduled until an open slot exists on the first section of the trip. Several reservation systems (arrangements) are discussed in Klauder (17). The main difference between the various arrangements is the ability of the system to use a reserved (but unoccupied) slot for a trip not physically interfering with the previously scheduled trip. Consider the simple example depicted in Figure 2.1 with a trip requested from e3 to B. Because an Open slot exists on the section, the trip is reserved by changing the status of the reservation bit of slot 91, even though the slot is not occupied physically. The next portrait of the reservation list shows the reserved slot shifted from e1 to e2. Assume a trip is now requested from e2 to e}. Without prOper control the slot could not be used, even though its use would not interfere with the trip requested from e3 to B. With the assumption of one entrance location per section, dual use is not possible, and the simple arrangement is adequate for the development of the control algorithm. 2.3.2 AllocatingCapacity Without proper control some space-time slots could be filled before downstream queues have access to the slots. A simple example of this problem is presented in Figure 2.2. High arrivals at A or B requesting section 5 will limit entry to section 5 for arrivals at C or E, and together these arrivals could completely i‘ 12 13 Arve agsB e1 e2 e3 1 1 aB1111l11111l1---1b (i) e e a] 12 ‘3 a ----- I; 1 1 1111 - - =_lb (ii) Figure 2.1. (i) Trip from e3 to B is reserved at slot e1. (ii) The reserved slot has progressed to slot e2. B 2 Ah—ré a; DHF 1 3 5 I. E (i) a/b c/e d 1/2, 1 3/5 A S l l l J Section 5 (ii) Figure 2.2. (i) A possible configuration for a general network. (ii) The reservation list representing section 5. block entry to section 5 for vehicles at entrance D. To prevent this in the general case, each reservation list is divided into a number of sectors. Then a maximum number of slots is allowed to be filled in any sector. This upper bound is dependent on the relative location of the sector upstream from the slots currently on the section in the reservation list. The limit is raised as a sector passes an index referred to as a.ppd. For later mathematical purposes in a general network, a rod exists at each point where a vehicle can enter a reservation list. Hence, the reservation list is divided into a specific number of sectors each bounded on the upstream side by an entrance location and on the down- stream side by another entrance location or an exit ramp. 2.3.3 Fitting Trips into Open Slots Assuming each slot in any section has an equal probability of being occupied, the probability of routing is the product of the fraction of open slots in each sector or one minus the normalized density in each sector. During high arrival rates, the large induced densities cause a high probability of route blockage. To decrease the probability of route blockage, the SSH needs the ability to shift vehicles during the course of a trip. If the adjacent slot is empty, the assumed 1O reservation system can shift a car forward or backward one slot while traversing any section or at any network interchange. The probability of routing is increased as the trip can now occupy one of three slots on all sections other than the first section. Thus, the probability becomes the product of one minus the normalized density on the first sector times one minus the normalized density cubed on the remaining sectors of the trip. CHAPTER III MATHEMATICAL DEVELOPMENT In conventional traffic systems, the velocity (v) and density (k) are related, in one commonly used model (A), by the differential equation n-1 v = -c::r (3.1) D. W where c and n are constants. Equation (3.1) is a mathemati- cal representation of the fact that velocity decreases as the density increases in a specific area of the highway. Combining the equation y = vk, y representing flow rate, with the solution of equation (3.1) for values of n, the graphical form develops as shown in Figure 3.1. In words, the flow rate increases with increasing density until reaching the density km after which increasing density causes a decline in the flow rate. This decrease in flow rate is caused by drivers reducing their speed to maintain a comfortable spacing between automobiles. Once this peak density is surpassed, the decay in the flow rate is very rapid, and the recovery time of the system is slow. 11 flow rate Figure 3.1. flow rate Figure 3.2. 12 control interval Jp——————— 1 I 1 1 1 I I 1 13a density Typical flow-density characteristics of a conventional highway system. density Flow-density characteristics of an SSH. 13 Ramp metering in a conventional freeway system maintains the density in the required interval (see Figure 3.1) during peak operation by controlling the number Of vehicles allowed to enter the system (29). The SSH system is also governed by the equation y = Vk where V is a constant velocity. The main advantage of the SSH system is the elimination of the reduction in speed as the density increases on the network. Hence, the maximum flow rate is the velocity times the maximum density (km)' However, there exists some realistic upper bound on the density (kr) caused by the stochastic nature of the arrivals at the various queues in the system and the associated trip distribution (see Figure 3.2). Although this maximum realistic density is achieved by a high vehicular arrival rate; the user waiting time is also very high. As the objective of the controlled routing algorithm is to increase system efficiency by selecting routes to reduce user waiting, it is necessary to develop the queueing characteristics of the problem. 3.1 Queueing Characteristics The mathematical prOperties of the network can be studied under the general heading of queueing theory where the identifying characteristics of this queueing problem are: (1) priority queues; vehicles on the system have priority over those in the queues. 14 (ii) two classes of units; priority and ordinary. (iii) head-of-the-line (nonpreemptive or postponable) priority; the service of an ordinary unit is continued to completion. (iv) tandem servers; vehicles leaving server j will require the use of server 3 - 1 after a constant time interval. (v) constant service time (with constraint*). (vi) unique parallel server case; vehicles require 11 servers simultaneously where 11 is the number th of sections in the i trip. Queueing analysis is usually done assuming the successive inter-arrival times and the service times are independent, identically distributed random variables (3,8,1h,27). However, the tandem server arrangement implies departures from one queue constitute an arrival at the next queue (with a constant waiting time) resulting in dependent interarrival times. Also, the constraint on the service time distribution negates any Markov prOperties Of the system because the future state depends not only on the present state but also the past states of the system. In addition, the parallel server case implies possible dependence between two or more reservation lists for any requested trip. Using the example in Figure 3.3, consider a vehicle arriving at point A desiring to reach point D. * The constraint imposed on the service time limits reservations at any server to a fraction of the total number of slots passing the server (see section 2.3.2). 15 A."-"—""—-—-TfB H 2 ”C 13 11 D (i) a" a' a l l l l l 1 I] b" b' b [7] 41.] l I J c" c' c [71 1 I l l I] (11) Figure 3.3. (1) Segment of a simple network. (ii) Location of pseudo-queues on the reservation lists. 16 The reservation system must set aside a slot in the first sector of section 1 (slot a), the second sector of section 2 (slot b'), and the third sector of section 3 (slot 0"). Thus, while the vehicle actually arrives and is queued at point A, the points a, b', and c" represent service points to the vehicle. Instead of studying the complex problem of the queue at point A, the prOperties of the points a, b', and c" will be analyzed neglecting the dependence between the three points. Vehicles waiting to enter a service point will form a pseudofigpgpg of the system. Also, as each section is partitioned into slots of length 1 moving with a constant velocity V, one time increment of the system is ts =‘% and is referred to as the service time of the system. 3.2 Approximations Queueing problems are distinguished by specifying four parameters: (1) input distribution (ii) service time distribution (iii) number of servers (iv) size of source In view of the difficulties presented, certain assumptions are made to simplify the problem. Consider first the 17 problem of the last sector of any reservation list without the constraint limiting the number of entries. In terms of the above four parameters, this problem has character- istics of a constant service time, one server, and an infinite source. In addition, the assumed model for the arrivals at the queues in the system is an exponential arrival time distribution. This implies a Poisson counting process at each of the queues in the system. However, the required distribution is the arrivals at each pseudo- queue in the network. Clearly, if a pseudo-queue is fed by only one queue, the number of arrivals at the pseudo-queue forms a Poisson counting process. Consider the case where more than one queue feeds a given pseudo-queue. Let Pg the probability a trip at queue j requires the use of pseudo-queue i. 13 intensity or rate of occurrence at the jth queue. th P{M1(t)=m} = the probability the i pseudo-queue contains m entries at time t. Then using the properties of a Poisson process, P{Mi(t+h)=n} = {§IJ(P£)}hP{M1(t)=n-1} + {1 - <§13)h}P{M1(t>=n} +{§13(1-pg)}hp{mi(t)=n} + 0(h2) (302) th In words, the probability the i pseudo-queue at time 18 t+h contains n vehicles equals the probability the ith pseudo-queue at time t contained n-1 entries times the probability of one arrival from any of the possible queues, plus the probability at time t there were n entries in the ith pseudo-queue multiplied by the probability of no arrivals from any queue, or the probability at time t there were n entries multiplied by the probability an arrival occurred at the jth queue but was not entered at the ith pseudo-queue. Rearranging equation (3.2), the following can be derived: P{Mi(t+h)=n} = (§13P£)hp{mi t)=n-1} - (§i3P§)hP{Mi(t)=n} +P{Mi(t)=n} + 0(h2) (3.3) Then using the following new notation r1 = §IJ(p§) and Pn,i(t+h) = P{M1(t+h)=n} equation (3.3) can be rearranged to give Pn 1(t+h) - P i(t) = riPn-1’i(t) - riPn’i(t) + o(h2) h (3.4) Equation (3.A) is known to give a Poisson distribution in the limit as h tends to zero. Thus, the pseudo-queue has a Poisson arrival rate with parameter r1 = rate of occurrence at the ith sector of any reservation list. r1 = §IJ(P3) (3.5) 19 Assuming the total number of arrivals to the system is in a steady-state condition, the initial problem simplifies to an M/D/1 queueing process whose properties are well documented (21,27). Using equation (3.5) and defining th r3 = the arrival rate at the i sector of the reservation list of section 3. and pg = mean service time mean interarrival time at the ith sector of the reservation list of section j. then pg = r3 E(S) (3.6) where E(S) = ts. The process can be defined as follows: (1) positive recurrent if pg < 1 (3.7A) (ii) null recurrent if p3 = 1 (3.7B) (iii) non-recurrent if pg > 1 (3.70) If the process is positive recurrent (3.7A), then a long- run probability distribution can be determined where th Pj = the probability the i pseudo-queue of section j contains k vehicles. In particular, it can be shown (21) P3 = the probability the 1th 0 i pseudo-queue of ! section j is empty = 1 - Pg (3.8) 2O 1 _ Pj th 0 i pseudo-queue of 9 = the probability the 1 section j is occupied = pg The previous probabilities for the status of the queues were developed without the constraint on the service time. However, as discussed in section 2.3.2 to prevent excessive blocking at the downstream sectors of the reservation lists, only a limited number of slots can be filled per sector. Hence, the Markov characteristics of the problem are lost as entry into the system depends on the previous states of the network. The constraint th sector of any of allowing only mk of Mk slots in the k reservation list to be filled is approximated by considering the previous sector to have Mk - mk slots already filled with 111k slots empty. Define mg = number of allowable slots to be filled in the kth sector of the reservation list of section j. M& = number of slots in the kth sector of reservation list of section j. A: 0 if a slot is empty 1 if a slot is filled Then assuming each slot has an equal probability of being filled or empty, P(A = O) = (309) 3' B xufi'u. 21 j j P(A = 1) = Mk "' mk (3.10) * :1 Mk The expected service time is then defined by m E(Sgi) = ;O ntSP(Si?; = nts) (3.11) where the individual probabilities P(S&=nts) are given by the formula j . . _ m __ J p(sJ = ms) = (‘ 1% >n ‘ mk (3.12) k ”3 "3’ k Mk 1.9., the probability of having n - 1 slots filled in the kth sector of the reservation list of section j before the arrival of an open slot. Substituting (3.12) into (3.11), the following is obtained: . J Mk M3: 3 i 1 - "‘13. 1 I 1':S mk n=1 n( —j )n- w J 3 1 - "‘1: mg) = ts %;O (n +1)( if; )m k 3 if 1 - mg n j: 1 - mi n or E(sg)=tsf_13: heel“ 11-13) *n=o( 1.43) Mk k k The second series is a geometric series and the limit of the first is also easily calculated (Appendix A). Thus, 22 j . 1 - mk 3 mJ ‘3 MI j m3 k mk 2 JS- ( ‘3' ) M3 Mk k and finally - J E(Sfl) = tS E); (3.13) mj k Substituting (3.13) into equation (3.6) gives the approximated parameter p' as J' :1 (p')j = I‘k__:___SM mi Ll (3.1h) Assuming p' satisfies equation (3.7A) for positive recurrence, then Pg k = the probability the kth pseudo- , queue of section j is empty becomes j r jt PO’k =1 - k 3“}: (3.15) m): Let Ni = the number of occupied slots in the kth sector of the reservation list of section j. and consider the number of slots filled in the kth sector of any reservation list. Again neglecting the inter- dependence between two or more sections, the probability of filling an empty slot has at each occurrence a Bernoulli probability of success equal to 1 - Pg,k’ i.e., the probability the queue is occupied. The expected number of 23 filled slots is determined using equation (3.15) assuming only mk total slots can be filled during Mk service times. Hence, the distribution is binomial in nature of mk trials with success on any trial equal to 1 - Pg,k. Thus the th expected number of slots filled in the k sector during Mk service times is E(Nfl) = mg (1 - P3 jt M3 (3.16) Then using the constraint for the existence of the long-run probability distribution equation (3.7A) in conjunction with equation (3.1A), the following inequalities hold: (p')ij{ = rfltSM£<1 mil Hence E(Nfl) = rgtsmgmg (3.17) SO the expected number filled in the kth equation (3.16) is bounded by the constraint (3.17), sector given by and on the average only a fraction of the available slots are filled on the kth sector of any reservation list. Equations (3.1A) and (3.15) can also be used to determine the upper bounds (mfl's) for each sector of any reservation list. The constraints for each sector can be determined by equating the probabilities of each queue being empty in any reservation list. This equalizes the usage of each sector in proportion to the arrival rate at 2h each pseudo-queue and the number of slots in each sector. Thus P3,}: = see = 133,2 = 133,1 or . j - j r1499. .1191. - r9). (3 18) mg mg m, where j ’ j m _ M i=1:L 1 The summation of all the rfl's (normalized to the first sector) for any particular reservation list give an equivalent Ed for the primary sector. Then equation (3.18) can be equated to Ed 1‘ . M? Where F3 :2 r2?- fi— (3019) i=1 M Combining equation (3.18) and (3.19), the constraints for each sector of any reservation list can be determined from J 3 mg = rk Mk for all k. (3.20) r Determination of constraints in a realistic system would necessitate measurements of individual arrival rates at the pseudo-queues in the system. Calculations of the bounds on each sector for the simulation example are given in Appendix A. 25 3.3 Expected Waiting Time It is also necessary to derive a formula for the eXpected waiting time of any proposed trip to be used as part of the performance index. Let the probability a trip can be routed after a .550 delay of 1 service times. (I) L1 11 the probability a slot is unoccupied in the th 1 sector of the reservation list of section j. Consider as an example a trip three sections in length routed over sections k, l, and m, resPectively. The initial probability is Q0 . (53,1) (1 - (1 - 59,2)3) (1 - (1 - sg,3)3) (3.21) This is interpreted as finding an Open slot in the first sector of the reservation list for section k, at least one of three slots Open in the second sector of the reservation list for section 1, and finally at least one of three slots Open in the third sector of the reservation list for section m. Then if QO is the probability of finding no blockage in in first attempting to route the trip, 1 - QO is the probability of the trip being blocked in the initial routing attempt. 26 Hence, assuming the system is in a steady-state mode, Q1 = (1 - QO)QO, Q2 = (1 - ()0)2 Q0,"‘, ()11 = (1 - Q0)“ Q0 (3.22) The expected waiting time can then be computed as E(Wt) = O.QO + tSQ1 + 2tsQ2 + "' or my E(wt) ‘ n=1 ntsQn (3.23) Substituting equation (3.22) into (3.23) gives E(Wt) = t‘sQo 1;] n“ " Q0)n The sum is easily derived (see Appendix A), and E(Wt) = t5% (1 - Qg) (Q0) Finally E(wt) = t5 (;0- Q0) (3.2a) where for an arbitrary trip over 61 sections with section number ki k1 8' ki 3 Q0 = 50’, gfl;(1 - (1 - 50,1 ) ) (3.23) 27 Assuming all slots have an equal probability of being occupied, the probability of a slot being empty (50,1) will be one minus a normalized density as discussed in section 2.3.3. Consider the situation on a specific section th j, the k sector as shown in Figure 3.A. (k + 1)th kth L :l—b slo t motion L. kth pseudo-queue th Figure 3.4. The k pseudo-queue of a reservation list. While SO 1 is the probability of an Open slot on the kth ’ th sector using a normalized density of the k sector is not a true indication of the number of empty slots arriving at the kth server. An alternate method might use the density of sector k + 1 to derive the required probability. However, this does not include the effect of the constraint limiting th the number of vehicles on the k sector. Hence, the normalized density needed to determine the slot availability at the kth server will be derived from the densities of the two adjacent sectors k and k + 1. Thus sO’k = 1 - X(k)2; X(k+1) (3.26) where X(k) th = the density on the k sector of any reservation list. 28 3.A Projected Densities The division of the highway into subsections with each link.having its first slot an entrance point generates the following assumption as a basis for the cost of a route. ASSUMPTION: The route cost of any trip is the sum of the normalized density on each section at the instant the vehicle enters the section. At the time the trip is scheduled only the density on the first section is known. For succeeding sections projections based on the current density on the section and the average number of vehicles entering the section are used to compute a predicted density when the trip will actually occupy the specific section. All densities used in the route cost will be normalized densities, where normalized density = density of sectipp maximum number of slots per section The first sector of each reservation list representing the slots currently on the section is used to define the primary portion of the reservation list. Secondary portions on the reservation list are defined by starting at each pseudo-queue location and counting in the direction of slot 29 motion the number of slots in the primary portion. Figure 3.5 presents two cases with the reservation lists divided into portions. In the simulation example discussed in Chapter A, the sections all contain the same number of slots (m). Hence, one period (T) will be defined as the cummulative time of m successive service times. In addition, the following notation will be used in the ensuing discussion. NOTATION: (1) Xj(n) = density of section j on portion n. Thus Xj(1) = density of section j. (2) xj(1) = normalized density of section j. (3) Xj(i,k) = density on section j, portion 1 after k periods (T) of time. i.e., X (1,1) = density of section j, after 1 period = x3 (2,0) + number of cars entering section j, portion 1 between 0 (3.32) CHAPTER IV COMPUTER SIMULATION A model was develOped to simulate the actual Operation of an SSH and the associated arrival Of vehicles. The GASP IIA simulation language was used as a basis: FORTRAN subroutines were written to simulate arrivals, updating, simple route selection, and controlled route selection. The model is initialized by establishing a steady-state low density condition with a low arrival rate. Experiments were conducted to demonstrate the benefits of the alternate routing algorithm, being designed to run in both the single minimum time path and the controlled route selection modes. Both the time integral of the queue length and the time integral of the average density on all sections were analyzed in the study. 4.1 Development pf_the Model A.1.1 Modeling Assumptions In any simulation model, certain criteria must be met to insure a prOper reproduction Of actual system Operation. 35 36 The first selection to be made is the simulation language. Criteria for selection in this simulation included the ability to transfer slots (simulating vehicle motion), handle the requests offered by users in the desired fashion, and allow for the shifting of vehicles already on the network. As the shifting criterion presents the most difficult programming problem, a FORTRAN based language Offers the best manipulation possibilities while still fulfilling the other requirements. Thus, the GASP IIA simulation language was chosen because it is FORTRAN based and was accessible as a library subroutine. To develop realistic arrival distributions and adequate service simulation, it is necessary to define the characteristics of the arrival and service mechanisms. First, the arrival times can be approximated by an ex— ponential distribution, implying the cummulative number of arrivals at each queue has a Poisson distribution. The following four axioms are required for the arrival distribution where N(t) = the number of arrivals in (O, t) (1) N(0) = 0 (ii) the process has independent increments. (iii) in any interval, no matter how small, there is a positive probability of occurrence. (iv) it is impossible for more than one arrival to occur at the same instant. 37 Also, a fifth axiom is necessary to have a Poisson process, namely, (v) the process has stationary increments. During the time of system operation under consideration (morning and evening rush hours), in the strictest sense, the process would not behave according to the fifth characteristic. However, by assuming a piecewise Poisson process, the stationary condition is met along with the known prOperties of rush hour, i.e., the rising to a high arrival rate and then gradual decline to moderate arrival rate. The final assumption is that arrivals have some distribution in regard to the length of the requested trip. This length distribution is a variable parameter in the simulation. In the same way properties of the service mechanism must be develOped before writing the simulation programs. The first criterion is servicing queues on a first-come, first-service basis. While another queue discipline might increase highway efficiency, it could result in extremely large waiting times for some users which is undesirable from a system viewpoint. Also, an arrival occuring during a slot shift must wait until the next slot reaches the entrance position before initiating service Of its requested trip. In addition, it will be assumed the queues are large enough to hold all arrivals; similarly, vehicles will not leave the system without being served (no balking). Each entrance point can be characterized as a server 38 processing two queues. One queue has the prOperty of exponential arrivals, infinite length queue, and no balking. The other has the prOperty of deterministic arrivals and allows no queue build-up. Thus, vehicles in the entrance queue have a lower priority than the vehicle already on the highway. Each request must find available the number of servers equal to the number of links to be traversed by the trip. 4.1.2 The Comparative Reservation Arrangement The assumption of the symmetric nature of the network plus the division of each section into identical subsections implies the reservation system can adequately be handled by the simple arrangement (17). Reservation lists are maintained with a 1 indicating a particular slot is occupied and a 0 representing the absence of a vehicle. It is not necessary to maintain detailed trip information because the simulation is not concerned with having to re-create trip paths forced by system breakdowns. This allows for storage of slot data in bits instead Of full words, considerably reducing the necessary memory. It is necessary in the simulation to have a representa- tive simple arrangement to use as a comparison with the controlled routing algorithm. Three possible reservation arrangements are given in the reference by L. T. Klauder, Jr. These are essentially: 39 (i) care may be shifted one slot forward or backward during either an inter-section movement or an intra—section movement. (ii) rescheduling of a trip causing blockage of another trip. (iii) cyclic modification of reservations to minimize trip blockage. The reservation modification is based on the idea of rescheduling reserved trips which have not yet commenced true travel. This modification was not used because the assumed network has only one entrance location at the beginning of each section implying a vehicle with a completely reserved trip immediately enters the highway. The cyclic modification is also not used as it requires storage of detailed trip information. Thus, the comparison is based on a combination of the intra-section and inter- section shifting for the simple arrangement with only the inter-section movement allowed during the controlled routing algorithm. A.2 The Network A.2.1 Selection p£.Alternate Paths The selection of paths for the 3x3 network started with a "best" path for each origin-destination pair as might be chosen by any user (10, 15). Added to each of 40 16 6 Q Q _I a) 29 2 #5 H8 11 35 9 21 1o 23‘ 11 19 12 28 3 (4 9 1o 36 22 23 24 13 14 15w|lllllllllpr' 16 27 26 25 Figure 4.1. The Network: Two-way exterior streets with one-way interior streets. 41 these minimum path routes (MPR) were all paths of the same minimum path length between the origin-destination pair. Then for all MPR of four and five sections, alternate paths were found traversing exactly two more sections than the minimum path (see Figure 4.1). Initially, (only reasonable alternate paths were stored and considered as possible secondary routes, and the elimination process was accomplished using the following rules: A. Minimum trip length five (5) sections: 1. no alternate path should traverse any four (4) sections of MPR. 2. no alternate path should traverse three (3) consecutive sections of any MPR. B. Minimum trip length four (4) sections: no alternate route should traverse any three (3) sections of any MPR. All alternate routes for the 3x3 example are shown in Table 0.3 of Appendix C with the dashed ones eliminated by the above rules. A.2.2 Off-Line Storage Arrays It is necessary to establish off-line storage arrays containing all destinations from a given origin and the actual sections required for any trip. Rather than store 42 each integer in a separate word, the data was encoded in consecutive bits of a given word. Thus, all destinations a specific length from a given origin were stored in the array DEST(POINTER) where the pointer is calculated using the equation POINTER = (ORIGIN - 1)*6 + LENGTH The destinations were stored in five bit strings in an integer word as the example of origin 1 shows in Table 4.1. Thus (2, 5) is encoded as 01000/10100/"' with an integer value of 162. The array can be treated schematically as shown in Figure 4.2. The flow diagram for encoding -the information is given in Appendix B, while the destina- tions a specific length from any origin are given in Table 0.1 of Appendix C. Similarly, the actual sections required for the trips were encoded into the array ITRIPS(POINTER) with the pointer located in a 16x16 word array TRPT(IORG,IDEST). Thus, as shown in Figure 4.3 the origin-destination pair is used to locate a pointer to the ITRIPS array where the sections were encoded in consecutive six bit segments of an integer word. As some origin-destination pairs required storage for alternate routes, a method was needed to locate the end of a given set of routes. Since the longest possible trip in the network is seven sections and the integer word length in the CDC 6500 is 48 bits in length, the eighth segment was unused in each word. Hence, an indicator of one was stored in the eighth segment 43 DEST(pointer) 162 9.411 I Pointer( IORG ,LGT) Figure 4.2. The destination array. TRPT(IORG,IDEST) (pointers) .____1. ITRIPS(pointer) Sections .4 Figure 4.3. The pointer array and corresponding trip section array. 41., Table 4.1. Encoding Of destinations for trips at entrance 1. Origin 1 Length Destinations DEST(pointer) 1 2,5 162 2 3,6,9 9,411 3 4.7.13 13,540 4 8,11,14 14,696 5 10.12.15 15.754 6 16 16 Table 4.2. Encoding of trip sections for arrivals at entrance 1. Origin 1 Destination Sections IND Integer 2 31 1 31 + 2“2 3 31,32 1 2079 + 2“2 4 31.32.33 1 137,247 + 2“2 5 1 1 1 + 242 6 1,16 1 1025 + 2‘2 7 31.32,? 30.751 1,16,17 1 70,657 + 252 45 of each word containing the last trip between any origin- destination pair. An example for origin 1 is presented in Thble 4.2. A complete listing of all pointers of array TRPT is given in Figure C.2 of Appendix C, while a flow chart for the above encoding procedure is given in Appendix B. “-3 9.82.4.9. 2.1.9.! ”Charts The central programming phiIOSOphy behind GASP IIA is very simple. First, a main program is written to initialize non-GASP variables and call the GASP simulation subroutine (see Figure 4.4). Second, subroutines are written for each event required to occur in the simulation (see Figure.4.5). These subroutines are all called from subroutine EVENTS and form the body of the programming effort. The primary goals of the two event subroutines are: A. SUBROUTINE ARRVL (i) select equally likely entrance points. (ii) use a probability distribution to determine a specific length of trip. (iii) determine equally likely destination based on entrance and trip length. B. SUBROUTINE UPDATE (1) shift necessary locations to simulate movement of vehicles on the highway. 46 IMAIN PROGRAM] 1 Initialize variables (non-GASP) (:Call GASP>> (:Call EXITj> Figure 4.4. Main program flow diagram. [SUBROUTINE EVENTS] 1 lGo To (1,2)l 2 | I l (:Call ARRvij> Call UPDATE Figure 4.5. The event subroutine. (17 (ii) check all queues determining a trip routing sequence. (iii) route vehicle through system per routing control. 4.4 GASP Parameters Before starting the simulation it is necessary to dimension the GASP variables to the desired size for the specific system. Figure 4.6 shows another view of the example network and the location of the various queues. The main feature is the sharing of queues by two or three sections. Thus, instead of thirty-six queue locations only sixteen queues (corresponding to the network inter- sections) were modeled for the simulation. Establishment of this characteristic allowed the file division to be as follows: File 1: Event File Attribute 1: Scheduled time of the event Attribute 2: Event code Attribute 3: ---------- File 2: Queue Processing File Attribute 1: Time of arrival Attribute 2: Destination Attribute 3: Queue number 48 5-CIIIIIIEHHIIIII 6-*{::::::::::::J 7-wllllliiiillll 8 14 15 6 DEE/E" Figure 4.6. Location of entrances on the sections of the network. 49 File 3 through File 18: Queue 1 through Queue 16 Attribute 1: Time Of arrival Attribute 2: Destination Attribute 3: Queue number The event codes were assigned as 1-arrivals to the system and 2-simulated updating of the highway. Appendix B contains flow charts and a detailed discussion of each of the main subroutines in the simulation. 11.5 3951.132 In each case the simulation was run for 120 time units to initialize the system. The key parameters are IN P1+1 P2+2 Let Case Case Case C Case the average interarrival time for each entrance location. the expected trip length for origin-destination pairs with a maximum trip length of six sections. the expected trip length for origin-destination pairs with a maximum trip length of five sections. IN = 0.90 P1 = 1.50 P2 = 1.25 IN = 1.20 P1 = 2.75 P2 = 2.00 IN = 2.00 P1 = 2.75 P2 = 2.00 IN = 2.00 P1 = 3.75 P2 = 3.00 50 The numerical results for these four cases are presented in Table 4.3 and Table 4.4 giving the average density on a section and the average number of vehicles in the queue, respectively.* The results are also plotted in Figures 4.7 and 4.8. Table 4.5 lists the increased travel time (caused by use of non-minimum time paths) for the controlled routing algorithm while Table 4.6 gives the data for K (the frustration factor) times the increased waiting time for single minimum time route selection. The difference (divided by the number of arrivals) between the increased waiting time (Table 4.5) and the increased travel time (Table 4.6) is listed in Table 4.7 and plotted in Figure 4.9. The theoretical calculations presented in Chapter 3 were used to predict a stable region of system Operation for the simulation as discussed in Appendix A. EXamination of the tables and graphs shows the advantages of the controlled routing algorithm. The large number of total slots in the network (60 slots x 36 sections) hides the effectiveness of the routing algorithm with only a small increase in the density. The average number of vehicles in the queues presents a better indicator with the relative percentages of decrease being: Case A, 11.3%; Case B, 26.1%; Case C, 1.4%; and Case D, 44.4%. Figure 4.9 also shows a system total trip * The abbreviation c for the controlled routing algorithm and nc for the single minimum time path selection will be used in the tables and graphs. 51 time savings is being made as the waiting time (multiplied by the frustration factor) for the single minimum time path selection becomes greater than the increased travel time for vehicles under the controlled routing algorithm. Analysis of the data results in the following conclusions: (i) the controlled routing algorithm is more effective as the arrival rate increases. (ii) the controlled routing algorithm is more effective as the average trip length is increased. (iii) the controlled routing algorithm is less effective for short average length trips if the arrival rate is small. Thus, the controlled routing algorithm is most effective as the average trip length is increased and/or the average interarrival time is decreased. While the simulation net- work is relatively small, the results indicate the algorithm will be even more effective in a large (more realistic) network. The results concerning the effect Of the inter- arrival time are likewise very encouraging as a realistic system during rush hour experiences a relatively high arrival rate. Table 4.3. Average 52 densities on the highway for different arrival rates and average trip length. Parameters , T IN = 0.90 IN = 1.20 IN = 2.00 IN = 2.00 I P1 = 1.50 P1 = 2.75 P1 = 2.75 P1 = 3.75 M P2 = 1.25 P2 = 2.00 P2 = 2.00 P2 = 3.00 E nc/c nc/c nc/c nc/c 120 20.08/20.08 16.96/16.96 11.31/11.31 12.12/12.12 150 22.02/22.03 19.49/19.51 12.96/12.96 14.23/14.28 18o 23.36/23.39 21.34/21.41 14.26/14.28 15.93/16.03 21o 24.37/24.41 22.66/22.79 15.23/15.24 17.03/17.29 240 25.09/25.14 23.58/23.73 15.90/15.91 17.89/18.28 27o 25.59/25.66 24.36/24.55 16.48/16.49 18.53/19.05 300 25.89/25.97 24.94/25.22 16.90/16.92 19.05/19.68 330 26.17/26.25 25.42/25.79 17.22/17.26 19.57/20.25 360 26.41/26.50 25.80/26.22 17.47/17.53 20.03/20.74 Table 4.4. Average number in queue for different arrival rates and average trip length. Parameters T IN = 0.90 IN = 1.20 IN = 2.00 IN = 2.00 I P1 = 1.50 P1 = 2.75 P1 = 2.75 P1 = 3.75 M P2 = 1.25 P2 = 2.00 P2 = 2.00 P2 = 3.00 E nc/c nc/c nc/c nc/c 120 2.31/2.31 1.96/1.96 1.26/1.26 1.82/1.82 150 2.53/2.50 2.26/2.20 1.29/1.29 2.30/2.19 180 2.84/2.77 2.71/2.57 1.33/1.31 2.56/2.32 210 3.08/2.98 3.07/2.78 1.35/1.32 2.91/2.33 240 3.29/3.12 3.47/3.09 1.37/1.34 3.31/2.39 270 3.37/3.14 3.83/3.27 1.38/1.35 3.73/2.43 300 3.40/3.11 4.14/3.36 1.38/1.35 4.03/2.41 330 3.44/3.1O 4.39/3.34 1.38/1.35 4.15/2.38 360 3.53/3.13 4.64/3.43 1.38/1.36 4.32/2.4O Average number of occupied Case slots 27- 26‘ 25 2L1. 23 22 21. 20 19 18 ‘- 17 16.. 15. 11+ 13 12 11 Figure 4.7. d? {b ‘1- «7 lb 1’ Case Case Case 60033? 4 1 A L. . . - 120 150 180 210 240 270 and average trip length. IN=0.90 P1=1.5 IN=1.20 P1=2.7 IN=2.00 P1=2.7 IN=2.00 P1=3.7 \NNN-‘ O OOON OOOUI Case A Case B Case D Case C A A 300 330 360 Time Density plots for various arrival rates 54 Average number in queue Case A: IN=0.90 P1=1.5O P2=1.25 Case B: IN=1.20 P1=2.75 P2=2.00 ,B(nc) Case C: IN=2.00 P1=2.75 P2=2.00 z’ 4.5 0 Case D: IN=2.00 P1=3.75 P2=3.00 I” I, D(nc) If, ”/’ / / I (+00 ‘) ”/ /’ I I I I, A(nc) 305 1’ I I ’*-—-..v’ I” l"” , ’ Mo) 300 1’ I ’I’ I I I . / ’9 ;/ I I 2.5 1) ’I’ ’I;I -x. A-—.~-*-—’.D(C) Case A /’/—--/ ’I/ 2'0 "Case B177 Case D 1.5 .. 1.4 .1 A #Casic *(nt):) 103 ‘3 (fl 7 : v : C 1.2 JL :_ 3 : + ‘ : ; : a - 120 150 180 210 240 270 300 330 360 Time Figure 4.8. Plots of the average number in the queues for variations in the parameters and control. 55 Table 4.5. Increased travel time (c). Parameters T IN = 0.90 IN = 1.20 IN = 2.00 IN = 2.00 99:19; 99:93.9 99:9:99 99:13:93 120 O O O O 150 120 720 480 1020 180 180 1380 840 2160 210 180 1980 1140 2820 240 240 2340 1440 3900 270 300 3060 1800 4740 300 360 3480 1860 5340 330 360 3660 2220 6300 360 360 4320 2520 7260 Table 4.6. Increased waiting time multiplied by 2.5 (no). Parameters T IN = 0.90 IN = 1.20 IN = 2.00 IN = 2.00 I P1 = 1.50 P1 = 2.75 P1 = 2.75 P1 = 3.75 % P2 = 1.25 P2 = 2.00 P2 = 2.00 P2 = 3.00 120 O O O O 150 62-5 235.5 17.5 466 180 467.5 490 137.5 925 210 570 1800 185 3217 240 1255 2632.5 220 6335 270 2232.5 3405 415 10.975.5 300 3347.5 5910 387.5 15.770 330 3950 10,277.5 372.5 21.990 360 4927.5 13,000 327.5 28,807.5 Table 4.7. The difference (divided by the number of arrivals) between increased travel time (c) and 2.5 times increased waiting time (nc). Parameters T IN = 0.90 IN = 1.20 IN = 2.00 IN = 2.00 I P1 = 1.50 P1 = 2.75 P1 I 2.75 P1 = 3.75 M P2 = 1.25 P2 = 2.00 P2 = 2.00 P2 = 3.00 E 120 0.00 0.00 0.00 0.00 150 ”0.12 -1035 -1087 “20#6 180 0030 -1023 ~1.42 “2.67 210 0.27 -0.16 -1.33 0.58 240 0.54 0.20 -1.24 2.59 270 0.82 0.19 -1.14 5.32 300 1.07 1.11 -1.01 7.50 330 1.10 2.63 -1009 9060 360 1.23 3.01 -1.14 11.28 57 Difference Case D Case A: IN=0.9O P1=1.50 P2=1.25 Case B: IN=1.20 P1=2.75 P2=2.00 Case C: IN=2.00 P1=2.75 P2=2.00 10.011 Case D: IN=2.00 P1=3.75 P2=3.00 900" 800‘ 7.0.. 6.01) 5.0.. 4.0 41 3,0«. Case B 2.0 0 1.0,, 2 J: Case A '1 120 150 ‘1- - - v, 21.0 270 300 330 360 Time -1.0 ” ‘ 1 ' " Case C -2.0 d) Figure 4.9. Plots of difference between K times expected waiting time (nc) and increased travel time (c) divided by the number of arrivals. CHAPTER V CONCLUSIONS AND FUTURE INVESTIGATIONS The primary objective of this research was the development of a controlled routing algorithm applicable to any system with properties similar to an SSH. A brief discussion of the function of an SSH is first presented. With the aid of results from queueing theory equations were derived for the expected waiting time of any trip and a prediction for the number of exPected users on any section in the network. The performance index to be minimized for route selection was composed of a user cost (the expected waiting time) and a system cost (the expected number of vehicles on any route). Finally, the SSH system was simulated for both the controlled routing algorithm and a single minimum time route selection with variations in vehicular arrival rate and average trip length. Results indicate the controlled routing algorithm can decrease the average number of vehicles in the entrance queues and increase the density on the network. The inclusion of non-minimum time paths as possible alternate routes is justified (in most cases) as the waiting time 58 59 multiplied by a frustration factor for vehicles in the single minimum time route selection is greater than the increased travel time of vehicles for the controlled routing situation. While analysis shows the effect of the control algorithm is greater as the average trip length is increased and/or the average interarrival time of the vehicle is decreased, there exists a region of short average trip length and high interarrival time for which the algorithm should not be applied (Section 4.5, Case C). These cut-off levels are a function of network complexity and size and require further investigation for a better understanding. A number of possible studies are suggested by this work. One extension is to apply the control algorithm (in particular, the idea of including non-minimum time paths) to systems other than vehicular traffic systems, i.e., conveyor belts, telephone systems, or warehouse storage patterns. Another possible problem is to develop in more rigor the queueing characteristics of the system. Relaxing the assumptions made in Chapter 3 will result in a very formidable problem for solution. The main problem might be to assume the Markov properties holds (i.e., neglect the constraint limiting the number of users per sector Of a reservation list) and derive the general queue characteristics of the problem. Also the maximum theoretical efficiency Of the SSH (assuming a high vehicular arrival rate) might be developed to compare with the maximum efficiency of other types of traffic systems. APPENDICES APPENDIX A SUPPLEMEN TARY DERI VA TION S Limit f Sum Consider the sum m _ i S ’ i=11Q th where the m partial sum is Sm = r + 2r2 + 3r3 + "’ + mrm Then S - r5 = r + r2 + r3 + "' + rm - mrm+1 m m or .. 0.. m‘] m+1 Sm - rSm — r(1 + r + + r ) - mr Using the known results for a geometric series Sm = r 1 (1 - rm) - mrm+1 1 - r 1 - r 1 - r So if r is less than 1, the sum has the limit 60 61 s = ___£L___. (1 - r)2 Upper Bounds for the Reservation Lists The constraints for the reservation lists were determined by assuming an average trip length of 3 for origin-destination pairs with a maximum trip length of five sections and 3.75 for origin-destination pairs with a maximum trip length of six sections. This gave average rates of occurrences as shown in Table B.1. Then the average rate of occurrence is 6 Z " = 2.26 k=1 1‘1: Using equation (3.20) the constraints were calculated as shown in Table B.1. Table B.1. The average rates of occurrences and corresponding constraints for portions of a reservation list. Portion 1 2 3 4 5 6 Average rate .439 .418 .366 .355 .381 .303 Constraint 11.64 11.09 9.71 9.41 10.10 8.03 62 Bounds pp_Interarrival Time The average rate of occurrence can also be used to determine a point of stable system Operation. Using the necessary condition for a long-run probability 2.26rtS < 1 and letting x = the mean interarrival time =‘l r then x_> 2.26tS for stability (queue size). APPENDIX B FLOW CHARTS Appendix B contains the flow-charts for the off-line storing and filing programs, in addition to the three main subroutines used in the simulation. Figure B.1 shows the flow-chart developing the coding of the trip sections into integer words, while Figure B.2 is the corresponding decoding of the integer words back into section numbers. Figure B.3 shows the flow-chart for encoding the destinations from any specific origin. Finally, brief explainations of the main subroutines (ARRVL, BEST, and UPDATE) are given with the corresponding flow diagrams presented in Figures B.4, B.5, and B.9. 63 64 IIND = 1 3 ISECT = 16] 1. I=1,16 ’’’’’’’ J=1,16 0 IF I EQUALS J WRITE ZERO IN POINTER ARRAY, c OTHERWISE STORE INDEX TO TRIP LOCATION. -_____-_J I = J 2 YES t-ITRPT(I,J) = (fie—— I I TRPT(I,J) = IND READ 131,152, --- ,IS8 l ITRIPS(IND) = IS1 + 182*(2**6) + IS3*(2**12) + 134*(2**18) + IS5*(2**24) + IS6*(2**30) + IS7*(2**36) + 158*(2**42) IND = IND + 1 1 F1 IS8 GREATER THAN ZERO INDICATES THE LAST C TRIP BETWEEN I AND J 7 N0 fies = 1 ey—Y-E-fi- ———————— L_______________________I Figure B.1. Flow diagram for storing trips and trip pointers. 65 lMASK2 = 63] DO 1< 91:12 > 1 1 III-TRIP = ITRIPS(PNT-ir (Do K=1,D-e- ————— .1 1 IST(K) = ITRIP.AND.MASfl ITRIP = ITRIP/(2**6) , YES r-_______________________ Figure B.2. Flow diagram for decoding sections of a given trip. 66 Q0 L=11,16)+ __________ _' READ IDT(K) ‘ K = 1 s DEST(PNT) = 0 (D0 J=1,21>-I- ———————— 1 YES IDT(J) = o ? 1 N0 I _ PNT=PNT+1 DEST(PNT) = 0 [J 207r NO fl-IK=J+fl--"' lYES PNT+fl~ ---------- Figure B.3. Flow diagram for storing destinations from each origin in the network. I l I I _ _ l [DEST(PNT) = IDT(J)*(2**((J-K)*5)) + DEST(PNfi-w-D-l I I I I l l l L----_.___..____.______________-- [PN T 67 Subroutine ARRVL and Subroutine BEST Subroutine ARRVL simulates with an equal probability the arrival of vehicles at the various queues in the network. A length destination is then determined based on a Poisson distribution; after which a destination the specified length is selected, again with equal probability. The flow chart is shown in Figure B.4, Subroutine BEST calculates the cost for all routes between an origin-destination pair. The route cost of the first section is calculated from a normalization of the density on the section. For each subsequent section a projected density based on current density plus an expected number of entering vehicles is the normalized addition to the route cost. Also, for each section the probability of an empty slot is determined for use in the calculation of the expected waiting time. The minimum route is actually determined in subroutine UPDATE. 68 DETERMINE ENTRANCE LOCATION; EQUALLY LIKELY. SELECT TRIP LENGTH BASED ON POISSON DISTRIBUTION AND MAXIMUM ALLOWABLE LENGTH. SELECT EQUALLY LIKELY DESTINATION. 1 [IORG = UNFRM(1,ENTS) s MASK3 = 31] GOOD 1.4.13.16 GO TO J LGT = NPOSN(MAXLEN) PNT = (IORG-1)*6 + LGT INT = DEST(PNT) 1 1_ —————— (Do $1,? 1 IDT(K) = INT.AND.MASK3 INT = INT/(2**5) 3 TS = K + 1 Figure 8.4. Flow diagram of subroutine ARRVL. 69 M = UNFRM(1,TS) IDEST = IDT(M) PARAM(3,4) = PARAM(3,4) + 1.0 1 THE ORIGIN, DESTINATION, AND LENGTH OF THE TRIP ARE NOW STORED IN THE VARIABLES IORG, IDEST, AND LGT RESPECTIVELY. PARAM(3,4) IS THE TOTAL NUMBER OF ARRIVALS. 1 CALL DRAND(ISEED,RNUM) ‘oooo ATRIB(1) = TNOW - XMTIM*ALOG(RNUM) JTRIB(1) = 1 CALL FILEM(1,NSET,QSET) JTRIB(1) = IDEST 9 IORG = IORG + 2 CALL FILEM(IORG,NSET,QSET) Figure B.4, (cont'd) r“--_______-_--___-.._._.m__-___-_-_- 70 Ic S(J) IS THE PROBABILITY SERVER J IS IDLE:] 1 [goN1 = 1.0/120.0 3 RX = 60.0*PARAM(3,3)] I r- ————————— -(D0 I=1,NTRIID I COST(I) = 0.0 3 IDX = 1 3 NM = NUMSEC(I) A = IST(I,1) 3 COST(I) = DEN(A,1,1)*CON1*2.0 S(1) = 1 - ((DEN(A,1,1) + DEN(A,2,1))*CON1) 00 = 5(1) I 1‘ ________ + B = IST(I,J) 3 L = J + 1 3 IODEN = DEN(B,J,1) S(J) = 1 - ((DEN(B,J,1) + DEN(B,L,1))*CON1) Q0 = 00*(1 - (1-S(J))**3) f' -------- -<:Do K£1,IDX:> I M:J-K8N=M+1 Y1 = DEN(B,M,1) - DEN(B,N,2) Y2 = DEN(B,M,2) - DEN(B,N,3) Y3 = DEN(B,M,3) — DEN(B,N,4) RATE = (Y1+Y2+Y3)/(2.0*TIME+TNOW-TLAST) I -—- IODHI = IODEN + RATE*RX r--_____-_- COST(I) = IODEN*CON1*2.0 + COST(I) IDX = IDX + 1 EW = PARAM(3,3)*(1-QO)/QO COST(I) = RX*COST(I) + 2.5*EW Figure B.5, Flow diagram of subroutine BEST. 71 Subroutine UPDATE 0f the programs necessary to merge with the GASP programs to construct the simulation model, subroutine UPDATE is the most complex. It executes seven fundamental Operations in the simulation: (1) (ii) (iii) (iv) (v) (vi) (fii) update the vehicles to their correct position on the highway. update file 2, ranking the queues based on the vehicles with the greatest waiting time. determine the routes between a specific origin-destination pair. check the availability of the slots required for a specific trip. check for a shifting possibility if the initial slots are occupied. store the trip when the reservation is completed. postpone routing of the trip if the necessary slots are occupied and the shifting algorithm finds a blockage. 72 The first action of the subroutine is to simulate the movement of vehicles on the highway. Each reservation list is represented by an octal word of 60 bit length with one in a bit indicating the slot is occupied. The slots are shifted from bit 59 of the preceding section to bit 0 of the succeeding section as shown in Figure B.6. Carry bits are used to hold the status of the progression and also for use in density computations. The SHIFT command is used to increment the slot status one location while the masking operation negates the effects of the end-around carry. The last Operation of this portion of the program is to update the density arrays if the time increment has exceeded the sampling interval. The second function assures the proper queue sequence when scheduling trips over the network. This is accomp- lished by storing the vehicle having the greatest waiting time in file 2 for each queue. Thus, at each update the vehicle with the longest waiting time is scheduled first, and each queue has the possibility of a one car removal from its length. The third Operation is the actual retrieval of trip information correSponding to the system under simulation. If the simple algorithm is being simulated, only one trip is removed; while if the controlled routing algorithm is being simulated, all the paths between an origin- destination pair must be retained for later manipulation. The program next determines the best route available for 73 [“11 [5910hl 4591—» progression of slots entrance exit entrance exit Figure B.6. Progression of slots in adjacent memory words. 31 2 32 3 33 1 2—7 2 2* 2a; 4 l 1 '2 9:3 Section 33 C A B I ' c—J Section 32 C A B [If ——1 Section 31 Figure B.7. Availability of slots for a vehicle requesting a trip from 1 to 4. TRNLST TRNSFT 1111110... Foooooon (i) TRNLST TRNSFT [I 1 1 1 1 1 °" [-0 1 1 1 1 ... ‘ (ii) * Figure B.8. (1) Status of system before applying shifting algorithm (ii) Status of system after shifting of vehicles and insertion of the scheduled trip. 71+ the trip by either calling subroutine BEST under the controlled routing algorithm or specifying the best route as the one stored under the simple scheme. The availability of the required slots is the next question to be answered by the program. The primary section is entered by checking the status of the entrance point. If this location is occupied, routing of the trip is postponed until the next update. In succeeding sections entry onto the highway can be gained by occupying one of three slots around the entrance point. The program proceeds in sequencial fashion to check for a vacancy in either slot A, B, or C as shown in Figure B.7. If all three slots are occupied, the shifting possibility is explored in an attempt to route the trip. The fifth section of the subroutine deals with the necessary Operations to incorporate the possibility of a vehicle shift. The algorithm requires an array TRNSFT to retain the status of each shift bit as a vehicle is allowed only one shift per section of highway. After finding a blockage in direct trip storage, the program attempts to shift vehicles on the highway. Using both the slot array TRNLST and shift status array TRNSFT, the subroutine alternately checks the slot status then the shift status. The algorithm terminates on three alternatives: (1) an Open slot is found; the trip is routed, or 75 (ii) the shift status of a slot is one; the trip routing is postponed, or (iii) all slots in the section are filled; the trip routing is postponed. A simple example is presented in Figure B.8, in which the first five slots are occupied and the trip can not be routed without the shift algorithm. As shown the shift status of all bits is zero so the trip can eventually be routed through the system. However, if any of the bits, except the first slot, had been previously shifted, the trip routing would have been postponed and the vehicle restored to the prOper queue. After verifying the necessary slots on all the sections of the current trip, the reservation is completed by changing the proper bit in array TRNLST and the corresponding bits, as required, in array TRNSFT for each section on the path. The density of each section is also incremented by one to account for the insertion. If the trip is instead blocked, postponement is accomplished by restoring the origin-destination pair to the prOper queue for processing during the next update. A flow diagram of subroutine UPDATE is presented in Figure B.9. 76 MASK 77777777777777777776B MASK1 #OOOOOOOOOOOOOOOOOOOB MASKQ = 2 3 MASKS = 2 IMASK(1) 2 3 IMASK(2) = h 3 IMASK(3) = 1 NROUT = O 3 ISFT = 1 3 MASK2 = 63 3 RTCAN = O LMAX O 3 TOTAL = 0.0 3 NVEH = O l SCHEDULE NEXT UPDATE. PARAM(4,1) GIVES THE TIME INTEGRAL OF THE TOTAL AVERAGE DENSITY. l ‘TNOW‘iTLAST + TIME? 1N0 TLAST = TNOW 3 IDEN = 1 _------—--—------ L--- ATRIB(1) = TNOW + PARAMGJ) YES CALL FILEM(1 ,NSET,QSET) F’"" DO IJ=1,36 E l L“known. = TOTAL + Dm(IJ,1,fl { |EARAM(4,1> = PARAM(#,1)+ PARAM(3,3)*TOTAL/56.0I Figure B.9. Flow diagram Of subroutine UPDATE. 77 D0 I-1,36 ------------- -l ICARRY = TRNLST(I 1).AND.MASK1 ICARRY = SHIFT(ICARRY 1) TRNLST(I,1) = SHIFT(TRNLST(I,1),1) TRNLST(I,1) = TRNLST(I,1).AND.MASK TRNSFT(I,1) = SHIFT(TRNSFT(I 1) 1) TRNSFT(I,1) = TRNSFT(I,1).AND.MASK L 630 be»? """"""" ‘1 CHECK CARRY BIT, BIT 60, OF PRESENT WORD FOR ENTRY INTO PREVIOUS WORD, BIT O. INCREASE DENSITY WITH CARRY AND DECREASE WITH ICARRY. _ CARRY = TRNLST(I,J).AND.MASK1 CARRY = SHIFT(CARRY 1) DEN(I,J-1,1) = DEN(I,J-1,1) - ICARRY + CARRY ICARRY = CARRY TRNLST(I,J—1) = TRNLST(I,J-1).OR.CARRY l I l L--___---__-__--_-- - CARRY = TRNSFT(I J).AND.MASK1 CARRY = SHIFT(CARRY,1) TRNSFT(I J-1) = TRNSFT(I,J-1).OR.CARRY TRNLST I,J) = SHIFT(TRNLST(I J) 1) TRNLST(I,J) = TRNLST(I J).AN1’>.MASK TRNSFT(I,J) = SHIFT(TRNSFT(I,J),1) TRNSFT(I,J) = TRNSFT(I,J).AND.MASK -----J l DEN(I,7,1) - ICARRfl I;TN(I,7,1) Figure B.9. (cont'd) ._ DEN(J,K,5-L) = DEN(J,K,L1-L:)-l ‘ IDEN = O v [C UPDATE FILE 2 FOR ROUTING. NROUT = NUMBER Oj 1 I I 1 1 L C VEHICLES IN FILE 2 TO BE ROUTED. NQ(K) = C NUMBER OF VEHICLES IN QUEUE K. 1 —-CQO K = 3,19It l NQ(K) 1: O ‘2] 1N0 ATRIB( 1) < rmow] lYES ALL RMOVE(MFE(K) ,K,NSET,QSET) s JTRIB(2) = K - § _, l 1 l I I l 1 YES NO k- CALL FILEM(2,NSET,QSET) 3 NROUT = NROUT + 1 NROUT = O 21er @ NO Figure B.9. (cont'd) 79 @--- DO NRT=1,NROUT CALL RMOVE(MFE(2),2 NSET,QSET) I IDEST = JTRIB(1) 3 IORG = JTRIB(2) PNT = TRPT(IORG,IDEST) [ITRIP = ITRIPS(RNT] -1, K7 [IST(L M) ITRIP.AND.MASK2 ITRIP ITRIP/( 2* *6) 1 - * YES [IST(L,M) = OE}~ I'NO t———— INUMSEC(L) = M ITRIPS(PNT) (2**42)|-—— NTRIP = L / , IIST(L,8) = 1 ?}Jg§i-q-(::) NO L— —————— -1PNT = PNT +_1] 89 __________,l I I I A I: IIST(L,8) _____-_____m._____________1 Figure B.9. (cont'd) 8O THE SECTIONS FOR THE TRIP ARE NOW STORED IN ARRAY IST(L,M) WITH NUMSEC(L) INDICATING THE NUMBER OF SECTIONS COMPRISING THE TRIP. NTRIP IS THE NUMBER OF TRIPS BETWEEN THE ORIGIN AND DESTINATION. GQOOO I NO re a ‘ lIRT =13] lYES' END = 3 s IBEST =1]——-—® I—u-[c DETERMINE BEST ROUTEJ I END=2 3 IBEST=fl |NTRIP = 1 fl—Y-Ei-OG) 1N0 EALL BEST( TIME ,N TRIP , TNow , TLAST , COST , PARAMfl I" ______ -> I l | _ 1 [ISLOT(M) = TRNLST(ISECT,M).AND.IMASK(J)I | 2 I O_______________...---___.l NO NO [.1 =-IND ? ISLOT(M)= 0 fl YES IYES |ISLOT(M)= 1IMASH(J)] ISH=IFT(M) -g]-v-I IISHIFT(M)= IMASK(J)I- --------- J Q Figure B.9. (cont'd) 83 CHECK FOR SHIFT POSSIBILITY. CHECK SECOND SLOT FIRST. THEN PROCEED TO OTHER SLOTS UNTIL AN OPEN SLOT IS FOUND OR THE SHIFT BIT IS ONE, IN WHICH CASE THE TRIP IS POSTPONED. QOOQQ [ISFT = TRNSFT(ISECT,M).AND.MASKAI ISFT = O ?:NO b<::) YES 1 I I I I l l I DO K=A,eo I SHIFT(MASKA ,1) MASKQ MASK5 MASK5.OR.MASKA ISLOT(M) = TRNLST(ISECT,M).AND.MASK4 * YES [ISLOT(M) = O ? ISLOT(M)=MASKA N0 ISHIFT(M)=MASK5 [ISFT = TRNSFT( ISECT,M) .AND.MASKA] @ r--____-_____.__u.__ Figure B.9. (cont'd) 84 [C STORE TRIP.I I <50 M=1,ND<— ———————— I ——-_I TRNLST