A Rejected-Reinsertion Heuristic for the Static Dial-A-Ride Problem

The authors present a new heuristic for the static multi-vehicle Dial-A-Ride Problem, which they call a rejected-reinsertion heuristic. Its main objective is to minimize the number of vehicles used to satisfy all the demand, subject to service quality constraints. Passenger deviation from desired time is minimized in the scheduling stage after the insertion position is determined. This method improves the basic parallel insertion heuristic in two aspects. First, a rejected-reinsertion operation is performed each time it is infeasible to insert a new request into the vehicle routes. Each assigned request close to the new request in time frame and geographic location is tentatively removed from its current vehicle and the new request is inserted into the best position in that vehicle route, followed by the reinsertion of the removed request elsewhere in the system. Of all available rejected-reinsertions, the least-cost one is then implemented. Second, an improvement procedure including trip reinsertion and trip exchange operations is implemented periodically. Two sets of problems are tested in a computational study. These show that the proposed heuristic achieves vehicle reductions of up to 17% over the parallel insertion heuristic and is very efficient computationally.

• Record URL:
  http://www.sciencedirect.com/science/article/B6V99-4ND7J7B-1/2/0655b92a95ac99fa15546a199b2abbbc
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/01912615
• Supplemental Notes:
  • Abstract reprinted with permission from Elsevier
• Authors:
  • Luo, Ying
  • Schonfeld, Paul
• Publication Date: 2007-8

Language

• English

Media Info

• Media Type: Print
• Features: Figures; References; Tables;
• Pagination: pp 736-755
• Serial:
  • Transportation Research Part B: Methodological
  • Volume: 41
  • Issue Number: 7
  • Publisher: Elsevier
  • ISSN: 0191-2615
  • Serial URL: http://www.sciencedirect.com/science/journal/01912615

Subject/Index Terms

• TRT Terms: Door to door service; Heuristic methods; Mathematical methods; Mathematical models; Numerical analysis; Paratransit services; Passengers; Public transit; Ridesharing; Routes; Scheduling; Travel
• Subject Areas: Passenger Transportation; Planning and Forecasting; Public Transportation;

Filing Info

• Accession Number: 01053963
• Record Type: Publication
• Files: TRIS, ATRI
• Created Date: Jul 12 2007 8:34AM