Empty vehicle redistribution for personal rapid transit

A Personal Rapid Transit (PRT) system uses compact, computer-guided vehicles running on dedicated guideways to carry individuals or small groups directly between pairs of stations. PRT vehicles operate on demand, much like conventional taxis. The empty vehicle redistribution (EVR) problem is to decide when and where to move empty PRT vehicles. These decisions are made in real time by an EVR algorithm. A reactive EVR algorithm moves empty vehicles only in response to known requests; in contrast, a proactive EVR algorithm moves empty vehicles in anticipation of future requests. In this thesis, two new proactive EVR algorithms, here called Sampling and Voting (SV) and Dynamic Transportation Problem (DTP), are developed and evaluated. It is shown that they reduce passenger waiting times substantially below those obtained by reactive EVR algorithms, with a modest increase in empty vehicle travel, and that they usually outperform similar algorithms in the literature. Several new theoretical tools are also developed, including a benchmark for maximum achievable throughput and two benchmarks for minimum achievable passenger waiting times. These provide an absolute measure of the performance of EVR algorithms, and they quantify the potential for further improvement. Finally, preliminary work on a Markov Decision Process formulation of the EVR problem is presented and used to obtain provably optimal policies for small systems.