Search

A paper published in 1983 in this journal by A. de Palma et at. uses a deterministic queueing supply model in combination with a random utility demand model to predict the pattern of traffic flows during a peak period. Two different versions of the supply model are included, a "basic model" which is identical to the supply model used by a number of other authors investigating the same general problem (e.g., M. J. Smith, 1984), and a more complicated "extended model." As detailed below, there is a mathematical discrepancy in the analysis. Because of this discrepancy, some of the conclusions about the traffic flow pattern in the case of the extended model are incorrect and all are unproven. For the simpler-and seemingly more realistic-basic model the discrepancy vanishes and the conclusions remain valid. [ABSTRACT FROM AUTHOR]

High levels of flight delays require implementation of airport congestion mitigation tools. In this paper, we optimize the use of airport capacity at the tactical level in the face of operational uncertainty. We formulate an original Dynamic Programming model that jointly and dynamically selects runway configurations and the balance of arrival and departure service rates at a busy airport to minimize congestion costs, under stochastic queue dynamics and stochastic operating conditions. Control is exercised as a function of flight schedules, of arrival and departure queue lengths, and of weather and wind conditions. We implement the model in a realistic setting at JFK Airport. The exact Dynamic Programming algorithm terminates within reasonable time frames. In addition, we implement an approximate one-step look-ahead algorithm that considerably accelerates execution of the model and results in close-to-optimal policies. Together, these solution algorithms enable online implementation of the model using real-time information on flight schedules and meteorological conditions. Application of the model shows that the optimal policy is path-dependent, i.e., it depends on prior decisions and on the stochastic evolution of arrival and departure queues during the day. This underscores the theoretical and practical need for integrating operating stochasticity into the decision-making framework. From comparisons with an alternative model based on deterministic queue dynamics, we estimate the benefit of considering queue stochasticity at 5% to 20%. Finally, comparisons with heuristics designed to imitate actual operating procedures suggest that the model can yield significant cost savings, estimated at 20% to 30%. [ABSTRACT FROM AUTHOR]

Observations of freeway traffic flow are usually quite scattered about an underlying curve when plotted versus density or occupancy. Although increasing the sampling intervals can reduce the scatter, whenever an experiment encompasses a rush hour with transitions in and out of congestion, some outlying data stubbornly remain beneath the ‘equilibrium’ curve. The existence of these nonequilibrium points is a poorly understood phenomenon that appears to contradict the simple kinematic wave (KW) model of traffic flow. This paper provides a tentative explanation of the phenomenon, based on experimental evidence. The evidence was a FIFO queue that grew and receded over two detector stations, generating typical flow-density scatter plots at both locations. The locations were far from other interacting traffic streams. The data revealed that a transition zone where vehicles decelerated gradually existed immediately behind the queue. The transition zone was quite wide (about 1 km at both locations), moved slowly (approximately with the ‘shock’ velocity of KW theory), and as a result spent many minutes over each detector station. Disequilibrium flow-density points arose only when the transition zone was over the detectors, suggesting that the transition zone explains their occurrence. The disequilibrium points drifted gradually from one branch of the curve to the other, as KW theory would have predicted if ‘shocks’ had a characteristic width equal to the dimension of the transition zone. Nothing was found in the data to contradict this view. This paper also shows that in our case, if one neglects the shocks' physical dimension, the position of every vehicle can be predicted with KW theory to within approximately five vehicle spacings. Thus, it appears that KW theory can predict rather accurately traffic behavior at the back of FTFO queues, i.e., when the lanes are equally attractive to all drivers. We end with a discussion offering some perspective on how the findings of this paper related to the traffic thinking found in the current literature. [ABSTRACT FROM AUTHOR]

This paper explores some of the traffic phenomena that arise when drivers have to navigate a network in which queues back up past diverge intersections. If a diverge provides two alternative routes to the same destination and the shorter route has a bottleneck that generates a queue, one would expect that queue to stabilize at an equilibrium level where the travel time on both routes is roughly equal. If the capacity of the alternative route is unlimited then this network can accommodate any demand level. However, if the bottleneck is so close to the upstream end of the link that the equilibrium queue cannot be contained in the link, then the trip time on the queued route cannot grow to match that on the alternate route. This means that the alternative route can never be attractive, even if the queue spills back past the diverge, and that drivers approaching the diverge will act as if the alternative route did not exist. As a result, a steady flow into the system greater than the capacity of the bottleneck will cause a queue to grow all the way back to the origin (blocking it). The final result is an "oversaturated static state" where the queue regulates the input flow into the system. Curiously, if the bottleneck capacity of this network is reduced below a critical level (or is eliminated altogether) then the alternative route becomes attractive again and the system cannot reach the saturation point. This phenomenon is explored in the paper, where it is also shown that: i) a network can become permanently oversaturated / undersaturated as a result of a temporary increase / decrease in link capacity, ii) even under the most favorable assumptions, and in contrast to the equivalent assignment problem with point queues, a network can be stable both in an oversaturated and an undersaturated state, and iii) temporary endogenous disturbances can permanently reverse the saturation state of a network. These findings suggest that in certain situations the time-dependent traffic assignment problem with physical queues is chaotic in nature and that (as in weather forecasting) it may be impossible to obtain input data with the required accuracy to make reliable predictions of cumulative output flows. [ABSTRACT FROM AUTHOR]

This paper studies single server queueing systems where customers arrive according to a schedule, but not punctually, and where service might be provided in the scheduled order; thus, customers may leave the system in a sequence different to that of their arrivals. The situation arises in connection with maritime container terminals. The steady state solution to the problem follows an integral equation that may be solved numerically. When congestion is light (as is usual in well managed ports) approximate analytic solutions to the integral equation can be found. As an illustration, formulas are given that apply if the deviations from the schedule and the service times have some specific distributions. These expressions accurately predict the expected delay for systems with fairly unpunctual arrivals and occasional congestion. The paper also contains an exact analytical solution for the special case in which service times are constant and the deviations from the arrival schedule are independent Gumbel variables. [ABSTRACT FROM AUTHOR]

Queueing because of congestion is an important aspect of road traffic. This paper provides a novel threshold queue that models the empirical shape of the fundamental diagram. In particular, we show that our threshold queue with two service phases captures the capacity drop that is eminent in the fundamental diagram of modern traffic. We use measurements on a Danish highway to illustrate that our threshold queue is indeed capable of capturing the fundamental diagram of real-world traffic systems. We furthermore indicate the modelling power of our threshold queue via a sensitivity study showing that our model is able to capture a wide range of shapes for the fundamental diagram. The online appendix is available at https://doi.org/10.1287/trsc.2018.0850. [ABSTRACT FROM AUTHOR]

Sequential zone picking systems are popular conveyor-based picker-to-parts order picking systems that divide the order picking area in work zones. When designing a zone picking system, it is important to know whether the throughput capability of the system can meet customer demand. However, the performance and maximum throughput capability of a zone picking system is largely determined by congestion and blocking that occur at the various conveyor merges in the system. In this paper we develop an analytical model to study the impact of conveyor merges in sequential zone picking systems. Because of finite buffers, blocking, recirculation, and merging, the resulting queueing model does not have a product-form stationary queue-length distribution which makes exact analysis practically infeasible. Therefore, we develop an approximate solution by using an aggregation technique and matrix-geometric methods to study the throughput capability of the system. The model is suitable to support rapid design of complex zone picking systems, in terms of number and length of zones, input and output buffer capacities, and storage allocation of products to zones to meet prespecified performance targets. Comparison of the approximation results to simulation show that for a wide range of parameters the mean relative error in the system throughput is typically less than 5%. The model accurately predicts the loss in throughput due to congestion and blocking at the merges, and can be used to allocate input and output buffer spaces to maximize the throughput capability of the system. [ABSTRACT FROM AUTHOR]

This paper proposes a link-based continuous-time dynamic user equilibrium model for networks with single destinations. The model captures realistic queue spillbacks by applying the double-queue concept at the link level and developing a new nodal model that extends the link-level dynamics to the network level. The departure-time choice, route choice, and other equilibrium conditions are introduced to complete the model. The proposed model is a differential complementary system formulation with time-varying, state-dependent delays. Approximations on travel times are constructed to simplify the model. Numerical tests are developed to illustrate the application of this model. [ABSTRACT FROM AUTHOR]

This paper develops a queueing model for aircraft arrivals at a single server under trajectory-based flight operations, which are expected to prevail in the Next Generation Air Transportation System. Aircraft are assigned scheduled times of arrival at a server, which they meet with some normally distributed stochastic error. The Clark approximation method is employed to estimate expected queueing delays, and it is shown, through comparison with simulation, that the method yields very accurate estimates. Exact results are derived for a special case in which aircraft are metered into a capacity-constrained area with constant excess time separation between them. This allows analysis of the tradeoff between the "stochastic delay" that results from imperfect adherence to metered times of arrival and the additional "deterministic delay" from metering at a headway above the minimum required. [ABSTRACT FROM AUTHOR]

In this paper we develop a service network design model that explicitly takes into account the elasticity of customer demand with respect to travel distance and congestion delays. The model incorporates a feedback loop between customer demand and congestion at the facilities. The problem is to determine the number of facilities, their locations, their service capacity, and the assignment of customers to facilities so as to maximize the overall profit of the system. Two versions of the problem are presented. In one, each facility is modeled as an M/M/1 queuing system where the service rate is a decision variable; in the other one, the facility is modeled as an M/M/k queuing model where the service rate is given, but the number k is a decision variable. An exact algorithm and heuristics are developed and tested via computational experiments. Although our model is of the "directed choice" type where the assignment of customers to facilities is controlled by the decision maker, computational results show that in the vast majority of cases the customers are assigned to the utility-maximizing facility, indicating that there is no conflict between the customers' and decision makers' goals. A case study of locating preventive medicine clinics in Toronto, Ontario, illustrates the model. [ABSTRACT FROM AUTHOR]

This paper deals with the fixed-cycle traffic-light (FCTL) queue, where vehicles arrive at an intersection controlled by a traffic light and form a queue. The traffic light alternates between green and red periods, and delayed vehicles are assumed to depart during the green period at equal time intervals. The key performance characteristic in the FCTL queue is the so-called mean overflow, defined as the mean queue length at the end of a green period. An exact solution for the mean overflow is available, but it has been considered to be of little practical value because it requires some numerical procedures. Therefore, most of the literature on the FCTL queue is about deriving approximations for the mean overflow. In deriving these approximations, most authors first approximate the FCTL queue by a bulk-service queue, approximate the mean overflow in the bulk-service queue, and use this as an approximation for the mean overflow in the FCTL queue. So far no quantitative comparison of both models has been given. We compare both models and assess the quality of the approximation for various settings of the parameter values. In this comparison and throughout the paper we do not restrict ourselves to Poisson arrivals, but consider a more general arrival process instead. We discuss the numerical issues that need to be resolved to calculate the exact expression for the mean overflow in both queues and show that clear computational schemes are available. Next, we present several bounds and approximations of the mean overflow that do not require numerical procedures. In particular, we derive a new approximation based on the heavy traffic limit and a scaling argument. We compare the new bounds and approximation with the existing ones. We elaborate on the impact of several parameters, like the length of the green and red period and the variance of the arrival distribution. [ABSTRACT FROM AUTHOR]

This paper focuses on designing a facility network, taking into account that the system may be congested. The objective is to minimize the overall fixed and service capacity costs, subject to the constraints that for any demand the disutility from travel and waiting times (measured as the weighted sum of the travel time from a demand to the facility serving that demand and the average waiting time at the facility) cannot exceed a predefined maximum allowed level (measured in units of time). We develop an analytical framework for the problem that determines the optimal set of facilities and assigns each facility a service rate (service capacity). In our setting, the consumers would like to maximize their utility (minimize their disutility) when choosing which facility to patronize. Therefore, the eventual choice of facilities is a user-equilibrium problem, where at equilibrium, consumers do not have any incentive to change their choices. The problem is formulated as a nonlinear mixed-integer program. We show how to linearize the nonlinear constraints and solve instead a mixed-integer linear problem, which can be solved efficiently. [ABSTRACT FROM AUTHOR]

The queueing-theoretical model for stationary traffic flow developed in a former paper is extended and modified for nonstationary flow. In particular it is shown how speed-flow-density relationships under nonstationary conditions may deviate from those obtained for stationary conditions.It is shown how the wide scatter which is often observed with empirical speed-flow-density data can be explained by nonstationarity. Furthermore, hysteresis loops,which may show up in speed-flow-density relationships, are interpreted by means of nonstationarity. [ABSTRACT FROM AUTHOR]

This paper evaluates the entrance capacity and queueing delay for Automated Highway Systems through use of simulations and analytical modeling. Queueing statistics are also used to determine the sustainable capacity of alternative concepts, taking trip length distribution and spacing between ramps into consideration. Based on safety-spacing headways (produced in a separate analysis), the most promising concept utilizes platoons both on the highway and on on-ramps. However, it is unclear whether comparable capacity can be achieved on exit, when vehicles must be decoupled from their platoons, and whether it is safe for vehicles to enter the highway in closely spaced platoons. The analytical evaluation indicates that entrance/exit spacing on the order of one per 2 km or closer would be required to support highways with total capacity on the order of 20,000 vehicles per hour. Most likely, this would be achieved most efficiently if separate dedicated entrances are provided for automated vehicles, to minimize weaving on manual lanes. [ABSTRACT FROM AUTHOR]

On two-lane two-way roads overtaking opportunities are limited by the opposing traffic. For fixed volumes of traffic in both directions the opportunities for vehicles in one lane to overtake depend on the mean length of queues in the second lane, so that the mean queue length in the first lane is a function of the mean queue length in the second lane and vice versa. This paper takes an earlier procedure for determining the mean queue lengths in the two lanes at equilibrium and simplifies it by assuming that the distribution of queue lengths is known. The results obtained by assuming that the underlying distribution is Miller, Borel-Tanner, or geometric are then compared by a numerical evaluation. [ABSTRACT FROM AUTHOR]

Dynamic fleet management problems are normally formulated as networks over dynamic networks. Additional realism usually implies the inclusion of complicating constraints, typically producing exceptionally large integer programs. In this paper, we present for the first time the formulation of dynamic fleet management problems in an optimal control setting, using a novel formulation called a Logistics Queueing Network (LQN). This formulation replaces a single, large optimization problem with a series of very small problems that involve little more than solving a single sort at each point in space and time. We show that this approach can produce solutions that are within a few percent of a global optimum but provide for consider- ably more flexibility than standard linear programs. [ABSTRACT FROM AUTHOR]

This work adds realistic dependency structure to a previously developed analytical stochastic network loading model. The model is a stochastic formulation of the link-transmission model, which is an operational instance of Newell's simplified theory of kinematic waves. Stochasticity is captured in the source terms, the flows, and, consequently, in the cumulative flows. The previous approach captured dependency between the upstream and downstream boundary conditions within a link (i.e., the respective cumulative flows) only in terms of time-dependent expectations without capturing higher-order dependency. The model proposed in this paper adds an approximation of full distributional stochastic dependency to the link model. The model is validated versus stochastic microsimulation in both stationary and transient regimes. The experiments reveal that the proposed model provides a very accurate approximation of the stochastic dependency between the link's upstream and downstream boundary conditions. The model also yields detailed and accurate link state probability distributions. [ABSTRACT FROM AUTHOR]

In the 1960s, Braess showed that the overall system performance of a transportation network can be degraded when a new link is added to the network, given that travelers choose their routes based on the user equilibrium (UE) principle. This phenomenon is often referred to as Braess' paradox (BP). The original five-link BP network has been studied extensively with static link performance functions. In this paper, we revisit the original BP network with a dynamic point-queue model and examine whether the results from the static model would hold for the case with time-dependent queues. For this purpose, we solve the BP problem with the consideration of dynamic queuing that leads the system to a steady state while satisfying the dynamic user equilibrium (DUE) condition at every instant. Our results indicate that the locations of congestion, or "hot spots," of the system are sensitive to the capacity of each link in an intricate manner. The "surprising result" reported in previous studies with link performance functions, that a system can spontaneously grow out of Braess' paradox if the demand is sufficiently high, does not occur with time-dependent queues. Instead, we show that queues in different stages have different impacts on the system performance. The implication of this result is discussed in the context of developing proactive dynamic traffic control strategies that can eliminate the negative impact of BP while keeping the system operating at the DUE condition. Even though this study focuses on the original five-link network, the results illustrate the potential pitfalls of extending insights developed from a static framework for dynamic traffic and the importance of studying the problem with a dynamic framework for real-time traffic control. [ABSTRACT FROM AUTHOR]

This paper presents an efficient algorithm for solving the dynamic user equilibrium (DUE) traffic assignment with a one-to-many origin-destination (OD) pattern. To achieve the efficiency of the algorithm, we employ the following three strategies. First,we exploit the decomposition property of the DUE assignment with respect to the departure time from an origin; we consider the algorithm that solves each of the decomposed DUE assignments sequentially. Second, we represent the decomposed DUE assignment by an arc-node formulation, not by using path variables. Third, we take advantage of the fact that the decomposed DUE assignment reduces to (finite dimensional) nonlinear complementarity problems (NCPs); we develop the algorithm based on the globally convergent Newton's method for general NCPs. These strategies, together with graph theoretic devices, enable us to design a new algorithm which does not require path enumeration and is capable of dealing with very large-scale networks. Numerical experiments disclose that the proposed algorithm solves the DUE assignment very rapidly, even in large-scale networks with some thousands of links and nodes where conventional heuristic algorithms do not converge to the accurate equilibrium solution. [ABSTRACT FROM AUTHOR]

Average delay is an important criterion of evaluating traffic signals. Traffic signals, stream merges, and stream splits influence vehicular delay in signalized networks through influencing random fluctuation of traffic. This paper proposes a method of estimating the random component of queues and delays at signalized intersections inside a network of urban streets. Equations describing the effect of signals and traffic merging and splitting are derived, as well as a comprehensive equation combining the considered effects. Fixed speeds and capacities are assumed. The derived comprehensive equation is used to discuss certain cases of signalized streets. The equation is evaluated using the Monte Carlo technique. The proposed method can be incorporated into existing procedures for evaluating and optimizing traffic signals. [ABSTRACT FROM AUTHOR]

The study of stochastic networks of queues in transportation has been confined to the use of highly simplified analytical models or the development of large, computationally expensive Monte Carlo simulations. We introduce a discrete-time approach for simulating stochastic, transient networks of bulk queues that often arise in consolidation networks. This paper presents the state variables and equations required to model the problem, and introduces a set of approximations to produce a computationally tractable algorithm. A companion paper describes the results of extensive numerical experiments which test the accuracy of the approximations and the overall efficiency of the procedure. [ABSTRACT FROM AUTHOR]

The article presents abstracts of research papers, on topics ranging from a queuing network analysis of automated handling systems to primal partitioning solutions for the routing of shipments for less-than-truckload motor carriers. These research papers were nominated for the Transportation Science Section Dissertation Prize Competition for the year 1990. This year, the winner is Jeffrey I. McGill for his dissertation, "Optimization and Estimation Problems in Airline Yield Management." This paper addressed a rich optimization problem with the statistical estimation challenges involved in working with actual observations.

This paper considers a districting problem for a demand-responsive service system in which queuing is allowed. Customers, located at the nodes of a transportation network call in a Poisson manner, asking for on-scene service by a mobile service unit. Two such units service the entire network, with unit i (i = 1, 2) responsible for all nodes Ni in its unique "service territory." In response to a call from within Nl unit i, if available, is dispatched immediately to the customer; if the unit is busy with a previous customer, the call is dispatched in a FIFO manner. Each service territory, with its response unit, behaves as an independently operating M/G/1 queuing system. The problem addressed in this paper is determination of the optimal service territories, given fixed home locations for each of the service units, so as to minimize the average response time (queuing delay plus travel time) to a random customer. Exact results are obtained for limiting values of demand rate, and efficient heuristics are presented for arbitrary demand rates. [ABSTRACT FROM AUTHOR]

This paper derives two easily programmable heuristic procedures for locating p mobile service units on a network in the presence of queueing-like congestion. Both heuristics take advantage of the Hypercube model, a location model for a single service unit, and a normalizing technique known as mean service time calibration. Heuristic I uses the 1-median problem, whereas heuristic 2 uses the stochastic queue median. A simulation model is employed to validate the results and compare the heuristics. [ABSTRACT FROM AUTHOR]

Average waiting times in queuing models are generally computed with the assumption that the arrival and service processes are independent and not related. In many applications and especially in queues with scheduled batch service times, this assumption is not valid and a formulation which relates the two processes is required. This paper proposes a model aimed at analyzing and exploiting the relationship between the arrival and service processes with emphasis on the impact of this relationship on average waiting times. The presentation is made in the context of a transportation model to motivate and validate the basic assumptions. [ABSTRACT FROM AUTHOR]

An analytic model of railyards has been developed and is reported in two separated studies ( Parts I and II). This paper (Part I) is a macroview of yards describing the major operations performed within a yard and how different yards may be classified for modeling purposes. The yard operations are analyzed as quequing phenomena and modeled using known queuing relations. These queuing models are then used to calculate the probability distribution of put-through times, and their moments, for each major type of traffic. These distributions are compared with observed histograms. Part II wil describe how the process rates in the queuing models are related to the physical configuration of the yard, the yard resources, the marshaling rules, and the traffic intensities. [ABSTRACT FROM AUTHOR]

In this paper, M/G/CIC state dependent queueing models are proposed for modeling and analyzing vehicular traffic flows. Congestion aspects of traffic flow are represented by introducing state dependent service rates as a function of number of vehicles on each road link. Analytical models for unidirectional and multisource flows are presented. Finally, queueing models to analytically determine the optimal capacity and performance measures of the road links are incorporated into a series of software programs available from the authors. [ABSTRACT FROM AUTHOR]

This paper considers the problem of locating the home base of a traveling server on a network. Calls for service arrive solely at nodes via independent, time-homogeneous Poisson processes. Calls finding the server busy enter a finite capacity queue which is depleted in a First-Come- First-Served (FCFS) manner. The server travels from his / her home base serving calls back-to-back, returning home only when he / she finds the system empty upon the completion of a service. The objective we consider is to minimize the average response time to an accepted call. The queueing system is analyzed via a busy period analysis, which uses a decoupling scheme to simplify the task of optimizing the home base location. Computational experience is discussed and a numerical example is presented. Generalizations of the model are also discussed. [ABSTRACT FROM AUTHOR]

In a companion study, Simao and Powell have introduced a numerical, discrete-time approach for simulating stochastic transient networks of bulk queues that often arise in consolidation networks. A set of approximations was proposed in order to produce a computationally tractable algorithm. This paper describes the numerical methods actually used for calculating probabilities and the results of extensive numerical experiments which test the accuracy of those approximations and the overall efficiency of the procedure, vis-a-vis the alternative Monte Carlo method. [ABSTRACT FROM AUTHOR]

In this paper we analyze the trajectory of stochastic queue median (SQM) location problem in a planar region with a rectilinear travel metric. The location objective is to minimize expected response time to customers (that is, travel time plus queue delay). We introduce a methodology for parametric analysis of planar location problems which is potentially applicable to other location problems as well. Using the methodology, we demonstrate strong parallels between our planar SQM problem and the same problem on a tree network. We show how the optimal SQM location must occur in a certain region of the plane. Given a mild regularity condition, we develop trajectory results for the optimal location as a function of the customer call rate, and we derive a simple necessary and sufficient ratio condition which characterizes points on the optimal trajectory, and present an algorithm for finding that trajectory. We also analyze the problem in the degenerate case when the regularity condition is violated. Finally, we extend our results to the planar stochastic expected queue median problem, which incorporates stochastic travel times. [ABSTRACT FROM AUTHOR]

This paper studies the peculiar queueing problem that arises at multipurpose port terminals serving two traffic types. Primary (liner ship) traffic obeys a schedule and has absolute priority on the use of the multipurpose facilities. Secondary (tramp) traffic, which arrives at random, can also be served elsewhere in the port. Secondary traffic is routed to the multipurpose berths only if doing so does not delay any primary ship. (The port knows a fair amount ahead of time the arrival times of these ships and the likely service times of both liners and tramps). The goal is to obtain simple analytical formulas for the multipurpose terminal's productivity, and for the resulting changes in berth utilization outside the terminal. Although the suggested strategy for routing secondary traffic leads to a queueing problem that is too complicated to yield a simple exact formula, an approximate solution for heavy tramp traffic was found. An exact numerical solution for arbitrary traffic levels, which only applies when liner operations are perfectly regular and deterministic, was also found. In this latter case, because the solution could be expressed as a function of only two parameters, it was possible to present it in graphical form and to obtain a simple analytical expression fitting the graphs. [ABSTRACT FROM AUTHOR]

This paper considers the problem of locating a single server on a network while explicitly accounting for queueing of calls for service. Calls from a node can either all be accepted or all be rejected by the service system. Two models are considered. In the first model a call can be rejected independent of the state of the system when the call arrives. In the second model, an arriving call can be rejected only ii it finds the server busy. The queueing systems are analyzed for both models. A greedy heuristic is developed which, parametrically in the arrival rate of calls, determines the location of the server and the rejection strategies at nodes. Extreme case analysis with respect to the arrival rate is investigated. A numerical example illustrates our results. Our major observation is that the rejection strategies for calls are dependent on the arrival rate, and the choice of model. [ABSTRACT FROM AUTHOR]

This paper presents queueing models for predicting dispatching delays on single track low speed rail lines with widely spaced passing locations. Because of scheduling unpredictabilities, we assume Poisson arrivals of trains. Because of the slow transit speeds, we assume that trains traveling in the same direction can do so on close headways. We also assume siding capacity at passing locations is not limiting. Under these assumptions, we calculate expected delays on individual segments of single track and for segments of single track with an alternate route. [ABSTRACT FROM AUTHOR]

Bulk service queues arise in a variety of settings in transportation as a result of the need to consolidate demands for service over time. In the case of traffic lights, service is rendered in terms of the ability of a batch of cars to move through an intersection. It is often necessary to control the departure of vehicles from a queue in order to avoid sending vehicles with uneconomically small loads. Two strategies that can be used are a vehicle holding strategy, where vehicles are held until the load is sufficiently large, and a vehicle cancellation strategy, where the scheduled departure of a vehicle is cancelled if the queue is too short, in which case any customers in the queue must wait until the next departure. A separate branch of research has used purely numerical approaches for solving bulk queuing problems, as opposed to the use of classical transform techniques which all the other papers use. The article develops models for different vehicle control strategies which can be solved extremely efficiently, and hence could be used in the design of large transportation networks.

Motorists going through a bottleneck during the morning rush hour have to time their departure times to ensure they arrive to work at a reasonable time. Traffic and congestion levels at the bottleneck depend on the motorists' work schedule and the disutility of unpunctuality. This paper shows that, under certain conditions, there is only one equilibrium order of arrivals; an order under which motorists do not have an incentive to jockey for position in the queue. [ABSTRACT FROM AUTHOR]

The paper gives conditions which guarantee the existence of an equilibrium arrival pattern at a single bottleneck. In the model, the times at which a driver wishes to leave the bottleneck depend on the driver. The equilibrium queue length in this model always has a continuous time derivative everywhere. However, the slope of the equilibrium cumulative arrival distribution is discontinuous at the beginning and end of congestion. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of peak period traffic congestion. It considers the queues and delays at a single point of insufficient capacity. A model is developed to predict the pattern of traffic volumes and travel times during a peak period. It consists of two basic elements: a deterministic queue and a random utility departure time choice. The utility represents the tradeoff that exists whenever congestion occurs at the desired departure time. A trip-maker can then shift his/her trip forward or backward in time to avoid a long delay. The properties of the equilibrium solution of the model are investigated analytically. It is shown that there cannot be more than one congestion period and that the equilibrium solution is unique. [ABSTRACT FROM AUTHOR]

The major components of delay to rail cars in passing through yards are waiting for classification and connection to an appropriate outbound train. This paper proposes queuing models for each of these components which provide expressions for both the mean and variance of delay times. The models are then used in an example application to draw inferences regarding the effectiveness of alternative strategies for dispatching trains between yards. [ABSTRACT FROM AUTHOR]

A mathematical model is proposed to describe activities at a nonsignalized pedestrian crossing. Starting from a set of simple assumptions, the distributions of times during which a crossing is alternately available to pedestrians and vehicles are given. A batch service queueing analysis is then undertaken, employing the imbedded Markov chain technique, to derive the statistics of the vehicular queueing situation. Such analysis usually leads to rather intractable expressions which require a great deal o f further effort before numerical results are obtained, but in the present paper these difficulties are overcome, and an explicit formula is derived for the vehicle mean queue length. [ABSTRACT FROM AUTHOR]

The movement of traffic past a point is compared to the output of a queuing system having random input. A generalization of the queue output model leads to a suitable headway model: this model is a mixture of two distributions, representing following and nonfollowing headways, in appropriate proportions. This model is compared with, several others that have been suggested; when used with a lognormal distribution of following headways, it gives the best overall fit to data from the M4 motorway, England, and two-way roads in Indiana, USA. For each site, the parameters of the following headway distribution can be assumed constant. The mean following headways are 1.3 sec and 1.6 sec for the M4 fast and slow lanes respectively, and 2 sec for the Indiana sites. The standard deviation of logarithms of following headways is 0.4 for both M4 lanes and 0.45 for the Indiana sites. For most samples, the reciprocal of the mean interbunch gap λ can be approximated by λ = λ* - ½λ*&frac32;, where λ* is the flow rate, and the proportion of the following vehicles ψ can be approximated by ψ = ρ -- ½ (ρ- 1) λ*&frac32;, where ρ is the traffic intensity. [ABSTRACT FROM AUTHOR]

Investigations of motorist delays at the intersection of a major and minor road have involved variations of one or the other of two merging strategies: (i) MILLER'S[8] model that assumes that a minor-road motorist makes consecutive decisions consistently, and (ii) that of WEISS AND MARADUDIN[7] that assumptions that a different, independent decision is made for each headway. In this paper we show that results for both models may be obtained easily, using the results of queuing theory, if certain reasonable assumptions are made. Simple expressions for the Laplace-Stieltjes transforms and means of the delays are derived in the case of independent major-road headways with a common, general distribution. For exponential headways, a numerical study shows the mean Miller delay to increase with the variation in the merge times, while the mean Weiss-Maradudin delay decreases. To illustrate the application of the expressions obtained, we investigate the reduction in the delay achieved by inserting a traffic island between two streams of major-road traffic. [ABSTRACT FROM AUTHOR]

We introduce a stochastic orienteering problem on a network of queues in which the traveler must arrive and enter service at locations within the respective time windows to collect rewards, but the traveler may experience stochastic wait time at each location before service can begin. To maximize the expected rewards collected, the traveler must determine which locations to visit and how long to wait in queues at each location. We formally model the problem as a Markov decision process with the objective of maximizing the expected collected rewards. We investigate the existence of optimal control limits and examine conditions under which certain actions cannot be optimal. To solve the problem, we propose an approximate dynamic programming approach based on rollout algorithms. The method introduces a two-stage heuristic estimation that we refer to as compound rollout. In the first stage, the algorithm decides whether to stay at the current location or go to another location. If departing the current location, it chooses the next location in the second stage. We demonstrate the value of our modeling and solution approaches by comparing the dynamic policies to a-priori-route solutions with recourse actions. [ABSTRACT FROM AUTHOR]

We consider curbside bus stops of the kind that serve multiple bus routes and that are isolated from the effects of traffic signals and other stops. A Markov chain embedded in the bus queueing process is used to develop steady-state queueing models of this stop type, as illustrated by two special cases. The models estimate the maximum number of buses that can arrive at and serve a stop and still satisfy a specified target of average bus delay. These models can be used to determine, for example, a stop's suitable number of bus berths, given the bus demand and the specified delay target. The solutions for the two cases are used to derive a closed-form, parsimonious approximation model for general cases. This approximation matches simulations reasonably well for many conditions that arise in real settings; differences of less than 10% were common. Our results unveil how suitable choices for the number of bus berths are influenced by both the variation in the time that buses spend serving passengers at the stop and the specified delay target. The models further show why the proxy measure commonly used for the delay target in previous bus stop studies is a poor one. [ABSTRACT FROM AUTHOR]

In his paper, PEARCE presents a method for determining the stationary probabilities of a G/Mt/1 system, the service mechanism being such that it operates regardless of whether or not customers are present. This note is an attempt to correct his results. [ABSTRACT FROM AUTHOR]

Many real-world vehicle routing problems are dynamic optimization problems, with customer requests arriving over time, requiring a repeated reoptimization. In this paper, we consider a dynamic vehicle routing problem where [...]

In the vehicle routing problem (VRP) the objective is to construct a minimum cost set of routes serving all customers where the demand of each customer is less than or equal to the vehicle capacity and where each customer is visited once. In the split delivery vehicle routing problem (SDVRP) the restriction that each customer is visited once is removed. We show that the cost savings that can be realized by allowing split deliveries is at most 50%. We also study the variant of the VRP in which the demand of a customer may be larger than the vehicle capacity, but where each customer has to be visited a minimum number of times. We show that the cost savings that can be realized by allowing more than the minimum number of required visits is again at most 50%. Furthermore, we analyze the performance of simple heuristics that handle customers with demands larger than the vehicle capacity by employing full load out-and-back trips to these customers until the demands become less than or equal to the vehicle capacity. Finally, we investigate situations in which demands are discrete and vehicle capacities are small. [ABSTRACT FROM AUTHOR]

We consider the fixed-cycle traffic-light (FCTL) queue, where vehicles arrive at an intersection controlled by a traffic light and form a queue. The traffic-light signal alternates between green and red periods, and delayed vehicles are assumed to depart during the green period at equal time intervals. Most of the research done on the FCTL queue assumes that the vehicles arrive at the intersection according to a Poisson process and focuses on deriving formulas for the mean queue length at the end of green periods and the mean delay. For a class of discrete arrival processes, including the Poisson process, we derive the probability generating function of both the queue length and delay, from which the whole queue length and delay distribution can be obtained. This allows for the evaluation of performance characteristics other than the mean, such as the variance and percentiles of the distribution. We discuss the numerical procedures that are required to obtain the performance characteristics, and give several numerical examples. [ABSTRACT FROM AUTHOR]

We analyze a Wardrop equilibrium model for passenger assignment in, general transit networks, including the effects of congestion over the passengers' choices. The model is based on the common-line paradigm, which is applied to general networks using a dynamic programming approach. Congestion is treated by means of a simplified bulk queue model described in the appendix. We provide a complete characterization of the set of equilibria in the common-line setting, including the conditions for existence and uniqueness. This characterization reveals the existence of ranges of flow in which a Braess-like paradox appears, and in which a flow increase does not affect the system performance as measured by transit times. The congested common-line model is used to state an equilibrium model for general transit networks, and to establish the existence of a network equilibrium. [ABSTRACT FROM AUTHOR]

Traditional analysis of bulk queues has relied on classical transform methods, which requires the determination of the complex zeroes of a given function, or iterative numerical techniques. In this research, transform results are used to help find approximate closed form expressions for the mean and variance of the length of the queue at departure instants. The moments of the length of the queue in continuous time and of the waiting time distribution are derived in closed form as a function of the new formulas. An approximate method for fitting a distribution for the length of the queue is provided and used to calculate the probability a customer will leave on a given outbound vehicle. Finally, approximate queueing and delay formulas are developed for bulk queues operating under a vehicle cancellation policy. [ABSTRACT FROM AUTHOR]

Several models for predicting mean waiting times of river traffic at a multiple chamber lock were developed and tested. Mean waiting times predicted by the M/G/1 model differed significantly from observed times. Analysis of possible causes of failure of this model suggested a limited queue length M/G/1 model for one chamber, from which more accurate predictions were derived. For the two chamber system, an M/G/1 model with random batch size was developed. This model yields a lower bound for mean waiting time. These last two models can be used to predict system performance under various operating conditions. [ABSTRACT FROM AUTHOR]