The Frequency Graph for the Traveling Salesman Problem

Traveling salesman problem (TSP) is hard to resolve when the number of cities and routes become large. The frequency graph is constructed to tackle the problem. A frequency graph maintains the topological relationships of the original weighted graph. The numbers on the edges are the frequencies of the edges emulated from the local optimal Hamiltonian paths. The simplest kind of local optimal Hamiltonian paths are computed based on the four vertices and three lines inequality. The search algorithm is given to find the optimal Hamiltonian circuit based on the frequency graph. The experiments show that the method can find the optimal Hamiltonian circuit within several trials.

Authors:

• Y. Wang

Keywords:

• Traveling salesman problem
• frequency graph
• local optimal Hamiltonian path
• four vertices and three lines inequality.

References:

[1] A. Rodríguez, and R. Ruiz, "The effect of the asymmetry of road
transportation networks on the traveling salesman problem," Computers
& Operations Research, Vol.39, pp.1566-1576, 2012.
[2] B.W. Douglas, Introduction to graph theory, Section Edition. Beijing:
Pearson Education Asia Limited and China Machine Press, 2006,
pp.75-76,
[3] L. Gouveia, S. Voβ, "A classification of formulations for the
(time-dependent) traveling salesman problem," European Journal of
Operational Research, Vol.83, pp.69-82, 1995.
[4] B. Bontoux, C. Artigues and D. Feillet, "A Memetic Algorithm with a
large neighborhood crossover operator for the Generalized Traveling
Salesman Problem," Computers & Operations Research, Vol.37,
pp.1844-1852, 2010.
[5] K. Helsgaun, "An effective implementation of the Lin-Kernighan
traveling salesman heuristic," Available:
www2.iwr.uni-heidelberg.de/groups/comopt/ software/TSPLIB95/tsp/,
May, 2012.
[6] D. S. Johnson, L. A. McGeoch, "The Traveling Salesman Problem and Its
Variations," Combinatorial Optimization, Vol.12, pp. 445-487, 2004.
[7] P.M. Binder, "Frustration in Complexity," Science, Vol.320, pp.322,
APRIL 2008.
[8] H. Ghaziri, and I. H. Osman, "A neural network algorithm for the
traveling salesman problem with backhauls," Computers & Industrial
Engineering, Vol.44, pp.267-281, 2003.
[9] Y. H. Liu, "Different initial solution generators in genetic algorithms for
solving the probabilistic traveling salesman problem," Applied
Mathematics and Computation, Vol.216, pp.125-137, 2010.
[10] S. Iordache, "Consultant-Guided Search-A New Metaheuristic for
Combinatorial Optimization Problems," Proceedings of the 12th annual
conference companion on Genetic and evolutionary computation
(GECCO-10), Portland, Oregon, July 7-11, 2010, pp.225-232.
[11] C. Seife, "What Are the Limits of Conventional Computing," Science,
Vol.309, pp.96, JULY 2005.
[12] V. Deineko, B. Klinz, G. Woeginger, "Four point conditions and
exponential neighborhoods for symmetric TSP," Proceedings of the
seventeenth annual ACM-SIAM symposium on Discrete algorithm (SODA
2006), Miami, January 22-26, 2006, pp.544-553.