摘要: 旅行商问题（TravelingSalesmanProblem，TSP）及扩展问题,如多旅行商问题（MultipleTravelingSalesmanProblem,MTSP）和不确定性多旅行商问题（UncertainMultipleTravelingSalesmanProblem,UMTSP）等，作为一种传统的组合优化问题，已被广泛地运用到... 展开 旅行商问题（TravelingSalesmanProblem，TSP）及扩展问题,如多旅行商问题（MultipleTravelingSalesmanProblem,MTSP）和不确定性多旅行商问题（UncertainMultipleTravelingSalesmanProblem,UMTSP）等，作为一种传统的组合优化问题，已被广泛地运用到各种实践场景，例如物流规划、任务调度、交通管理、航空运输等。采用适当的限制条件后，能够帮助人们更好地解决日常生活中的许多问题。由于问题规模增大，TSP及扩展问题很难通过使用精确方法得到较满意的解，研究人员更倾向于使用蚁群算法等智能优化算法来求解该问题，因为它能够在较短时间内得到质量较好的解。 本文的目的是探讨改进的蚁群算法求解TSP及扩展问题，具体的研究工作主要包括以下三个部分。 针对传统的蚁群算法中出现的收敛速度慢，在优化过程中容易陷入局部最优等问题，本文提出了一种新的混合蚁群算法（HybridAntColonyOptimization,HACO），该算法结合了改良圈策略和蚁群算法。在每次迭代中，该算法采用改良圈策略优化蚁群算法得到的解，使其转化为更优的解，并采用均匀设计方法寻找最佳参数组合。通过8个TSPLIB标准库中的问题实例进行比较试验，实验结果表明，本文算法在求解质量和效率方面均优于其他算法，表明了其在解决旅行商问题方面表现出较高的求解能力和更优的效率。 在前述研究的基础上提出了一种新的混合蚁群算法，即基于信息素均衡化操作的混合蚁群算法（BalancedHybridAntColonyOptimization,BHACO）。该算法在求解MTSP时，通过信息素均衡化操作，增强了算法跳出局部最优解的能力，以寻找更优解。通过TSPLIB标准库中的8个问题实例进行比较试验，实验结果表明，BHACO算法在求解MTSP时具有更好的性能，能够获得更优的解。 针对理想化的旅行商问题在实际环境中的不可靠性，本文研究了UMTSP，并在前述研究的基础上提出了一种带路况系数的混合蚁群算法（Road-ConditionBalancedHybridAntColonyOptimization，RBHACO）。该算法将路况系数视为权重因子，与原始信息素相乘，以考虑路径对信息素分布的影响。同时，使用路况系数来更新启发信息，更好地反映路径的信息。通过8个TSPLIB标准库中的问题实例进行比较试验，实验结果表明，本文提出的混合蚁群算法在求解UMTSP时能够求出更优的解。 收起