Login New user?  
01-Applied Mathematics & Information Sciences
An International Journal


Volumes > Volume 9 > No. 2


Monte Carlo Simplification Model for Traveling Salesman Problem

PP: 721-727
Dong WANG, Dong-mei LIN,
Traveling Salesman Problem (TSP) is one of classical NP-hard problems in the field of combinatorial optimization. It is because of the problem complexity that almost all of the accurate computing algorithm could not find the global optimal solution (GOS) in a reasonable time. The complexity is characterized by the large number of edges in the initial edge set of TSP. By analyzing the relationship between GOS and high-quality local optimal solutions, it is found that the edge union set of some local optimal solutions could include most even all edges of GOS, and that their edge intersection could fix partial edges of GOS with high probability. The method reducing the initial edge set of TSP is established based on the probability statistic principle. The search space in which to solve the problem is cut down greatly, and the edge quantity in the new edge set is about twice times of the problem scale. Accureate algorithm can find GOS with high probability for TSPs whose scale are up to 200 nodes based on the simplified initial edge set. The method could be applied to many kinds of algorithms also used for solving TSP.

  Home   About us   News   Journals   Conferences Contact us Copyright naturalspublishing.com. All Rights Reserved