Queueing Theory

1. A city builds a new toll road with a toll plaza and electronic toll tags. Due to the characteristics of the reading mechanism for the toll tags and the database used to charge drivers' accounts, the reading times for each toll tag can vary (cars have to wait for the green light indicating successful reading and drivers are assumed to react instantaneously) and behaves like a Poisson process with an average tag read rate of 20 tags per minute (this is not intended to be realistic). Based on the current traffic patterns, city planners determined that during normal hours (non rush hours) the likelihood of a car arriving at any given time is the same and estimate that during those times during the day the average number of cars using the road will be 1100 per hour while at night on average 650 cars will use the road per hour.

a) Assuming that in order to save money, the city wants to build only one toll booth (with one reader), and ignoring transition effects when traffic patterns change, determine the average amount of time that cars will be delayed due to the toll plaza under each of the normal traffic conditions (normal hours in the day time and at night). Also determine for each of the traffic patterns what the expected number of cars at the toll plaza is.

b) To accelerate the process, the city investigates the possibility to establish multiple toll booths with toll tag readers but without any individual waiting areas (each car simply drives through the next empty toll booth). Assuming that two toll booths are used, compute the average delay time at the toll plaza as well as the average number of cars at the toll plaza for both of the normal traffic conditions (day time and night). Also compute the average number of cars that are waiting in line at the toll plaza (i.e. the cars waiting but not at a toll booth).

c) Given the scenario from part b), how many toll booths with toll tag readers would the city have to set up in order to reduce the average number of cars waiting line below 8 (i.e. to reduce the length of the traffic jam caused by the toll booths below 50m) during the day time. Also, how many toll booths could be closed while still ensuring the same limit at night). How many toll booths would be needed if rather than reducing the average number of cars waiting in line below 8, the goal would be to reduce the probability that there will be more than 8 cars in line at any given time below 1%. Again, how many toll booths could be closed at night while still ensuring the same limit.

2. Consider again the problem from Question 1 but with the addition of the consideration that during rush hour the planners estimate that the traffic volume will be 4000 cars per hour.

a) What is the minimum number of toll booths (i.e. toll tag readers) that are required in order for the toll plaza to be able to handle rush hour traffice (i.e. to avoid an ever increasing line) ? How many toll booths would be necessary to keep the average number of cars at the toll plaza during rush hour below 16 ?

b) Since the area available for the toll plaza is limited and cars backing up into beyond the plaza area would be dangerous, city planners add an alternate (but slower) side road at the beginning of the plaza and put in place a rule that if a car arrives while the line of waiting cars is backed up beyond up to the exit, this car has to take the alternate route (while cars are prohibited from taking this alternate route if the line is shorter). Assuming that the line is long enough for exactly 10 cars, determine the expected number of cars per hour that will have to take the alternate route (and thus the amount of lost revenue for the toll authority) during each of the three traffic conditions (normal day time, normal night, and rush hour) if there were only one toll booth (with one tag reader).

c) Given the scenario from part b), what would the number of toll booths have to be under each of the three traffic conditions if we would like the percentage of cars that have to take the alternate route to be below 5% ?

Queueing Networks

3. After operating the toll plaza from part 1. for a while, the city planners find out that the mixture of different sizes of cars cause a lot of problems at the toll booths and decide to build separate toll plaza areas with separate lines for each of the car types. In particular, they decide to separate cars, SUVs, and trucks into separate areas. Through observation they determined that of all the vehicles arriving, 50% are cars, 30% are SUVs, and 20% are trucks.

a) How many toll booths does each of the toll booth areas need to be able to handle the three traffic conditions (i.e. to not have an ever increasing line) ?

b) Using the minimal number of toll booths from part a), how long a delay will each of the different types of cars incur at the toll plaza ?

4. After a year, the city planners expand the toll road from part 3, extending it past the next exit and on-ramp, also adding another toll booth there. From traffic observations it is found that of the cars passing the first toll plaza, 25% leave at the exit and that during all traffic conditions
750 cars per hour enter at the new on-ramp. To address this new setting, two possibilities for the new toll plaza are considered. The first adds another toll plaza on the main road right after the exit and on-ramp, requiring all cars to pass the new toll booths to pay for the second half of the road. The second builds two new toll plazas, one at the exit and one at the on-ramp (the first being used to reduce the fare of the drivers who exit here and the second to charge the drivers who enter).

a) Given both of these settings, what are the minimum number of toll booths in each of the toll plazas in order for none of the lines to grow uncontrollably during any of the three traffic conditions ? Which one requires fewer toll booths ?

b) Given that the city wants to make sure that the probability that the number of vehicles at any toll plaza grows larger than 10 is below 5%, how many toll booths have to be built for each of the two toll plaza arrangements ?

c) Assuming that the city decides that they want to build a total of 10 toll booths, either in a 5 / 5 arrangement for the first scenario (i.e. 5 at the first toll plaza and 5 at the second one), or in a 6 / 2 / 2 arrangement (6 at the first toll plaza, 2 at the exit plaza, and 2 at the on-ramp plaza), determine the expected number of cars in each toll plaza as well as the expected total delay of a car due to the toll system under each of the three traffic conditions. Also determine what the expected delay for the three different routes (entering before the first plaza but entering in the middle, traveling the whole route, and entering the system at the on-ramp) would be for the three traffic conditions.

5. Consider the second setting from scenario 4c) (i.e. the 6 / 2 / 2 organization).

a) Program a simulation for this setting and use it to verify your results from part 4c). Not that since the arrival and toll tag reading processes are poisson, the timing of the next arrival or departure can be determined using a random number generator for an exponential distribution.

b) Use your simulator to see what happens to the queue lengths when the traffic pattern suddenly changes from normal night to rush hour and back. Plot the queue length as a function of time for the transition period (averaging over at least 20 simulations).

c) Add the space limit from part 2b) to each of the toll plazas (i.e. that the maximum number of cars in each toll plaza has to be less than or equal to 10 or any additional arriving car has to take an alternate route without a toll). Use the simulation to re-evaluate the average queue length, delay time, and the percentage of cars that have to take the alternate route in this setting for each of the three traffic conditions (you do not have to look at traffic pattern transitions).