Preview

Russian Technological Journal

Расширенный поиск

Сплайн-аппроксимация многозначных функций в проектировании трасс линейных сооружений

https://doi.org/10.32362/2500-316X-2022-10-4-65-74

Аннотация

Цели. В настоящее время наблюдается бурное развитие теории и методов сплайн-аппроксимации плоских кривых, заданных последовательностью точек. Проведенные исследования, первые результаты которых были опубликованы ранее, показали возможность применения сплайн-аппроксимации в проектировании трасс линейных сооружений, несмотря на принципиальные отличия используемых сплайнов от рассматриваемых в теории и ее приложениях. Главное отличие состоит в том, что в проектировании трасс нельзя заранее считать известным число элементов сплайна. Кроме того, в отличие от получивших широкое распространение полиномиальных сплайнов, повторяющимся элементом является связка «отрезок прямой + + дуга окружности» или «отрезок прямой + дуга клотоиды + дуга окружности + дуга клотоиды». Ранее была предложена двухэтапная схема: определение числа элементов искомого сплайна, затем - оптимизация его параметров. Алгоритм решения задачи применительно к проектированию продольного профиля реализован и опубликован. Но этот алгоритм непригоден для проектирования плана трассы, т.к. план трассы, в отличие от профиля, в общем случае является многозначной функцией. Цель работы - обобщить алгоритм на случай сплайн-аппроксимации многозначных функций с учетом особенностей проектирования трасс линейных сооружений.

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

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

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

Об авторах

Д. А. Карпов
МИРЭА - Российский технологический университет
Россия

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

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

SPIN-код РИНЦ 2619-7100


Конфликт интересов:

Нет



В. И. Струченков
МИРЭА - Российский технологический университет
Россия

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

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

SPIN-код РИНЦ 4581-4698


Конфликт интересов:

Нет



Список литературы

1. Карпов Д.А., Струченков В.И. Двухэтапная сплайн-аппроксимация в компьютерном проектировании трасс линейных сооружений. Российский технологический журнал. 2021;9(5):45-56. https://doi.org/10.32362/2500-316X-2021-9-5-45-56

2. Альберг Дж., Нильсон Э., Уолш Дж. Теория сплайнов и ее приложения: пер. с англ. М.: Мир; 1972. 312 с.

3. Хакимов Б.В. Моделирование корреляционных зависимостей сплайнами на примерах в геологии и экологии. СПб.: Нева; 2003. 144 с. ISBN 5-7654-2951-3

4. Pu 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.12392

5. Струченков В.И., Баранов М.А., Рабинович В.С. Использование математических методов оптимизации и ЭВМ при проектировании продольного профиля железных дорог; под ред. Малявского Б.К. Серия: Труды Всесоюзного научно-исследовательского института транспортного строительства. Вып. 101. М.: Транспорт; 1977. 169 с.

6. Price M. Under construction: building and calculating turn radii. ArcUser Magazine. 2010;13(1):50-56. URL: https://www.esri.com/news/arcuser/0110/turning.html

7. 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;27(4):303-312. https://doi.org/10.1111/j.1467-8667.2011.00750.x

8. Imran M., Hassan Y., Patterson D. GPS-GIS-based procedure for tracking vehicle path on horizontal alignments. Computer-Aided Civil and Infrastructure Engineering. 2006;21(5):383-394. https://doi.org/10.1111/j.1467-8667.2006.00444.x

9. Othman S., Thomson R., Lanner G. Using naturalistic field operational test data to identify horizontal curves. J. Transport. Eng. 2012;138(9):1151-1160. https://doi.org/10.1061/(asce)te.1943-5436.0000408

10. Vazquez-Mendez M.E., Casal G., Castro A. An algorithm for random generation of admissible horizontal alignments for optimum layout design. Computer-Aided Civil and Infrastructure Engineering. 2021;36(8):1056-1072 https://doi.org/10.1111/mice.12682

11. 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.00242

12. Jha M.K., Schonfeld P. A highway alignment optimization model using geographic information systems. Transportation Research Part A: Policy and Practice. 2004;38(6):455-481. https://doi.org/10.1016/j.tra.2004.04.001

13. 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;15(4):261-271. https://doi.org/10.1111/0885-9507.00190

14. 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;24(2):109-119. https://doi.org/10.1111/j.1467-8667.2008.00574.x

15. Pushak Y., Hare W., Lucet Y. Multiple-path selection for new highway alignments using discrete algorithms. Eur. J. Operational Res. 2016;248(2):415-427. https://doi.org/10.1016/j.ejor.2015.07.039

16. Sarma 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.00234

17. Shafahi 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.x

18. Audet C., Hare W. Derivative-Free and Blackbox Optimization. Springer Series in Operations Research and Financial Engineering. Springer International Publishing; 2017. 302 р. https://doi.org/10.1007/978-3-319-68913-5

19. Cerf R. The quasispecies regime for the simple genetic algorithm with roulette wheel Selection. Advances in Applied Probability. 2017;49(3):903-926. https://doi.org/10.1017/apr.2017.26

20. Струченков В.И. Методы оптимизации трасс в САПР линейных сооружений. М.: Солон-Пресс; 2014. 272 с. ISBN 978-5-91359-139-5

21. Struchenkov V.I. Piecewise parabolic approximation of plane curves with restrictions in computer-aided design of road routes. Transaction Machine Learning and Artificial Intelligence. 2013;1(1):16-26. URL: http://scholarpublishing.org/index.php/TMLAI/article/view/10/TMLAI-13-1015

22. Вентцель Е.С. Исследование операций: задачи, принципы, методология. М.: КноРус; 2010. 198 с. ISBN 978-5-406-00682-5


Дополнительные файлы

1. Расчет при углах поворота больше π
Тема
Тип Исследовательские инструменты
Посмотреть (24KB)    
Метаданные
  • Рассмотрена задача аппроксимации многозначных функций, заданных последовательностью точек на плоскости, сплайном, состоящим из повторяющихся связок: прямая + дуга окружности при ограничениях на длины отрезков прямых и дуг окружностей и радиусы. Число элементов неизвестно.
  • Задача решена в два этапа:

1) с помощью специального алгоритма динамического программирования определяется число элементов и приближённые (в силу дискретности поиска) значения их параметров;

2) оптимизация параметров сплайна с использованием нелинейного программирования.

  • В статье представлен алгоритм первого этапа, второй этап будет рассмотрен в следующей статье.

Рецензия

Для цитирования:


Карпов Д.А., Струченков В.И. Сплайн-аппроксимация многозначных функций в проектировании трасс линейных сооружений. Russian Technological Journal. 2022;10(4):65-74. https://doi.org/10.32362/2500-316X-2022-10-4-65-74

For citation:


Karpov D.A., Struchenkov V.I. Spline approximation of multivalued functions in linear structures routing. Russian Technological Journal. 2022;10(4):65-74. https://doi.org/10.32362/2500-316X-2022-10-4-65-74

Просмотров: 307


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2782-3210 (Print)
ISSN 2500-316X (Online)