Abstract
Original language  English 

Awarding Institution 

Supervisors/Advisors 

Award date  12 Jun 2015 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9789036538121 
DOIs  
Publication status  Published  12 Jun 2015 
Fingerprint
Keywords
 Matrix Analytic Methods
 QuasiBirthandDeath
 Threshold queueing
 Traffic
Cite this
}
Queueing and traffic. / Baër, Niek.
Enschede : Universiteit Twente, 2015. 155 p.Research output: Thesis › PhD Thesis  Research UT, graduation UT › Academic
TY  THES
T1  Queueing and traffic
AU  Baër, Niek
PY  2015/6/12
Y1  2015/6/12
N2  Traffic jams are everywhere, some are caused by constructions or accidents but a large portion occurs naturally. These "natural" traffic jams are a result of variable driving speeds combined with a high number of vehicles. To prevent these traffic jams, we must understand traffic in general, and to understand traffic we must understand the relations between the three key parameters of highway traffic, speed, the average speed of a vehicle, flow, the number of vehicles passing a reference point, and density, the number of vehicles on the road, where flow equals the product of speed and density. Queueing theory offers new insights in the remaining relation between these three parameters. In this thesis we have developed queueing models that are able to capture modernday highway traffic behaviour, and we have developed solution methods enabling the analysis of these queueing models. This thesis is organised in two parts, the first part covers traffic models based on queueing systems, while the second part discusses the theory behind the queueing models used. Chapter 1 provides a general introduction to the thesis. It indicates what we want to achieve with our traffic models and motivates our choice of queueing models. Furtermore, it explains the general idea behind our queueing models, i.e., the hystertic behaviour of highway traffic. The chapter concludes with an outline of the thesis. Chapter 2 is the introductory chapter to Part I. The chapter gives a historical overview of traffic models used to create the fundamental diagram of highway traffic. It discusses both singleregime traffic models and multiregime traffic models arising in literature. Furthermore, it gives a literature review on traffic models based on queueing theory. Two main queueing theoretic approaches can be identified to model highway traffic: the queue with waiting room of Heidemann, and the queue with blocking by Jain and Smith. The queueing models in this thesis are based Heidemann's queueing model. In Chapter 3 we introduce two queueing systems to model the a single highway section: the twostage $M/M/1$ threshold queue, and the fourstage $M/M/1$ feedback threshold queue. The service rates in the twostage $M/M/1$ threshold queue are controlled by a threshold policy, based on its queue length. This queueing system model the hysteretic behaviour of traffic on a single highway section. Since this hysteretic behavious is not limited to a single highway section we introduce the fourstage $M/M/1$ feedback threshold queue. In this queueing system, both the arrival rates and the service rates are controlled by a threshold policy modelling both the hysteretic behaviour of traffic on a single highway section, as well as its progression to the upstream highway section. Both queueing models are validated with empirical data on highway traffic obtained in Denmark. A sensitivity analysis was performed to investigate the effects of small changes in the parameters on the shape of the fundamental diagram. In Chapter 4 we model highway traffic on a sequence of highway sections. To this end, we extend the single queue models from Chapter 3 to a tandem network of twostage $M/M/1$ threshold queues and a tandem network of fourstage $M/M/1$ feedback threshold queues. In a tandem network of twostage $M/M/1$ threshold queues, the service rate of each queue is controlled by a threshold policy based on its queue length. This tandem network assumes that the hysteretic behaviour of traffic is conned to a single highway section. The tandem of fourstage $M/M/1$ feedback threshold queues also assumes a hysteretic relation between consecutive queues. In this tandem network, the service rates are controlled by the threshold policies of two consecutive queues. Both queueing models were solved numerically and the fundamental diagram of each individual queue was obtained. Next, a sensitivity analysis was performed to investigate the effects of small changes in the parameters on the shape of the fundamental diagram. Chapter 5 is the introductory chapter to Part II. It presents known results from the field of Matrix analytic methods on PhaseType distributions, Markovian Arrival Process and Markovian Service Processes, regular QuasiBirthandDeath processes and Level Dependent QuasiBirthandDeath processes. Chapter 6 extends the single queue traffic models of Chapter 3 to a more general queueing model, the $PH/PH/1$ multithreshold queue. In this queueing models, the arrival process and service process are given by a PhaseType distribution and controlled by an arbitrary threshold policy. The $PH/PH/1$ multithreshold queue is modelled as a Level Dependent QuasiBirthandDeath process and the stationary queue length distribution is obtained by decomposing the dfferent stages. Chapter 7 discusses a system of connected Level Dependent QuasiBirthandDeath processes, in which the Markov chain can be divided into subsets, each describing a Level Dependent QuasiBirthandDeath process. We provide a successive censoring algorithm to obtain the stationary distribution of such a system and investigate the possible connections between dierent subsets. In Chapter 8 we present an iterative aggregation method which gives an approximation of a single queue in a larger tandem network. While focusing on a single queue in the network, the aggregation method aggregates all upstream network behaviour into a Markovian Arrival Process, and all downstream network behaviour into a Markovian Service Process. This is done in an iterative fashion, aggregating one queue in each iteration, until all upstream (or downstream) queues are aggregated. The resulting queueing model is then analysed using results from the field of Matrix analytic methods. The iterative aggregation method is compared to simulation results of a tandem network of $M/M/1/k$ queues, a tandem network of twostage $M/M/1/k$ threshold queues, and a tandem network of fourstage $M/M/1/k$ feedback threshold queues. Chapter 9 gives concluding remarks and possibilities for further research.
AB  Traffic jams are everywhere, some are caused by constructions or accidents but a large portion occurs naturally. These "natural" traffic jams are a result of variable driving speeds combined with a high number of vehicles. To prevent these traffic jams, we must understand traffic in general, and to understand traffic we must understand the relations between the three key parameters of highway traffic, speed, the average speed of a vehicle, flow, the number of vehicles passing a reference point, and density, the number of vehicles on the road, where flow equals the product of speed and density. Queueing theory offers new insights in the remaining relation between these three parameters. In this thesis we have developed queueing models that are able to capture modernday highway traffic behaviour, and we have developed solution methods enabling the analysis of these queueing models. This thesis is organised in two parts, the first part covers traffic models based on queueing systems, while the second part discusses the theory behind the queueing models used. Chapter 1 provides a general introduction to the thesis. It indicates what we want to achieve with our traffic models and motivates our choice of queueing models. Furtermore, it explains the general idea behind our queueing models, i.e., the hystertic behaviour of highway traffic. The chapter concludes with an outline of the thesis. Chapter 2 is the introductory chapter to Part I. The chapter gives a historical overview of traffic models used to create the fundamental diagram of highway traffic. It discusses both singleregime traffic models and multiregime traffic models arising in literature. Furthermore, it gives a literature review on traffic models based on queueing theory. Two main queueing theoretic approaches can be identified to model highway traffic: the queue with waiting room of Heidemann, and the queue with blocking by Jain and Smith. The queueing models in this thesis are based Heidemann's queueing model. In Chapter 3 we introduce two queueing systems to model the a single highway section: the twostage $M/M/1$ threshold queue, and the fourstage $M/M/1$ feedback threshold queue. The service rates in the twostage $M/M/1$ threshold queue are controlled by a threshold policy, based on its queue length. This queueing system model the hysteretic behaviour of traffic on a single highway section. Since this hysteretic behavious is not limited to a single highway section we introduce the fourstage $M/M/1$ feedback threshold queue. In this queueing system, both the arrival rates and the service rates are controlled by a threshold policy modelling both the hysteretic behaviour of traffic on a single highway section, as well as its progression to the upstream highway section. Both queueing models are validated with empirical data on highway traffic obtained in Denmark. A sensitivity analysis was performed to investigate the effects of small changes in the parameters on the shape of the fundamental diagram. In Chapter 4 we model highway traffic on a sequence of highway sections. To this end, we extend the single queue models from Chapter 3 to a tandem network of twostage $M/M/1$ threshold queues and a tandem network of fourstage $M/M/1$ feedback threshold queues. In a tandem network of twostage $M/M/1$ threshold queues, the service rate of each queue is controlled by a threshold policy based on its queue length. This tandem network assumes that the hysteretic behaviour of traffic is conned to a single highway section. The tandem of fourstage $M/M/1$ feedback threshold queues also assumes a hysteretic relation between consecutive queues. In this tandem network, the service rates are controlled by the threshold policies of two consecutive queues. Both queueing models were solved numerically and the fundamental diagram of each individual queue was obtained. Next, a sensitivity analysis was performed to investigate the effects of small changes in the parameters on the shape of the fundamental diagram. Chapter 5 is the introductory chapter to Part II. It presents known results from the field of Matrix analytic methods on PhaseType distributions, Markovian Arrival Process and Markovian Service Processes, regular QuasiBirthandDeath processes and Level Dependent QuasiBirthandDeath processes. Chapter 6 extends the single queue traffic models of Chapter 3 to a more general queueing model, the $PH/PH/1$ multithreshold queue. In this queueing models, the arrival process and service process are given by a PhaseType distribution and controlled by an arbitrary threshold policy. The $PH/PH/1$ multithreshold queue is modelled as a Level Dependent QuasiBirthandDeath process and the stationary queue length distribution is obtained by decomposing the dfferent stages. Chapter 7 discusses a system of connected Level Dependent QuasiBirthandDeath processes, in which the Markov chain can be divided into subsets, each describing a Level Dependent QuasiBirthandDeath process. We provide a successive censoring algorithm to obtain the stationary distribution of such a system and investigate the possible connections between dierent subsets. In Chapter 8 we present an iterative aggregation method which gives an approximation of a single queue in a larger tandem network. While focusing on a single queue in the network, the aggregation method aggregates all upstream network behaviour into a Markovian Arrival Process, and all downstream network behaviour into a Markovian Service Process. This is done in an iterative fashion, aggregating one queue in each iteration, until all upstream (or downstream) queues are aggregated. The resulting queueing model is then analysed using results from the field of Matrix analytic methods. The iterative aggregation method is compared to simulation results of a tandem network of $M/M/1/k$ queues, a tandem network of twostage $M/M/1/k$ threshold queues, and a tandem network of fourstage $M/M/1/k$ feedback threshold queues. Chapter 9 gives concluding remarks and possibilities for further research.
KW  Matrix Analytic Methods
KW  QuasiBirthandDeath
KW  Threshold queueing
KW  Traffic
U2  10.3990/1.9789036538121
DO  10.3990/1.9789036538121
M3  PhD Thesis  Research UT, graduation UT
SN  9789036538121
T3  CTIT Ph.D.thesis Series
PB  Universiteit Twente
CY  Enschede
ER 