Two-stage spline-approximation in linear structure routing

In the article, computer design of routes of linear structures is considered as a spline approximation problem. A fundamental feature of the corresponding design tasks is that the plan and longitudinal profile of the route consist of elements of a given type. Depending on the type of linear structure, line segments, arcs of circles, parabolas of the second degree, clothoids, etc. are used. In any case, the design result is a curve consisting of the required sequence of elements of a given type. At the points of conjugation, the elements have a common tangent, and in the most difficult case, a common curvature. Such curves are usually called splines. In contrast to other applications of splines in the design of routes of linear structures, it is necessary to take into account numerous restrictions on the parameters of spline elements arising from the need to comply with technical standards in order to ensure the normal operation of the future structure. Technical constraints are formalized as a system of inequalities. The main distinguishing feature of the considered design problems is that the number of elements of the required spline is usually unknown and must be determined in the process of solving the problem. This circumstance fundamentally complicates the problem and does not allow using mathematical models and nonlinear programming algorithms to solve it, since the dimension of the problem is unknown. The article proposes a two-stage scheme for spline approximation of a plane curve. The curve is given by a sequence of points, and the number of spline elements is unknown. At the first stage, the number of spline elements and an approximate solution to the approximation problem are determined. The method of dynamic programming with minimization of the sum of squares of deviations at the initial points is used. At the second stage, the parameters of the spline element are optimized. The algorithms of nonlinear programming are used. They were developed taking into account the peculiarities of the system of constraints. Moreover, at each iteration of the optimization process for the corresponding set of active constraints, a basis is constructed in the null space of the constraint matrix and in the subspace – its complement. This makes it possible to find the direction of descent and solve the problem of excluding constraints from the active set without solving systems of linear equations. As an objective function, along with the traditionally used sum of squares of the deviations of the initial points from the spline, the article proposes other functions taking into account the specificity of a particular project task.

1. Struchenkov V.I. The use of mathematical optimization methods and a computer in the design of the longitudinal profile of railways; B.K. Malyavskii (Ed.). Seriya: Trudy Vsesoyuznogo nauchno-issledovatel’skogo instituta transportnogo stroitel’stva = Series: Proceedings of the All-Union Scientific Research Institute of Transport Construction. Iss. 101. Moscow: Transport; 1977. 169 p. (in Russ.).

2. Struchenkov V.I. Computer technologies in line structure routing. Rossiiskii tekhnologicheskii zhurnal = Russian Technological Journal. 2017;5(1):29−41 (in Russ.). https://doi.org/10.32362/2500-316X-2017-5-1-29-41

3. Ahlberg J.H., Nilson E.N., Walsh J.L. The theory of splines and their applications. Academic press; 1967. 296 p. [Alberg J., Nilson E., Walsh J. Teoriya splainov i ee prilozheniya (The theory of splines and their applications). Moscow: Mir; 1972. 312 p. (in Russ.).]

4. Khakimov B.V. Modelirovanie korrelyatsionnykh zavisimostei splainami na primerakh v geologii i ekologii(Modeling of correlation dependences by splines on examples in geology and ecology). St. Petersburg: Neva; 2003. 144 p. (in Russ). ISBN 5-7654-2951-3

5. Dierckx P. Curve and Surface fitting with splines. Oxford University Press; 1995. 285 p.

6. Mikhalevich V.S., Bykov V.I., Sibirko A.N. To the question of designing the optimal longitudinal profile of the road. Transportnoe stroitel’stvo = Transport Construction. 1975;6:39−40 (in Russ.).

7. Kosmin V.V., Struchenkov V.I., Fradkov E.B. Computer design of the longitudinal profile of the road. Transportnoe stroitel’stvo= Transport Construction. 1971;4:38−42 (in Russ.).

8. Bentley Rail Track. Available from URL: https://www.bentley.com/-/media/1EA2B937CB5B42BEA5EAE802620C0BA3.ashx

9. CARD/1. Available from URL: http://card-1.ru/

10. Autodesk. Available from URL: https://www.architect-design.ru/autodesk/autocad/

11. Тоpomatic Robur. Available from URL: http://www.topomatic.ru/

12. Credo-Dialog. Available from URL: https://credo-dialogue.ru/

13. Struchenkov V.I. The use of parabolic splinees in CAD of linear structures. Rossiiskii tekhnologicheskii zhurnal = Russian Technological Journal. 2018;6(1):40−51 (in Russ). https://doi.org/10.32362/2500-316X-2018-6-1-40-52

14. Struchenkov V.I. Metody optimizatsii trass v SAPR lineinykh sooruzhenii (Methods for route optimization in CAD of linear structures). Moscow: Solon-Press; 2014. 271 р. (in Russ). ISBN 978-5-91359-139-5

15. Lezhnev A.V. Dinamicheskoe programmirovanie v ekonomicheskikh zadachakh (Dynamic programming in economic problems). Moscow: Binom; 2016. 176 p. (in Russ). ISBN 5-94774-344-2

16. Cavagnari G., Marigonda A., Piccoli B. Generalized dynamic programming principle and sparse mean-field control problems. Journal of Mathematical Analysis and Applications. 2020;481(1):123437. https://doi.org/10.1016/j.jmaa.2019.123437

17. He S., Shin H.-S., Tsourdos A. Computational guidance using sparse Gauss-Hermite quadrature differential dynamic programming. IFAC-PapersOnLine. 2019;52(12):13−18. https://doi.org/10.1016/j.ifacol.2019.11.062

18. Fayaed S.S., Fiyadh S.S., Khai W.J., Ahmed A.N., Afan H.A., Ibrahim R.K. Improving dam and reservoir operation rules using stochastic dynamic programming and artificial neural network integration model. Sustainability. 2019;11(19):5367. https://doi.org/10.3390/su11195367

19. Işik H., Sintunavarat W. An investigation of the common solutions for coupled systems of functional equations arising in dynamic programming. Mathematics. 2019;7(10):977. https://doi.org/10.3390/math7100977

20. Karpov D.A., Struchenkov V.I. Dynamic Programming as a Method of Spline Approximation in the CAD Systems of Linear Constructions. Rossiiskii tekhnologicheskii zhurnal = Russian Technological Journal. 2019;7(3):77−88 (in Russ.). https://doi.org/10.32362/2500-316X-2019-7-3-77-88

21. Karpov D.A., Struchenkov V.I. Metody i algoritmy resheniya prikladnykh zadach diskretnoi optimizatsii(Methods and algorithms for solving applied discrete optimization problems). Moscow: Solon-Press; 2020. 201 p. (in Russ.). ISBN 978-5-91359-399-3

22. Kochenderfer M., Wheeler T. Algorithms for Optimization. The MIT Press; 2019. 521 p. [Kokhenderfer M., Uiler T. Algoritmy optimizatsii. Moscow: Vil’yams; 2020. 528 р. (in Russ.). ISBN 978-5-907144-76-7]

23. Chernorutskii I.G. Metody optimizatsii. Komp’yuternye tekhnologii (Optimization methods. Computer technologies). St. Petersburg: BHV-Petersburg; 2011. 370 p. (in Russ.). ISBN 978-5-9775-0784-4

24. Ovchinnikov V.A. Modeli i metody diskretnoi optimizatsii(Models and methods of discrete optimization). Moscow: MGTU im. N.E. Baumana; 2019. 278 p. (in Russ.). ISBN 978-5-7038-5105-0

25. Struchenkov V.I. Prikladnye zadachi optimizatsii (Applied optimization problems). Moscow: Solon-Press; 2016. 314 p. (in Russ.). ISBN 978-5-91359-191-3

26. Karikh Yu.S. Evaluation of existing longitudinal profile design methods. In: Collection of works of GiprodorNII: Improving the economic efficiency of investment in the construction, repair and maintenance of roads. Moscow: Izdanie GiprodorNII; 1976. P. 105−112. (in Russ.).