Implementation Of The Visual Process Software For Solving TSP Based On Modified Lin-Kernighan Algorithm

TSP is a typical problem of its genre: combinatorial optimization, furthermore, TSP is the original form of many realistic problems. So, that taking a thorough and broad study on TSP has important theory value and practical value. This paper describes an effective Visual Process Software For Solving TSP which's construction is based on the Modified Lin-Kernighan Algorithm Engine. Subjects as follows are made a thorough study.For the first time, the development of the TSP process software is considered as a center research problem. In fact, algorithm's design and software's construction are the two dominating facets that determine the final success. Therefore, it's necessary to give emphasis on the both sides.The definition of the Visual Process Software For Solving TSP (VPS-TSP) is a research innovation. According to the definition, "Visual" consists of visualize of the standard problem create, visualize of the data display, and visualize of the result and the performance.At the first chapter, classic Lin-Kernighan algorithm is introduced, on which a comprehensive modification is made then. An important measure—a-nearness is used to produce the Candidate Set. Compared with the nearest neighbor measure, α-nearness brings out much better performance.Relationship between the program's detail and algorithm's performance is thought much of. It takes two separate chapters to introduce the design of algorithm's engine (by C language) and the construct of the VPS-TSP (by Visual C++). At the second chapter, according to the engine's general procedure, important heuristic operators are presented as the form of pseudo code in turn. And, the strategies for simplify the cost's calculate, store and lookup;producing initial tour;selecting suitable data structure, etc, are presented. At the third chapter, according to VPS-TSP's modularization, development of the Data Processing Module, Visualize Module and intergration of the Extended Module and the Algorithm Engineer are presented in details. In a word, the paper is a full guide for developing high quality TSP software.The test of VPS-TSP is impressive. At first, it can support many kind of TSP (include TSP, ATSP and HCP), and can find the best tour of TSPLIB's majority problems in little time (the largest problem has a dimension of 7397 points). Secondly, its Extended Module supports quickly creating TSP problem, its Map and Coordinate Module enable interacting operation between the user and the software.