The paratransit vehicle scheduling problem involves scheduling a fleet of specially equipped vehicles for serving transportation needs of disabled and elderly people. It is also referred to as a dial-a-ride problem, and it can be classified as a multi-depot pickup and delivery problem with time windows and side constraints. The column generation approach constitutes one of the effective methodologies to solve this problem. However, in order to cope with the complexity of the problem, it is commonly applied in two consecutive stages: clustering and routing. First, clusters of customers are formed who will receive service together; next, vehicle routing decisions are made subject to the clustering decisions. This paper develops a nested column generation method, which integrates clustering and routing decisions, thus extending the applicability of the column generation approach in the context of the subject problem. The proposed method is implemented and applied to solve a problem faced by the transit authority of a mid size US city. A detailed account of implementation experience is provided. The computational results, based on actual data, indicate that problem instances with up to 680 requests and 48 vehicles can be solved within 2% of optimality under mild assumptions, and a 12% performance improvement over a well-established manual planning system can be achieved.
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.