Experience of Applying the Geometric Optimization Method for the Huge Traveling Salesman Problem

This research is devoted to the neighborhood-based method of optimization of the obtained fast feasible TSP solutions. The experiments were carried out using the well-known problem with the size of 1 million points. The sequential version of the proposed algorithm has been implemented. The efficiency is ensured by solving small sub-problems (taking points that are geometrically close to each other), making problem sizes more manageable and allowing for the tackling of larger problems. The advantage of the algorithm is that its parallel version can be applied to the TSP in 3D space for problems of up to billions of points.