Hybrid scheduling methods for paratransit operations

We study an extension to the general routing problem, which deals with integrating fixed route service with the general pickup and delivery problem to create a hybrid routing problem. The primary application for such a service is a dial-a-ride system used by transit agencies to transport disabled or elderly individuals. The main aim of the integration is to reduce the vehicle miles of the on-demand vehicles while not significantly reducing the customer service level. Due to the combinatorial nature of the problem, we propose a heuristic algorithm that provides an approximate solution, which is computationally efficient for solving large sized problems. The proposed heuristic is tested using real data from a transit agency.