Algorithms for Routing Vehicles and Their Application to the Paratransit Vehicle Scheduling Problem (UTCM 09-15-13)

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 service provided to the customers while minimizing the cost 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 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 problem, 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.