组合优化是运筹学的重要分支，主要通过对数学方法的研究寻找离散事件的最优排序、分类或筛选等。大多数这类问题通常在多项式时间里无法求解，属于NP完全问题。随着问题规模的扩大，问题空间呈现组合爆炸特征，无法用常规的方法求解。旅行商问题(TSP)就是一个经典的组合优化问题，属于NP完全问题，其中，现实旅行商问题更具有普遍意义。 本文首先介绍了一般旅行商问题和现实旅行商的相互关系，给出了由现实旅行商问题转化成一般旅行商问题的方法。其次，分别介绍了应用回溯法、分支定界法和动态规划法等完全算法求解旅行商问题的一般步骤，并且对各种算法做了分析比较。接下来，文章研究了应用蚁群算法、模拟退火算法解决旅行商问题，并且给出了模拟退火蚁群混合算法求解旅行商问题的主要流程，分析了各种算法的优劣。最后，本文重点分析了蚁群算法和模拟退火算法并行实现的可行性，研究了基于Windows和MPI的PC机群实验环境下蚁群算法、模拟退火算法以及混合算法的并行实现。利用建立的平台，对并行算法进行了测试，比较了并行算法和传统串行算法耗时的差异。同时，也比较了在并行算法设计中网络通信(消息传递)因素对并行算法效果的影响。最后，根据理论研究和实际测试的结果，总结了利用PC机群系统实现并行算法来求解旅行商问题的可行性，得出了关于并行效率等方面的一些有意义的结论。