Construction of Shortest Line of Restricted Curvature in a Non-singly-connected Polygonal Area

In a computer aided laying-out of roads and railway lines there arises the problem of the modeling of optimal routes with restricted curvature in a given non-singly-connected polygonal (NSCP) area. However, since the triangulating network models are used now for the NSCP areas, the development of the respective AutoCADs is sufficiently hampered due to the lack of an efficient approach allowing to simulate the routes of continuous curvature with the required accuracy. Therefore, optimization of routes cannot be carried out in a proper way. For solving this nonlinear problem in compliance with the requirements of the engineering standards, a model is presented that comprises a set of basic optimization problems for the construction of the shortest route composed of segments and circular arcs. In order to provide smooth growth of acceleration for eliminating overload at high speeds, these elements are mated with the easement curves — clothoid (Euler spiral) or cubic parabola fragments. For these problems the condition of optimality and respective optimization methods are presented that show linear memory and time complexity.