Combined approximation algorithms for interactive design of road routes in CAD

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

1. Gorinov A.V. Izyskaniya i proektirovanie zheleznykh dorog (Research and Design of Railways). V. 2. Moscow: Transzheldorizdat; 1961. 338 p. (in Russ.).

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

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

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

17. Smirnov V.I. Kurs vysshei matematiki (Higher Mathematics Course). V. 2. Moscow: Nauka; 1979. 479 p. (in Russ.).

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

19. Kantor I.I. Izyskaniya i proektirovanie zheleznykh dorog (Research and Design of Railways). Moscow: Akademkniga; 2003. 288 p. (in Russ.).

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

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

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

23. Chernorutskii I.G. Metody optimizatsii. Komp’yuternye tekhnologii (Methods of optimization. Computer technologies). St. Petersburg: BHV-Petersburg; 2011. 329 p. (in Russ.).

24. Struchenkov V.I. New algorithm for perelement calculation of line structures routes. Informacionnye tekhnologii = Information Technologies. 2015;21(4): 271–276 (in Russ.).