Local search heuristics for the probabilistic dial-a-ride problem

This paper introduces the probabilistic dial-a-ride problem, and describes an efficient request-relocation neighborhood evaluation procedure for the problem. The running time of the procedure is O(n(5)), compared to (On(6)) for a straightforward approach. For solving the problem we embed the suggested evaluation procedure in a pure local search heuristic and in a tabu search heuristic. The quality of the solutions obtained by the two heuristics have been compared experimentally. Computational results confirm that our neighborhood evaluation technique is much faster than the straightforward one, and for cases with 144 users and 4 vehicles it is demonstrated that the computation time can be reduced by a factor larger than 27.