旅行商问题(Travelling Salesman Problem)是典型的组合优化问题，可以应用在诸多领域，它的特点是问题容易描述却难于求解。随着问题规模的扩大，该问题对求解质量和求解速度都提出了更高的要求，因此寻求一种适合大规模并行且具有智能优化特征的算法具有重大的现实意义。目前，随着并行计算技术的发展，利用高速网络将几台普通的PC机或工作站连接起来，搭建高性价比的机群系统，求解大规模问题提供了一种途径。　　 蚂蚁算法具有正反馈和隐并行性等特点，是求解旅行商问题的理想算法。论文首先利用基本蚂蚁算法求解旅行商问题，针对算法在求解过程中，存在搜索时间长、容易陷入局部最优解等缺陷，对蚂蚁算法进行了改进。针对蚂蚁算法搜索时间长的缺陷，引入了局部搜索的模拟退火算法，生成初始信息素分布，加快算法的收敛速度；针对早熟停滞现象，采用信息量动态加权的方法，控制信息素对算法的引导作用，增加解空间的多样性。接下来，论文重点分析了蚂蚁算法并行实现的可行性，在机群环境下，基于消息传递机制的MPI(Message Passing Interface)并行编程，实现了用并行蚂蚁算法求解大规模旅行商问题。　　 论文最后在机群环境下，对用并行蚂蚁算法求解旅行商问题进行了测试，分析比较了用蚂蚁算法和改进蚂蚁算法串行和并行实现对求解大规模旅行商问题的求解质量和求解速度的差异。并对两种算法的并行实现进行了横向比较。根据理论研究和实验测试结果证明，利用机群系统实现并行算法求解旅行商问题是可行的，并且可以取得相对串行计算较优的效果。