基于四边形最优圈内最短路径的旅行商问题割边方法

Cutting Edge Method for Traveling Salesman Problem Based on the Shortest Paths in Optimal Cycles of Quadrilaterals

随着旅行商问题规模的增长,完全图上最优解的搜索空间呈指数增长。为了减小最优解的搜索空间,提出一种针对旅行商问题的割边算法。推导出四边形最优圈内的最短路径包含一般边与最优哈密顿圈边的不同概率,采用一定数量的四边形最优圈内的最短路径计算边频率,根据所有边的平均边频率割边,基于建立的二项分布模型推导出最优哈密顿圈内边的保留概率。任给一个完全图,割边算法有4个步骤:1)随机选取包含每条边的若干个四边形;2)采用所选四边形最优圈内的最短路径计算各边的边频率;3)步删除5/6条最小边频率的边;4)对度数小于2的节点进行添边操作。计算实验表明:保留边数为完全图上边数量的1/6左右,采用精确算法求解割边后旅行商问题的计算时间也有所减少。

With the expansion of traveling salesman problem,the search space for optimal solution on the complete graph increases exponentially.The cutting edge algorithm is proposed to reduce the search space of the optimal solution for the traveling salesman problem.It proves that the probability that an optimal Hamiltonian cycle edge contained in the shortest paths in the optimal cycles of quadrilaterals is different from that for a common edge.A number of shortest paths in the optimal cycles of quadrilaterals are selected to compute the edge frequency of edges.As the edges are cut according to the average edge frequency of all edges,the retention probability that an optimal Hamiltonian cycle edge is derived based on the constructed binomial distributions.Given K;of a traveling salesman problem,there are four steps for eliminating edges.Firstly,a finite number of quadrilaterals containing each edge are chosen.Secondly,the shortest path in the optimal cycle of every selected quadrilateral is used to compute the edge frequency.Thirdly,5/6 of edges having the smallest edge frequencies are cut.In the last step,some edges are added for vertices of degree below 2 according to the edge frequency.Experiments illustrate that the preserved edges occupy 1/6 of the total edges.Moreover,the computation time of the exact algorithms for the traveling salesman problem on the remaining graphs is reduced to some extent.