A Heuristic Algorithm to Compute a Subgraph for TSP Based on Frequency Quadrilaterals. Issue 1 (August 2021)

• Record Type: Journal Article
• Authors: Deng, Qirong; Wang, Yong; Chen, Liping
• Is Part Of: Journal of physics. Volume 1995:Issue 1(2021)
• Publication Date: 2021-08
• Subjects: Traveling salesman problem -- Frequency graph -- Frequency Quadrilateral -- Heuristic algorithm -- Subgraph; Physics -- Congresses; 530.5
• DOI: 10.1088/1742-6596/1995/1/012041
• Languages: English
• ISSNs: 1742-6588

Abstract

Abstract: A heuristic algorithm was presented to compute certain subgraphs for symmetric traveling salesman problem using frequency quadrilaterals. If we choose a set of frequency quadrilaterals containing an edge to compute the frequency for it, the frequency of an edge contained within the optimal Hamiltonian cycle approaches an extreme value as the city number is big enough. A heuristic algorithm was designed to compute a frequency graph with randomly selected frequency quadrilaterals. A subgraph containing the optimal solution was computed according to a given frequency threshold. The experimental results illustrated that in certain instances for Euclidean TSP with scale above 1000, the number of edges in complete graph is reduced by more than 30 times. Moreover, the bigger the number of frequency quadrilaterals is used, the higher the frequency threshold is and the smaller the number of edges in the subgraphs is kept.