Strategies of the level-by-level approach to the minimal route

Abstract

The task of optimal path planning for drilling tool with numerical control is considered. Such tools are used in the production of printed circuit boards. The algorithm modification of level-by-level route construction for the approximate solution of the traveling salesman problem is discussed. Bypass objects can be specified either as a table of distances or values represented by a symmetric matrix, or as Cartesian coordinates (in applied cases of using numerically controlled equipment). The algorithm was tested on many different examples. As a result of the calculations performed for examples from the TSPLIB library (defined through a full distance matrix or Cartesian coordinates) with a dimension of up to 100 cities, the ability of the algorithm to construct the optimal route was confirmed. For examples from other sources or for artificially constructed ones (up to 130 objects), in the testing of the algorithm, the declared record values of the route minimum length were also achieved or improved. © 2019 ASTES Publishers. All rights reserved.