Deep clustering of the traveling salesman problem to parallelize its solution
提出一种通过深度聚类将大型旅行商问题分解为可并行求解的开放回路子问题的方法，利用遗传算法求解，并通过质心或蛇形方式聚合子路径得到近似解，显著提升计算速度。
A method of heuristically solving large traveling salesman problems is suggested, where a dramatic computational speedup is guaranteed. A specific genetic algorithm is the solver. The initial problem is broken into a set of open-loop subproblems by clustering the nodes. First, the nodes are broken into just two clusters. If these open-loop subproblems are tractable and can be solved within reasonable amount of time, no further clustering is needed. Otherwise, the clustering pattern is applied once again, and each of the previous clusters is broken into just two clusters. Thus, the clusters evolve being re-clustered deeper until the size of the respective open-loop subproblems becomes sufficiently small. Therefore, the number of clusters is a power of 2 depending on the number of available processors and available memory with the maximum possible array. The cluster open-loop subproblems are quickly solved in any order and then their solutions as open-loop subroutes are aggregated into the close-loop route as an approximate solution of the initial problem. By the centroid-based approach, the open-loop subroutes are aggregated by the shortest closed loop route passing through the centroids of the clusters. The aggregation route is found as the respective supplementary traveling salesman problem solution. By the serpentine-based approach, the open-loop subroutes are aggregated by a symmetric rectangular close-loop serpentine passing through the rectangular lattice cell centers approximately corresponding to the centroids.