Комбинированные алгоритмы аппроксимации для интерактивного проектирования дорожных трасс в системах автоматизированного проектирования

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

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

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

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

1. Горинов А.В. Изыскания и проектирование железных дорог. Т. 2. М.: Трансжелдориздат; 1961. 338 с.

2. Шейдвассер Д.М. Оптимизация трасс железных дорог на напряженных ходах. В кн.: Автоматизация проектирования объектов транспортного строительства. М.: Транспорт; 1986. С. 16–29.

3. Струченков В.И., Шейдвассер Д.М. Оптимизация на ЭВМ трассы новой железной дороги на напряженных ходах. Транспортное строительство. 1987;3:7–9.

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

5. Jha 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.001

6. 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

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

8. Pushak 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.039

9. 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

10. 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

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

12. Cerf R. The quasispecies regime for the simple genetic algorithm with roulette wheel selection. arXiv:1506.0981v2. https://doi.org/10.48550/arXiv.1506.09081

13. 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

14. Li 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.0000691

15. Pu 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

16. Сальков Н.А. Моделирование геометрических форм автомобильных дорог: монография. М.: ИНФРА-М; 2019. 162 с.

17. Смирнов В.И. Курс высшей математики. Т. 2. М.: Наука; 1967. 479 c.

18. Горинов А.В., Кантор И.И., Кондратенко А.П., Турбин И.В. Изыскания и проектирование железных дорог. М.: Транспорт; 1979. 319 с.

19. Кантор И.И. Изыскания и проектирование железных дорог. М.: ИКЦ «Академкнига»; 2003. 288 с.

20. Федотов Г.А., Поспелов И.И. Изыскания и проектирование автомобильных дорог. Кн. 1. М.: Высшая школа; 2009. 650 с.

21. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация: пер. с англ. М.: Мир; 1985. 509 c.

22. Кохендерфер М.Д., Уилер Т.А. Алгоритмы оптимизации. M.: Вильямс; 2020. 528 с.

23. Черноруцкий И.Г. Методы оптимизации. Компьютерные технологии. СПб.: БХВ-Петербург; 2011. 329 с.

24. Струченков В.И. Новый алгоритм поэлементного расчета трасс в САПР линейных сооружений. Информационные технологии. 2015;21(4):271–276.