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.     

Minimising bins in transmission systems

This paper deals with the problem of minimising the transmission cost in an EDI system and proves the optimality of a policy which minimizes the slack of partial sums under conditions with practical interpretations. This policy is shown to be useful as a heuristic in more general cases.     

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.      

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.     

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.     

Multi-item spare parts systems with lateral transshipments and waiting time constraints

This paper deals with the analysis of a multi-item, continuous review model of two-location inventory systems for repairable spare parts, used for expensive technical systems with high target availability levels. Lateral and emergency shipments occur in response to stockouts. A continuous review basestock policy is assumed for the inventory control of the spare parts. The objective is to minimize the total costs for inventory holding, lateral transshipments and emergency shipments subject to a target level for the average waiting time per demanded part at each of the two locations. A solution procedure based on Lagrangian relaxation is developed to obtain both a lower bound and an upper bound on the optimal total cost. The upper bound follows from a heuristic solution. An extensive numerical experiment shows an average gap of only 0.31% between the lower and upper bounds. The experiment also gives insights into the relative improvement achieved by applying lateral transshipments and or the system approach. We also apply the proposed model to actual data from an air carrier company.     

Finite-time filtering for switched linear systems with a mode-dependent average dwell time

This study considers the problem of finite-time filtering for switched linear systems with a mode-dependent average dwell time. By introducing a newly augmented Lyapunov–Krasovskii functional and considering the relationship between time-varying delays and their upper delay bounds, sufficient conditions are derived in terms of linear matrix inequalities such that the filtering error system is finite-time bounded and a prescribed noise attenuation level is guaranteed for all non-zero noises. Thus, a finite-time filter is designed for switched linear systems with a mode-dependent average dwell time. Finally, an example is given to illustrate the efficiency of the proposed methods.     

Stability and stabilization of positive switched systems with mode-dependent average dwell time

This paper investigates stability and stabilization of positive switched systems with mode-dependent average dwell time, which permits to each subsystem in the underlying systems to have its own average dwell time. First, by using the multiple linear copositive Lyapunov function, the stability analysis of continuous-time systems in the autonomous form is addressed based on the mode-dependent average dwell time switching strategy. Then, the stabilization of non-autonomous systems is considered. State-feedback controllers are constructed, and all the proposed conditions are solvable in terms of linear programming. The obtained results are also extended to discrete-time systems. Finally, the simulation examples are given to illustrate the correctness of the design. The switching strategy used in the paper seems to be more effective than the average dwell time switching by some comparisons.     

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     

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.     

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).     

On the complete monotonicity of the waiting time density in some GI/G/k systems

In this note the complete monotonicity of the waiting time density in GI/G/k queues is proved under the assumption that the service time density is completely monotone. This is an extension of Keilson's [3] result for M/G/1 queues. We also provide another proof of the result that complete monotonicity is preserved by geometric compounding.     

Almost global stability of nonlinear switched systems with mode-dependent and edge-dependent average dwell time

It has recently been shown that almost global stability of nonlinear switched systems can be characterized using multiple Lyapunov densities. This has been accomplished for switched systems subject to a minimum dwell time or an average dwell time constraint. In this paper, as an extension of the aforementioned results, we provide a sufficient condition on mode-dependent and edge-dependent average dwell time to ensure almost global stability of a nonlinear switched system. The relations between average dwell time, mode-dependent, and edge-dependent average dwell time have been discussed. The obtained results for nonlinear switched systems imply the existing results for linear switched systems.     

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.