A Fast, Action-Based Algorithm for Paratransit Vehicle Assignment

Principal Investigator:

John Carlsson, Assistant Professor, Mechanical Engineering

Project Summary:

This project seeks to develop and implement a potentially patentable algorithm for rapidly assigning paratransit vehicles that provide transportation services for the disabled and elderly. Large paratransit organizations such as the Dakota Area Rapid Transit Service (DARTS) and First Transit use expensive, sophisticated software such as TRAPEZE in conjunction with a staff of "dispatchers" who handle such assignment problems on a daily basis. However, smaller non-profit disability services such as Phoenix Alternatives and Merrick, Inc. (both based in the Twin Cities metro region) rely on smaller-scale software packages such as Microsoft MapPoint, Streets and Trips, or MileCharter, which 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 dropoff times, all contribute to the combinatorial intractability of the problem. This project develops a customized algorithm tailored to the needs of such agencies, and delivers a software implementation for future operational use.

Sponsor:

Project Details:

  • Start date: 02/2011
  • Project Status: Active
  • Research Area: Planning and Environment
  • Topics: Planning, Transit
  • Phased Project(s):