Modification of the wave algorithm for Euclidean distances calculation in transport applications

Abstract

Many engineering problems could be either reduced to or directly involve the mathematical problem of finding the shortest path in some confined space with obstacles. To solve this problem, graph theory and dynamic programming offers quite a lot of exact and heuristic algorithms that work with directed and undirected, weighted and unweighted, connected and disconnected graphs. All these methods are based on their own techniques of calculating the distance between the vertices, the choice of which is dictated by the convenience of implementation and methodological considerations. As a result, the resulted paths found by the algorithms usually are characterized by a certain abstract length, which is often difficult to convert into Euclidean one. Nevertheless, spatial problems in engineering practice often require an answer in terms of real physical distances. Specifically, such a task fully arises in engineering applications related to the design of seaports, namely, in the laying of routes of intra-terminal transport, power supply networks, in the design of approach channels. A modification of the most common method for finding the shortest paths, the wave orthogonal-diagonal algorithm, is described in the paper. It allows you to include the geometric characteristics of its individual sections in the calculation of the length of the found route, which makes it possible to accurately estimate the length in the sense of the Euclidean distance.