An Exact Algorithm for the Single Vehicle Many-to-Many Dial-A-Ride Problem with Time Windows

Abstract

This paper modifies the exact Dynamic Programming algorithm developed by the author for the single vehicle many-to-many immediate request Dial-A-Ride problem to solve the problem where each customer has specified upper and lower bounds for his pickup and delivery times and where the objective is to minimize the time needed to service all customers. The major difference between the two algorithms is the substitution of backward recursion with forward recursion. The new algorithm requires the same computational effort as the old one (0(N²3^N) for N customers) and is able to recognize infeasible problem instances.