An adaptive routing approach for personal rapid transit

Personal Rapid Transit (PRT) is a public transportation mode, in which small automated vehicles transport passengers on demand. Central control of the vehicles leads to interesting possibilities for optimized routings. The complexity of the involved routing problems together with the fact that routing algorithms for PRT essentially have to run in real-time often leads to the choice of fast greedy approaches. The most common routing approach is arguably a sequential one, where upcoming requests are greedily served in a quickest way without interfering with previously routed vehicles. The simplicity of this approach stems from the fact that a chosen route is never changed later. This is as well the main drawback of it, potentially leading to large detours. It is natural to ask how much one could gain by using a more adaptive routing strategy. This question is the main motivation of this article. In this paper, we first suggest a simple mathematical model for PRT, and then introduce a new adaptive routing algorithm that repeatedly uses solutions to an LP as a guide to route vehicles. Our routing approach incorporates new requests in the LP as soon as they appear, and reoptimizes the routing of all currently used vehicles, contrary to sequential routing. We provide preliminary computational results that give first evidence of the potential gains of an adaptive routing strategy, as used in our algorithm.     

The average virtual waiting time as a measure of performance

Under weak conditions the average virtual waiting time converges exponentially fast to its limit. For this reason this quantity has been suggested as a measure of performance for queueing systems. We consider theM/G/1 queue and provide estimation and limiting behaviour of the index of exponential decay.     

Generating asymptotically optimal broadcasting schedules to minimize average waiting time

The performance of a Video-on-Demand broadcasting scheme is commonly evaluated by the maximum waiting time encountered by the customer before viewing can start. This paper addresses the issue of minimizing the average waiting time. Recently, we proposed Harmonic Block Windows scheduling to specifically minimize the average waiting time for given bandwidth. Here, we present an efficient heuristic algorithm that generates asymptotically optimal Harmonic Block Windows schedules. Using simulation, we demonstrate that, as we increase the “block size”, the normalized average waiting time of these schedules approaches the theoretical minimum achievable by any “fixed start points” schedule.     

Approximating queue size and waiting time distributions in general polling systems

Polling system models are extensively used to model a large variety of computer and communication networks as well as production and service systems in which multiple customer classes or a number of distinct items compete for the capacity of a common server or production facility. In this paper we describe an efficient approximation method for the steady state distributions of the queue sizes and waiting times. This method is highly accurate as demonstrated by an extensive numerical study. In addition, it is highly adaptable to a variety of arrival patterns and switching protocols, including exhaustive and gated regimes, simple cyclical systems as well as general polling tables. For a system withN stations, one finds the firstK probability density function values of the steady state queue size in any given station inO(max(N, K ²) time only. When executed on an IBM system RS/6000, we have observed an average CPU time of less than 1 second for systems with as many as 50 stations over a large variety of parameter settings.     

Approximations for waiting time in GI/G/1 systems

The Sokolov procedure is described and used to obtain an explicit and easily applied approximation for the waiting time distribution in the FIFO GI/G/1 queue.     

Expected waiting time in symmetric polling systems with correlated walking times

Polling systems have been extensively studied, and have found many applications. They have often been used for studying wired local area networks such as token passing rings and wireless local area networks such as bluetooth. In this contribution we relax one of the main restrictions on the statistical assumptions under which polling systems have been analyzed. Namely, we allow correlation between walking times. We consider (i) the gated regime where a gate closes whenever the server arrives at a queue. It then serves at that queue all customers who were present when the gate closes. (ii) The exhaustive regime in which the server remains at a queue till it empties. Our analysis is based on stochastic recursive equations related to branching processes with migration with a random environment. In addition to our derivation of expected waiting times for polling systems with correlated walking times, we set the foundations for computing second order statistics of the general multi-dimensional stochastic recursions.      

The unbalance and bounds on the average waiting time for periodic routing to one queue

In this paper we introduce the combinatorial notion of unbalance for a periodic zero-one splitting sequence. Using this unbalance we derive an upper bound for the average expected waiting time of jobs which are routed to one queue according to a periodic zero-one splitting sequence. In the companion paper [16] the upper bound will be extended to the routing to N parallel queues.Acknowledgement.The authors would like to thank Bruno Gaujal for his hospitality during their visits to LORIA, Nancy. During one of the stimulating discussions with him the graph order was found. The authors thank Robert Tijdeman for his helpful comments.     

Mean and variance of waiting time and their optimization for alternating traffic control systems

We analyze alternating traffic crossing a narrow one-lane bridge on a two-lane road. Once a car begins to cross the bridge in one direction, arriving cars from the other direction must wait, forming a queue, until all the arrivals in the first direction finish crossing the bridge. Such a situation can often be observed when road-maintenance work is being carried out. Cars are assumed to arrive at the queues according to independent Poisson processes and to cross the bridge in a constant time. In addition, once cars join the queue, each car needs a constant starting delay, before starting to cross the bridge. We model the situation where a signal controls the traffic so that the signal gives a priority to one direction as long as a new car from the same direction arrives in a fixed time. For this model, we get a closed form for the first two moments of the waiting time of cars arriving at the bridge, and then numerically obtain Pareto optimal solutions of holding times to minimize the mean waiting time and its standard deviation. To the memory of our best friend, Yo Ishizuka     

Transit passenger origin-destination estimation in congested transit networks with elastic line frequencies

This paper deals with the transit passenger origin-destination (O-D) estimation problem by using updated passenger counts in congested transit networks and outdated prior O-D matrix. A bilevel programming approach is extended for the transit passenger O-D updating problem where the upper-level problem seeks to minimize the sum of error measurements in passenger counts and O-D matrices, while the lower level is the stochastic user equilibrium assignment problem for congested transit networks. The transit assignment framework is based on a frequency-adaptive transit network model in this paper, which can help determine transit line frequencies and the network flow pattern simultaneously in congested transit networks. A heuristic solution algorithm is adapted for solving the transit passenger O-D estimation problem. Finally, a numerical example is used to illustrate the applications of the proposed model and solution algorithm. The work described in this paper was mainly supported by two research grants from the Research Grants Council of the Hong Kong Special Administrative Region (Project No. PolyU 5143/03E and PolyU 5040/02E).     

Time-dependent analysis of virtual waiting time behaviour in discrete time queues

Discrete time queueing models have been shown previously to be of practical use for modelling the approximate time-dependent behaviour of queue length in systems of the form M(t)/G/c. In this paper we extend these models to include the time-dependent behaviour of virtual waiting time.     

On the waiting time in a generalized roulette game

The waiting times in certain multinomial experiments are studied. Special cases are the waiting times in a roulette game and in some dice problems sought for earlier. The main ingredients are the theory of stopped sums and an alternative formulation using independent Poisson processes.     

Simple,efficient heuristics for multi-item multi-location spare parts systems with lateral transshipments and waiting time constraints

This paper deals with the analysis of a multi-item, continuous review model of a multi-location inventory system of repairable spare parts, in which lateral and emergency shipments occur in response of stock-outs. The objective is to determine close-to-optimal stocking policies minimizing the total cost for inventory holding, lateral transshipments, and emergency shipments subject to a target level for the average waiting times at all locations. We structure the optimization problem as a combinatorial problem and four different heuristics are developed and evaluated in terms of their total costs and computation times. It is shown that the greedy-type heuristic has the best performance. A numerical study is carried out to look at the relative cost savings obtained from the use of multi-item approach and lateral transshipments.     

Expected waiting times in polling systems under priority disciplines

In this paper, we analyse a service system which consists of several queues (stations) polled by a single server in a cyclic order with arbitrary switchover times. Customers from several priority classes arrive into each of the queues according to independent Poisson processes and require arbitrarily distributed service times. We consider the system under various priority service disciplines: head-of-the-line priority limited to one and semi-exhaustive, head-of-the-line priority limited to one with background customers, and global priority limited to one. For the first two disciplines we derive a pseudo conservation law. For the third discipline, we show how to obtain the expected waiting time of a customer from any given priority class. For the last discipline we find the expected waiting time of a customer from the highest priority class. The principal tool for our analysis is the stochastic decomposition law for a single server system with vacations.     

Asymptotics of waiting time distributions in the accumulating priority queue

Queueing Systems - We analyze the asymptotics of waiting time distributions in the two-class accumulating priority queue with general service times. The accumulating priority queue was suggested by...     

An exact FCFS waiting time analysis for a general class of G/G/s queueing systems

A closed form expression for the waiting time distribution under FCFS is derived for the queueing system MGE_k/MGE_m/s, where MGE_n is the class of mixed generalized Erlang probability density functions (pdfs) of ordern, which is a subset of the Coxian pdfs that have rational Laplace transform. Using the calculus of difference equations and based on previous results of the author, it is proved that the waiting time distribution is of the form 1- , under the assumption that the rootsU _j are distinct, i.e. belongs to the Coxian class of distributions of order . The present approach offers qualitative insight by providing exact and asymptotic expressions, generalizes and unifies the well known theories developed for the G/G/1,G/M/s systems and leads to an algorithm, which is polynomial if only one of the parameterss orm varies, and is exponential if both parameters vary. As an example, numerical results for the waiting time distribution of the MGE₂/MGE₂/s queueing system are presented.     

Integration of timetable planning and rolling stock in rapid transit networks

The aim of this paper is to propose an integrated planning model to adequate the offered capacity and system frequencies to attend the increased passenger demand and traffic congestion around urban and suburban areas. The railway capacity is studied in line planning, however, these planned frequencies were obtained without accounting for rolling stock flows through the rapid transit network. In order to provide the problem more freedom to decide rolling stock flows and therefore better adjusting these flows to passenger demand, a new integrated model is proposed, where frequencies are readjusted. Then, the railway timetable and rolling stock assignment are also calculated, where shunting operations are taken into account. These operations may sometimes malfunction, causing localized incidents that could propagate throughout the entire network due to cascading effects. This type of operations will be penalized with the goal of selectively avoiding them and ameliorating their high malfunction probabilities. Swapping operations will also be ensured using homogeneous rolling stock material and ensuring parkings in strategic stations. We illustrate our model using computational experiments drawn from RENFE (the main Spanish operator of suburban passenger trains) in Madrid, Spain. The results show that through this integrated approach a greater robustness degree can be obtained.     

Sooner and later waiting time problems in a two-state Markov chain

LetX ₁,X ₂,... be a time-homogeneous {0, 1}-valued Markov chain. LetF ₀ be the event thatl runs of 0 of lengthr occur and letF ₁ be the event thatm runs of 1 of lengthk occur in the sequenceX ₁,X ₂, ... We obtained the recurrence relations of the probability generating functions of the distributions of the waiting time for the sooner and later occurring events betweenF ₀ andF ₁ by the non-overlapping way of counting and overlapping way of counting. We also obtained the recurrence relations of the probability generating functions of the distributions of the sooner and later waiting time by the non-overlapping way of counting of 0-runs of lengthr or more and 1-runs of lengthk or more.