论文部分内容阅读
作为组合优化中经典的NP-hard问题之一,旅行商问题(TSP)在实际生产中有广泛的应用,如物流路线规划、电路板印刷等。对该问题的研究不管是在实际应用中还是在科学研究中都有十分重大的意义。1992年Ejection Chain算法被提出,随后被证明在求解旅行商问题中和有名的Lin-Kernighan(LK)启发式算法一样高效。在本文中,我们着重研究了 Ejection Chain算法及其混合算法。我们对Ejection Chain算法进行了改进,并进行了大规模的算法性能实验测试。与其他研究仅仅关注算法实验最终结果不同,本文中使用多种时间维度来分析算法在整个运行过程中的状态。本文中的工作为以下四个方面:第一,我们研究了高效的Ejection Chain算法,并且在原始的Ejection Chain算法上进行了多项改进,比如针对Ejection Chain算法的特点设计了高效的数据存储结构,对根节点候选集合的大小进行探索实验,同时对Ejection Chain算法的终止条件策略进行了调整,得到改进的Ejection Chain算法在测试的110个实例求解全局最优解中,比原始Ejection Chain算法多解决了 28%的测试实例。第二,我们对Ejection Chain算法进行了大规模的实验测试,通过与LK局部搜索算法相比较,深入分析了 Ejection Chian算法性能。第三,由于局部搜索算法以及组合局部搜索算法(LS-LS混合算法)容易陷入局部最优,所以我们将交叉算子加入到组合局部搜索算法中得到混合交叉算子的组合搜索算法(LS-LS-X混合算法),其算法在110个测试实例求解最优解中比单一的局部搜索算法和组合搜索算法分别多解决41%和28%的实例。最后,我们将局部搜索算法和混合交叉算子的组合搜索算法与进化算法和基于种群的蚁群优化算法进行混合,得到的混合算法在时间限制为1小时,求解城市规模为85900的实例中,所得到的解与全局最优解仅仅相差4.85%。