10.14489/vkit.2021.07.pp.015-026

DOI: 10.14489/vkit.2021.07.pp.015-026

Карпов Д. А., Смирнов С. С., Струченков В. И.
ОПТИМИЗАЦИЯ ПАРАМЕТРОВ СПЛАЙНОВ ПРИ ПРОЕКТИРОВАНИИ ТРАСС ЛИНЕЙНЫХ СООРУЖЕНИЙ
(c. 15-26)

Аннотация. Рассматривается задача аппроксимации дискретной последовательности точек на плоскости сплайном, состоящим из отрезков прямых, сопрягаемых дугами окружностей при неизвестных границах и числе элементов сплайна. Работа является продолжением статьи, опубликованной в № 6, 2019*. Данная задача возникает при проектировании продольного профиля новых и реконструируемых железных и автомобильных дорог. Показаны принципиальные отличия рассматриваемой задачи от задач, решаемых в теории сплайнов и ее приложениях. Предложена двухэтапная схема. На первом этапе с использованием специального алгоритма динамического программирования определяется число элементов сплайна и приближенные значения его параметров, удовлетворяющие всем ограничениям. На втором этапе этот результат используется как начальное приближение для оптимизации параметров сплайна с помощью специального алгоритма нелинейного программирования. Реализованы существенные упрощения алгоритма первого этапа по сравнению с опубликованным ранее, обусловленные отсутствием клотоид при сопряжении прямых и кривых. Обоснована необходимость второго этапа при проектировании новых дорог для учета взаимосвязи элементов сплайна в насыпях и в выемках, если насыпи будут сооружаться из грунта выемок, а оптимизация выполняется по критерию минимума строительных затрат. Предложен новый алгоритм нелинейного программирования, основанный на построении базиса в нуль-пространствах матриц активных ограничений и корректировке этого базиса в итерационном процессе при изменении набора активных ограничений. Показано, как найти направление спуска и решить вопрос об исключении ограничений из активного набора без решения систем линейных уравнений вообще или решая линейные системы малой размерности. В качестве модели целевой функции вместо традиционно используемой суммы квадратов отклонений аппроксимируемых точек от сплайна предложены другие модели с учетом специфики конкретной проектной задачи.

Ключевые слова: трасса; план и продольный профиль; сплайн; нелинейное программирование; целевая функция; ограничения; базис; антиградиент.

Karpov D. A., Smirnov S. S., Struchenkov V. I.
OPTIMIZATION OF SPLINE PARAMETERS WHEN DESIGNING ROUTES OF LINEAR STRUCTURES
(pp. 15-26)

Abstract. It considers the problem of approximating a discrete sequence of points on a plane by a spline consisting of line segments conjugated by circular arcs with unknown boundaries and the number of spline elements. This article is a continuation of the article published in N 6, 2019. This problem arises when designing the longitudinal profile of new and reconstructed railways and highways. The fundamental differences of the considered problem from the problems solved in the theory of splines and its applications are shown. A two-stage scheme is proposed: at the first stage, using a special dynamic programming algorithm, the number of elements of the spline and the approximate values of its parameters that satisfy all the constraints are determined. At the second stage, this result is used as an initial approximation to optimize the spline parameters using a special nonlinear algorithm. Significant simplifications of the algorithm of the first stage are implemented in comparison with the previously published one, due to the absence of clothoids when conjugating straight lines and curves. The necessity of the second stage in the design of new roads is substantiated to take into account the interconnection of spline elements in embankments and in excavations, if embankments will be constructed from excavation soil, and optimization is performed according to the criterion of minimum construction costs. A new nonlinear programming algorithm is proposed based on the construction of a basis in zero spaces of matrices of active constraints and the correction of this basis in an iterative process when changing the set of active constraints. It is shown how to find the direction of descent and solve the problem of excluding constraints from the active set without solving systems of linear equations in general or by solving linear systems of low dimension. Instead of the traditionally used sum of squares of deviations of the approximated points from the spline, other models are proposed as a model of the objective function, taking into account the specifics of a specific design problem.

Keywords: Route; Plan and Longitudinal Profile; Spline; Nonlinear Programming; Objective Function; Constraints; Basis.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

Д. А. Карпов, С. С. Смирнов, В. И. Струченков (Институт кибернетики МИРЭА – Российский технологический университет, Москва, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

D. A. Karpov, S. S. Smirnov, V. I. Struchenkov (Institute of Cybernetics of the MIREA – Russian Technological University, Moscow, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Альберт Дж., Нильсон Э., Уолш Дж. Теория сплайнов и ее приложения: монография / пер. с англ. М.: Мир, 2012. 312 с.
2. Василенко В. А. Оптимизация энергетического функционала для вариационных сплайнов // Бюл. Новосибирского вычислительного центра. 1996. № 7. С. 101 – 107.
3. Зайниддинов Х. Н., Мадхусудан Сингх. Полиномиальные сплайны для цифровых систем. Германия: LAMBERT Academic Publishing, 2019. 208 с.
4. Дхананджай Сингх, Мадхусудан Сингх, Хакимжон Зайниддинов. Применение многомерных полиномиальных сплайнов. Брифинги по прикладным наукам и технологиям. Сингапур: Springer, 2019. 70 с.
5. Уткир Хамдамов, Хакимжон Зайниддинов. Алгоритмы обработки растровых изображений вейвлет Добеши: 10-я Международная конференция по коммуникационным программным сетям, 2018, июль. Чэнду, Китай, С. 537 – 541.
6. Струченков В. И., Баранов М. А., Рабинович В. С. Использование математических методов оптимизации и ЭВМ при проектировании продольного профиля железных дорог. М.: Транспорт, 1977. 169 с.
7. Струченков В. И. Методы оптимизации трасс в САПР линейных сооружений. М.: СОЛОН-Пресс, 2014. 271 с.
8. Карпов Д. А., Струченков В. И. Динамическое программирование как метод сплайн-аппроксимации в САПР линейных сооружений // Российский технологический журнал. 2019. T. 7, № 3. С. 78 – 88.
9. Струченков В. И., Карих Ю. С., Шварц П. С. Математические методы оптимизации при автоматизированном проектировании дорог // Автомобильные дороги. 1980. № 12. С. 17 – 26.
10. Зойтендейк Дж. Г. Методы возможных направлений. M.: ИЛ, 1963. 214 с.
11. Гилл Ф., Мюррей В., Райт М. Практическая оптимизация / пер. с англ. M.: Мир, 1985. 290 с.
12. Bentley ProjectWise 365. https://www.bentley.com/ru/products/product-line/project-delivery-software/projectwise-365 (дата обращения: 16.02.2021).
13. CARD/1. URL: https://www.card-1.com/en/home/ (дата обращения: 20.02.2021).
14. Autodesk AutoCAD URL: https://www.autodesk. ru/products/autocad/overview?term=1-YEAR&support=null (дата обращения: 26.02.2021).
15. Программные продукты и технологии CREDO: офиц. сайт. Credo-Dialog. URL: https://credo-dialogue.ru/ (дата обращения: 14.02.2021).

Eng

1. Al'bert Dzh., Nil'son E., Uolsh Dzh. (2012). Spline theory and its applications: monograph. Moscow: Mir. [in Russian language]
2. Vasilenko V. A. (1996). Optimization of the energy functional for variational splines. Byulleten' Novosibirskogo vychislitel'nogo tsentra, (7), pp. 101 – 107. [in Russian language]
3. Zayniddinov H. N., Madhusudan Singh. (2019). Polynomial splines for digital systems. Germany: LAMBERT Academic Publishing. [in Russian language]
4. Dhanandzhay Singh, Madhusudan Singh, Hakimzhon Zayniddinov. (2019). Application of multidimensional polynomial splines. Applied Science and Technology Briefings. Singapore: Springer. [in Russian language]
5. Utkir Hamdamov, Hakimzhon Zayniddinov. (2018). Raster Image Processing Algorithms Wavelet Daubechies: 10th International Conference on Software Communication Networks, pp. 537 – 541. Chengdu. [in Russian language]
6. Struchenkov V. I., Baranov M. A., Rabinovich V. S. (1977). The use of mathematical optimization methods and computers in the design of the longitudinal profile of railways. Moscow: Transport. [in Russian language]
7. Struchenkov V. I. (2014). Methods for route optimization in CAD of linear structures. Moscow: SOLON-Press. [in Russian language]
8. Karpov D. A., Struchenkov V. I. (2019). Dynamic programming as a spline approximation method in CAD of linear structures. Rossiyskiy tekhnologicheskiy zhurnal, Vol. 7, (3), pp. 78 – 88. [in Russian language]
9. Struchenkov V. I., Karih Yu. S., Shvarts P. S. (1980). Mathematical optimization methods for automated road design. Avtomobil'nye dorogi, (12), pp. 17 – 26. [in Russian language]
10. Zoytendeyk Dzh. G. (1963). Possible directions methods. Moscow. [in Russian language]
11. Gill F., Myurrey V., Rayt M. (1985). Practical optimization. Moscow: Mir. [in Russian language]
12. Bentley ProjectWise 365. Available at: https://www. bentley.com/ru/products/product-line/project-delivery-software/ projectwise-365 (Available at: 16.02.2021). [in Russian language]
13. CARD/1. Available at: https://www.card-1.com/en/ home/ (Accessed: 20.02.2021). [in Russian language]
14. Autodesk AutoCAD. Available at: https://www.auto-desk.ru/products/autocad/overview?term=1-YEAR&support=null (Accessed: 26.02.2021). [in Russian language]
15. CREDO software products and technologies: official site. Credo-Dialog. Available at: https://credo-dialogue.ru/ (Accessed: 14.02.2021). [in Russian language]

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 450 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа скопируйте doi статьи:

10.14489/vkit.2021.07.pp.015-026

и заполните форму

Отправляя форму вы даете согласие на обработку персональных данных.

Eng

This article is available in electronic format (PDF).

The cost of a single article is 450 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please copy the article doi:

10.14489/vkit.2021.07.pp.015-026

and fill out the form