A Novel Approach for Traveling Salesman Problem Via Probe Machine

The Traveling Salesman Problem is a combinatorial optimization problem that seeks to find the shortest path visiting a set of locations, where each location is visited exactly once, and the path returns to the starting point. Using traditional computing model to solve Traveling Salesman Problem would face the issue of state explosion. This paper proposes a solving method based on the probe machine model, greatly accelerating the solving speed. By iteratively adding probes and performing probe operations in sequence, both optimal and feasible solutions for this problem can be obtained. We developed a solver PROBE4TSP and presented its framework and execution process. Through comparative experiments, we demonstrate that this method is faster than some classical solvers for small-scale Traveling Salesman Problems, especially fewer than thirty nodes.