The Frequency Graph for the Traveling Salesman Problem

Authors: Y. Wang

Abstract:

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.

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

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1058041

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.