Sampling for Personal Rapid Transit Empty Vehicle Redistribution

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, when a passenger requests service at his/her origin station. Because the number of trips requested from a station need not equal the number of trips ending there, some vehicles must move empty to balance the flows. The empty vehicle redistribution (EVR) problem is to decide which empty vehicles to move, either reactively, in response to known requests, or proactively, in anticipation of future requests. This paper develops a new algorithm for the EVR problem called Sampling and Voting (SV). SV chooses reactive movements using a simple nearest-neighbor rule, and it chooses proactive movements by generating an ensemble of possible sequences of future passenger requests, solving a deterministic optimization problem for each sequence individually, and then finding the empty vehicle movements that are common among the sequences. Moving vehicles proactively is essential for providing low passenger waiting times. The new SV algorithm is tested in simulation with several case study systems, and it produces significantly lower passenger waiting times than existing EVR algorithms. Variants of the SV method developed here for PRT are also applicable to conventional taxi systems and emergency response systems.