Point queue models: A unified approach

In transportation and other types of facilities, various queues arise when the demands of service are higher than the supplies, and many point and fluid queue models have been proposed to study such queueing systems. However, there has been no unified approach to deriving such models, analyzing their relationships and properties, and extending them for networks. In this paper, we derive point queue models as limits of two link-based queueing model: the link transmission model and a link queue model. With two definitions for demand and supply of a point queue, we present four point queue models, four approximate models, and their discrete versions. We discuss the properties of these models, including equivalence, well-definedness, smoothness, and queue spillback, both analytically and with numerical examples. We then analytically solve Vickrey’s point queue model and stationary states in various models. We demonstrate that all existing point and fluid queue models in the literature are special cases of those derived from the link-based queueing models. Such a unified approach leads to systematic methods for studying the queueing process at a point facility and will also be helpful for studies on stochastic queues as well as networks of queues.     

Optimal queue placement in dynamic system optimum solutions for single origin-destination traffic networks

The Dynamic System Optimum (DSO) traffic assignment problem aims to determine a time-dependent routing pattern of travellers in a network such that the given time-dependent origin-destination demands are satisfied and the total travel time is at a minimum, assuming some model for dynamic network loading. The network kinematic wave model is now widely accepted as such a model, given its realism in reproducing phenomena such as transient queues and spillback to upstream links. An attractive solution strategy for DSO based on such a model is to reformulate as a set of side constraints apply a standard solver, and to this end two methods have been previously proposed, one based on the discretisation scheme known as the Cell Transmission Model (CTM), and the other based on the Link Transmission Model (LTM) derived from variational theory. In the present paper we aim to combine the advantages of CTM (in tracking time-dependent congestion formation within a link) with those of LTM (avoiding cell discretisation, providing a more computationally attractive with much fewer constraints). The motivation for our work is the previously-reported possibility for DSO to have multiple solutions, which differ in where queues are formed and dissipated in the network. Our aim is to find DSO solutions that optimally distribute the congestion over links inside the network which essentially eliminate avoidable queue spillbacks. In order to do so, we require more information than the LTM can offer, but wish to avoid the computational burden of CTM for DSO. We thus adopt an extension of the LTM called the Two-regime Transmission Model (TTM), which is consistent with LTM at link entries and exits but which is additionally able to accurately track the spatial and temporal formation of the congestion boundary within a link (which we later show to be a critical element, relative to LTM). We set out the theoretical background necessary for the formulation of the network-level TTM as a set of linear side constraints. Numerical experiments are used to illustrate the application of the method to determine DSO solutions avoiding spillbacks, reduce/eliminate the congestion and to show the distinctive elements of adopting TTM over LTM. Furthermore, in comparison to a fine-level CTM-based DSO method, our formulation is seen to significantly reduce the number of linear constraints while maintaining a reasonable accuracy.     

On dynamics of traffic queues in a road network with route choice based on real time traffic information

Introducing real time traffic information into transportation network makes it necessary to consider development of queues and traffic flows as a dynamic process. This paper initiates a theoretical study of conditions under which this process is stable. A model is presented that describes within-one-day development of queues when drivers affected by real-time traffic information choose their paths en route. The model is reduced to a system of differential equations with delay. Equilibrium points of the system correspond to constant queue lengths. Stability of the system is investigated using characteristic values of the linearised minimal face flow. A traffic network example illustrating the method is provided.     

Analysing queueing at toll plazas using a coupled,multiple-queue,queueing system model: application to toll plaza design

A vehicle approaching a toll plaza observes the queues at each of the available toll-lanes before choosing which to join. This choice process, the arrival process of vehicles and the service characteristics of the toll-booths, affect the queues and delay the drivers. In this paper, queueing at a toll plaza is modelled as a multiple-queue queueing system where the arrival process to a queue (toll-lane) is dependent on the state of all the queues. In the past, such systems have been modelled mathematically only for two queues and are not applicable for toll plazas with three or more toll-lanes. The proposed model determines the steady-state probability density function (pdf) for the queues at large toll plazas. This study is used to determine the number of toll-lanes or the length of the upstream queueing area required to achieve certain user-specified levels-of-service. Expected delay and maximum queue length are used as level-of-service measures. Indicative design charts are also provided.     

Walking-distance introduced queueing model for pedestrian queueing system: Theoretical analysis and experimental verification

We have introduced the effect of delay in walking from the head of a queue to the service windows in the queueing model and obtain a suitable type of queueing system under various conditions by both computational simulation and theoretical analysis. When there are multiple service windows, the queueing theory indicates that mean waiting time in a fork-type queueing system (Fork), which collects pedestrians into a single queue, is smaller than that in a parallel-type queueing system (Parallel), i.e., queues for each service window. However, in our walking-distance introduced queueing model, we have examined that mean waiting time in Parallel becomes smaller when both the arrival probability of pedestrians and the effect of walking distance are large. Moreover, enhanced Forks, which shorten waiting time by reducing the effect of walking distance, are considered, and parts of our results are also verified by real queueing experiments.     

Nonlinear gating control for urban road traffic network using the network fundamental diagram

This work proposes a nonlinear model predictive controller for the urban gating problem. The system model is formalized based on a research on existing models of the network fundamental diagram and the perimeter control systems. For the existing models, modifications are suggested: additional state variables are allocated to describe the queue dynamics at the network gates. Using the extended model, a nonlinear model predictive controller is designed offering a ‘non‐greedy’ policy compared with previous, ‘greedy’ gating control designs. The greedy and non‐greedy nonlinear model predictive control (NMPC) controllers are compared with a greedy linear feedback proportional‐integral‐derivative (PID) controller in different traffic situations. The proposed non‐greedy NMPC controller outperforms the other two approaches in terms of travel distance performance and queue lengths. The performance results justify the consideration of queue lengths in dynamic modeling, and the use of NMPC approach for controller design. Copyright © 2014 John Wiley & Sons, Ltd.     

Network traffic flow optimization under performance constraints

In this paper, a model-based perimeter control policy for large-scale urban vehicular networks is proposed. Assuming a homogeneously loaded vehicle network and the existence of a well-posed Network Fundamental Diagram (NFD), we describe a protected network throughout its aggregated dynamics including nonlinear exit flow characteristics. Within this framework of constrained optimal boundary flow gating, two main performance metrics are considered: (a) first, connected to the NFD, the concept of average network travel time and delay as a performance metric is defined; (b) second, at boundaries, we take into account additional external network queue dynamics governed by uncontrolled inflow demands. External queue capacities in terms of finite-link lengths are used as the second performance metric. Hence, the corresponding performance requirement is an upper bound of external queues. While external queues represent vehicles waiting to enter the protected network, internal queue describes the protected network’s aggregated behavior.By controlling the number of vehicles joining the internal queue from the external ones, herewith a network traffic flow maximization solution subject to the internal and external dynamics and their performance constraints is developed. The originally non-convex optimization problem is transformed to a numerically efficiently convex one by relaxing the performance constraints into time-dependent state boundaries. The control solution can be interpreted as a mechanism which transforms the unknown arrival process governing the number of vehicles entering the network to a regulated process, such that prescribed performance requirements on travel time in the network and upper bound on the external queue are satisfied. Comparative numerical simulation studies on a microscopic traffic simulator are carried out to show the benefits of the proposed method.     

Continuum signalized junction model for dynamic traffic networks: Offset,spillback, and multiple signal phases

This paper extends the continuum signalized intersection model exhaustively studied in Han et al. (2014) to more accurately account for three realistic complications: signal offsets, queue spillbacks, and complex signal phasing schemes. The model extensions are derived theoretically based on signal cycle, green split, and offset, and are shown to approximate well traffic operations at signalized intersections treated using the traditional (and more realistic) on-and-off model. We propose a generalized continuum signal model, which explicitly handles complex vehicle spillback patterns on signalized networks with provable error estimates. Under mild conditions, the errors are small and bounded by fixed values that do not grow with time. Overall, this represents a significant improvement over the original continuum model, which had errors that grew quickly with time in the presence of any queue spillbacks and for which errors were not explicitly derived for different offset cases. Thus, the new model is able to more accurately approximate traffic dynamics in large networks with multiple signals under more realistic conditions. We also qualitatively describe how this new model can be applied to several realistic intersection configurations that might be encountered in typical urban networks. These include intersections with multiple entry and exit links, complex signal phasing, all-red times, and the presence of dedicated turning lanes. Numerical tests of the models show remarkable consistency with the on-and-off model, as expected from the theory, with the added benefit of significant computational savings and higher signal control resolution when using the continuum model.     

Design and evaluation of dynamic traffic management strategies for congested conditions

This paper presents a procedure for dynamic design and evaluation of traffic management strategies in oversaturated conditions. The method combines a dynamic control algorithm and a disutility function. The dynamic algorithm designs signal control parameters to manage formation and dissipation of queues on system links with explicit consideration of current and projected queue lengths and demands. The disutility function measures the relative performance of the dynamic control algorithm based on preset system performance goals. The user may statically select the management strategy, or alternatively the system may be instructed to set off different management schemes based on predefined performance thresholds. The problem was formulated as one of output maximization subject to state, control, and traffic management strategy choices. Solutions were obtained using genetic algorithms. Four traffic management plans were tested to show the capabilities of the new procedure. The results show that the procedure is able to generate suitable signal control schemes that are favorable to attaining the desired traffic management goals. The results showed that multiple, or hybrids of single measures of effectiveness may need to be examined in order to correctly assess system performance. The procedure has potential for real-time implementation in an intelligent transportation system setting.     

The representation and implementation of time-dependent inundation in large-scale microscopic evacuation simulations

Multi-agent simulation has increasingly been used for transportation simulation in recent years. With current techniques, it is possible to simulate systems consisting of several million agents. Such multi-agent simulations have been applied to whole cities and even large regions. In this paper it is demonstrated how to adapt an existing multi-agent transportation simulation framework to large-scale pedestrian evacuation simulation. The underlying flow model simulates the traffic-based on a simple queue model where only free speed, bottleneck capacities, and space constraints are taken into account. The queue simulation, albeit simple, captures the most important aspects of evacuations such as the congestion effects of bottlenecks and the time needed to evacuate the endangered area. In the case of an evacuation simulation the network has time-dependent attributes. For instance, large-scale inundations or conflagrations do not cover all the endangered area at once.These time-dependent attributes are modeled as network change events. Network change events are modifying link parameters at predefined points in time. The simulation framework is demonstrated through a case study for the Indonesian city of Padang, which faces a high risk of being inundated by a tsunami.     

Stochastic dynamic itinerary interception refueling location problem with queue delay for electric taxi charging stations

A new facility location model and a solution algorithm are proposed that feature (1) itinerary-interception instead of flow-interception; (2) stochastic demand as dynamic service requests; and (3) queueing delay. These features are essential to analyze battery-powered electric shared-ride taxis operating in a connected, centralized dispatch manner. The model and solution method are based on a bi-level, simulation–optimization framework that combines an upper level multiple-server allocation model with queueing delay and a lower level dispatch simulation based on earlier work by Jung and Jayakrishnan. The solution algorithm is tested on a fleet of 600 shared-taxis in Seoul, Korea, spanning 603 km², a budget of 100 charging stations, and up to 22 candidate charging locations, against a benchmark “naïve” genetic algorithm that does not consider cyclic interactions between the taxi charging demand and the charger allocations with queue delay. Results show not only that the proposed model is capable of locating charging stations with stochastic dynamic itinerary-interception and queue delay, but that the bi-level solution method improves upon the benchmark algorithm in terms of realized queue delay, total time of operation of taxi service, and service request rejections. Furthermore, we show how much additional benefit in level of service is possible in the upper-bound scenario when the number of charging stations is unbounded.     

Modeling and simulation of vehicle projection arrival–discharge process in adaptive traffic signal controls

Real‐time signal control operates as a function of the vehicular arrival and discharge process to satisfy a pre‐specified operational performance. This process is often predicted based on loop detectors placed upstream of the signal. In our newly developed signal control for diamond interchanges, a microscopic model is proposed to estimate traffic flows at the stop‐line. The model considers the traffic dynamics of vehicular detection, arrivals, and departures, by taking into account varying speeds, length of queues, and signal control. As the signal control is optimized over a rolling horizon that is divided into intervals, the vehicular detection for and projection into the corresponding horizon intervals are also modeled. The signal control algorithm is based on dynamic programming and the optimization of signal policy is performed using a certain performance measure involving delays, queue lengths, and queue storage ratios. The arrival–discharge model is embedded in the optimization algorithm and both are programmed into AIMSUN, a microscopic stochastic simulation program. AIMSUN is then used to simulate the traffic flow and implement the optimal signal control by accessing internal data including detected traffic demand and vehicle speeds. Sensitivity analysis is conducted to study the effect of selecting different optimization criteria on the signal control performance. It is concluded that the queue length and queue storage ratio are the most appropriate performance measures in real‐time signal control of interchanges. Copyright © 2010 John Wiley & Sons, Ltd.     

Real-time queue length estimation for congested signalized intersections

How to estimate queue length in real-time at signalized intersection is a long-standing problem. The problem gets even more difficult when signal links are congested. The traditional input–output approach for queue length estimation can only handle queues that are shorter than the distance between vehicle detector and intersection stop line, because cumulative vehicle count for arrival traffic is not available once the detector is occupied by the queue. In this paper, instead of counting arrival traffic flow in the current signal cycle, we solve the problem of measuring intersection queue length by exploiting the queue discharge process in the immediate past cycle. Using high-resolution “event-based” traffic signal data, and applying Lighthill–Whitham–Richards (LWR) shockwave theory, we are able to identify traffic state changes that distinguish queue discharge flow from upstream arrival traffic. Therefore, our approach can estimate time-dependent queue length even when the signal links are congested with long queues. Variations of the queue length estimation model are also presented when “event-based” data is not available. Our models are evaluated by comparing the estimated maximum queue length with the ground truth data observed from the field. Evaluation results demonstrate that the proposed models can estimate long queues with satisfactory accuracy. Limitations of the proposed model are also discussed in the paper.     

Optimal freeway ramp metering using the asymmetric cell transmission model

The onramp metering control problem is posed using a cell transmission-like model called the asymmetric cell transmission model (ACTM). The problem formulation captures both freeflow and congested conditions, and includes upper bounds on the metering rates and on the onramp queue lengths. It is shown that a near-global solution to the resulting nonlinear optimization problem can be found by solving a single linear program, whenever certain conditions are met. The most restrictive of these conditions requires the congestion on the mainline not to back up onto the onramps whenever optimal metering is used. The technique is tested numerically using data from a severely congested stretch of freeway in southern California. Simulation results predict a 17.3% reduction in delay when queue constraints are enforced.     

The dynamics of traffic assignment and traffic control: A theoretical study

The paper considers traffic assignment, with traffic controls, in an increasingly dynamic way. First, a natural way of introducing the responsive policy, P_o, into steady state traffic assignment is presented. Then it is shown that natural stability results follow within a dynamical version of this static equilibrium model (still with a constant demand). We are able to obtain similar stability results when queues are explicitly allowed for, provided demand is constant. Finally we allow demand to vary with time; we consider the dynamic assignment problem with signal-settings now fixed. Here we assume that vehicles are very short and that deterministic queueing theory applies, and show that the time-dependent queueing delay at the bottleneck at the end of a link is a monotone function of the time-dependent input profile to the bottleneck. We have been unable to obtain results when dynamic demand and responsive signal control are combined.     

A probabilistic model for traffic at actuated control signals

Vehicle actuated controls are designed to adapt green and red times automatically, according to the actual dynamics of the arrival, departure and queuing processes. In turn, drivers experience variable delays and waiting times at these signals. However, in practice, delays and waiting times are computed at these systems with models that assume stationariety in the arrival process, and that are capable of computing simply expectation values, while no information is given on the uncertainty around this expectation. The growing interest on measures like travel time reliability, or network robustness motivates the development of models able to quantify the variability of traffic at these systems.This paper presents a new modeling approach for estimating queues and signal phase times, based on probabilistic theory. This model overcomes the limitations of existing models in that it does not assume stationary arrival rates, but it assumes any temporal distribution as input, and allows one to compute the temporal evolution of queue length and signal sequence probabilities. By doing so, one can also quantify the uncertainty in the estimation of delays and waiting times as time-dependent processes. The results of the probabilistic approach have been compared to the results of repeated microscopic simulations, showing good agreement. The smaller number of parameters and shorter computing times required in the probabilistic approach makes the model suitable for, e.g., planning and design problems, as well as model-based travel time estimation.     

A kinematic wave approach to traffic statics and dynamics in a double-ring network

Recently there has been much interest in understanding macroscopic fundamental diagrams of stationary road networks. However, there lacks a systematic method to define and solve stationary states in a road network with complex junctions. In this study we propose a kinematic wave approach to defining, analyzing, and simulating static and dynamic traffic characteristics in a network of two ring roads connected by a 2 × 2 junction, which can be either an uninterrupted interchange or a signalized intersection. This study is enabled by recently developed macroscopic junction models of general junctions. With a junction model based on fair merging and first-in-first-out diverging rules, we first define and solve stationary states and then derive the macroscopic fundamental diagram (MFD) of a stationary uninterrupted network. We conclude that the flow-density relationship of the uninterrupted double-ring network is not unique for high average network densities (i.e., when one ring becomes congested) and unveil the existence of infinitely many stationary states that can arise with a zero-speed shockwave. From simulation results with a corresponding Cell Transmission Model, we verify that all stationary states in the MFD are stable and can be reached, but show that randomness in the retaining ratio of each ring drives the network to more symmetric traffic patterns and higher flow-rates. Furthermore we model a signalized intersection as two alternate diverge junctions and demonstrate that the signalized double-ring network can reach asymptotically periodic traffic patterns, which are therefore defined as “stationary” states in signalized networks. With simulations we show that the flow-density relation is well defined in such “stationary” states, and asymptotic traffic patterns can be impacted by signal cycle lengths and retaining ratios. But compared with uninterrupted interchanges, signalized intersections lead to more asymmetric traffic patterns, lower flow-rates, and even gridlocks when the average density is higher than half of the jam density. The results are consistent between this study and existing studies, but the network kinematic wave model, with appropriate junction models, is mathematically tractable and physically meaningful. It has offered a more complete picture regarding the number and type of stationary states, their stability, and MFD in freeway and signalized networks.     

Distributions of queue lengths at fixed time traffic signals

This paper presents a new model which studies probability distributions of queue lengths at fixed time traffic signals. It extends Haight's model for Poisson arrivals that the arrival distribution during the effective red period is general and the headway between two successive departures is not less than the minimum departure headway. Moreover, the probability generating function of the queue length, at the end of the effective red period, is derived. The probabilities of the queue lengths, at the ends of the effective green, actual red and amber periods, are also obtained. Comparison is made with Haight's model. Finally a case study for the proposed model is reported.     

Effects of queue spillover in networks considering simultaneous departure time and route choices

This paper explores the effects of queue spillover in transportation networks, in the context of dynamic traffic assignment. A model of spatial queue is defined to characterize dynamic traffic flow and queuing formation in network links. Network users simultaneously choose departure time and travel route to minimize the travel cost including journey time and unpunctuality penalty. Using some necessary conditions of the dynamic user equilibrium, dynamic network flows are obtained exactly on some networks with typical structure. Various effects of queue spillover are discussed based on the results of these networks, and some new paradoxes of link capacity expansion have been found as a result of such effects. Analytical and exact results in these typical networks show that ignoring queuing length may generate biased solutions, and the link storage capacity is a very important factor concerning the performance of networks.     

Access control policies without inside queues: Their properties and public policy implications

An access control policy that eliminates all queues beyond the entry points to a network has obvious benefits, which include smooth travel and predictable travel times inside the network. Yet it has never been proven, to the best of our knowledge, whether excluding inside queues yields sub-optimal network performance or, in other words, allowing inside queues can actually further reduce the system travel cost. Moreover, it is not clear whether an optimal control policy derived from efficiency considerations can also be a fair policy to all road users. This paper provide answers to these questions in the context of a monocentric network. By analyzing the structure of the access control problem considering all feasible policies (with/without inside queues), we show that the minimal system cost realizable by access control can be obtained without directly solving a non-convex optimization program, and can indeed always be achieved by a control policy excluding all of the inside queues. These optimal policies are defined by a polyhedral set and a Finite Generation Algorithm can be applied to derive the analytical form of this set. The optimal policies are not unique in general, thus making it possible to achieve both minimal system cost and fairness simultaneously.