A Heuristic Algorithm to Compute a Subgraph for TSP Based on Frequency Quadrilaterals. Issue 1 (August 2021) - Deng, Qirong; Wang, Yong; Chen, Liping
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.