Algorithms for routing vehicles and their application to the paratransit vehicle scheduling problem.

794121911Final report; Sept. 2009-Sept. 2011.PDFTech ReportUTCM 09-15-13DTRT06-G-0044Paratransit servicesPublic transitRoutes and routingRoutesRoutingMathematical modelsSchedulesSchedulingTexasTexas Transportation Institute. University Transportation Center for MobilityPark, MyoungkukOberlin, PaulRathinam, SivakumarQuadrifoglio, LucaDarbha, SwaroopTexas Transportation Institute. University Transportation Center for MobilityTexas Transportation InstituteUnited States. Dept. of Transportation. Research and Innovative Technology AdministrationUniversity Transportation Centers Program (U.S.)NTL-PUBLIC TRANSPORTATION-ParatransitNTL-PUBLIC TRANSPORTATION-Transit Planning and PolicyNTL-PLANNING AND POLICY-Transit Planning and PolicyUS Transportation CollectionAs the demand for paratransit services increases, there is a constant pressure to maintain the quality ofservice provided to the customers while minimizing the cost of operation; this is especially important asthe availability of public funding for paratransit services has been on the decline. Key tasks inaccomplishing this objective are efficiently allocating vehicles to service trips and adjusting the schedulesof vehicles dynamically in response to calls received by the service providers from the customers on theday of the service. For many paratransit services, capacity of vehicles is not a binding constraint. This isespecially so in rural applications. For this reason, we will focus on dealing with routing vehicles that arenot subject to any passenger capacity constraints.In this report, we consider two important relaxations of this problem, which may be considered asproblems of independent interest and significance. The first problem deals with relaxing all theconstraints associated with the order in which the vehicles must visit pickup and delivery locations of thepassengers as well as the time window constraints. The second relaxation additionally imposes orderingrequirements. Both problems are combinatorially hard problems, and we provide formulations andalgorithms for finding sub-optimal solutions along with an estimate of their quality. In the last section ofthis report, we consider the time window constraints for pickup and delivery of customers and provide aheuristic to find feasible solutions. We corroborate the results numerically with small, randomly generatedinstances of the paratransit scheduling problem