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

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.