遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。它的研究历史比较短,早期是一种试图解释自然系统中生物的复杂适应过程入手,模拟生物进化的机制来构造人工系统的模型。近年来世界范围形成的进化计算热潮,计算智能已作为人工智能研究的一个重要方向,以及后来的人工生命研究兴起,使遗传算法受到广泛的关注。鉴于遗传算法存在着收敛速度慢或易出现“早熟”现象,本文对遗传算法进行改进,针对TSP问题提出贪心3PM交叉算子,同时对模拟退火算法进行改进,并将改进后的两种算法相结合,形成一种基于3PM交叉算子的模拟退火遗传算法(GCBSAGA)。主要研究工作如下:首先介绍了遗传算法国内外的研究现状,以及现有的遗传算法与模拟退火算法相结合的现有情况。其次,在阐述遗传算法基本概念、原理、方法、步骤的基础上,针对巡回旅行商问题(TSP)提出一种基于3PM交叉算子的模拟退火遗传算法(GCBSAGA)。在新算法中,一方面,对遗传算法进行了改进,先改进了它的构架,再引入判断搜索效率的条件,一旦搜索效率下降,便终止遗传算法,这样便保留了遗传算法前期全局高效的搜索,屏弃了后期搜索能力低的毛病。然后又提出了一种新的交叉算子―—贪心3PM交叉算子,这种算子不但考虑到了城市位置的关系,更重要的是考虑到了城市之间边的关系。采用三个父代产生子代的方法,能够得到更优的边信息,而且采用双向轮转的方法,使子完全地继承了父代的边的信息。而且对产生的子代还进行退火选择,从而将温度这一概念加入到遗传算法中,这样使子代基本不会出现退化现象。通过实验也可以看出,贪心3PM交叉算子收敛速度非常快,搜索能力极高。另一方面,对模拟退火算法进行改进,它使用的初始解就是遗传算法结束后得到的全局较优解,即对全局较优解进行独立退火,这样使得原本盲目搜索的模拟退火算法固定在有希望的区域里搜索,大大提高了搜索效率。模拟退火算法使用的初始温度也是遗传算法结束后的温度,这样高温时使用遗传算法,发挥它高效的全局搜索能力,低温时使用模拟退火算法,发挥它强大的局部搜索能力。然后选用国际公认的TSP库的数据进行测试,找到了比TSP库提供的最优解更优的解,证明了新算法的有效性。最后把新算法运用到配送和回收一体化的车辆路径问题这一实际问题中,并且针对问题的特殊性加入了编码解码机制,通过实验和对比验证了GCBSAGA算法在解决此类问题时的高效性。