|
DOI: 10.14489/vkit.2022.07.pp.003-012
Карпов Д. А., Смирнов С. С., Струченков В. И.
КОМПЬЮТЕРНОЕ ПРОЕКТИРОВАНИЕ ТРАСС ЛИНЕЙНЫХ СООРУЖЕНИЙ С ПРИМЕНЕНИЕМ АЛГОРИТМОВ СПЛАЙН-АППРОКСИМАЦИИ МНОГОЗНАЧНЫХ ФУНКЦИЙ. ЧАСТЬ 1
(с. 3-12)
Аннотация. Рассматривается задача преобразования плоской ломаной линии в сплайн, элементами которого являются дуги окружностей, сопрягаемые отрезками прямых. Эта задача возникает при проектировании плана и профиля трасс линейных сооружений. Для таких сооружений, как траншеи для прокладки трубопроводов различного назначения, она имеет самостоятельное значение, как и при проектировании продольного профиля железных и автомобильных дорог. При проектировании плана трассы дороги решение этой задачи рассматривается как первый шаг в решении более сложной задачи, в которой для сопряжения дуг окружностей и прямых используются клотоиды. Применительно к проектированию продольного профиля дорог задача аппроксимации сплайном с окружностями решена ранее. План трассы в общем случае является многозначной функцией, и для его проектирования разработанный ранее алгоритм непригоден. Задача рассматривается при наличии ограничений на параметры сплайна и неизвестном числе его элементов. Предложено на первом этапе определить число элементов сплайна и приближенные значения его параметров, на втором – оптимизировать эти параметры. В качестве целевой функции используется простая или взвешенная сумма квадратов отклонений исходных точек (узлов ломаной) от сплайна. Здесь рассмотрен первый этап решения задачи с учетом особенностей аппроксимации многозначных функций. Реализован алгоритм динамического программирования; результат является начальным приближением для алгоритма нелинейного программирования. Принципиально новым для этого алгоритма является вычисление производных целевой функции по параметрам, определяющим положение сплайна, при отсутствии ее аналитического выражения через эти параметры. Решение задачи на втором этапе приведено в следующей статье.
Ключевые слова: трасса; план и продольный профиль; сплайн; динамическое программирование; целевая функция, ограничения.
Karpov D. A., Smirnov S. S., Struchenkov V. I.
COMPUTER DESIGN OF ROUTES OF LINEAR STRUCTURES USING ALGORITHMS SPLINE-APPROXIMATIONS OF MULTIPLE-VALUED FUNCTIONS. PART 1
(pp. 3-12)
Abstract. The problem of converting a flat broken line into a spline, whose elements are arcs of circles conjugated by line segments, is considered. This problem arises when designing the plan and profile of the routes of linear structures. For such structures as trenches for laying pipelines for various purposes, it has independent significance, as well as in the design of the longitudinal profile of railways and highways. When designing a road alignment plan, the solution of this problem is considered as the first step in solving a more complex problem in which clothoids are used to pair arcs of circles and straight lines. With regard to the design of the longitudinal profile of roads, the problem of approximation by a spline with circles was solved earlier. The principal feature of the problem under consideration in relation to the design of the route plan is that the spline is a multivalued function and the previously developed algorithm is unsuitable. The problem is considered in the presence of restrictions on the parameters of the spline and an unknown number of its elements. It is proposed at the first stage to determine the number of spline elements, and at the second stage to optimize its parameters. As an objective function, a simple or weighted sum of squared deviations of the initial points (polyline nodes) from the spline is used. The article considers the first stage, taking into account the features of the approximation of multivalued functions. Implemented dynamic programming algorithm; the result is an initial guess for the non-linear programming algorithm. Fundamentally new is the calculation of the derivatives of the objective function with respect to the parameters that determine the position of the spline in the absence of its analytical expression through these parameters. The next article will be devoted to the solution of the problem at the second stage.
Keywords: Route; Plan and longitudinal profile; Spline; Dynamic programming; Objective function; Constraints.
Д. А. Карпов, С. С. Смирнов, В. И. Струченков (Институт искусственного интеллекта МИРЭА – Российского технологического университета, Москва, Россия) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
D. A. Karpov, S. S. Smirnov, V. I. Struchenkov (Institute of Artificial Intelligence of the MIREA – Russian Technological University), Moscow, Russia) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
1. Альберт Дж., Нильсон Э., Уолш Дж. Теория сплайнов и ее приложения / пер. с англ. М.: Мир, 2012. 312 с.
2. Зайниддинов Х. Н., Сингх М. Полиномиальные сплайны для цифровых систем. LAMBERT Германия: Academic Publishing, 2019. 208 с.
3. Bosurgi 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. V. 27(4). P. 303 – 312. URL: https://doi.org/10.1111/j.1467-8667. 2011.00750.x
4. Imran M., Hassan Y., Patterson D. GPS-GIS-Based Procedure for Tracking Vehicle Path on Horizontal Alignements // Computer-Aided Civil and Infrastructure Engineering. 2006. V. 21(5). P. 383 – 394. URL: https:// doi.org/10.1111/j.1467-8667.2006.00444.x
5. Othman S., Thomson R., Lanner G. Using Naturalistic Field Operational Test Data to Identify Horizontal Curves // Journal of Transportation Engineering. 2012. V. 138(9). P. 1151 – 1160. URL: https://ascelibrary.org/ doi/10.1061/%28ASCE%29TE.1943-5436.0000408
6. Miguel E. Vazquez-Mendez, Casal G., Castro A. An Algorithm for Random Generation of Admissible Horizontal Alignments for Optimum Layout Design // Computer-Aided Civil and Infrastructure Engineering. 2021. V. 36(8). P. 1056 – 1072. URL: https://doi.org/ 10.1111/mice.12682
7. Шейдвассер Д. М. Оптимизация трассы железных дорог на напряженных ходах // Автоматизация проектирования объектов транспортного строительства. М.: Транспорт, 1986. C. 16 – 29.
8. Jha, M. K., Schonfeld, P. A Highway Alignment Optimization Model Using Geographic Information Systems // Transportation Research Part A Policy and Practice. 2004. V. 38(6). P. 455 – 481. URL: https://doi.org/10.1016/j.tra.2004.04.001
9. Hao Pu, Wei Li, Schonfeld P. A Method for Automatically Recreating the Horizontal Alignment Geometry of Existing Railways // Computer-Aided Civil and Infrastructure Engineering. 2019. V. 34(1). P. 71 – 94. URL: https://doi.org/10.1111/mice.12392
10. Jha M. K., McCall C., Schonfeld P. Using GIS, Genetic Algorithms, and Visualization in Highway Development // Computer-Aided Civil and Infrastructure Engineering. 2001. V. 16(6). P. 399 – 414. URL: https:// doi.org/10.1111/0885-9507.00242
11. Jong J. C., Jha M. K., Schonfeld P. Preliminary Highway Design with Genetic Algorithms and Geographic Information Systems // Computer-Aided Civil and Infrastructure Engineering. 2000. V. 15(4). P. 261 – 271. URL: https://doi.org/10.1111/0885-9507. 00190
12. Kang M. W., Schonfeld P., Yang N. Prescreening and Repairing in a Genetic Algorithm for Highway Alignment Optimization // Computer-Aided Civil and Infrastructure Engineering. 2009. V. 24(2). P. 109 – 119. URL: https://doi.org/10.1111/j.1467-8667. 2008.00574.x
13. Pushak Y., Hare W., Lucet Y. Multiple-Path Selection for New Highway Alignments Using Discrete Algorithms // European Journal of Operational Research. 2016. V. 248(2). P. 415 – 427. URL: https://doi.org/ 10.1016/ j.ejor.2015.07.039
14. Sarma K. C., Adeli H. Bilevel Parallel Genetic Algorithms for Optimization of Large Steel Structures // Computer Aided Civil and Infrastructure Engineering. 2001. V. 16(5). P. 295 – 304. URL: https://doi.org/ 10.1111/0885-9507.00234
15. Карпов Д. А., Струченков В. И. Сплайнаппроксимация в проектировании трасс линейных сооружений // Вестник компьютерных и информационных технологий. 2019. № 6. С. 16 – 22. DOI: 10.14489/vkit. 2019.06.pp.016-022
16. Struchenkov V. I., Karpov D. A. Two-Stage Spline-Approximation with an Unknown Number of Elements in Applied Optimization Problem of a Special Kind // Mathematics and Statistics. 2021. V. 9(4). P. 411 – 420. DOI: 10.13189/ms.2021.090401 https://www. hrpub.org/download/20210630/MS1-13423288.pdf
17. Вентцель Е. С. Исследование операций: задачи, принципы, методология. М.: Кнорус, 2010. 198 с.
18. Струченков В. И. Методы оптимизации трасс в САПР линейных сооружений. М.: Солон-Пресс, 2015. 272 с.
19. Кохендерфер М., Уилер Т. Алгоритмы оптимизации. M.: Вильямс, 2020. 528 с.
1. Al'bert Dzh., Nil'son E., Uolsh Dzh. (2012). Spline theory and its applications. Moscow: Mir. [in Russian language]
2. Zayniddinov H. N., Singh M. (2019). Polynomial splines for digital systems. LAMBERT Germany: Academic Publishing. [in Russian language]
3. Bosurgi G., D’Andrea A. (2012). A Polynomial Parametric Curve (PPC-Curve) for the Design of Horizontal Geometry of Highways. Computer-Aided Civil and Infrastructure Engineering, Vol. 27, (4), pp. 303 – 312. Available at: https://doi.org/10.1111/j.1467-8667.2011.00750.x
4. Imran M., Hassan Y., Patterson D. (2006). GPS-GIS-Based Procedure for Tracking Vehicle Path on Horizontal Alignements. Computer-Aided Civil and Infrastructure Engineering, Vol. 21, (5), pp. 383 – 394. Available at: https://doi.org/10.1111/j.1467-8667.2006.00444.x
5. Othman S., Thomson R., Lanner G. (2012). Using Naturalistic Field Operational Test Data to Identify Horizontal Curves. Journal of Transportation Engineering, Vol. 138, (9), pp. 1151 – 1160. Available at: https://ascelibrary.org/doi/10.1061/%28ASCE%29TE.1943-5436.0000408
6. Miguel E. Vazquez-Mendez, Casal G., Castro A. (2021). An Algorithm for Random Generation of Admissible Horizontal Alignments for Optimum Layout Design. Computer-Aided Civil and Infrastructure Engineering, Vol. 36, (8), pp. 1056 – 1072. Available at: https://doi.org/10.1111/mice.12682
7. Sheydvasser D. M. (1986). Optimization of the railroad route on busy tracks. In the book: Automation of the design of transport construction objects, pp. 16 – 29. Moscow: Transport. [in Russian language]
8. Jha, M. K., Schonfeld, P. (2004). A Highway Alignment Optimization Model Using Geographic Information Systems. Transportation Research Part A: Policy and Practice, Vol. 38, (6), pp. 455 – 481. Available at: https://doi.org/10.1016/j.tra.2004.04.001
9. Hao Pu, Wei Li, Schonfeld P. (2019). A Method for Automatically Recreating the Horizontal Alignment Geometry of Existing Railways. Computer-Aided Civil and Infrastructure Engineering, Vol. 34, (1), pp. 71 – 94. Available at: https://doi.org/10.1111/mice.12392
10. Jha M. K., McCall C., Schonfeld P. (2001). Using GIS, Genetic Algorithms, and Visualization in Highway Development. Computer-Aided Civil and Infrastructure Engineering, Vol. 16, (6), pp. 399 – 414. Available at: https://doi.org/10.1111/0885-9507.00242
11. Jong J. C., Jha M. K., Schonfeld P. (2000). Preliminary Highway Design with Genetic Algorithms and Geographic Information Systems. Computer-Aided Civil and Infrastructure Engineering, Vol. 15, (4), pp. 261 – 271. Available at: https://doi.org/10.1111/0885-9507. 00190
12. Kang M. W., Schonfeld P., Yang N. (2009). Prescreening and Repairing in a Genetic Algorithm for Highway Alignment Optimization. Computer-Aided Civil and Infrastructure Engineering, Vol. 24, (2), pp. 109 – 119. Available at: https://doi.org/10.1111/j.1467-8667.2008.00574.x
13. Pushak Y., Hare W., Lucet Y. (2016). Multiple-Path Selection for New Highway Alignments Using Discrete Algorithms. European Journal of Operational Research, Vol. 248, (2), pp. 415 – 427. Available at: https://doi.org/10.1016/j.ejor.2015.07.039
14. Sarma K. C., Adeli H. (2001). Bilevel Parallel Genetic Algorithms for Optimization of Large Steel Structures. Computer Aided Civil and Infrastructure Engineering, Vol. 16, (5), pp. 295 – 304. Available at: https://doi.org/10.1111/0885-9507.00234
15. Karpov D. A., Struchenkov V. I. (2019). Spline Approximation in the Design of Routes of Linear Structures. Vestnik komp'yuternyh i informatsionnyh technologiy, (6), pp. 16 – 22. [in Russian language] DOI: 10.14489/vkit. 2019.06.pp.016-022
16. Struchenkov V. I., Karpov D. A. (2021). Two-Stage Spline-Approximation with an Unknown Number of Elements in Applied Optimization Problem of a Special Kind. Mathematics and Statistics, Vol. 9, (4), pp. 411 – 420. DOI: 10.13189/ms.2021.090401 Available at: https://www.hrpub.org/download/20210630/MS1-13423288.pdf
17. Venttsel' E. S. (2010). Operations research: tasks, principles, methodology. Moscow: Knorus. [in Russian language]
18. Struchenkov V. I. (2015). Methods for optimizing routes in CAD for linear structures. Moscow: Solon-Press. [in Russian language]
19. Kohenderfer M., Uiler T. (2020). Optimization algorithms. Moscow: Vil'yams. [in Russian language]
Статью можно приобрести в электронном виде (PDF формат).
Стоимость статьи 500 руб. (в том числе НДС 20%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.
После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.
Для заказа скопируйте doi статьи:
10.14489/vkit.2022.07.pp.003-012
и заполните форму
Отправляя форму вы даете согласие на обработку персональных данных.
.
This article is available in electronic format (PDF).
The cost of a single article is 500 rubles. (including VAT 20%). 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.2022.07.pp.003-012
and fill out the form
.
|
Архив номеров
Разработка концепции и создание сайта - ООО «Издательский дом «СПЕКТР»