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.