ESTIMATIONS OF THE ASYMPTOTIC COMPLEXITY OF APPLIED MULTIPLE TRANSPORT ALGORITHMS WHEN DIVISIONING THEM INTO CLUSTERS

Abstract

Applied multiple transport algorithms are usually heuristic and overly complex. Depending on the chosen heuristic of the algorithm, the real time of the software implementation depends on the programming language, the structure of the input data representation and the algorithmic complexity of the solution. The research is based on the use of the provisions of discrete mathematics and graph theory. It is shown that by analyzing asymptotic complexity it is possible to determine effective heuristics. Refinement of applied problem models also contributes to reducing complexity. Since the multiplicity of transport tasks is contained in a discrete coverage or in the functionality of multiple vehicles, it is possible to simplify the algorithm by decomposing them into clusters for which the conditions and constraints of the standard transport task apply. The features of geometric and combinatorial decomposition into clusters are presented. The formalization of cluster construction algorithms for multiple transport problems is provided. A comparative analysis of optimal and heuristic algorithms for solving multiple transport problems is carried out. The hierarchy of asymptotic complexity of heuristic algorithms is determined and the possibilities of their decomposition into clusters are analyzed, which simplify the solution of multiple applied transport problems. The notation of the complexity of the solution and the possibility of their evaluation by the objective function of the selected algorithm or by its approximation are provided. An analysis of the asymptotic complexity of heuristic algorithms for Big-O notation has been carried out. It has been shown that algorithms with a complexity not exceeding polynomial are suitable for implementation, and the use of algorithms with an exponential complexity estimate and higher is undesirable. It is noted that asymptotic estimates of algorithm complexity are suitable for large-dimensional tasks, and for tasks of small dimension, control runs are appropriate.