A rejected-reinsertion heuristic for the static Dial-A-Ride Problem

Ying Luo and Paul Schonfeld

Transportation Research Part B: Methodological, 2007, vol. 41, issue 7, 736-755

Abstract: We present here a new heuristic for the static multi-vehicle Dial-A-Ride Problem, which we 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.

Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191-2615(07)00015-X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:41:y:2007:i:7:p:736-755

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().