+7 (495) 987 43 74 ext. 3304
Join us -              
Рус   |   Eng

articles

Authors: Karpov D., Smirnov S., Struchenkov V.     Published in № 5(95) 31 october 2021 year
Rubric: Algorithmic efficiency

Spline-approximation as the basis of computer technology design of linear structures routes

This article is a continuation of the article published in Journal of Applied Informatics nо.1 in 2019 [1]. In it, the problems of computer design of routes of various linear structures (new and reconstructed railways and highways, pipelines for various purposes, canals, etc.) are considered from a unified standpoint, as problems of approximating a sequence of points on plane of a smooth curve consisting of elements of a given type, i.e. spline. The fundamental difference from other approximation problems considered in the theory of splines and its applications is that the boundaries of the elements of the spline and even their number are unknown. Therefore, a two-stage scheme for finding a solution has been proposed. At the first stage, the number of spline elements and their parameters are determined using dynamic programming. For some tasks, this stage is the only one. In more complex cases, the result of the first stage is used as an initial approximation to optimize the spline parameters using nonlinear programming. Another complicating factor is the presence of numerous restrictions on the spline parameters, which take into account design standards and conditions for the construction and subsequent operation of the structure. The article discusses the features of mathematical models of the corresponding design problems. For a spline consisting of arcs of circles, mated by line segments, used in the design of the longitudinal profile of both new and reconstructed railways and highways and pipelines, a mathematical model is built and a new algorithm for solving a nonlinear programming problem is proposed, taking into account the structural features of the constraint system. In contrast to standard nonlinear programming algorithms, a basis is constructed in the zero-space of the matrix of active constraints and its modification is used when the set of active constraints changes. At the same time, to find the direction of descent at each iteration, no solution of auxiliary systems of equations is required at all. Two options for organizing the iterative optimization process are considered: descent through groups of variables in the presence of sections for independent construction of the descent direction and the traditional change of all variables in one iteration. Experimentally, no significant advantage of one of these options has been revealed.

Key words

route, plan and longitudinal profi spline, nonlinear programming, objective function, constraints, basis, reduced antigradient

The author:

Karpov D.

Degree:

PhD in Technique, Institute of Cybernetics of the Russian Technological University (MIREA)

Location:

Moscow

The author:

Smirnov S.

Degree:

Applicant for Cand. Sci. (Eng.), Senior Lecturer, General Informatics Department, Russian Technological University (MIREA)

Location:

Moscow, Russia

The author:

Struchenkov V.

Degree:

Dr. Sci. (Eng.), Professor, Senior Researcher, General Informatics Department, Russian Technological University (MIREA)

Location:

Moscow, Russia