基于分段多方位近邻算法求解TSP问题

Multi segment and multi orientation nearst neighbor solving TSP

在利用构造法求解欧氏平面上的TSP问题时,先构造1个只包含4个结点(左上角结点-右上角结点-右下角结点-左下角结点-左上角结点)的简单的环路,这个环路将求解路径分成4段.每个序列每一步都是从当前结点出发,在4个方位近邻结点中按照距离与方位的因素综合考虑选择一个较为合理的近邻结点作为下一步的目标结点,直至每个序列都到达其终点,然后将剩余的结点加入其中的某个序列,最后将4个序列首尾相接形成环路.实验表明,它将经典的最近邻算法的求解结果的精度提高了一个数量级,在许多例子中NN求解长度是它的2～28倍,它的长解长度与最优解的比小于2.8,总体上来说它的性能与最近插入法的性能相当接近.图8,表1,参6.

In constructional algorithms of solving TSP, NN＇s solving process is simplest, but its performance is worst. An improved NN algorithm for solving TSP （in Euclid） was proposesed, at first four comer citys was found out, a simply tour was gained only include four corner city, tour＇order was left_up city-right_up city-right_down city-left_down city-lefLup city. Each sequence was started off current city at every step,from tetrad nearst neighbor city selected a city in reason as object city, their distance and direction was concered at same time, up to each sequence was arrived at their end city. Then those left city was thinked about, insert them in right sequence, at last four sequence was connected in tail and head,form final tour. Experiment result indicates this algorithm is just double of the best tour, its capability is algorithm greatly improve the NN＇S result,the tour length of this clost to Nearst Insertion. 8figs., ltab., 6refs.