Online Rejected-Reinsertion Heuristics for Dynamic Multivehicle Dial-a-Ride Problem

This paper presents and compares online implementations of rejected-reinsertion heuristics for the dynamic multivehicle dial-a-ride problem (DARP), which the authors previously developed for static DARP. In dynamic DARP, transportation requests are received in real time, whereas in static DARP, all information about service requests is known in advance. The main objective for the DARP heuristics is to minimize the number of vehicles used to satisfy all trip requests, subject to service quality constraints. Two online implementation strategies, called “immediate insertion” and “rolling-horizon insertion,” coupled with two variations of the insertion heuristic rejected reinsertion without and with periodic improvement procedures, are developed and compared. Computational results show that the rolling-horizon insertion heuristics, which take advantage of the advance information available, achieve vehicle reductions of up to 10% more than their immediate-insertion counterpart. The proposed online rejected-reinsertion heuristics achieve vehicle reductions up to 16% and 10% more, respectively, than the online parallel insertion heuristics that use immediate insertion and rolling-horizon insertion strategies, while keeping the computation time at the same magnitude as the parallel-insertion heuristics. Sensitivity analysis shows that the rolling-horizon insertion heuristics are insensitive to the time horizon and the rolling interval.