mireabulletinRussian Technological JournalRussian Technological Journal2782-32102500-316XRTU MIREA10.32362/2500-316X-2023-11-4-72-83mireabulletin-736Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGКомбинированные алгоритмы аппроксимации для интерактивного проектирования дорожных трасс в системах автоматизированного проектированияCombined approximation algorithms for interactive design of road routes in CADhttps://orcid.org/0000-0003-3734-7182КарповД. А.KarpovD. A.

Карпов Дмитрий Анатольевич, к.т.н., заведующий кафедрой общей информатики Института искусственного интеллекта

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

Dmitry A. Karpov, Cand. Sci. (Eng.), Head of the General Informatics Department, Institute of Artificial Intelligence

78, Vernadskogo pr., Moscow, 119454

karpov@mirea.ruhttps://orcid.org/0000-0002-9801-7454СтрученковВ. И.StruchenkovV. I.

Струченков Валерий Иванович, д.т.н., профессор, кафедра общей информатики Института искусственного интеллекта

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

Valery I. Struchenkov, Dr. Sci. (Eng.), Professor, General Informatics Department, Institute of Artificial Intelligence

78, Vernadskogo pr., Moscow, 119454

str1942@mail.ruМИРЭА – Российский технологический университетРоссияMIREA – Russian Technological UniversityRussian Federation2023010820231147283Copyright © Карпов Д.А., Струченков В.И., 20232023Карпов Д.А., Струченков В.И.Karpov D.A., Struchenkov V.I.Данная работа распространяется под лицензией 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/736Цели

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

Метод

Метод. Задача поэлементной аппроксимации окружностью или клотоидой формализована как задача нелинейного программирования малой размерности. Целевая функция – сумма квадратов отклонений от исходных точек. Поскольку клотоида в декартовых координатах представляется степенными рядами, возникают трудности вычисления производных целевой функции по искомым параметрам элементов сплайна. Предложен математически корректный алгоритм вычисления этих производных на основе интегрального представления декартовых координат точек клотоиды как функций ее длины.

Результаты

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

Выводы

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

Objectives

Objectives. The aim of the work is to create algorithms for approximating a sequence of points on a plane by arcs of clothoids and circles. Such a problem typically arises in the design of railroad and highway routes. The plan (projection onto a horizontal plane) of the road route is a curve (spline) consisting of a repeating bundle of elements “straight line + clothoid arc + circle arc + clothoid arc + ...”. Such a combination of elements provides continuity not only for the curve and its tangent, but also for the curvature. Since the number of spline elements is not known in advance, and their parameters are subject to restrictions, there is no mathematically consistent algorithm for this problem. The two-stage scheme for solving the problem is developed at RTU MIREA only for a spline with lines and circles (i.e., without clothoid elements). At the first stage, the scheme uses dynamic programming to determine the number of spline elements. At the second stage, the scheme optimizes parameters of the spline using nonlinear programming. This scheme has yet to be implemented for a spline with clothoids due to a significantly more complicated nature of this problem. Therefore, the design of route plans in existing computer aided design (CAD) systems is carried out in interactive mode using iterative selection of elements. In this regard, it makes sense to develop mathematically consistent algorithms for element-by-element approximation.

Methods

Methods. The problem of element-by-element approximation by a circle and a clothoid is formalized as a lowdimensional non-linear programming problem. The objective function is the sum of squared deviations from the original points. Since a clothoid can only be represented in Cartesian coordinates by power series, there are difficulties in calculating the derivatives of the objective function with respect to the desired parameters of the spline elements. The proposed mathematically consistent algorithm for calculating these derivatives is based on the integral representation of the Cartesian coordinates of the points of the clothoid as functions of its length.

Results

Results. A mathematical model and algorithms have been developed for approximating a sequence of points on a plane by clothoids and circles using the method of nonlinear programming. A second-order algorithm is implemented with the calculation and inversion of the matrix of second derivatives (Hesse matrix).

Conclusions

Conclusions. For approximation by circles and clothoids using nonlinear programming, it is not necessary to have an analytical expression of the objective function in terms of the required variables. The proposed algorithms make it possible to calculate not only the first, but also the second derivatives in the absence of such expressions.

план трассысплайннелинейное программированиеклотоидацелевая функцияградиентматрица Гессеroute plansplinenon-linear programmingclothoidobjective functiongradientHessian matrixReferencesГоринов А.В. Изыскания и проектирование железных дорог. Т. 2. М.: Трансжелдориздат; 1961. 338 с.Gorinov A.V. Izyskaniya i proektirovanie zheleznykh dorog (Research and Design of Railways). V. 2. Moscow: Transzheldorizdat; 1961. 338 p. (in Russ.).Шейдвассер Д.М. Оптимизация трасс железных дорог на напряженных ходах. В кн.: Автоматизация проектирования объектов транспортного строительства. М.: Транспорт; 1986. С. 16–29.Sheidwasser D.M. Optimization of railroad tracks on busy tracks. In: Avtomatizatsiya proektirovaniya ob’ektov transportnogo stroitel’stva (Automation of the Design of Transport Construction Objects). Moscow: Transport; 1986. P. 16–29 (in Russ.).Струченков В.И., Шейдвассер Д.М. Оптимизация на ЭВМ трассы новой железной дороги на напряженных ходах. Транспортное строительство. 1987;3:7–9.Struchenkov V.I., Sheidwasser D.M. Optimization on a computer of the route of a new railway on stressful passages. Transportnoe stroitel’stvo = Transport Construction. 1987;3:7–9 (in Russ.).Jha M.K., McCall C., Schonfeld P. Using GIS, genetic algorithms, and visualization in highway development. Computer-Aided Civil and Infrastructure Engineering. 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. Computer-Aided Civil and Infrastructure Engineering. 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. Computer-Aided Civil and Infrastructure Engineering. 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. Computer-Aided Civil and Infrastructure Engineering. 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. Computer-Aided Civil and Infrastructure Engineering. 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. Computer-Aided Civil and Infrastructure Engineering. 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. Computer Aided Civil and Infrastructure Engineering. 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. Computer Aided Civil and Infrastructure Engineering. 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. Computer-Aided Civil and Infrastructure Engineering. 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. Computer-Aided Civil and Infrastructure Engineering. 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. Computer-Aided Civil and Infrastructure Engineering. 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. Computer-Aided Civil and Infrastructure Engineering. 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. arXiv:1506.0981v2. https://doi.org/10.48550/arXiv.1506.09081Cerf R. The quasispecies regime for the simple genetic algorithm with roulette wheel selection. arXiv:1506.0981v2. https://doi.org/10.48550/arXiv.1506.09081Pu H., Li W., Schonfeld P., et al. A Method for Automatically Recreating the Horizontal Alignment Geometry of Existing Railways. Computer-Aided Civil and Infrastructure Engineering. 2019;34(1):71–94. https://doi.org/10.1111/mice.12392Pu H., Li W., Schonfeld P., et al. A Method for Automatically Recreating the Horizontal Alignment Geometry of Existing Railways. Computer-Aided Civil and Infrastructure Engineering. 2019;34(1):71–94. https://doi.org/10.1111/mice.12392Li W., Zhen S., Schonfeld P., et al. Recreating Existing Railway Horizontal Alignments Automatically Using Overall Swing Iteration. J. Transport. Eng. Part A: Systems. 2022;148(8). https://doi.org/10.1061/JTEPBS.0000691Li W., Zhen S., Schonfeld P., et al. Recreating Existing Railway Horizontal Alignments Automatically Using Overall Swing Iteration. J. Transport. Eng. Part A: Systems. 2022;148(8). https://doi.org/10.1061/JTEPBS.0000691Pu H., Fu H., Schonfeld P., et al. Modelling and optimization of constrained alignments for existing railway reconstruction. Int. J. Rail Transportat. 2023;11(3):428–447. https://doi.org/10.1080/23248378.2022.2081878Pu H., Fu H., Schonfeld P., et al. Modelling and optimization of constrained alignments for existing railway reconstruction. Int. J. Rail Transportat. 2023;11(3):428–447. https://doi.org/10.1080/23248378.2022.2081878Сальков Н.А. Моделирование геометрических форм автомобильных дорог: монография. М.: ИНФРА-М; 2019. 162 с.Sal’kov N.A. Modelirovanie geometricheskikh form avtomobil’nykh dorog: Monografiya (Modeling Geometric Shapes of Highways: Monograph). Moscow: INFRA-M; 2019. 162 p. (in Russ.).Смирнов В.И. Курс высшей математики. Т. 2. М.: Наука; 1967. 479 c.Smirnov V.I. Kurs vysshei matematiki (Higher Mathematics Course). V. 2. Moscow: Nauka; 1979. 479 p. (in Russ.).Горинов А.В., Кантор И.И., Кондратенко А.П., Турбин И.В. Изыскания и проектирование железных дорог. М.: Транспорт; 1979. 319 с.Gorinov A.V., Kantor I.I., Kondratenko A.P., Turbin I.V. Izyskaniya i proektirovanie zheleznykh dorog (Research and Design of Railways). Moscow: Transport; 1979. 319 p. (in Russ.).Кантор И.И. Изыскания и проектирование железных дорог. М.: ИКЦ «Академкнига»; 2003. 288 с.Kantor I.I. Izyskaniya i proektirovanie zheleznykh dorog (Research and Design of Railways). Moscow: Akademkniga; 2003. 288 p. (in Russ.).Федотов Г.А., Поспелов И.И. Изыскания и проектирование автомобильных дорог. Кн. 1. М.: Высшая школа; 2009. 650 с.Fedotov G.A., Pospelov I.I. Izyskaniya i proektirovanie avtomobil’nykh dorog (Research and Design of Highways). V. 1. Moscow: Vysshaya shkola; 2009. 650 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.]Кохендерфер М.Д., Уилер Т.А. Алгоритмы оптимизации. 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: MIT Press; 2019. 520 p.]Черноруцкий И.Г. Методы оптимизации. Компьютерные технологии. СПб.: БХВ-Петербург; 2011. 329 с.Chernorutskii I.G. Metody optimizatsii. Komp’yuternye tekhnologii (Methods of optimization. Computer technologies). St. Petersburg: BHV-Petersburg; 2011. 329 p. (in Russ.).Струченков В.И. Новый алгоритм поэлементного расчета трасс в САПР линейных сооружений. Информационные технологии. 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.).

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