A Dynamic Programming Solution of the Large-Scale Single-Vehicle Dial-A-Ride Problem with Time Windows

SYNOPTIC ABSTRACT

The single-vehicle dial-a-ride problem with time window constraints for both pick-up and delivery locations, and precedence and capacity constraints, is solved using a forward dynamic programming algorithm. The total distance is minimized. The development of criteria for the elimination of infeasible states results in solution times which increase linearly with problem size.

Key Words and Phrases:

• dial-a-ride
• dynamic programming
• routing
• scheduling