As the demand for paratransit services increases, there is a constant pressure to maintain the quality of service provided to the customers while minimizing the cost of operation; this is especially important as the availability of public funding for paratransit services has been on the decline. Key tasks in accomplishing this objective are efficiently allocating vehicles to service trips and adjusting the schedules of vehicles dynamically in response to calls received by the service providers from the customers on the day of the service. For many paratransit services, capacity of vehicles is not a binding constraint. This is especially so in rural applications. For this reason, we will focus on dealing with routing vehicles that are not subject to any passenger capacity constraints. In this report, we consider two important relaxations of this problem, which may be considered as problems of independent interest and significance. The first problem deals with relaxing all the constraints associated with the order in which the vehicles must visit pickup and delivery locations of the passengers as well as the time window constraints. The second relaxation additionally imposes ordering requirements. Both problems are combinatorially hard problems, and we provide formulations and algorithms for finding sub-optimal solutions along with an estimate of their quality. In the last section of this report, we consider the time window constraints for pickup and delivery of customers and provide a heuristic to find feasible solutions. We corroborate the results numerically with small, randomly generated instances of the paratransit scheduling problem.


    Access

    Access via TIB

    Check availability in my library


    Export, share and cite



    Title :

    Algorithms for Routing Vehicles and Their Application to the Paratransit Vehicle Scheduling Problem


    Contributors:
    M. Park (author) / P. Oberlin (author) / S. Rathinam (author) / L. Quadrifoglio (author) / S. Darbha (author)

    Publication date :

    2012


    Size :

    46 pages


    Type of media :

    Report


    Type of material :

    No indication


    Language :

    English




    Automation of Paratransit Reservation, Routing, and Scheduling

    Chira-Chavala, T. | Online Contents | 2000



    Automated Paratransit Scheduling Using KBGIS

    Spring, G. S. / American Society of Civil Engineers | British Library Conference Proceedings | 1998