A Fast, Action-Based Algorithm for Paratransit Vehicle Assignment

Project summary:

This project aimed to develop and implement a potentially patentable algorithm for rapidly assigning paratransit vehicles that provide transportation services for the disabled and elderly. Two smaller nonprofit disability services in St. Paul rely on small-scale software packages that do not have any utilities for optimally assigning vehicles to customers. The assignment and routing decisions for vehicles are therefore made manually. This is inefficient for two reasons: first, it requires the investment of person-hours on a task that can be automated. More importantly, even for a small instance of around 30 customers, optimal routing and assignment can be a difficult task; heterogeneous vehicles, heterogeneous customer classes (ambulatory and wheelchair bound passengers, for instance), time windows, and variable pickup and drop-off times, all contribute to the combinatorial intractability of the problem.

Early attempts at a solution revealed facets of its structure and illuminated an inherent trade-off between vehicle capacity and uninhibited vehicle operating time. To address this, the method proposed by the researchers uses high-capacity vehicles to serve routes in both runs while allotting easily served passengers to these vehicles to relieve temporal constraints. This heuristic carries the additional advantage of partitioning the rest of the solution into two single-run problems, and the decrementing adaptive memory program (DAMP) is devised as a way of discovering solution components and promoting those more effective at producing good solutions to be used in future attempts. When applied to a data set provided by the organizations, the algorithm improved the current benchmark solution, generated by hand, by more than 12 percent in reasonable operating time, serving 574 passengers with 64 routes in 53 vehicles. Its absolute measure of quality, in light of lower bounds that were constructed, is also considered good. In addition to the algorithm, the project delivered a software implementation for future operational use.