mireabulletinRussian Technological JournalRussian Technological Journal2782-32102500-316XRTU MIREA10.32362/2500-316X-2024-12-1-111-122mireabulletin-830Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGИспользование сплайнов сложной структуры в проектировании дорожных трассThe use of complex structure splines in roadway designhttps://orcid.org/0000-0002-9801-7454СтрученковВ. И.StruchenkovV. I.

Струченков Валерий Иванович - д.т.н., профессор, кафедра геоинформационных систем Института радиоэлектроники и информатики. Scopus Author ID 36451166800.

119454, Москва, пр-т Вернадского, д. 78

Valery I. Struchenkov - Dr. Sci. (Eng.), Professor, Department of Geographic Information Systems, Institute of Radio Electronics and Informatics. Scopus Author ID 36451166800.

78, Vernadskogo pr., Moscow, 119454

str1942@mail.ruhttps://orcid.org/0000-0003-3734-7182КарповД. А.KarpovD. A.

Карпов Дмитрий Анатольевич - к.т.н., заведующий кафедрой геоинформационных систем Института радиоэлектроники и информатики. Scopus Author ID 57211584863.

119454, Москва, пр-т Вернадского, д. 78

Dmitry A. Karpov - Cand. Sci. (Eng.), Head of the Department of Geographic Information Systems, Institute of Radio Electronics and Informatics. Scopus Author ID 57211584863.

78, Vernadskogo pr., Moscow, 119454

karpov@mirea.ruМИРЭА – Российский технологический университетРоссияMIREA – Russian Technological UniversityRussian Federation202402022024121111122Copyright © Струченков В.И., Карпов Д.А., 20242024Струченков В.И., Карпов Д.А.Struchenkov V.I., Karpov D.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.rtj-mirea.ru/jour/article/view/830Цели

Цели. Цель работы состоит в развитии теории сплайн-аппроксимации последовательности точек на плоскости на случай использования составных сплайнов сложной структуры. В отличие от простого, например, полиномиального сплайна, составной сплайн содержит повторяющиеся связки нескольких элементов. Такая задача возникает в проектировании трасс железных и автомобильных дорог. План (проекция на горизонтальную плоскость) такой трассы – это кривая, состоящая из повторяющейся связки элементов «прямая ++ клотоида + окружность + клотоида …», что обеспечивает непрерывность не только кривой и касательной, но и кривизны. Число элементов сплайна неизвестно и должно определяться в процессе решения проектной задачи. Алгоритм решения задачи применительно к сплайну, состоящему из дуг окружностей, сопрягаемых прямыми, реализован и опубликован ранее. Аппроксимирующий сплайн в общем случае – многозначная функция. На координаты точек ее графика могут накладываться ограничения. Еще одним существенным фактором, усложняющим задачу, является наличие клотоид, которые не выражаются аналитически (формулой). Алгоритм определения числа элементов сплайна с клотоидами и построения начального приближения опубликован ранее. В настоящей статье рассматривается следующий этап решения задачи – оптимизация с применением нелинейного программирования сплайна, полученного на первом этапе по методу динамического программирования.

Методы

Методы. Для оптимизации параметров сплайна используется новая математическая модель в виде модифицированной функции Лагранжа и специальный алгоритм нелинейного программирования. При этом удается вычислять аналитически производные целевой функции по параметрам сплайна при отсутствии ее аналитического выражения через эти параметры.

Результаты

Результаты. Разработаны математическая модель и алгоритм оптимизации параметров составного сплайна, состоящего из дуг окружностей, сопрягаемых клотоидами и прямыми.

Выводы

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

Objectives

Objectives. The aim of the work is to develop the theory of spline-approximation of a sequence of points on a plane for using compound splines with a complex structure. In contrast to a simple spline (e.g., polynomial), a compound spline contains repeating bundles of several elements. Such problems typically arise in the design of traces for railroads and highways. The plan (projection on the horizontal plane) of such a trace is a curve consisting of a repeating bundle of elements “line + clothoid + circle + clothoid ...,” which ensures continuity not only of curve and tangent but also of curvature. The number of spline elements, which is unknown, should be determined in the process of solving the design problem. An algorithm for solving the problem with respect to the spline, which consists of arcs conjugated by straight lines, was implemented and published in an earlier work. The approximating spline in the general case is a multivalued function, whose ordinates may be limited. Another significant factor that complicates the problem is the presence of clothoids that are not expressed analytically (in a formula). The algorithm for determining the number of elements of a spline with clothoids and constructing an initial approximation was also published earlier. The present work considers the next stage of solving the spline approximation problem: optimization using a nonlinear programming spline obtained at the first stage by means of the dynamic programming method.

Methods

Methods. A new mathematical model in the form of a modified Lagrange function is used together with a special nonlinear programming algorithm to optimize spline parameters. In this case, it is possible to calculate the derivatives of the objective function by the spline parameters in the absence of its analytical expression through these parameters.

Results

Results. A mathematical model and algorithm for optimization of compound spline parameters comprising arcs of circles conjugated by clothoids and lines have been developed.

Conclusions

Conclusions. The previously proposed two-step scheme for designing paths of linear structures is also suitable for the utilization of compound splines with clothoids.

план трассысплайннелинейное программированиеклотоидацелевая функцияограниченияtrace plansplinenonlinear programmingclothoidobjective functionconstraintsReferencesКарпов Д.А., Струченков В.И. Двухэтапная сплайн-аппроксимация в компьютерном проектировании трасс линейных сооружений. Russ. Technol. J. 2021;9(5):45–56. https://doi.org/10.32362/2500-316X-2021-9-5-45-56Karpov D.A., Struchenkov V.I. Two-stage spline-approximation in linear structure routing. Russ. Technol. J. 2021;9(5):45−56 (in Russ.). https://doi.org/10.32362/2500-316X-2021-9-5-45-56Карпов Д.А., Струченков В.И. Сплайн-аппроксимация многозначных функций в проектировании трасс линейных сооружений. Russ. Technol. J. 2022;10(4):65–74. https://doi.org/10.32362/2500-316X-2022-10-4-65-74Karpov D.A., Struchenkov V.I. Spline approximation of multivalued function in leaner structures routing. Russ. Technol. J. 2022;10(4):65–74 (in Russ.). https://doi.org/10.32362/2500-316X-2022-10-4-65-74Карпов Д.А., Струченков В.И. Оптимизация параметров сплайна при аппроксимации многозначных функций. Russ. Technol. J. 2023;11(2);72–83. https://doi.org/10.32362/2500-316X-2023-11-2-72-83Karpov D.A., Struchenkov V.I. Optimization of spline parameters in approximation of multi-valued function Russ. Technol. J. 2023;11(2):72–83 (in Russ.). https://doi.org/10.32362/2500-316X-2023-11-2-72-83Li W., Pu H., Schonfeld P., et al. A Method for Automatically Recreating the Horizontal Alignment Geometry of Existing Railways. Comput. Aided Civ. Infrastruct. Eng. 2019;34(1):71–94. https://doi.org/10.1111/mice.12392Li W., Pu H., Schonfeld P., et al. A Method for Automatically Recreating the Horizontal Alignment Geometry of Existing Railways. Comput. Aided Civ. Infrastruct. Eng. 2019;34(1):71–94. https://doi.org/10.1111/mice.12392Jha M.K., McCall C., Schonfeld P. Using GIS, genetic algorithms, and visualization in highway development. Comput. Aided Civ. Infrastruct. Eng. 2001;16(6):399–414. https://doi.org/10.1111/0885-9507.00242Jha M.K., McCall C., Schonfeld P. Using GIS, genetic algorithms, and visualization in highway development. Comput. Aided Civ. Infrastruct. Eng. 2001;16(6):399–414. https://doi.org/10.1111/0885-9507.00242Jha M.K., Schonfeld P. A highway alignment optimization model using geographic information systems. Transp. Res. Part A. Policy Pract. 2004;8(6):455–481. https://doi.org/10.1016/j.tra.2004.04.001Jha M.K., Schonfeld P. A highway alignment optimization model using geographic information systems. Transp. Res. Part A. Policy Pract. 2004;8(6):455–481. https://doi.org/10.1016/j.tra.2004.04.001Jong J.C., Jha M.K., Schonfeld P. Preliminary highway design with genetic algorithms and geographic information systems. Comput. Aided Civ. Infrastruct. Eng. 2000;15(4):261–271. https://doi.org/10.1111/0885-9507.00190Jong J.C., Jha M.K., Schonfeld P. Preliminary highway design with genetic algorithms and geographic information systems. Comput. Aided Civ. Infrastruct. Eng. 2000;15(4):261–271. https://doi.org/10.1111/0885-9507.00190Kang M.W., Schonfeld P., Yang N. Prescreening and repairing in a genetic algorithm for highway alignment optimization. Comput. Aided Civ. Infrastruct. Eng. 2009;24(2):109–119. https://doi.org/10.1111/j.1467-8667.2008.00574.xKang M.W., Schonfeld P., Yang N. Prescreening and repairing in a genetic algorithm for highway alignment optimization. Comput. Aided Civ. Infrastruct. Eng. 2009;24(2):109–119. https://doi.org/10.1111/j.1467-8667.2008.00574.xPushak Y., Hare W., Lucet Y. Multiple-path selection for new highway alignments using discrete algorithms. Eur. J. Oper. Res. 2016;248(2):415–427. https://doi.org/10.1016/j.ejor.2015.07.039Pushak Y., Hare W., Lucet Y. Multiple-path selection for new highway alignments using discrete algorithms. Eur. J. Oper. Res. 2016;248(2):415–427. https://doi.org/10.1016/j.ejor.2015.07.039Sarma K.C., Adeli H. Bilevel parallel genetic algorithms for optimization of large steel structures. Comput. Aided Civ. Infrastruct. Eng. 2001;16(5):295–304. https://doi.org/10.1111/0885-9507.00234Sarma K.C., Adeli H. Bilevel parallel genetic algorithms for optimization of large steel structures. Comput. Aided Civ. Infrastruct. Eng. 2001;16(5):295–304. https://doi.org/10.1111/0885-9507.00234Shafahi Y., Bagherian M. A customized particle swarm method to solve highway alignment optimization problem. Comput. Aided Civ. Infrastruct. Eng. 2013;28(1):52–67. https://doi.org/10.1111/j.1467-8667.2012.00769.xShafahi Y., Bagherian M. A customized particle swarm method to solve highway alignment optimization problem. Comput. Aided Civ. Infrastruct. Eng. 2013;28(1):52–67. https://doi.org/10.1111/j.1467-8667.2012.00769.xBosurgi G., D’Andrea A. A polynomial parametric curve (PPC-curve) for the design of horizontal geometry of highways. Comput. Aided Civ. Infrastruct. Eng. 2012;27(4):303–312. https://doi.org/10.1111/j.1467-8667.2011.00750.xBosurgi G., D’Andrea A. A polynomial parametric curve (PPC-curve) for the design of horizontal geometry of highways. Comput. Aided Civ. Infrastruct. Eng. 2012;27(4):303–312. https://doi.org/10.1111/j.1467-8667.2011.00750.xCerf R. The quasispecies regime for the simple genetic algorithm with roulette wheel Selection. Cornell University. Adv. Appl. Probability. 2017;49(3):903–926. https://doi.org/10.1017/apr.2017.26Cerf R. The quasispecies regime for the simple genetic algorithm with roulette wheel Selection. Cornell University. Adv. Appl. Probability. 2017;49(3):903–926. https://doi.org/10.1017/apr.2017.26Oudshoorn M., Koppenberg T., Yorke-Smith N. Optimization of annual planned rail maintenance. Comput. Aided Civ. Infrastruct. Eng. 2021;37(6):669–687. https://doi.org/10.1111/mice.12764Oudshoorn M., Koppenberg T., Yorke-Smith N. Optimization of annual planned rail maintenance. Comput. Aided Civ. Infrastruct. Eng. 2021;37(6):669–687. https://doi.org/10.1111/mice.12764Струченков В.И. Новый алгоритм поэлементного расчета трасс в САПР линейных сооружений. Информационные технологии. 2015;21(4):271–276.Struchenkov V.I. New algorithm for perelement calculation of line structures routes. Informacionnye tekhnologii = Information Technologies. 2015;21(4):271–276 (in Russ.).Бородакий Ю.В., Загребаев А.М., Крицына Н.А., Кулябичев Ю.П., Шумилов Ю.Ю. Нелинейное программирование в современных задачах оптимизации. М.: НИЯУ МИФИ; 2011. 244 с. ISBN 987-5-7262-1451-1Borodakii Yu.V., Zagrebaev A.M., Kritsyna N.A., Kulyabichev Yu.P., Shumilov Yu.Yu. Nelineinoe programmirovanie v sovremennykh zadachakh optimizatsii (Nonlinear Programming in Modern Optimization Problem). Moscow: NIYAU MEPhI; 2008. 244 р. (in Russ.).Поляков В.М., Агаларов З.С. Методы оптимизации. М.: Дашков и К; 2022. 86 с. ISBN 978-5-3940-5003-9Polyakov V.M., Agalarov Z.S. Metody optimizatsii (Optimization Methods). Moscow: Dashkov i K; 2022. 86 p. (in Russ.). ISBN 978-5-3940-5003-9Гасников А.В. Современные численные методы оптимизации. Метод универсального градиентного спуска. М.: МЦНМО; 2021. 272 с. ISBN 978-5-4439-1614-9Gasnikov A.V. Sovremennye chislennye metody optimizatsii. Metod universal’nogo gradientnogo spuska (Modern Numerical Optimization Methods. Universal Gradient Method Descent). Moscow: MTsNMO; 2021.272 p. (in Russ.). ISBN 978-5-4439-1614-9Струченков В.И. Методы оптимизации трасс в САПР линейных сооружений. М.: СОЛОН-Пресс; 2020. 272 с. ISBN 978-5-9135-9139-5Struchenkov V.I. Metody optimizatsii trass v SAPR lineinykh sooruzhenii (Methods for Route Optimization in CAD of Linear Structures). Moscow: SOLON-Press; 2020. 272 р. (in Russ.). ISBN 978-5-9135-9139-5Кохендерфер М. Д., Уилер Т.А. Алгоритмы оптимизации. M.: Вильямс; 2020. 528 с.Kochenderfer M.D., Wheeler T.A. Algoritmy optimizatsii (Algorithms for Optimization). Moscow: Vil’yams; 2020. 528 p. (in Russ.). [Kochenderfer M.D., Wheeler T.A. Algorithms for Optimization. London: The MIT Press; 2019. 520 p.]Audet C., Hare W. Derivative-Free and Blackbox Optimization. Springer Series in Operations Research and Financial Engineering. Springer; 2017. 302 р. https://doi.org/10.1007/978-3-319-68913-5Audet C., Hare W. Derivative-Free and Blackbox Optimization. Springer Series in Operations Research and Financial Engineering. Springer; 2017. 302 р. https://doi.org/10.1007/978-3-319-68913-5Черноруцкий И.Г. Методы оптимизации. Компьютерные технологии. СПб.: БХВ-Петербург; 2011. 329 с.Chernorutskii I.G. Metody optimizatsii. Komp’yuternye tekhnologii (Methods of Optimization. Computer Technologies). St. Petersburg: BHV-Petersburg; 2011. 329 p. (in Russ.).Гилл Ф., Мюррей У., Райт М. Практическая оптимизация: пер. с англ. М.: Мир; 1985. 509 c.Gill Ph.E., Murray W., Wright M.H. Prakticheskaya optimizatsiya (Practical Optimization): transl. from Engl. Moscow: Mir; 1985. 509 p. (in Russ.). [Gill Ph.E., Murray W., Wright M.H. Practical Optimization. London: Academic Press; 1981. 402 p.]Ларичев О.И., Горвиц Г.Г. Методы поиска локальных экстремумов овражных функций. М.: Наука; 1990. 96 с.Larichev O.I., Gorvits G.G. Metody poiska lokal’nykh ekstremumov ovrazhnykh funktsii (Methods for Finding Local Extrema of Ravine Functions). Moscow: Nauka; 1990. 96 p. (in Russ.).

The authors declare that there are no conflicts of interest present.