Spline approximation of multivalued functions in linear structures routing

Objectives. The theory and methods of spline approximation of plane curves given by a sequence of points are currently undergoing rapid development. Despite fundamental differences between used splines and those considered in the theory and its applications, results published earlier demonstrate the possibility of using spline approximation when designing routes of linear structures. The main difference here consists in the impossibility of assuming in advance the number of spline elements when designing the routes. Here, in contrast to widely use polynomial splines, the repeating element is the link “segment of a straight line + arc of a circle” or “segment of a straight line + arc of a clothoid + arc of a circle + arc of a clothoid.” Previously, a two-stage scheme consisting of a determination of the number of elements of the desired spline and subsequent optimization of its parameters was proposed. Although an algorithm for solving the problem in relation to the design of a longitudinal profile has been implemented and published, this is not suitable for designing a route plan, since, unlike a profile, a route plan is generally a multivalued function. The present paper aims to generalize the algorithm for the case of spline approximation of multivalued functions making allowance for the design features of the routes of linear structures.

Methods. At the first stage, a novel mathematical model is developed to apply the dynamic programming method taking into account the constraints on the desired spline parameters. At the second stage, nonlinear programming is used. In this case, it is possible to analytically calculate the derivatives of the objective function with respect to the spline parameters in the absence of its analytical expression through these parameters.

Results. An algorithm developed for approximating multivalued functions given by a discrete series of points using a spline consisting of arcs of circles conjugated by line segments for solving the first stage of the problem is presented. An additional nonlinear programming algorithm was also used to optimize the parameters of the resulting spline as an initial approximation. However, in the present paper, the first stage is considered only, since the complex algorithm of the second stage and its justification require separate consideration.

Conclusions. The presented two-stage spline approximation scheme with an unknown number of spline elements is also suitable for approximating multivalued functions given by a sequence of points on a plane, in particular, for designing a route plan for linear structures.

1. Karpov D.A., Struchenkov V.I. Two-stage splineapproximation in linear structure routing. Russian Technological Journal. 2021;9(5):45-56 (in Russ.). https://doi.org/10.32362/2500-316X-2021-9-5-45-56

2. Ahlberg J.H., Nilson E.N., Walsh J.L. The theory of splines and their applications. Academic press; 1967. 296 p. [Alberg J., Nilson E., Walsh J. Teoriya splainov i ee prilozheniya (The theory of splines and their applications): transl. from Engl. Moscow: Mir; 1972. 312 p. (in Russ.).]

3. Khakimov B.V. Modelirovanie korrelyatsionnykh zavisimostei splainami na primerakh v geologii i ekologii (Modeling of correlation dependences by splines on examples in geology and ecology). St. Petersburg: Neva; 2003. 144 p. (in Russ.). 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. Struchenkov V.I., Baranov M.A., Rabinovich V.S. The use of mathematical optimization methods and a computer in the design of the longitudinal profile of railways. Malyavskii B.K. (Ed.). Seriya: Trudy Vsesoyuznogo nauchno-issledovatel'skogo instituta transportnogo stroitel'stva = Series: Proceedings of the All Union Scientific Research Institute of Transport Construction. Iss. 101. Moscow: Transport; 1977. 169 p. (in Russ.).

6. Price M. Under construction: building and calculating turn radii. ArcUser Magazine. 2010;13(1):50-56. Available from 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. Struchenkov V.I. Metody optimizatsii trass v SAPR lineinykh sooruzhenii (Methods for route optimization in CAD of linear structures). Moscow: Solon-Press; 2014. 272 р. (in Russ). ISBN 8-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. Available from URL: http://scholarpublishing.org/index.php/TMLAI/article/view/10/TMLAI-13-1015

22. Venttsel' E.S. Issledovanie operatsii: zadachi, printsipy, metodologiya (Operations Research: Objectives, Principles, Methodology). Moscow: KnoRus; 2010. 198 p. (in Russ.). ISBN 978-5-406-00682-5