Implementation and complexity of dynamic programming techniques for solving the time table and vehicle routing problems

In all dynamic programming problems, the aim is to solve the recurrence equations for all states. The optimal is a set of paths going from the initial states to the final states. The authors study a class of discrete dynamic programming problems: the shortest path problems with several constraints. They will compare two classes of algorithms; ‘reaching’ algorithms and ‘pulling’ algorithms. The authors will describe one ‘reaching’ implementation and two ‘pulling’ ones. They will compare their computational complexity and the results of an empirical study on large scale problems. The main conclusion of this study is that the computation times of the second implementation of the ‘pulling’ algorithm does not grow with the number of states but is rather proportional to the number of feasible paths in the solution.