Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0733.90035
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)
[J] RAIRO, Rech. Opér. 25, No.3, 291-310 (1991). ISSN 0399-0559

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 2000:: *90B35 Scheduling theory
90C39 Dynamic programming
90C60 Abstract computational complexity for math. programming problems
90C35 Network programming
90B06 Transportation, logistics
90-08 Computational methods (optimization)
90C06 Large-scale problems

Keywords: resource constraints; discrete dynamic programming; shortest path; ``reaching'' algorithms; ``pulling'' algorithms

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]