旅行商问题的近似求解算法

An Approximate Algorithm for Solving Traveling Salesman Problem

在最近邻法、k-变换策略和贪心算法的基础上,尝试设计效率较高的产生旅行商问题较优可行解的方法。将3变换邻域分成两种结构(称为3_1和3_2变换邻域)考虑,设计以下算法:利用最近邻法产生初始当前最优解;然后依次在当前最优解的3_2、3_1、2变换邻域中寻找更优的局部最优解成为当前最优解,直到结果没有改进。利用算法对一些经典的实例进行实验,依次将每个城市作为出发地,在多项式时间O(n4)得到的最优解与给定的最优解相对误差在1%内。

Based on nearest neighbor（NN）algorithm,k-OPT,and greedy algorithm,an approximate algorithm for solving traveling salesman problem（TSP） is proposed.According to the topological structure of 3-local domain,we define＂3_1-local domain＂and ＂3_2-local domain＂,and design the follwoing algorithm,from which the initial current optimal solution with NN is designed.Then we replace the current optimal solution with the better one which is the local optimal solution of its 3_2-local domain,3_1-local domain,and 2-local domain in turn,and repeat the procedure above until no better one can be found.The experiment results shou that this algorithm is efficient.The relative differences between The valuse of optimal solutions obtained from this algorithm in polynomial time O（n^4）and the given ones are less than 1% for many classical cases.