A restricted dynamic programming algorithm for the dial-a-ride problem

International audienceIn this paper, a restricted dynamic programming algorithm for the static multiple vehicle dial-a-ride problem is presented. Passengers have to be transported between pickup and delivery locations, while minimizing travel distances, respecting time window, user ride time and route duration constraints. We report preliminary results for benchmark instances which provide promising results. Algorithmic extensions and a hybrid metaheuristic are considered as pathways for future work