Scheduling dial-a-ride paratransit under time-varying, stochastic congestion

This paper discusses a study on the dial-a-ride paratransit scheduling problems arising in paratransit service systems that are subject to tight service time constraints and time-varying, stochastic traffic congestion. Different from existing methodologies, we explicitly incorporate a time-dependent, stochastic travel time model in the problem formulation. A set of recursive relations is first identified to approximate the distribution parameters of arrival times at individual stops of a given route which. coupled with a first-in-first-out (FIFO) assumption, allows us to extend the conventional heuristic algorithms for solving the proposed problem with only marginal increase in computational complexity. Results from a series of numerical experiments on a set of hypothetical problems are described, aiming to illustrate the computational efficiency of the proposed algorithm and the sensitivity of solutions to various model parameters. (C) 2002 Elsevier Science Ltd. All rights reserved.