Team # 348 Page 1 of 18
The Optimal Number of Tollbooths Problem
Assumptions
The various effects of weather conditions on the traffic are negligible. All of the discussions are based on the assumption that the weather is normalfor driving.
The physical condition of toll lanes is desirable. There is no congestion problem due to the imperfection condition of toll lanes.
While waiting in queue, the distance between two waiting vehicles can be ignored.
Neglect the effects of different types of vehicles and different levels of driving skills. The time spent driving through a particular road with different drivers under different types of vehicles is assumed to be the same.
There is only one way of collecting tolls; the average service time toeach tollbooth is assumed to be the same.
Perfect signal systems and lane markings are assumed to be available, which lead vehicles passing through the toll plaza efficiently.
Figure-1 is an illustrative layout of a typical toll plaza.
figure -1
Definition of Terms and Parameters
Average Waiting Time
T: The average waiting time, which is defined to be the sum of Pre-toll-collection waiting time and Post-toll-collection waiting time. This is the key measurement of “optimal”.
Passing Rate
Passing rate is defined as the number of vehicles passing through a particular toll plaza per unit time. Note that “through” means the completion of the process of a vehicle driving from the entry of the plaza to the exit of it.
Other Parameters
: The expected number of vehiclesin the queuing system, including vehicles being served.
: The expected number of vehicles in queue, not including vehicles being served.
: The expected time spent in the queuing system, including time being served.
: The expected time spent waiting in queue.
: The average arrival rate.
: The averagetime between two consecutive arrivals.
: The average service rate per busy server(tollbooth).
: The average service time per vehicle.
: , is defined to be the service intensity.
Pn: The probability of having n vehicles in the whole system.
P0: The probability of the whole system being empty.
C: The number of tollbooth.
C*: The optimal number of tollbooth.
N0: The maximum number of vehicles per lane waiting in the departure area.
N: The capacity of the departure area, i.e. N=C*N0
(The detail of Queuing Theory can be found in appendix 1)
The Development of the Model
The construction of the model is based on “Queuing Theory”. See Appendix-1 for detailed explanation of the theory.
For simplicity, the model starts with a one-way road condition. The more complex model is an extension of the simple one.
One-way Road with Single Incoming Lane
One Tollbooth Per Incoming Lane (1-1 Model)
This is a typical queuing model, which is the simplest among all. Figure 2 illustrates the situation.
From “Queuing Theory”, we have
The expected number of vehicles in the queue:
The average waiting time:
We have listed a few possible values of and , and the resultant value of and T in Table 1.
（The unit of ，is vehicle per hour. The unit of T is hour）
/ / / T / / / / T100 / 450 / 0.06 / 0.0006 / 200 / 600 / 0.17 / 0.0008
200 / 450 / 0.36 / 0.0018 / 300 / 600 / 0.50 / 0.0017
300 / 450 / 1.33 / 0.0044 / 400 / 600 / 1.33 / 0.0033
400 / 450 / 7.11 / 0.0178 / 520 / 600 / 5.63 / 0.0108
420 / 450 / 13.07 / 0.0311 / 570 / 600 / 18.05 / 0.0317
Table 1
Obviously, whenis small, i.e. when average arrival rate is small or average serving rate is large, the above model is well enough to work efficiently. However, appears to be pretty large in reality. Hence, a model with several tollbooths per lane is considered.
Several Tollbooths per Incoming Lane (1-N Model)
Apparently, the model with several tollbooths per incoming lane reduces the congestion problem in the approach area. However, it tends to re-creates this problem in the departure area by having several vehicles back into one lane. Hence, an optimal number of tollbooths is required to minimize such problem. Figure-3 is an illustration of such a model.
To find the optimal number of tollbooths, the above model is decomposed into two queuing models.
Queuing Model I
This model is the process of a particular vehicle start queuing to the end of toll collection.
This is a typical model.
So,
Queuing Model II
This model is the process of a particular vehicle leaving the departure area. In this model, the arrival process and the services are used in an abstract sense, i.e. there is no physical service.
The arrival process follows Poisson process.
When in the Queuing Model I, the arrival rate of the whole system distributes in Poisson with parameter . Firstly, the tollbooths are working successively because that the number of vehicles waiting in queue is greater than one. Secondly, the interarrival time between two vehicles is just equivalent to the service time. From Queuing Model 1, it is clear that the service time obeys exponential distribution with parameter . Hence, for each lane, the arrival rate follows Poisson distribution with parameter . Since all tollbooths are distributed independently and identically, therefore, the arrival rate distributes in Poisson with parameter .
When in the Queuing Model I, the arrival rate of the whole system distributes in Poisson with parameter . This is because that there is no waiting time for paying tolls so that the arrival process is approximately the same as in the Queuing Model I.
The service time of this model is distributed exponentially with parameter sigma. Note that the service time means from the point when a vehicle just reaches the exit to the point when it just leaves exit.
Since the physical size of the departure area is a certain value, hence there is a limitation on its capacity N.
To vehicle A, the waiting timeis from t1 to t2. The service timeis from t2 to t3.
From the analysis above, Queuing Model II is clearly a M/M/1/N model.
Hence, the following is obtained:
The Determination of the Optimal Number of Tollbooths
To determine the optimal number of tollbooths, the average waiting time T is used in the discussion, where . Given all other condition, T is a function of C. To find an optimal number of tollbooths C* is equivalent as to find C so that T is minimized, i.e. .
Table-2 gives some value of C* under certain ，，and N0.
(See the program of Matlab inAppendix 2)
/ / / N0 / C* / T350 / 360 / 320 / 8 / 2 / 0.0151
600 / 360 / 320 / 8 / 3 / 0.0386
900 / 360 / 320 / 8 / 4 / 0.0601
1200 / 360 / 320 / 8 / 5 / 0.0810
600 / 360 / 350 / 8 / 3 / 0.0349
600 / 360 / 420 / 8 / 3 / 0.0280
600 / 360 / 560 / 8 / 3 / 0.0152
600 / 360 / 320 / 5 / 3 / 0.0229
600 / 360 / 320 / 10 / 3 / 0.0490
Table 2—1
/ / / N0 / C* / T420 / 450 / 400 / 8 / 2 / 0.0108
800 / 450 / 400 / 8 / 3 / 0.0335
1200 / 450 / 400 / 8 / 4 / 0.0515
1500 / 450 / 400 / 8 / 5 / 0.0648
800 / 450 / 500 / 8 / 3 / 0.0259
800 / 450 / 600 / 8 / 3 / 0.0204
800 / 450 / 750 / 8 / 3 / 0.0121
800 / 450 / 400 / 5 / 3 / 0.0199
800 / 450 / 400 / 10 / 3 / 0.0421
Table 2—2
/ / / N0 / C* / T530 / 600 / 500 / 8 / 2 / 0.0081
1000 / 600 / 500 / 8 / 3 / 0.0248
1500 / 600 / 500 / 8 / 4 / 0.0385
2000 / 600 / 500 / 8 / 5 / 0.0519
1000 / 600 / 650 / 8 / 3 / 0.0184
1000 / 600 / 800 / 8 / 3 / 0.0136
1000 / 600 / 950 / 8 / 3 / 0.0085
1000 / 600 / 500 / 5 / 3 / 0.0148
1000 / 600 / 500 / 10 / 3 / 0.0315
Table 2—3
Supplementary to table 2-3
a．The unit of ，，is vehicle per hour
b．T is the average waiting time, its unit is hour.
c． C=1 is the situation where there is only one tollbooth per incoming lane ；is the situation where there are several tollbooths per incoming lane, and C is the critical value at which T is minimized.
Analysing Table-2 , the conclusion is as follows,
Given a certain value of , the number of vehicles arriving per hour is the main factor affecting C*. The more the vehicles arrive per hour, the larger the C* is.
has tiny impact on C*, but has great impact on average waiting time T, the larger the , the shorter the T.
When N0 is relatively small, it does not affect C* effectively, but highly related to the average waiting time T. The larger the N0, the larger the T.
When N0 is relatively large, this model no longer follows the “Queuing Theory”..
The Comparison of Two Models
/ / C / N0 / / T / / / C / N0 / / T360 / 220 / 1 / 0.004 / 450 / 270 / 1 / 0.003
2 / 5 / 200 / 0.008 / 2 / 8 / 250 / 0.011
300 / 1 / 0.014 / 380 / 1 / 0.012
2 / 5 / 270 / 0.009 / 2 / 8 / 350 / 0.011
340 / 1 / 0.047 / 420 / 1 / 0.031
2 / 5 / 300 / 0.009 / 2 / 8 / 380 / 0.012
Table 3.1 / Table 3.2
/ / C / N0 / / T
600 / 400 / 1 / 0.003
2 / 10 / 380 / 0.010
500 / 1 / 0.008
2 / 10 / 480 / 0.009
570 / 1 / 0.032
2 / 10 / 540 / 0.010
Table 3.3
It is obvious that when , the model with one booth per incoming lane will causeinfinite queues. Under this situation, only the model with several booths per incoming lane is the suitable one.
In presenting the situation when, the following three charts are used.
- Given all other factors are fixed, there exists a, such that when, it is more efficient to use several booths per lane.
- When, C usually takes 2.
- is related to all factors, ,and N0. The larger the, the larger the.
One-way Road with Several Incoming Lane
n incoming lanes to n tollbooths (N-N Model)
This model is obtained simply by adding up the 1-1 model. This model is well accommodated to those quite streets.
m incoming lanes to mn tollbooths (M-MN Model)
This model is obtained by adding up the 1-N model. However, unlike the N-N model, it is necessary to approximate an average flow of vehicles. This is close to reality in the sense that vehicles canlanes before entering to the approach area. After determining the average flow, an optimal number of tollbooth per lane C* can be calculated. Multiply C* by M gives the total number of tollbooths required. Nevertheless, this is not the best way of obtaining optimal. To solve such a problem, taking integer of mC* is required instead of critical value C*.
m lanes to n tollbooths(M—N model)
In the real life, when one of the tollbooths has the less queuing lengths, serval vehicles from different lanes will driver to it at one time. The condition like this is out of the queuing theory, so we developed M—N model to improve M-MN model to be more practical and we can get an exact result through computer simulation.
(See thesimulation arithmetic and program of M—N model in appendix 3)
The Extension of the Model
The above discussion suggests that M-N is the best model among all. However, several problems are posed by the model. Firstly, the optimal number of tollbooths appears to be very large, which uneconomical and inconvenient for management. Secondly, when is very large, the congestion problem still exists, especially in the departure area. N-N Model does not have such a problem because there is only one tollbooth per lane when the vehicles leaving the plaza. Therefore, a further two models are built based on the advantage of previous models.
Note that the passing rate is adopted for evaluating the model.
Advanced M-N Model
The following is an illustration of the model:
Let the number of tollbooths be twice the number of travel lane, i.e..
Divide tollbooths into two equal parts, the upper one (part A) and the bottom one (part B),with m tollbooths in each part. Meanwhile, we set a signal light at the entry of tollbooth. Vehicles enter into tollbooth when green light is on; stop while red light is on.
The approach area should be designed to satisfy the following condition: each vehicle is able to finish the process of driving from the entry to the farthest tollbooths within a period of(from when it starts to when it stops).
Let thosem vehicles in the 1st row enter the part A of the tollbooths first (refer to figure-5.1). When doing this, it is better to have each lane conforming to only one tollbooth.
When the 1st row arrives at the part A of tollbooths and start paying tolls, the m vehicles in the 2nd row are signaled to enter the part B of the tollbooths (refer to figure-5.2). The time spent in this process is .
When the 2nd row arrives at the part B and start paying tolls, the m vehicles in the 3rd row are allowed to enter part A (refer to figure-5.3). At this point, the 1st m vehicles have spent on paying the toll.
When the m vehicles in the 3rd row arrive at thepart A of tollbooths and start paying tolls, the 1st row has finished paying tolls and leaves the tollbooths. It is clear that there are only m vehicles depart from the toll plaza. Consequently, these m vehicles are able to leave without any congestion (refer to figure-5.4).
So and forth, it is ensured there are only m vehicles leaving the tollbooths at a time which causes no congestion at all.
The advantages of such arrangements
This model can easily be extend to the situation that c=3m with some simple modifications.Under such situation, the approach area should be designed to satisfy the condition that each vehicle is able to finish the process of driving from the entry to the farthest tollbooths within a period of. Under such circumstance, motorists are demanded to have a better control of time to improve the efficiency. However, it is far away from practices. Furthermore, once there is an accident, it will be troublesome. Last but not least, the construction and management can be costly for such a large toll plaza.
Demanding vehicles entering in turns ensures the smoothness of the traffic outflow. Since each vehicle is provided with a travel lane both in the approach area and the departure area, there will be no travel disruption caused by lacking of travel lane.Here, we adopt the advantage of N-N model, decrease the waiting time to the greatest extent. Furthermore, 2m vehicles are allowed to enter the tollbooths in a period of , which ease the congestion further in the approach area. Such is also the advantage of M-N model.
The Assessment of The Model:
With N-N model:The pre-toll-collection waiting time is reduced.Since the time spent after arriving at the tollbooths is the same for all vehicles, only pre-toll-collection waiting time is considered. In N-N model, the pre-toll-collection waiting time for vehicles in the xth row is, whereas it is in the advanced model.
With M-N model:The congestion in the departure area is better prevented in the advanced model. Still suppose there are 2m tollbooths to make a comparison in an easier way.
In M-N model, 2m vehicles leave the tollbooths in the period of , while only m vehicles leave in the advanced model. Although, M-N model appears to be more efficient in the current stage, it does not mean M-N model is more efficient in leaving the departure area. From the discussion above, we know that in M-N model each vehicle spends a period much longe than , squeezing back into travel lane. This disadvantage is more significant when congestion is already existed in M-N model. In the advanced model, each vehicle is able to get through the toll plaza in time after paying the toll. Therefore, much more vehicles are able to travel through the toll plaza in the advanced model in the same units time.
F1 Model
When the number of travel lanes is relatively small, e.g. n=2, another model is recommended. As this model is somewhat like the repairing zone in F1 tournament,it is called F1 model.
The design of the model is as follows,
Let the distance between the entry to No.2 tollbooth satisfy the condition that each vehicle is able to finish this length within a period of (from when it starts to when it stops).
Set two signal lights at the entry to the toll plaza. Number‘1’ or ‘2’ shows up when the green light is on, which guides each vehicle to the correct tollbooth. Otherwise, the red light is on.
Since No.1 tollbooth is located at the entry to the toll plaza, it takes no time for each vehicle to enter the tollbooth from the entry. Due to the lateral design, vehicles will not interfere each other.
For this is a symmetrical design, we only make a detailed analysis of one side:
The first vehicle is allowed to enter No.1 tollbooth, while the second vehicle to No.2 tollbooth (refer to figure-7.1).
After a period of, the first vehicle pays the toll and leaves the booth, while the second vehicle arrives at No.2 tollbooth and starts paying the toll. Meanwhile, the third vehicle is allowed to enter NO.1 tollbooth and starts the process (refer to figure-7.2).
After another period of, the second and the third vehicles finish paying the toll at the same time. Since there is a certain distance between these two vehicles, congestion will not be caused. When passing No.2 tollbooth, the first vehicle is running at a quite fast speed. Generally speaking, it will not take a longer period than for the first vehicle to go through No.1 and No.2 tollbooth. Thus, congestion will not be caused between these two vehicles as well.
Then, the forth and the fifth vehicles are allowed to enter No.1 and No.2 tollbooth separately. The rest may be deduced by analogy.
The Assessment of The Model:
With N-N model:The pre-toll-collection waiting time is shorter for F1 model. The waiting time for the xthvehicle is for odd x and for even x.
With M-N model:Suppose there are two travel lanes with four tollbooths in M-N model. Then, eight vehicles leave the tollbooths in each period of. But in F1 model, six vehicles leave in the same period. Taking the time spent on waiting in the departure area in M-N model into consideration, it is clear that F1 model is more efficient.
With advanced M-N model: In advanced M-N model, four vehicles leave the tollbooths in each period of. Apparently, F1 model is the most excellent under the condition of two travel lanes.
According to the practical demands of traffic conditions, F1 model can easily be deduced to the circumstance of six tollbooths (we can set the former four tollbooths laterally, which will not obstruct the road for the latter vehicles). This design brings out an extra advantage, that is, the total area of the toll plaza is decreased, especially where width is limited. In the daily practice, it may be quite difficult for some larger vehicles such as trucks to enter No.1 tollbooth. So the construction of the tollbooth becomes more difficult when applying F1 model. Another solution to this problem is to demand those larger vehicles to enter No.2 tollbooths, due to which the management of the toll plaza becomes more difficult.
Through the discussion above, we have developed two models that are more practical. Traffic jam is efficiently eased by decreasing the congestion in the departure area when applying these two models. The high efficiency is also guaranteed with a small number of tollbooths. When there are less travel lanes, F1 model is recommended. Otherwise, advanced M-N model is more practical. When constructing a toll plaza, a model is determined by observing the flow of vehicles during the rush hours. The operation of the tollbooths can vary according to the traffic flows in order to save the cost.
Two-way Road Condition
N-N Model, M-N Model and the Advanced Model can be easily extended to the situation where the road is a two-way one. However, the F1 model can only be used in a two-way road with only one lane on each direction.
Conclusion
With the average waiting time and passing rate as the standards, we determine the optimal number of tollbooths to deploy in a barrier-toll plaza on the basis of queuing theory combined with computer simulation.
When the traffic flow is not very heavy, N-N model is a good choice. Otherwise, M-MN model can ease the congestion in the approach area in N-N model. As an adjustment of M-MN model, M-N model is more practical.