论文摘要
旅行商问题TSP（traveling salesman problem）是经典的NP-难解组合优化问题之一，在交通、网络、电路设计等方面有着广泛的应用背景。根据计算复杂性理论可知：对于NP-难解问题，除非P=NP，否则不存在多项式时间内得到最优解的精确算法。因此对于大规模的实例，求解它的高效启发式算法设计一直是计算机科学研究的热点。骨架、脂肪等作为描述TSP结构特征的工具，对启发式算法设计有着重要的意义，已经成为目前研究TSP问题的主要研究领域。本文首先对TSP问题的研究现状进行了介绍和分析，指出在TSP结构特征工具的研究上的不足之处。通过构造偏移实例的技巧，分析了TSP问题的脂肪计算复杂性，并首次给出了获取TSP的脂肪是NP-难解的理论证明，即在P≠NP的假设下，不存在算法可以在多项式时间内获得完整脂肪。在此基础上，通过分析TSP问题局部最优解与脂肪的关系，给出了求解TSP问题新的元启发式算法——动态候选集搜索算法。利用该算法，本文改进了目前求解TSP问题最好的算法之一的LKH。然后，本文在分析局部最优解与全局最优解关系的基础上，提出一种新的描述TSP结构特征工具——扰边。通过假设可以构造多项式时间内的算法求得扰边，进而引出可以在多项式时间内求的TSP问题的最优解，用反证法给出了求解扰边是NP-难的理论证明。通过试验分析，发现通过对局部最优解之间的相互操作，可以求得有效模拟扰边的“近似扰边”。并在此基础上，提出了基于近似扰边的元启发式算法框架MAFBOAD（Meta-Heuristic Algorithm Frame Based On Approximate Disturb-edge）。最后同样在LKH上对算法框架进行了实现。