A nested decomposition approach for solving the paratransit vehicle scheduling problem
Document Type
Journal Article
Publication Date
2009
Subject Area
operations - scheduling, infrastructure - vehicle, planning - route design, ridership - old people, policy - disability, mode - paratransit
Keywords
Time windows, Senior citizens, Schedules and scheduling, Routes and routing, PUD, Pickup and delivery service, Physically handicapped persons, People with disabilities, Paratransit services, Older people, Old people, Nested columns, Handicapped persons, Elderly persons, Disabled persons, Dial a ride, Decomposition method, Constraints, Clustering, Aged
Abstract
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.
Recommended Citation
Karabuk, Suleyman, (2009). A nested decomposition approach for solving the paratransit vehicle scheduling problem. Transportation Research Part B: Methodological, Volume 43, Issue 4, pp 448-465.
Comments
Transportation Research Part B Home Page: http://www.sciencedirect.com/science/journal/01912615