A Fast, Auction-Based Algorithm for Paratransit Vehicle Assignment

A problem based on the actual passenger transportation operations of two community disability service organizations in St. Paul is presented. The problem is to minimize the number of routes needed to serve all the passengers subject to spatial and temporal constraints on the routing of vehicles. Additional problem characteristics include heterogeneous vehicle and passenger classes, multiple destinations, separate "runs" defined by service time windows, and rules governing the embarkment as well as maximum travel times. Here is developed a method able to generate a good problem solution within a reasonable amount of time to guide these companies' operations. Early attempts at problem solution reveal facets of its structure and illuminate an inherent trade-off between vehicle capacity and uninhibited vehicle operating time. To address this, the method proposed 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 over 12% 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.

• Record URL:
  • http://www.cts.umn.edu/Publications/ResearchReports/pdfdownload.pl?id=2338
• 
• Summary URL:
  • http://www.cts.umn.edu/Publications/ResearchReports/reportdetail.html?id=2316
• Corporate Authors:

  University of Minnesota, Twin Cities

  Department of Industrial and Systems Engineering
  111 Church Street, SE
  Minneapolis, MN  United States  55455

  University of Minnesota, Twin Cities

  Center for Transportation Studies, 511 Washington Avenue, SE
  Minneapolis, MN  United States  55455
• Authors:
  • Carlsson, John Gunnar
  • Houle, Jason
• Publication Date: 2013-9

Language

• English

Media Info

• Media Type: Digital/other
• Edition: Final Report
• Features: Appendices; Figures; References; Tables;
• Pagination: 64p

Subject/Index Terms

• TRT Terms: Algorithms; Paratransit services; Routes and routing; Scheduling; Travel time; Vehicle capacity
• Subject Areas: Passenger Transportation; Planning and Forecasting; Public Transportation; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01496667
• Record Type: Publication
• Report/Paper Numbers: CTS 13-28
• Contract Numbers: CTS Project #2011112
• Files: TRIS
• Created Date: Oct 28 2013 9:47AM