A dynamic optimization algorithm of Traveling Salesman Problem based on construction of greed circuit
Hongbo Li, Ma Wenjun, Jun Chen · 2008
This new algorithm was composed of four phases in turn, that is, construction of the initial circuit path based on the shortest edge first, iterative decreases of individual point, iterative decreases of individual edge and iterative decreases of multiple edges. For convenience and simplicity of computation, the most appropriate data structure was introduced. Being tested by three instances in TSPLIB shows that some current known best solutions are able to be largely decreased by the new algorithm, at the same time, their corresponding circuit path are also given. The time complexity of the new algorithm is O(max(n(logntimessume/Deltae+sumk/Deltak+ntimessumi,j/Deltai,j),n3)).