旅行商问题(Traveling Salesman Problem,TSP)是一个经典的组合优化问题,一直受到计算机科学和运筹学界广泛关注,在现代物流运输领域中发挥了重要的作用,具有重要的实际意义。本文研究了TSP文献中四个经典的旅行商扩展问题,即带酒店选择的旅行商问题(TSPHS)、带先进先出规则的取货派货旅行商问题(TSPPDF)、多商品取货派货旅行商问题(m-PDTSP)和簇旅行商问题(CTSP),为它们分别设计了高效的元启发式算法,与文献中最好的算法进行对比,来评价所提出算法的性能和效率,并对提出算法的一些重要组成部分进行分析和讨论。本文的主要贡献包括:(1)针对TSPHS问题,本文提出了一个高效的基于动态规划的混合进化算法(HEA)。该算法包括三个重要组成部分:动态规划、三个交叉算子和两阶段的局部搜索。本文提出的动态规划方法为一个给定顾客旅行序列寻找最优的住宿酒店序列,将传统的TSP解转化为TSPHS解。同时,HEA算法使用三个专门的交叉算子,用于生成高质量的后代个体,在每次进化中,算法会自适应地选择合适的交叉算子去产生子代解。此外,HEA算法使用基于合法解和非法解同时搜索的两阶段局部搜索优化程序,有效地探索搜索空间。通过对文献中131个基准算例进行实验,并且与目前文献中求解该问题最好的启发式算法作比较,对提出的HEA算法进行评估。实验结果表示,所提出的HEA算法具有很大的优势和很强的竞争力。具体表现在,它有效的改进当前基准算例中24个大算例的历史最好解,匹配了104个算例的历史最好解。(2)针对TSPPDF问题,本文提出一种新的带多次重启策略的迭代搜索算法(MIS)。该算法的新颖性在于一个新的基于阈值的探索阶段和一个多次重启策略被嵌入到迭代局部搜索框架内。在基于阈值的探索阶段,一个劣质解被接受取代当前解,当且仅当它的目标值不超过给定阈值。阈值在搜索过程中动态地、自适应地调整大小。同时,一旦搜索被认为陷入深度局部最优陷阱,就为当前搜索生成新的搜索起点。从计算结果来看,MIS算法在42个基准算例上表现出非常大的竞争力。具体表现在:与文献中五个最近的求解TSPPDF问题最好的启发式算法比较,它能够报告20个算例新的最好解,也就是改进了已知的历史最好解,并且能够匹配其余22个算例的历史最好解。(3)针对m-PDTSP问题,本文提出了一种高效的基于种群的随机禁忌阈值搜索算法(PRTTA)。在该算法中,随机禁忌阈值搜索程序在一个混合阶段和一个更新阶段上交替进行搜索,用于局部优化,以达到搜索的集中性。高质量解构成的种群为随机禁忌阈值搜索提供多个搜索起点,以达到搜索的多样性。从计算结果的角度来看,PRTTA算法在文献中240个小算例和108个大算例上展示了非常大的竞争力。具体表现在:与文献中精确算法相比,在已知最优解的206个小算例中,它报告了204个最优解,并且对未知最优解的34个算例,它报告了30个新的最好解。与文献中最好的启发式算法相比,PRTTA算法改进了108个大算例中97个已知的最好解。(4)为了高效地求解CTSP问题,本文首先将CTSP问题转换为一个TSP问题,然后提出一个高效的混合进化算法来求解这个转化后的TSP问题。通过对文献中给出的基准算例进行大量的实验对比测试,结果表明,所提出的算法从解的质量上和算法的运行时间上都要远远优于文献中所有的启发式算法。特别是,它几乎为所有的中大型算例报告了新的最好解,同时为剩余的小算例报告了最优解。并且,在大部分算例上,所提出的算法比文献中最好的启发式算法快约3至10倍。以上研究成果表明,本文提出的这些优化算法分别是求解这些旅行商问题最高效的启发式算法,都超过了文献中最好的启发式算法。在今后的研究中,我们尝试应用这些算法去求解其它相关的旅行商问题或者车辆路径问题。