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

Document Type

Journal Article

Publication Date

2007

Subject Area

operations - scheduling, planning - methods, planning - route design, mode - mass transit, mode - paratransit

Keywords

Trips, Travel, Transit, Scheduling, Routes, Ridesharing, Public transit, Passengers, Paratransit services, Numerical solutions, Numerical analysis, Mathematical techniques, Mathematical models, Mathematical methods, Mass transit, Local transit, Journeys, Heuristic methods, Door to door service, Dial a ride

Abstract

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.

Comments

Transportation Research Part B Home Page: http://www.sciencedirect.com/science/journal/01912615

Link to Full Text

Share

COinS