Traveling salesman problem (TSP) is a typical combinatorial optimization problem. A heuristic model called frequency graph is introduced for TSP. It is computed with a set of optimal i-vertex paths (OP) in a weighted graph. The frequencies on the edges are enumerated from the set of OPs. The OPs have more intersections of edges with the optimal Hamiltonian cycle (OHC) than they do with the other Hamiltonian cycles. Thus, the frequencies of the OHC edges are generally bigger than those of most of the other edges. They are taken as the heuristic information instead of edges’ weights for TSP. The ant colony optimization is used to find an approximation or OHC based on the frequency graph. The solutions are compared with those using weighted graphs for certain TSP instances. The experimental results show that the frequency graph is better than weighted graph (WG) for most TSPs under the same preconditions.

Traveling salesman problem (TSP) is one of well-known discrete optimization problems. The genetic algorithm is improved with the mixed heuristics to resolve TSP. The first heuristics is the four vertices and three lines inequality, which is applied to the 4-vertex paths to generate the shorter Hamiltonian cycles (HC). The second local heuristics is executed to reverse the i-vertex paths with more than two vertices, which also generates the shorter HCs. It is necessary that the two heuristics coordinate with each other in the optimization process. The time complexity of the first and second heuristics are O(n) and O(n3), respectively. The two heuristics are merged into the original genetic algorithm. The computation results show that the improved genetic algorithm with the mixed heuristics can find better solutions than the original GA does under the same conditions.