A New Heuristic Algorithm Based on Christofides Algorithm and Nearby Measures for TSP Problem

In order to solve the NP hard problem of TSP problem, this paper proposes the C-N-GA (Christofides Algorithm& Nearby Measures & Genetic Algorithm) algorithm that combines the Christofides algorithm and Near Measures. This algorithm can provide better gene initialization and real-time evaluation of the quality of exchanged genes using Nearby Measures through the Christofides algorithm, improving the effectiveness of fast convergence. By conducting experiments on six TSPLIB datasets of different scales, it has been proven that under the same number of iterations, the C-N-GA algorithm has faster convergence and better accuracy compared to classical algorithms, and can obtain better global solutions.