瓶颈TSP下界快速算法

A Quick Algorithm for Calculating the Lower Bound of Bottleneck Traveling Salesman Problem

瓶颈TSP是网络设计和优化中的一个NP难题,在数学推导和证明的基础上,给出了一个求解对称型瓶颈TSP问题下界的快速算法,利用该算法求解了TSP问题标准库中部分对称型问题,给出了计算结果并与标准问题库中已知的最好解进行了比较。

Finding the Bottleneck Traveling Salesman Problem （BTSP） tour in a given graph is a NP-hard problem which is important in network design and combinatorial optimization. Based on mathematical inference and proof, a quick algorithm for calculating the lower bound of symmetric bottleneck is proposed Travelling Salesman Problem is proposed. Series of numerical examples of BTSP from TSBLIB are tested and the computational results of the algorithm are compared with the best-known solutions published.