Dynamic Programming as a Method of Spline Approximation in the CAD Systems of Linear Constructions
https://doi.org/10.32362/2500-316X-2019-7-3-77-88
Abstract
Under study is a problem of the line structure routing of roads, railways and other linear constructions. Designing a trace plan and longitudinal profile are considered as non-linear programming tasks. Since the number of elements of the plan and the longitudinal profile is not known, the problem is solved in three stages. First, a search is performed for a polyline consisting of short elements. On the second stage it is used to determine the initial approximation of the desired line, which is optimized at the last stage. The required line consists of a given type elements and it is a spline with a number of features:
- In contrast to the polynomial elements considered in the theory of splines, when designing roads unknown spline is a sequence of elements: straight, clothoid, circle, clothoid, straight and so on.
- In this task, the spline does not have to be a single-valued function.
- The parameters of the elements of the desired spline must satisfy the constraints in the form of inequalities.
These features of the task do not allow the use of non-linear programming methods to solve it. Converting a broken line to a spline is carried out using dynamic programming. For this purpose a special formalization of this task is proposed. A new algorithm of dynamic programming is given. The result is used as an initial approximation to optimize the parameters of the spline using a previously developed non-linear programming program.
About the Authors
D. A. Karpov
MIREA – Russian Technological University
Russian Federation
Russian Federation
Ph.D. (Engineering), Head of the Chair of General Informatics, Institute of Cybernetics
78, Vernadskogo pr., Moscow 119454, Russia
V. I. Struchenkov
MIREA – Russian Technological University
Russian Federation
Russian Federation
D.Sc. (Engineering), Professor of the Department of General Informatics of the Institute of Cybernetics of Chair of General Informatics, Institute of Cybernetics
78, Vernadskogo pr., Moscow 119454, Russia
References
1. Struchenkov V.I. Methods to optimize the routes in CAD linear structures. Moscow, Solon Press Publ., 2014. 271 p. (in Russ.)
2. Mikhalevich V.S., Shor N.Z. Mathematical foundations for solving the problem of choice optimal outline of the longitudinal profile. Trudy Vsesoyuznogo nauchno-issledovatel'skogo instituta transportnogo stroitel'stva (Proceed. of the All-Union Scientific Research Institute of Transport Construction). 1964. Is. 51. Moscow: Transport Publ., 1964. P. 12-24. (in Russ.)
3. Karikh Yu.S. Evaluation of existing longitudinal profile design methods. In the Collection of works of GiprodorNII: Improving the economic efficiency of investment in the construction, repair and maintenance of roads. M.: GiprodorNII Publ., 1976. P. 105-112. (in Russ.)
4. Sheidvasser D.M. Optimization of the route of the railways on tight passages. In the Collection of scientific works of the All-Union Scientific Research Institute of Transport Construction: Automation of the design of transport construction objects. M.: Transport Publ., 1986. P. 16-29. (in Russ.)
5. Struchenkov V.I. The use of parabolic splinees in CAD of linear structures. Rossiyskiy tekhnologicheskiy zhurnal ( Russian Technological Journal). 2018; 6(1):40-51. (in Russ.)
6. Alberg J., Nilson E., Walsh J. The theory of splines and its applications. Moscow: Mir Publ., 2012. 312 p. (in Russ.)
7. Bellman R. Dynamic programming. Moscow: Inostrannaya literatura Publ., 1960. 402 p. (in Russ.)
Supplementary files
|
|
1. Fig.1. The elements of the desired spline: AB, CD, EF, GH – clothoids; BC, FG - circles; DE - straight; θ - rotation angle. | |
| Subject | ||
| Type | Research Instrument | |
View
(38KB)
|
Indexing metadata ▾ | |
Review
For citations:
Karpov D.A., Struchenkov V.I. Dynamic Programming as a Method of Spline Approximation in the CAD Systems of Linear Constructions. Russian Technological Journal. 2019;7(3):77-88. (In Russ.) https://doi.org/10.32362/2500-316X-2019-7-3-77-88
Views:
870
Email this article 