Large Neighborhood Heuristic Algorithm for Multivehicle Dial-a-Ride Problem with Time Windows

This paper is concerned with the static dial–a–ride problem; it introduces an exact approach for the 2-vehicle problem, which then is used for designing an efficient multivehicle large scale neighborhood search heuristic. The exact algorithm is based on Psaraftis’ (2) Dynamic Programming pioneering design but computationally improved for memory management. The very large neighborhood heuristic algorithm iteratively redistributes requests between any two vehicles at a time until no more improvements cane be achieved. The computational results demonstrate the efficiency of the approach and quality of the produced solutions.

• Corporate Authors:

  Transportation Research Board

  500 Fifth Street, NW
  Washington, DC  United States  20001
• Authors:
  • Lois, Athanasios
  • Ziliaskopoulos, Athanasios K
  • Aifadopoulou, Georgia
• Conference:
  • Transportation Research Board 87th Annual Meeting
  • Location: Washington DC, United States
  • Date: 2008-1-13 to 2008-1-17
• Date: 2008

Language

• English

Media Info

• Media Type: DVD
• Features: Figures; References; Tables;
• Pagination: 16p
• Monograph Title: TRB 87th Annual Meeting Compendium of Papers DVD

Subject/Index Terms

• TRT Terms: Algorithms; Heuristic methods; Neighborhoods; Operations; Paratransit services; Programming (Planning); Public transit; Statistical analysis; Transit operating agencies
• Subject Areas: Administration and Management; Data and Information Technology; Highways; Operations and Traffic Management; Planning and Forecasting; Public Transportation; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01099243
• Record Type: Publication
• Report/Paper Numbers: 08-3038
• Files: TRIS, TRB
• Created Date: May 21 2008 7:05AM