Queueing and traffic

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 modern-day 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 single-regime traffic models and multi-regime 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 two-stage $M/M/1$ threshold queue, and the four-stage $M/M/1$ feedback threshold queue. The service rates in the two-stage $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 two-stage $M/M/1$ threshold queues and a tandem network of four-stage $M/M/1$ feedback threshold queues. In a tandem network of two-stage $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 four-stage $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 Phase-Type distributions, Markovian Arrival Process and Markovian Service Processes, regular Quasi-Birth-and-Death processes and Level Dependent Quasi-Birth-and-Death processes. Chapter 6 extends the single queue traffic models of Chapter 3 to a more general queueing model, the $PH/PH/1$ multi-threshold queue. In this queueing models, the arrival process and service process are given by a Phase-Type distribution and controlled by an arbitrary threshold policy. The $PH/PH/1$ multi-threshold queue is modelled as a Level Dependent Quasi-Birth-and-Death process and the stationary queue length distribution is obtained by decomposing the dfferent stages. Chapter 7 discusses a system of connected Level Dependent Quasi-Birth-and-Death processes, in which the Markov chain can be divided into subsets, each describing a Level Dependent Quasi-Birth-and-Death 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 two-stage $M/M/1/k$ threshold queues, and a tandem network of four-stage $M/M/1/k$ feedback threshold queues. Chapter 9 gives concluding remarks and possibilities for further research.