Transportation Engineering

CETRANSPO
MODULE 4
Queuing Model
Theory and
Analysis
OBJECTIVES

uAfter completing this module, the student must be able to:

q describe queuing;
q discuss queueing modules and interpret Kendall’s notation ; and
q analyze queueing using different models.
Introduction
Queuing

Queueing is the study of traffic behavior

near a certain section where demand
exceeds available capacity
Traffic Queue
Under extreme
conditions,
queuing delay
can account for
90% or more of a
motorist’s total
trip travel time.
Cumulative Input-Output Diagram
(Newell Curve)
Traffic Queue
Queuing Theory

• Waiting behavior
• Queuing and servicing models
• Queuing disciplines
Importance of Queuing Theory

• Retail
• Telecommunications
• Transportation
• Finance and banking
• Computing
• Logistics
• Project management
Understanding Queuing Theory
• Arrival, which refers to the arrival of customers who
are first in line.
• Capacity, which refers to the system’s limit with
regards to the number of customers in line.
• Service, which refers to service points where
service occurs.
• Departure or output, which refers to customers
leaving the system after receiving service.
Little’s Formula

L = λW
The average number of customers (L) is calculated from the average customer arrival
rate (λ) multiplied by the average service time for a customer (W).

If the arrival rate doubles but the service time remains constant, the number
of customers will rise twofold. By the same logic, should the average service time
double without the arrival rate changing, the number of customers will double,
as well. If customers arrive at the rate of 10 per hour and stay in the restaurant
for an hour (1), the average numbers of customers at any time will be 10.

L = 10*1 = 10
Kendall’s Notation

• A for the arrival process.

• S for the mathematical distribution of the service time.
• c for the number of servers.
• K for the capacity of the queue (if not unlimited).
• N for the number of possible customers (if not infinite).
• D for the queuing discipline (first-in, first-out by default).
Queuing models
1. Single Channel, Single Phase
A single-channel, single-phase business has only one server. As soon as
a customer is attended to, they receive full service.
2. Single Channel, Multi Phase
A single-channel, multi-phase business has one server and a multi-step
servicing process.
3. Multi Channel, Single Phase
A multi-channel, single-phase business has several servers and a one-
step servicing process.
4. Multi Channel, Multi Phase
A multi-channel, multi-phase business has several servers and a multi-
step servicing process.
Queuing Disciplines

First-in, first-out queuing

Last-in

Priority queuing
Real Life Causes of Queue Generation
For Roads:
§ Geometric Bottlenecks (lane drops, hard curves, hills)
§ Accidents and Incident
§ Traffic Signals and Intersection Controls
§ At-Grade Crossings with other Modes (Railroad crossings,
drawbridges, etc.)
§ Toll Booths
§ "Gawker" Effect
§ Inclement Weather
Real Life Causes of Queue Generation
o For Trains and Transit:
§ Platform Capacities
§ Fare Gates
§ Ticket Windows/Ticket Machines
§ Minimum Safe Separation for Trains
§ Security Checkpoints
§ Efficiency of Trains Entering and Leaving Station (number of
tracks, switches, etc.)
Real Life Causes of Queue Generation
o For Aviation and Airports:
§ Runways
§ Designated Minimum Safe Following Distances for Planes (by
government)
§ Physical Minimum Safe Following Distance for Planes (creation of
turbulence, etc.)
§ Available Airspace for Approaches and Departures
§ Ticketing Counters/Check-in Procedures
§ Security Checkpoints
§ Baggage Systems
§ Terminal Capacity for Planes
§ Internal Terminal Capacity for Passengers
§ Inclement Weather
Real Life Causes of Queue Generation
o For Water and Maritime:
§ Locks and Dams
§ Port Capacities
§ Minimum "Safe" Distances (determined by government and
physics)
§ Inclement Weather
Real Life Causes of Queue Generation

o For Space Flight:

§ Launch Capacity
§ Minimum Spacings between Orbital Vehicles
§ Inclement Weather on Earth
§ Unfavorable Celestial Conditions
Dimensions of Queuing Model
Two possible distributions of the time between the arrival of
successive vehicles

1. Equal time intervals (derived from the assumption of uniform,

deterministic arrivals)

2. Exponentially distributed time intervals (derived from the

assumption of Poisson-distributed arrivals).
Dimensions of Queuing Model

Ø Queuing models are often identified by three alphanumeric

values.
Ø The first value indicates the arrival rate assumption, the second
value gives the departure rate assumption, and the third value
indicates the number of departure channels.
Ø For traffic arrival and departure assumptions, the uniform,
deterministic distribution is denoted D and the exponential
distribution is denoted M.
D/D/1 Model

The D/D/1 queue lends itself to an intuitive graphical or

mathematical solution that is best illustrated by an
example.
D/D/1 Model
D/D/1 Model
D/D/1 Model

total number of vehicle arrivals at time t

v 8t for t ≤ 20 min
v 160 + 2(t – 20) for t > 20 min

vehicle departure

v 4t for all t
D/D/1 Model

160 + 2(t − 20)= 4t

t= 60 minutes

• 240 vehicles will have arrived and

departed (4 veh/min × 60 min)
D/D/1 Model

"#(%#) "#('#)
• 𝐷! = %
+ %
= 2400 𝑣𝑒ℎ − 𝑚𝑖𝑛

• average delay per vehicle = 10 minutes

(2400 veh-min/240 veh)

• average queue length = 40 vehicles

(2400 veh-min/60 min)
Transportation Engineering
CETRANSPO
MODULE 4
Queuing Model
Theory and
Analysis
OBJECTIVES

uAfter completing this module, the student must be able to:

q describe queuing;
q discuss queueing modules and interpret Kendall’s notation ; and
q analyze queueing using different models.
D/D/1 Model
D/D/1 Model
D/D/1 Model

!"#$.#&
average delay per vehicle for the non–priority-pass vehicles is 8.86 min !'".("
.
D/D/1 Model
D/D/1 Model

)$$.!$
Average delay per vehicle for the priority-pass vehicles is 7.89 min $'.')
The priority pass saves an average of 0.97 min, or about 58.2 seconds.
D/D/1 Model
D/D/1 Model
D/D/1 Model
D/D/1 Model
D/D/1 Model
D/D/1 Model
D/D/1 Model
M/D/1 Model
M/D/1 Model
M/D/1 Model
M/D/1 Model
M/D/1 Model
M/D/1 Model
M/M/1 Model
M/M/1 Model
M/M/1 Model
M/M/N Model
M/M/N Model
M/M/N Model
M/M/N Model
M/M/N Model
M/M/N Model
M/M/N Model
M/M/N Model
M/M/N Model
M/M/N Model
M/M/N Model
M/M/N Model
Summary
ü Queuing
ü Kendall’s Notation
ü Queuing Models
ü Sample Computations
Questions?
4
Queuing Model
Theory and
Analysis

Outline

4. Queing Model Theory and Analysis

4.1 Dimensions of Queueing Model
4.2 D/D/1 Queing
4.3 M/D/1 Queing
4.4 M/M/1 Queing
4.5 M/M/N Queing

Learning Outcomes
1. Describe what is queueing;
2. Discuss queueing modules and interpret Kendall’s notation; and
3. Analyze queueing using different models.
INTRODUCTION
The formation of traffic queues during congested periods is a source of considerable delay
and results in a loss of highway performance. Under extreme conditions, queuing delay can
account for 90% or more of a motorist’s total trip travel time. Given this, it is essential in traffic
analysis to develop a clear understanding of the characteristics of queue formation and
dissipation along with mathematical formulations that can predict queuing-related elements.
As is well known, the problem of queuing is not unique to traffic analysis. Many non-
transportation fields, such as the design and operation of industrial plants, retail stores, service-
oriented industries, and computer networks, must also give serious consideration to the problem
of queuing. The impact of queues on performance and productivity in manufacturing, retailing,
and other fields has led to numerous theories of queuing behavior (the process by which queues
form and dissipate). As will be shown, the models of traffic flow presented earlier (uniform,
deterministic arrivals and Poisson arrivals) will form the basis for studying traffic queues within
the more general context of queuing theory.

Queueing
Queueing is the study of traffic behavior near a certain section where demand exceeds
available capacity. Queues can be seen in many common situations: boarding a bus or train or
plane, freeway bottlenecks, shopping checkout, exiting a doorway at the end of class, waiting for
a computer in the lab, a hamburger at McDonald’s, or a haircut at the barber. In transportation
engineering, queueing can occur at red lights, stop signs, bottlenecks, or any design-based or
traffic-based flow constriction. When not dealt with properly, queues can result in severe
network congestion or "gridlock" conditions, therefore making them something important to be
studied and understood by engineers.

Traffic Queue
The formation of traffic queues during congested periods is a source of considerable delay
and results in a loss of highway performance. Under extreme conditions, queuing delay can
account for 90% or more of a motorist’s total trip travel time. Given this, it is essential in traffic
analysis to develop a clear understanding of the characteristics of queue formation and
dissipation along with mathematical formulations that can predict queuing-related elements.
As is well known, the problem of queuing is not unique to traffic analysis. Many non-
transportation fields, such as the design and operation of industrial plants, retail stores, service-
oriented industries, and computer networks, must also give serious consideration to the problem
of queuing. The impact of queues on performance and productivity in manufacturing, retailing,
and other fields has led to numerous theories of queuing behavior (the process by which queues
form and dissipate). As will be shown, the models of traffic flow presented earlier (uniform,
deterministic arrivals and Poisson arrivals) will form the basis for studying traffic queues within
the more general context of queuing theory.
 Figure 1 Newell Curve showing the cumulative inputs and outputs from a queue

Cumulative Input-Output Diagram (Newell Curve)

Based on the departure rate and arrival rate pair data, the delay of every individual vehicle
can be obtained. Using the input-output (I/O) queueing diagram shown in Figure 1, it is possible
to find the delay for every individual vehicle: the delay of the ith vehicle is time of departure –
time of arrival ( 𝑡2−𝑡1). Total delay is the sum of the delays of each vehicle, which is the area in
the triangle between the arrival (A(t)) and departure (D(t)) curves.

Distributions
• Arrival Distribution - Deterministic (uniform) OR Random (e.g. Poisson)
• Service Distribution - Deterministic OR Random
Characterizing Queues
• Queue Length Characteristics - Finite or Infinite
• Number of Channels - Number of Waiting Lines

Use the following notation:

• Arrival Rate = 𝜆
• Departure Rate = 𝜇
• Utilization Rate 𝜌 = 𝜌=𝜆/𝜇

Degree of Saturation
• Oversaturated: 𝜆>𝜇
• Undersaturated: 𝜆<𝑚𝑢
• Saturated: 𝜆=𝜇
Queueing Theory
The queuing theory studies and models the inner dynamics of queues, and ways in which
lines could be managed more efficiently. It is a massive topic, which includes many different
facets of the waiting experience, such as:
• Waiting behavior
• Queuing and servicing models
• Queuing disciplines
Queuing theory is the mathematical study of the formation and function of waiting lines.
Queuing theory assesses the arrival process, service process, customer flow and other
components of the waiting experience. The application of queuing theory helps businesses
improve the satisfaction of customers and employees, increase customer flow.

The history of queuing theory

The first paper on queuing theory was The Theory of Probabilities and Telephone
Conversations by Agner Krarup Erlang, published in 1909. Erlang worked with the Copenhagen
Telephone Company and wanted to determine how many telephone circuits were necessary to
prevent customers from waiting too long. Erlang’s findings were applicable to many other fields,
as telecommunications wasn’t the only industry suffering from long waiting times. This
realization prompted him to develop his theory further into what later became known as the
modern queuing theory. Erlang’s role in developing the queuing theory has been recognized by
naming the international unit for telephone traffic the erlang (E) in his honor. A single cord circuit
has the capacity to be used for 60 minutes in one hour. Whole 60 minutes of traffic constitute 1
erlang.

Importance of Queuing Theory

Queues are a way of dealing with the imbalance between supply and demand. As long as
demand (the number of customers) exceeds supply (capacity and the number of service points).
Queuing theory provides the tools and understanding for optimizing queues. As such, it has
applications in many different industries, including but not limited to:

• Retail
• Telecommunications
• Transportation
• Finance and banking
• Computing
• Logistics
• Project management

No matter the industry, as long as there is some waiting involved, businesses tend to bank
on queuing theory. Especially in customer-facing industries, managing waiting lines is becoming
an increasingly bigger part of the experience package.
 Because although not many customers admit to it, queues are among the biggest deciding
factors when it comes to satisfaction. Waiting experiences can even impact the overall
impression from the interaction with a business. Understanding the underlying mechanism of
queues gives businesses the opportunity to better prepare for customers and optimize their
processes.

Understanding the Queuing Theory

When looking at queues through the lens of the queuing theory, it’s not enough to only
talk about the length of the queue. The queuing process can be broken down into four equally
vital components:

• Arrival, which refers to the arrival of customers who are first in line.
• Capacity, which refers to the system’s limit with regards to the number of customers in
line.
• Service, which refers to service points where service occurs.
• Departure or output, which refers to customers leaving the system after receiving service.
In turn, all of these aspects of queuing can be further broken down into smaller segments,
i.e. arrival and departure rates, average service completion times, queuing discipline, number of
servers, etc. The system has one or more servers which manage customers from their arrival to
their departure. The classic example of such a design is a cashier at a supermarket.

Little's Formula

The average queue size (measured in vehicles) equals the arrival rate (vehicles per unit
time) multiplied by the average waiting time (both delay time in queue plus service time) (in units
of time). This result is independent of particular arrival distributions and, while perhaps obvious,
is an important fundamental principle that was not proven until 1961.

John Little came up with a law that describes the relationship between the distribution
rate of customers and time spent by them in the system. Little’s theorem can be summarized in
this short equation:

L = λW

The average number of customers (L) is calculated from the average customer arrival rate
(λ) multiplied by the average service time for a customer (W). To understand this dynamic,
consider your typical restaurant:

If the arrival rate doubles but the service time remains constant, the number of customers
will rise twofold. By the same logic, should the average service time double without the arrival
rate changing, the number of customers will double, as well. If customers arrive at the rate of 10
per hour and stay in the restaurant for an hour (1), the average numbers of customers at any
time will be 10.

L = 10*1 = 10

Kendall’s Notation
Queuing theory studies the behavior of single queues, also called queuing nodes. David
George Kendall proposed a system for classifying these queuing nodes — the so-called Kendall’s
notation. According to Kendall’s notation, queuing nodes are described as A/S/c/K/N/D:

• A for the arrival process.

• S for the mathematical distribution of the service time.
• c for the number of servers.
• K for the capacity of the queue (if not unlimited).
• N for the number of possible customers (if not infinite).
• D for the queuing discipline (first-in, first-out by default).

Depending on the theoretical model used, the last three nodes can be omitted from the
equation, making it a more manageable A/S/c. Based on how each of the parameters is specified,
we get different queuing models. Some of the more well-known models are M/M/1, M/M/c (also
called Erlang-C model), M/G/1, M/D/1 and more.

These models deal with the mathematical theory of probability and are used to describe
models of distribution in computation and logistics. The M in the name refers to a Markov chain
— a model describing a sequence of possible events whose probability depends on the state
attained in a previous event. In simpler terms, the future and past states of the system are
independent. What happens tomorrow depends on today’s state and nothing else.

Queuing models
To determine the queuing model we’re dealing with, we need to look at two main
parameters: the number of channels (or servers) and the number of phases of service. Think of
channels as the number of stations where you receive service, and phases as the number of steps
you need to get full service.
Each parameter can take two values: single (one), or multi (several). Different
combinations of channels and phases give us four distinct types of queue management:

1. Single Channel, Single Phase

A single-channel, single-phase business has only one server. As soon as a customer
is attended to, they receive full service. Example: an automated car wash.
 2. Single Channel, Multi Phase
A single-channel, multi-phase business has one server and a multi-step servicing
process. Example: retail banking, with different counters for withdrawals, deposits, new
accounts, etc.

3. Multi Channel, Single Phase

A multi-channel, single-phase business has several servers and a one-step
servicing process. Example: airline ticket counter with separate queues for business class
and economy class passengers.

4. Multi Channel, Multi Phase

A multi-channel, multi-phase business has several servers and a multi-step
servicing process. Example: a laundromat with several washers and dryers.

Queuing Disciplines
A queuing discipline refers to the method of choosing which customers to serve in which
order.

• First-in, first-out queuing

A FIFO queue is a queue that operates on the first-in, first-out principle, hence the
name. This is also referred to as the first-come, first-serve principle. FIFO queuing refers to a
queuing discipline where customers are served in the exact order in which they arrive. The
first to join the line is the first one to leave it, all other factors being equal. FIFO queuing is
the predominant method of queuing, as it promotes fairness and its rules are universally
understood. You can see it almost everywhere: banks, post offices, DMVs, retail, etc.

• Last-in, first-out queuing

Although the principle of last-in, first-out sounds illogical at first, there might be some
power to it. Professor Lars Peter Osterdal of the University of Southern Denmark thinks that
LIFO actually has the edge over FIFO: “The problem with a regular queue where you serve
first those who arrive first is that people tend to arrive too early.”
LIFO forces people to come at staggered times, resulting in shorter queues. Coming
early poses more risks, which is why in Osterdal’s experiment people chose to come later and
spend as little time in the queue as possible. Since this system rewarded late-comers, it wasn’t
popular with people who were more accustomed to a traditional way of queuing.
There was nothing stopping some customers from leaving the queue and rejoining it
to gain advantage, which had a negative effect on people trying to play by the rules. That’s
why LIFO is usually reserved for solving transportation and logistical problems, rather than
issues of customers standing in line.
 • Priority queuing
In priority queuing, some customers have a special status which allows them to skip
the usual means of queuing. This type of queuing is most commonly seen in industries where
there can be emergency cases — for example, healthcare. A patient with a severe case is
naturally treated ahead of everyone else.
In non-healthcare industries, this type of queuing is usually called VIP queuing. For
instance, business class passengers board the airplane before others. The same goes for
clubs, restaurants and similar venues.
The drawback of this system is that it may appear unfair unless it was clearly
communicated in advance. After all, getting jumped ahead of you sounds infuriating if you
weren’t aware that the business had priority queuing in place.

Real Life Causes of Queue Generation

o For Roads:
▪ Geometric Bottlenecks (lane drops, hard curves, hills)
▪ Accidents and Incident
▪ Traffic Signals and Intersection Controls
▪ At-Grade Crossings with other Modes (Railroad crossings, drawbridges, etc.)
▪ Toll Booths
▪ "Gawker" Effect
▪ Inclement Weather

o For Trains and Transit:

▪ Platform Capacities
▪ Fare Gates
▪ Ticket Windows/Ticket Machines
▪ Minimum Safe Separation for Trains
▪ Security Checkpoints
▪ Efficiency of Trains Entering and Leaving Station (number of tracks, switches, etc.)

o For Aviation and Airports:

▪ Runways
▪ Designated Minimum Safe Following Distances for Planes (by government)
▪ Physical Minimum Safe Following Distance for Planes (creation of turbulence, etc.)
▪ Available Airspace for Approaches and Departures
▪ Ticketing Counters/Check-in Procedures
▪ Security Checkpoints
▪ Baggage Systems
▪ Terminal Capacity for Planes
▪ Internal Terminal Capacity for Passengers
▪ Inclement Weather
 o For Water and Maritime:
▪ Locks and Dams
▪ Port Capacities
▪ Minimum "Safe" Distances (determined by government and physics)
▪ Inclement Weather

o For Space Flight:

▪ Launch Capacity
▪ Minimum Spacings between Orbital Vehicles
▪ Inclement Weather on Earth
▪ Unfavorable Celestial Conditions

4.1 DIMENSIONS OF QUEUING MODEL

The purpose of traffic queuing models is to provide a means to estimate important
measures of highway performance, including vehicle delay and traffic queue lengths. Such
estimates are critical to roadway design (the required length of left-turn bays and the number of
lanes at intersections) and traffic operations control, including the timing of traffic signals at
intersections.
Queuing models are derived from underlying assumptions regarding arrival patterns,
departure characteristics, and queue disciplines. Traffic arrival patterns were explored in Module
3, where, given an average vehicle arrival rate (λ), two possible distributions of the time between
the arrival of successive vehicles were considered:

1. Equal time intervals (derived from the assumption of uniform, deterministic arrivals)
2. Exponentially distributed time intervals (derived from the assumption of Poisson-
distributed arrivals).
In addition to vehicle arrival assumptions, the derivation of traffic queuing models
requires assumptions relating to vehicle departure characteristics. Of particular interest is the
distribution of the amount of time it takes a vehicle to depart—for example, the time to pass
through an intersection at the beginning of a green signal, the time required to pay a toll at a toll
booth, or the time a driver takes before deciding to proceed after stopping at a stop sign. As was
the case for arrival patterns, given an average vehicle departure rate (denoted as μ, in vehicles
per unit time), the assumption of a deterministic or exponential distribution of departure times
is appropriate.
Another important aspect of queuing models is the number of available departure
channels. For most traffic applications only one departure channel will exist, such as a highway
lane or group of lanes passing through an intersection. However, multiple departure channels
are encountered in some traffic applications, such as at toll booths on turnpikes and at entrances
to bridges.
The final necessary assumption relates to the queue discipline. In this regard, two options
have been popularized in the development of queuing models: first- in, first-out (FIFO), indicating
that the first vehicle to arrive is the first to depart, and last-in, first-out (LIFO), indicating that the
last vehicle to arrive is the first to depart. For virtually all traffic-oriented queues, the FIFO
queuing discipline is the more appropriate of the two.
Queuing models are often identified by three alphanumeric values. The first value
indicates the arrival rate assumption, the second value gives the departure rate assumption, and
the third value indicates the number of departure channels. For traffic arrival and departure
assumptions, the uniform, deterministic distribution is denoted D and the exponential
distribution is denoted M. Thus a D/D/1 queuing model assumes deterministic arrivals and
departures with one departure channel. Similarly, an M/D/1 queuing model assumes
exponentially distributed arrival times, deterministic departure times, and one departure
channel.

4.2 D/D/1 QUEUEING

The case of deterministic arrivals and departures with one departure channel (D/D/1
queue) is an excellent starting point in understanding queuing models because of its simplicity.
The D/D/1 queue lends itself to an intuitive graphical or mathematical solution that is best
illustrated by an example.

EXAMPLE 1. D/D/1 QUEUING WITH CONSTANT ARRIVAL AND DEPARTURE RATES

Vehicles arrive at an entrance to a recreational park. There is a single gate (at which all
vehicles must stop), where a park attendant distributes a free brochure. The park opens at 8:00
A.M., at which time vehicles begin to arrive at a rate of 480 veh/h. After 20 minutes, the arrival
flow rate declines to 120 veh/h, and it continues at that level for the remainder of the day. If the
time required to distribute the brochure is 15 seconds, and assuming D/D/1 queuing, describe
the operational characteristics of the queue.

SOLUTION

Begin by putting arrival and departure rates into common units of vehicles per minute:

𝑣𝑒ℎ
480 ℎ𝑟 𝑣𝑒ℎ
𝜆= 𝑚𝑖𝑛 =8 for t ≤ 20 min
60 ℎ𝑟 𝑚𝑖𝑛

𝑣𝑒ℎ
120 ℎ𝑟 𝑣𝑒ℎ
𝜆= 𝑚𝑖𝑛 =2 for t > 20 min
60 ℎ𝑟 𝑚𝑖𝑛

𝑠
60𝑚𝑖𝑛 𝑣𝑒ℎ
𝜇= 𝑠 =4 for all t
15𝑣𝑒ℎ 𝑚𝑖𝑛
 Figure 2 D/D/1 queuing diagram for Example 1

Equations for the total number of vehicles that have arrived and departed up to a
specified time, t, can now be written. Define t as the number of minutes after the start of the
queuing process (in this case the number of minutes after 8:00 A.M.). The total number of vehicle
arrivals at time t is equal to

8t for t ≤ 20 min
and
160 + 2(t – 20) for t > 20 min

Similarly, the number of vehicle departures is

4t for all t

The preceding equations can be illustrated graphically as shown in Fig. 2. When the arrival curve
is above the departure curve, a queue condition exists. The point at which the arrival curve meets
the departure curve is the moment when the queue dissipates (no more queue exists). In this
example, the point of queue dissipation can be determined graphically by inspection of Fig. 2, or
analytically by equating appropriate arrival and departure equations, that is,

160 + 2(t − 20)= 4t

Solving for t gives t = 60 minutes. Thus the queue that began to form at 8:00 A.M. will dissipate
60 minutes later (9:00 A.M.), at which time 240 vehicles will have arrived and departed (4
veh/min × 60 min).
Another aspect of interest is individual vehicle delay. Under the assumption of a FIFO
queuing discipline, the delay of an individual vehicle is given by the horizontal distance between
arrival and departure curves starting from the time of the vehicle’s arrival in the queue. So, by
inspection of Fig. 1, the 160th vehicle to arrive will have the longest delay, 20 minutes (the longest
horizontal distance between arrival and departure curves), and vehicles arriving after the 239th
vehicle will encounter no queue delay because the queue will have dissipated and the departure
rate will continue to exceed the arrival rate. It follows that with the LIFO queuing discipline, the
first vehicle to arrive would have to wait until the entire queue clears (60 minutes of delay).
The total length of the queue at a specified time, expressed as the number of vehicles, is
given by the vertical distance between arrival and departure curves at that time. For example, at
10 minutes after the start of the queuing process (8:10 A.M.) the queue is 40 vehicles long, and
the longest queue (longest vertical distance between arrival and departure curves) will occur at
t = 20 minutes and is 80 vehicles long (see Fig. 2).
Total vehicle delay, defined as the summation of the delays for the individual vehicles, is
given by the total area between the arrival and departure curves (see Fig. 1) and, in this case, is
in units of vehicle-minutes. In this example, the area between the arrival and departure curves
can be determined by summing triangular areas, giving total delay, Dt, as

80(20) 80(40)
𝐷𝑡 = + = 2400 𝑣𝑒ℎ − 𝑚𝑖𝑛
2 2

Finally, because 240 vehicles encounter queuing delay (as previously determined), the average
delay per vehicle is 10 minutes (2400 veh-min/240 veh), and the average queue length is 40
vehicles (2400 veh-min/60 min).
EXAMPLE 2. D/D/1 QUEUING WITH TIME-VARYING ARRIVAL RATE AND CONSTANT DEPARTURE
RATE
Vehicles start arriving at an entrance to a national park at 5:45 A.M. and a park booth
collecting entrance fees opens at 6:00 A.M. and process vehicles at a deterministic rate of 20
veh/min. It is estimated that 20% of the arriving vehicles have priority passes that allow them to
access a separate processing booth that also opens at 6:00 A.M. but processes vehicles at a
slower deterministic rate of 15 veh/min. The deterministic arrival rate of vehicles is a function of
time such that λ(t) = 17.2 − 0.2t where t is in minutes after 5:45 A.M. Determine the average
delay per vehicle for the non–priority- pass vehicles and the priority-pass vehicles (starting with
their arrival at 6:45 A.M.) until their respective queues clear, assuming D/D/1 queuing.

SOLUTION
This problem has time-dependent deterministic arrivals and departure rates that do not
vary over time. Begin by computing the arrivals of non–priority-pass vehicles. Because 20% of all
arrivals are priority-pass vehicles, the non–priority-pass vehicle arrivals will be (starting at 5:45
A.M.):

= ∫ 17.2 − 0.2𝑡 𝑑𝑡
0

= 17.2𝑡 − 0.1𝑡 2 − 0.2(17.2𝑡 − 0.1𝑡 2 )

= 17.2𝑡 − 0.1𝑡 2 − 3.44𝑡 + 0.02𝑡 2

= 13.76𝑡 − 0.08𝑡 2

The time required to clear the queue of the non–priority-pass vehicles (with a departure
rate of 20 veh/min) is determined as:

13.76𝑡 − 0.08𝑡 2 = 20(𝑡 − 15)

−0.08𝑡 2 − 6.24𝑡 + 300 = 0

𝑡 = 33.60 𝑚𝑖𝑛

At t = 33.60 minutes, the total number of non–priority-pass vehicle arrivals is

= 13.76𝑡 − 0.08𝑡 2
= 13.76(33.60) − 0.08(33.60)2
= 372.02 𝑣𝑒ℎ
So the total delay for the non–priority-pass vehicles, Dnp will be the area under the arrival
function minus the area under the departure function, which will be a simple triangle with a
height of 372.02 vehicles and a base of 18.60 min (33.60 − 15):

33.60
1
𝐷𝑛𝑝 = ∫ 13.76𝑡 − 0.08𝑡 2 𝑑𝑡 − (33.60 − 15)(372.02)
2
0

𝐷𝑛𝑝 = 6755.69664 − 3459.786

𝐷𝑛𝑝 = 3295.91 𝑣𝑒ℎ − 𝑚𝑖𝑛

3295.91
So the average delay per vehicle for the non–priority-pass vehicles is 8.86 min ( 372.02 ).
For the priority-pass vehicles, the arrival function is 20% of the total vehicle 0 arrival function
or,

= 0.2 ∫ 17.2 − 0.2𝑡 𝑑𝑡

0
= 0.2 (17.2𝑡 − 0.1𝑡 2 )

= 3.44𝑡 − 0.02𝑡 2

The time required to clear the queue of the priority-pass vehicles (with a departure rate of 15
veh/min) is:

3.44𝑡 − 0.02𝑡 2 = 15(𝑡 − 15)

−0.02𝑡 2 − 11.56𝑡 + 225 = 0

𝑡 = 18.85 𝑚𝑖𝑛

At t = 18.84 minutes, the total number of priority-pass vehicle arrivals is

= 3.44𝑡 − 0.02𝑡 2

= 3.44(18.85) − 0.02(18.85)2

= 57.74 𝑣𝑒ℎ
So the total delay for the priority-pass vehicles, Dp will again be the area under the arrival
function minus the area under the departure function, which will be a simple triangle with a
height of 57.74 vehicles and a base of 3.85 min (18.85 − 15):

18.85
1
𝐷𝑝 = ∫ 3.44𝑡 − 0.02𝑡 2 𝑑𝑡 − (18.85 − 15)(57.74)
2
0

𝐷𝑝 = 566.5025 − 111.1495

𝐷𝑝 = 455.35 𝑣𝑒ℎ − 𝑚𝑖𝑛

455.35
So the average delay per vehicle for the priority-pass vehicles is 7.89 min ( 57.74 ). Thus the
priority pass saves an average of 0.97 min, or about 58.2 seconds.

EXAMPLE 3. D/D/1 QUEUING WITH TIME-VARYING ARRIVAL AND DEPARTURE RATES

After observing arrivals and departures at a highway toll booth over a 60-minute time
period, an observer notes that the arrival and departure rates (or service rates) are deterministic,
but instead of being uniform, they change over time according to a known function. The arrival
rate is given by the function λ(t) = 2.2 + 0.17t − 0.0032t 2, and the departure rate is given by μ(t)
= 1.2 + 0.07t, where t is in minutes after the beginning of the observation period and λ(t) and μ(t)
are in vehicles per minute. Determine the total vehicle delay at the toll booth and the longest
queue, assuming D/D/1 queuing.

SOLUTION
Note that this problem is an example of a time-dependent deterministic queue because
the deterministic arrival and departure rates change over time. Begin by computing the time to
queue dissipation by equating vehicle arrivals and departures:

𝑡 𝑡
2
∫ 2.2 + 0.17𝑡 − 0.0032𝑡 𝑑𝑡 = ∫ 1.2 + 0.07𝑡 𝑑𝑡
0 0

2.2𝑡 + 0.085𝑡 2 − 0.00107𝑡 3 = 1.2𝑡 + 0.035𝑡 2

−0.00107𝑡 3 + 0.05𝑡 2 + 𝑡 = 0
This gives t = 61.84 minutes. Therefore, the total vehicle delay (the area between the arrival
and departure functions) is

61.84 61.84

𝐷𝑡 = ∫ 2.2𝑡 + 0.085𝑡 2 − 0.00107𝑡 3 𝑑𝑡 − ∫ 1.2𝑡 + 0.035𝑡 2 𝑑𝑡

0 0

𝐷𝑡 = 1.1𝑡 2 + 0.283𝑡 3 − 0.0002675𝑡 4 − 0.6𝑡 2 − 0.0117𝑡 3]61.84

0

𝐷𝑡 = 1941.53 𝑣𝑒ℎ − 𝑚𝑖𝑛

The queue length (in vehicles) at any time t is given by the function

𝑡 𝑡

𝑄(𝑡) = ∫ 2.2 + 0.17𝑡 − 0.0032𝑡 2 𝑑𝑡 − ∫ 1.2 + 0.07𝑡 𝑑𝑡

0 0

𝑄(𝑡) = −0.00107𝑡 3 + 0.05𝑡 2 + 𝑡

Solving for the time at which the maximum queue length occurs yields

𝑑𝑄(𝑡)
= −0.00321𝑡 2 + 0.1𝑡 + 1 = 0
𝑑𝑡

𝑡 = 39.12 𝑚𝑖𝑛

Substituting with t = 39.12 minutes gives the maximum queue length:

𝑄(39.12) = −0.00107𝑡 3 + 0.05𝑡 2 + 𝑡

𝑄(39.12) = −0.00107(39.12)3 + 0.05(39.12)2 + 39.12

𝑄(39.12) = 51.58 𝑣𝑒ℎ − 𝑚𝑖𝑛

EXAMPLE 4. DETERMINING A REQUIRED DEPARTURE RATE
A parking garage has a single processing booth where cars pay for parking. The garage
opens at 6:00 A.M. and vehicles start arriving at 6:00 A.M. at a deterministic rate of λ(t) = 6.1 −
0.22t where λ(t) is in vehicles per minute and t is in minutes after 6:00 A.M. What is the minimum
constant departure rate (from 6:00 A.M. on) needed to ensure that the queue length does not
exceed 10 vehicles?

SOLUTION
Let μ be the unknown departure rate (in veh/min) so that the queue length (in vehicles)
at any time t is:

𝑡 𝑡

𝑄(𝑡) = ∫ 6.1 − 0.22𝑡 𝑑𝑡 − ∫ 𝜇𝑑𝑡

0 0

𝑄(𝑡) = 6.1𝑡 − 0.11𝑡 2 − 𝜇𝑡

Using this and solving for the time at which the maximum queue length occurs gives

𝑑𝑄(𝑡)
= 6.1 − 0.22𝑡 − 𝜇
𝑑𝑡

6.1 − 𝜇
𝑡=
0.22

Substituting this value of t into the queue-length equation with a maximum Q(t) = 10 vehicles
as specified in the problem gives

6.1 − 𝜇 6.1 − 𝜇 2 6.1 − 𝜇

𝑄(𝑡) = 10 = 6.1 ( ) − 0.11 ( ) −𝜇( )
0.22 0.22 0.22

which gives 2.28μ2 − 27.79μ + 74.67 = 0. Solving for μ gives possible solutions as 9 veh/min (8.19)
and 4 veh/min (3.9989), so the minimum departure rate would be 4 veh/min.
4.1 M/D/1 QUEUEING
The assumption of exponentially distributed times between the arrivals of successive
vehicles (Poisson arrivals) will, in some cases, give a more realistic representation of traffic flow
than the assumption of uniformly distributed arrival times. Therefore, the M/D/1 queue
(exponentially distributed arrivals, deterministic departures, and one departure channel) has
some important applications within the traffic analysis field. Although a graphical solution to an
M/D/1 queue is difficult, a mathematical solution is straightforward. Defining a new term (traffic
intensity) for the ratio of average arrival to departure rates as

𝜆
𝜌=𝜇 Equation 1

where
ρ = traffic intensity, unitless,
λ = average arrival rate in vehicles per unit time, and
μ = average departure rate in vehicles per unit time,

and assuming that ρ is less than 1, it can be shown that for an M/D/1 queue the following queuing
performance equations apply:

𝜌 2
𝑄̅ = 2(1−𝜌) Equation 2

𝜌
𝑤
̅ = 2𝜇(1−𝜌) Equation 3

2−𝜌
𝑡̅ = 2𝜇(1−𝜌) Equation 4

where
𝑄̅ = average length of queue in vehicles,
𝑤̅ = average waiting time in the queue, in unit time per vehicle,
𝑡̅ = average time spent in the system (the summation of average waiting time in
the queue and average departure time), in unit time per vehicle, and other
terms are as defined previously.

It is important to note that under the assumption that the traffic intensity is less than 1 (λ < μ),
the D/D/1 queue will predict no queue formation. However, a queuing model that is derived
based on random arrivals or departures, such as the M/D/1 queuing model, will predict queue
formations under such conditions. Also, note that the M/D/1 queuing model presented here is
based on steady-state conditions (constant average arrival and departure rates), with
randomness arising from the assumed probability distribution of arrivals. This contrasts with the
time-varying deterministic queuing case, presented in Example 3, in which arrival and departure
rates changed over time but randomness was not present.

EXAMPLE 5 M/D/1 QUEUING: PARK-ENTRANCE APPLICATION

Consider the entrance to the recreational park described in Example 1. However, let the
average arrival rate be 180 veh/h and Poisson distributed (exponential times between arrivals)
over the entire period from park opening time (8:00 A.M.) until closing at dusk. Compute the
average length of queue (in vehicles), average waiting time in the queue, and average time spent
in the system, assuming M/D/1 queuing.

SOLUTION

Putting arrival and departure rates into common units of vehicles per minute gives

𝑣𝑒ℎ
180 ℎ𝑟 𝑣𝑒ℎ
𝜆= 𝑚𝑖𝑛 =3 for all t
60 ℎ𝑟 𝑚𝑖𝑛

𝑠
60𝑚𝑖𝑛 𝑣𝑒ℎ
𝜇= 𝑠 =4 for all t
15𝑣𝑒ℎ 𝑚𝑖𝑛

and
𝑣𝑒ℎ
𝜆 3 𝑚𝑖𝑛
𝜌= = = 0.75
𝜇 4 𝑣𝑒ℎ
𝑚𝑖𝑛

For the average length of queue (in vehicles), Eq. 2 is applied:

𝜌2 0.752
𝑄̅ = = = 1.125 𝑣𝑒ℎ
2(1 − 𝜌) 2(1 − 0.75)

For average waiting time in the queue, Eq. 3 gives

𝜌 0.75 𝑚𝑖𝑛
𝑤
̅= = = 0.375
2𝜇(1 − 𝜌) 2(4)(1 − 0.75) 𝑣𝑒ℎ

For average time spent in the system [queue time plus departure (service) time], Eq. 4 is used:

2−𝜌 2 − 0.75 𝑚𝑖𝑛

𝑡̅ = = = 0.625
2𝜇(1 − 𝜌) 2(4)(1 − 0.75) 𝑣𝑒ℎ
or, alternatively, because the departure (service) time is 1/μ (the 0.25 minutes it takes the park
attendant to distribute the brochure),

1 1 𝑚𝑖𝑛
𝑡̅ = 𝑤
̅+ = 0.375 + = 0.625
𝜇 4 𝑣𝑒ℎ

4.2 M/M/1 QUEUEING

A queuing model that assumes one departure channel and exponentially distributed
departure times in addition to exponentially distributed arrival times (an M/M/1 queue) is
applicable in some traffic applications. For example, exponentially distributed departure patterns
might be a reasonable assumption at a toll booth, where some arriving drivers have the correct
toll and can be processed quickly, and others do not have the correct toll, producing a distribution
of departures about some mean departure rate. Under standard M/M/1 assumptions, it can be
shown that the following queuing performance equations apply (again assuming that ρ is less
than 1):

𝜌 2
𝑄̅ = (1−𝜌) Equation 5

𝜆
𝑤
̅ = 𝜇(𝜇−𝜆) Equation 6

1
𝑡̅ = (𝜇−𝜆) Equation 7

where
𝑄̅ = average length of queue in vehicles,
𝑤̅ = average waiting time in the queue, in unit time per vehicle,
𝑡̅ = average time spent in the system (w + 1/μ), in unit time per vehicle, and other
terms are as defined previously.
EXAMPLE 6. M/M/1 QUEUING: PARKING-LOT APPLICATION
Assume that the park attendant in Examples 1 and 5 takes an average of 15 seconds to
distribute brochures, but the distribution time varies depending on whether park patrons have
questions relating to park operating policies. Given an average arrival rate of 180 veh/h as in
Example 5, compute the average length of queue (in vehicles), average waiting time in the queue,
and average time spent in the system, assuming M/M/1 queuing.

SOLUTION

Using the average arrival rate, departure rate, and traffic intensity as determined in Example 5,
the average length of queue is (from Eq. 5):

𝜌2 (0.75)2
𝑄̅ = = = 2.25 𝑣𝑒ℎ
(1 − 𝜌) (1 − 0.75)

the average waiting time in the queue is (from Eq. 6):

𝜆 3 𝑚𝑖𝑛
𝑤
̅= = = 0.75
𝜇(𝜇 − 𝜆) 4(4 − 3) 𝑣𝑒ℎ

and the average time spent in the system is (from Eq. 7):

1 1 𝑚𝑖𝑛
𝑡̅ = = =1
(𝜇 − 𝜆) (4 − 3) 𝑣𝑒ℎ

4.3 M/M/N QUEUEING

A more general formulation of the M/M/1 queue is the M/M/N queue, where N is the
total number of departure channels. M/M/N queuing is a reasonable assumption at toll booths
on turnpikes or at toll bridges, where there is often more than one departure channel available
(more than one toll booth open). A parking lot is another example, with N being the number of
parking stalls in the lot and the departure rate, μ, being the exponentially distributed times of
parking duration. M/M/N queuing is also frequently encountered in non- transportation
applications such as checkout lines at retail stores, security checks at airports, and so on.
The following equations describe the operational characteristics of M/M/N queuing. Note
that unlike the equations for M/D/1 and M/M/1, which require that the traffic intensity, ρ, be
less than 1, the following equations allow ρ to be greater than 1 but apply only when ρ/N (which
is called the utilization factor) is less than 1.
 1
𝑃0 = 𝜌 𝑛𝑐 𝜌𝑁
Equation 8
∑𝑁−1
𝑛𝑐 =0 𝑛𝑐 ! +𝑁!(1− 𝜌 )
𝑁

𝜌 𝑛 𝑃0
𝑃𝑛 = 𝑓𝑜𝑟 𝑛 ≤ 𝑁 Equation 9
𝑛!

𝜌𝑛𝑃
𝑃𝑛 = 𝑁𝑛−𝑁0𝑁! 𝑓𝑜𝑟 𝑛 ≥ 𝑁 Equation 10

𝑃0 𝜌 𝑁+1
𝑃𝑛>𝑁 = 𝜌 Equation 11
𝑁!𝑁(1− )
𝑁

where
P0 = probability of having no vehicles in the system,
Pn = probability of having n vehicles in the system,
Pn>N =probability of waiting in a queue (the probability that the number of vehicles in
the system is greater than the number of departure channels),
n = number of vehicles in the system,
N = number of departure channels,
nc =departure channel number, and
ρ = traffic intensity (λ/μ).

𝑃 𝜌 𝑁+1 1
𝑄̅ = 0𝑁!𝑁 [ 𝜌 2
] Equation 12
(1−𝑁)

𝜌+𝑄̅ 1
𝑤
̅= − Equation 13
𝜆 𝜇

𝜌+𝑄̅
𝑡̅ = Equation 14
𝜆

where
𝑄̅ = average length of queue in vehicles,
𝑤̅ = average waiting time in the queue, in unit time per vehicle,
𝑡̅ = average time spent in the system, in unit time per vehicle, and other terms
are as defined previously.
 EXAMPLE 7. M/M/N QUEUING: TOLL-BRIDGE APPLICATION
At an entrance to a toll bridge, four toll booths are open. Vehicles arrive at the bridge at
an average rate of 1200 veh/h, and at the booths, drivers take an average of 10 seconds to pay
their tolls. Both the arrival and departure rates can be assumed to be exponentially distributed.
How would the average queue length, time in the system, and probability of waiting in a queue
change if a fifth toll booth were opened?

SOLUTION
Using the equations for M/M/N queuing, we first compute the four-booth case. Note that
μ = 6 veh/min and λ = 20 veh/min, and therefore ρ = 3.333. Also, because ρ/N = 0.833 (which is
less than 1), Eqs. 8 to 14 can be used. The probability of having no vehicles in the system with
four booths open (using Eq. 8) is

1 1
𝑃0 = = = 0.0213
𝜌𝑛𝑐 𝜌𝑁 3.333 3.3332 3.3333 3.3334
∑𝑁−1
𝑛𝑐 ! + 𝑁! (1 − 𝜌 ) [1 + 1! +
𝑛𝑐 =0 + 3! ] + [ ]
2! 4! (0.1667)
𝑁

The average queue length is (from Eq. 12)

𝑃0 𝜌𝑁+1 1 0.0213(3.333)4+1 1
𝑄̅ = [ 2] = [ ] = 3.282 𝑣𝑒ℎ
𝑁! 𝑁 𝜌
(1 − 𝑁 )
4! (4) 3.333 2
(1 − 4 )

The average time spent in the system is (from Eq. 14)

𝜌 + 𝑄̅ 3.333 + 3.282 𝑚𝑖𝑛
𝑡̅ = = = 0.331
𝜆 20 𝑣𝑒ℎ

And the probability of having to wait in a queue is (from Eq. 11)

𝑃0 𝜌𝑁+1 0.0213(3.333)5
𝑃𝑛>𝑁 = 𝜌 = 4! (4)(0.1667) = 0.547
𝑁! 𝑁 (1 − 𝑁)

With a fifth booth open, the probability of having no vehicles in the system is (from Eq. 8)

1 1
𝑃0 = = = 0.0318
𝜌𝑛𝑐 𝜌𝑁 3.333 3.3332 3.3333 3.3334 3.3335
∑𝑁−1
𝑛𝑐=0 𝑛𝑐 ! + 𝑁! (1 − 𝜌 ) 1 + [ 1! + 2! + 3! + 4! ] + [
5! (0.1667)
]
𝑁
The average queue length is (from Eq.12)

𝑃0 𝜌𝑁+1 1 0.0318(3.333)6 1
𝑄̅ = [ ] = [ ] = 0.654 𝑣𝑒ℎ
𝑁! 𝑁 𝜌 2 5! (5) (0.3333)2
(1 − 𝑁)

The average time spent in the system is (from Eq.14)

𝜌 + 𝑄̅ 3.333 + 0.654 𝑚𝑖𝑛

𝑡̅ = = = 0.199
𝜆 20 𝑣𝑒ℎ

And the probability of having to wait in a queue is (from Eq. 11)

𝑃0 𝜌𝑁+1 0.0318(3.333)6
𝑃𝑛>𝑁 = 𝜌 = = 0.218
𝑁! 𝑁 (1 − 𝑁) 5! (5)(0.3333)

So opening a fifth booth would reduce the average queue length by 2.628 veh (3.282 − 0.654),
the average time in the system by 0.132 min/veh (0.331 − 0.199), and the probability of waiting
in a queue by 0.329 (0.547 − 0.218).
EXAMPLE 8. M/M/N QUEUING: PARKING-LOT APPLICATION
A convenience store has four available parking spaces. The owner predicts that the
duration of customer shopping (the time that a customer’s vehicle will occupy a parking space)
is exponentially distributed with a mean of 6 minutes. The owner knows that in the busiest hour
customer arrivals are exponentially distributed with a mean arrival rate of 20 customers per hour.
What is the probability that a customer will not find an open parking space when arriving at the
store?

SOLUTION

Putting mean arrival and departure rates in common units gives μ = 10 veh/h and λ= 20 veh/h.
So ρ = 2.0, and because ρ/N = 0.5 (which is less than 1), Eqs. 8 to 14can be used. The probability
of having no vehicles in the system with four parking spaces available (using Eq. 8) is

1 1
𝑃0 = = = 0.1304
𝜌 𝑛𝑐 𝜌𝑁 2 22 23 24
∑𝑁−1
𝑛𝑐 ! + 𝑁! (1 − 𝜌 )
𝑛𝑐=0 [1 + 1! + 2! + 3! ] + [ ]
4! (0.5)
𝑁

Thus the probability of not finding an open parking space upon arrival is (from Eq. 11)

𝑃0 𝜌𝑁+1 0.1304(2)5
𝑃𝑛>𝑁 = 𝜌 = = 0.087
𝑁! 𝑁 (1 − 𝑁) 4! (4)(0.5)

References
Fundamentals of Transportation/Queueing - Wikibooks, open books for an open world. (n.d.).
https://en.wikibooks.org/wiki/Fundamentals_of_Transportation/Queueing
Garber, N. J., & Hoel, L. A. (2019). Traffic and highway engineering. Cengage Learning
Homburger, W. S., Hall, J. W., Reilly, W. R., & Sullivan, E. C. (2007). Fundamentals of traffic engineering.
Tšernov, K. What is Queue Management? The Definitive Guide to Queuing .. Qminder. October 4, 2023.
https://www.qminder.com/blog/queue-management/what-is-queue-management-system/
 This gives the u-

(3.25)
Two more models can be easily identified:

n = -1
Parabolic model: n=0

Table 3.4 summarizes the different macroscopic model depending on the value of n:

Table 3.4
Macroscopic models

3.6 QUEUING THEORY

Queuing at a gasoline station or at the toll gate, falling in line to transact business at the
bank or just to get a movie pass, queuing at a busy parking lot, jet planes waiting before being
given the signal to land or takeoff these are everyday occurrences that wou
patience.
Queuing analysis provides ways of assessing the impacts of these activities by knowing
the magnitude of vehicular delay and the extent of queue propagated. The models that will be
discussed in this section are derived based on some assumptions related to arrival and departure
patterns, and the prevailing queue discipline. Consider the system shown in figure 3.7.

Figure 3.7
Queuing system

The input is normally characterized by some form of arrival pattern usually given by its
arrival distribution. The output generally depends on the queue discipline and the service
mechanism at the service station. The most common type of queue discipline s the so-called
FIFO or first-in first-out, i.e., the first one that arrives at the service station gets served first and
therefore the first to leave the system as well. (Another type of queue discipline, which has
limited application to traffic flow, is the so-called LIFO or last-on first-out. Typical examples of
this discipline are the following: the last rider of an elevator normally gets out first; the last
document piled on top gets signed first not a recommended practice!) Service mechanism
refers to the manner customers are served at the station. For example, a toll booth that charges a
single fee, accepts only a fixed amount, and does not give back any change will have a fairly
uniform service rate compared to a booth that charges variable toll fees and gives back change up
to the last centavo.
d to describe a queuing system. It takes the form
A / B / C (n)
 where
A
B represents the service mechanism
C represents the number of services
n represents the limit of the queue or users

Arrivals and departure may either follow a random or deterministic pattern. Markov (M)
is used for random processes while Deterministic (D) is used for processes that are characterized
by regular or constant arrivals or departures. Typical examples of these processes are:
random arrival and departure (service rate); one or single server; infinite
queue (no limit)
random arrival and departure; N or multiple servers; infinite queue
regular arrival; regular service rate or departure; single server; limit of
queue is 100.
A combination of Markov and deterministic processes, say M / D / 1 may also be used.

3.6.1 D / D / 1 Queuing
Due to the regularity of both arrivals and departures, it is more convenient to analyze a
D/D/1 queuing system graphically. Arrivals and departures are easily represented by straight
lines with the slopes corresponding to their rates.

Example 3.10
Consider a temporary single lane o-ramp/entrance to the expressway. While the entrance
is open 24 hours, a fixed toll fee of P10 is charged from 7AM to 9AM as a form of congestion
pricing. On the average, a vehicle is served for 7.5 seconds during which the teller receives the
fee and gives back the charge, The flow rate is 600 vehicles/hour during the first 25 minutes after
which, it is reduced to 360 vehicles/hour and remains constant for the next hours as shown in
figure 3.8.
 Figure 3.8
Graphical representation of D/D/1 queuing for example 3.10

Consider time t reckoned from 7AM. The total number of vehicles that have arrived and
departed are estimated:

Queue is expected to dissipate at the intersection of the two lines. At this point, the total
number of arrivals will be equal to the total number of departures.
250 + 6 x (t-25) = 8 t
or t = 50 min
Therefore queue dissipated at about 7:50 AM. After which, no queue is expected to
propagate since the departure rate (8 veh/min) is already higher than the arrival rate (veh/min).
The total number of vehicles delayed is 8 x t = 8 x 50 = 400 veh
The longest queue occurs at t = 25 min with a value of
(10-8) x t = 2 x 25 = 50 veh
The total vehicular delay is estimated from the area of the triangle, i.e., area between
arrival and departure curves.
 Total vehicular delay =
½ x 50 veh x 25 min + ½ x 50 veh x (50-25) min = 1250 veh/min
The average delay per vehicle is 1250/400 = 3.12 min/veh

3.6.2 M/D/1 Queuing

The M/D/1 queuing system assumes that the arrivals of vehicles follow a negative
exponential distribution, a probability distribution characterized by randomness. Departure is
assumed to be regular as in D/D/1. The reader is advised to refer to other books on queuing
theory for the derivation of the formulas.

µ, which means that the system is stable. Otherwise, queue

becomes longer and longer (unstable condition).
Basic formulas for M/D/1:

(3.26)

(3.27)

(3.28)

Example 3.11
At the exit of a toll gate with a single booth, vehicles arrive at random at a rate of 20
vehicles per minute. The service has an average rate of 22 vehicles per minute.
Estimate the following:
a. average length of queue formed at the toll gate
 b. average waiting time of vehicles
c. average time vehicles spent in the system

Solution:
A
Service rate is µ = 22 vehicles/minute.

3.6.3 M/M/1 Queuing

The M/M/1 queuing system assumes negative exponential for both arrival and departure
distributions.
 Basic formulas for M/M/1:

(3.29)

(3.30)

(3.31)

Example 3.12
Consider the same problem in example 3.11. However, due to variable toll fees, the
service is also random with an average rate of 22 vehicles per minute.

Solution:
 It may be observed that with a stochastic service rate, estimates for M/M/1 are almost
twice that of the M/D/1.

3.6.4 M/M/N Queuing

When there is more than one server, such as in toll gate shown in figure 3.9, an arriving
vehicle will be able to proceed to a vacant gate, if available.

Figure 3.9
Toll plaza with N gates

Otherwise, the driver may have to wait in queue if all gates are full. Again the arrivals are

per server is µ . However, is

defined as the utilization factor.

must be less than 1 for stable

condition.
Basic formulas for M/M/N:
a. Average length of queue

(3.32)
where

(3.33)
 b. Average waiting time

(3.34)

c. Average time spent in the system

(3.35)

Exercise 3.13
If the operator of the toll road in the previous example wants to improve the current
condition at the toll plaza, determine the new queue characteristics if the number of toll booths is
increased to 2.

Solution:

The probability of having no vehicles in the system is computed first using equation 3.33
 Increasing the number of toll booths to 2 will greatly improve the operation of the toll
plaza.

3.7 SHOCK WAVE

Stalled vehicles, traffic accidents, parades, or any other temporal activities will cause
abnormal traffic flow and will definitely reduce the capacity of the roadway. Such occurrences
lead to long queues extending several kilometers that can only be dissipated long after the
obstruction has been removed. Analysis of this type of problem is done using shock wave theory.
Shock wave is simply the motion or propagation of a change in density and flow. Consider two
flow regions A and B as shown in figure 3.10. Region A has prevailing flow described by speed
u1 and density k1 while flow in region B has a speed u2 and k2.