This article examines a constrained shortest path problem which occurs in the design by column generation of vehicle routes constructed to satisfy a set of transportation requests, each requiring both pick-up and delivery. The additional constraints relate to the capacity of the vehicle and the time intervals within which pick-up and delivery must occur. We propose a very efficient dynamic programming algorithm for this problem. This algorithm uses various criteria for eliminating states that do not satisfy some constraints. Heuristic procedures for accelerating the algorithm are also proposed.