Statistical analysis of frequency graph for traveling salesman problem

Article type: Research Article

Authors: Wang, Yong

Affiliations: School of Renewable Energy, North China Electric Power University, Beijing, China

Note: [] Corresponding author. Yong Wang, School of Renewable Energy, North China Electric Power University, 102206, Beijing, China. Tel.: +86 010 61772051; Fax: +86 010 61772234; E-mail: [email protected]

Abstract: Traveling salesman problem (TSP) is a typical of combinatorial optimization problem. Its objective is to find an optimal Hamiltonian circuit (OHC). It has been proven to be NP-complete. The frequency graph for TSP has been introduced in a previous paper. This article is the progressive research of the frequency graph for TSP. The probability of the edges is computed based on a frequency graph which is computed with a set of local optimal Hamiltonian paths. The bigger the probability of an edge, the more possible the edge belongs to the OHC. The value span of the probability of an edge in the OHC is derived and used to select the candidate edges to form the OHC. A variable m is noted as the number of the local optimal Hamiltonian paths with each edge. These optimal Hamiltonian paths are used to compute a frequency graph. The probability function of the edges in the OHC is derived and it is a geometric progression according to variable m. The general term formula of the probability of the edges in the OHC is simulated based on the experiments with the Euclidean TSP instances. It is used to evaluate the rightness of the generated OHC composed of the candidate edges.

Keywords: Traveling salesman problem, frequency graph, probability function, general term formula

DOI: 10.3233/IFS-141394

Journal: Journal of Intelligent & Fuzzy Systems, vol. 28, no. 3, pp. 1109-1118, 2015