United States Department of Transportation
ROSA P serves as an archival repository of USDOT-published products including scientific findings, journal articles, guidelines, recommendations, or other information authored or co-authored by USDOT or funded partners.
As a repository, ROSA P retains documents in their original published format to ensure public access to scientific information.
i
Algorithms for routing vehicles and their application to the paratransit vehicle scheduling problem.
-
2012-03-01
-
Details:
-
Creators:
-
Corporate Creators:
-
Corporate Contributors:
-
Subject/TRT Terms:
-
Publication/ Report Number:
-
Resource Type:
-
Geographical Coverage:
-
Edition:Final report; Sept. 2009-Sept. 2011.
-
Corporate Publisher:
-
Abstract: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.
-
Format:
-
Funding:
-
Collection(s):
-
Main Document Checksum:
-
Download URL:
-
File Type:
[PDF-1.62 MB]
