Desrochers, Martin; Soumis, François Implantation et complexité des techniques de programmation dynamique dans les méthodes de confection de tournées et d’horaires. (Implementation and complexity of dynamic programming techniques in methods of vehicle routing and scheduling). (French) Zbl 0733.90035 RAIRO, Rech. Opér. 25, No. 3, 291-310 (1991). Summary: In all dyamic programming problems, the aim is to solve the recurrence equations for all states. The optimal solution is a set of paths going from the initial states to the final. We study a class of discrete dynamic programming problems: the shortest path problems with several constraints. We will compare two classes of algorithms; “reaching” algorithms and “pulling” algorithms. We will describe one “reaching” implementation and two “pulling” ones. We 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. MSC: 90B35 Deterministic scheduling theory in operations research 90C39 Dynamic programming 90C60 Abstract computational complexity for mathematical programming problems 90C35 Programming involving graphs or networks 90B06 Transportation, logistics and supply chain management 90-08 Computational methods for problems pertaining to operations research and mathematical programming 90C06 Large-scale problems in mathematical programming Keywords:resource constraints; discrete dynamic programming; shortest path; “reaching” algorithms; “pulling” algorithms PDFBibTeX XMLCite \textit{M. Desrochers} and \textit{F. Soumis}, RAIRO, Rech. Opér. 25, No. 3, 291--310 (1991; Zbl 0733.90035) Full Text: DOI EuDML