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. Each customer has specified upper and lower bounds for his pickup and delivery times and 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(N23N) for N customers) and is able to recognize infeasible problem instances.
Original language | English |
---|---|
Journal | Transportation Science |
Volume | 17 |
Issue number | 3 |
Pages (from-to) | 351-357 |
Number of pages | 7 |
ISSN | 0041-1655 |
DOIs | |
Publication status | Published - 1983 |
Externally published | Yes |