An exact algorithm for the single vehicle many-to-many dial-a-ride problem with time windows

HN Psaraftis - Transportation science, 1983 - pubsonline.informs.org
Transportation science, 1983pubsonline.informs.org
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 …
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(N23N) for N customers) and is able to recognize infeasible problem instances.
INFORMS
以上显示的是最相近的搜索结果。 查看全部搜索结果