Fast approximation of the traveling salesman problem shortest route by rectangular cell clustering pattern to parallelize solving

Abstract

A method of quickly obtaining an approximate solution to the traveling salesman problem (TSP) is suggested, where a dramatic computational speedup is guaranteed. The initial TSP is broken into open-loop TSPs by using a clustering method. The clustering method is based on either imposing a rectangular lattice on the nodes or dividing the dataset iteratively until the open-loop TSPs become sufficiently small. The open-loop TSPs are independent and so they can be solved in parallel without synchronization, whichever the solver is. Then the open-loop subroutes are assembled into an approximately shortest route of the initial TSP via the shortest connections. The assemblage pattern is a symmetric rectangular closed-loop serpentine. The iterative clustering can use the rectangular assembling approach as well. Alternatively, the iterative clustering can use the centroid TSP assembling approach, which requires solving a supplementary closed-loop TSP whose nodes are centroids of the open-loop-TSP clusters. Based on results of numerical simulation, it is ascertained that both the iterative clustering and rectangular cell clustering pattern are roughly equally accurate, but the latter is way more computationally efficient on squarish datasets. Fast approximation of the TSP shortest route serves as an upper bound. In addition, the route can be studied to find its bottlenecks, which subsequently are separated and another bunch of open-loop TSPs is approximately solved. For big-sized TSPs, where the balance of the accuracy loss and computational time is uncertain, the rectangular cell clustering pattern allows obtaining fast solution approximations on multitudinous non-synchronized parallel processor cores.