TSP问题(Traveling Salesman Problem,TSP)是一个典型的组合优化问题,己经成为并仍将继续成为测试组合优化新算法的热点问题。在传统的TSP问题中,城市的规模以及城市之间的距离是固定不变的,但在实际应用中,问题的规模及费用向量矩阵常常是随着时间而动态变化的,称这类问题为动态TSP问题。为了给管理者提供正确的决策方案,算法必须根据实时信息在较短时间内给出满意解。对这类问题的研究,不仅可为各类动态组合优化问题提供一种理论上的参考,而且还具有广泛的实际应用价值。遗传算法作为一种自适应的全局优化概率搜索算法,具有简单通用、鲁棒性强、智能性及并行性等优点,已成功地应用于求解组合优化问题。本文采用改进的遗传算法对TSP问题进行求解,主要的研究工作和创新如下:1)对TSP问题进行了分析,建立了数学模型。融合当前的研究成果,对动态TSP提出了三种模型,分别从不同层面表现问题的动态性,并提出一种可以适应所有情形的统一的动态TSP问题模型;2)针对静态TSP问题,提出了一种双倍体编码方案,该方案集近邻关系和访问序列于一体,使得个体评价表现出多种性能,即增加了种群的多样性,同时又加快了种群的收敛速度,使遗传算法更具使用价值;3)在遗传算法理论方面,提出了“二八”种群控制策略,对种群的少部分个体进行控制,实现了种群的整体收敛,同时较好地保持了种群的多样性,减少了运行时间;提出了判官算子,提高了种群的收敛速度,达到了提高求解速度同时又保持种群多样性的双重功效。4)提出了一种两阶段反转映射遗传算法。该算法分为两阶段,在第一阶段主要使用反转交叉算法和个体竞争策略,运行到种群“稳定”态,以保证最优解的子串基本包含在当前的种群的个体之间,甚至是最优解本身,第二阶段主要运用映射算法,通过对种群中个体的映射修改,构造出最优解,从而完成遗传算法的求解。实验表明改进后的遗传算法,有较快的求解速度,具有一定的实用价值。5)针对动态TSP问题设计了嵌入式遗传算法,算法分为两层循环,外层循环主要适应环境的变化,根据时间间隔或其他约束条件,并将动态的TSP问题离散化为静态问题;内层主要是嵌入在当前环境下的遗传算法求解过程,主体是两阶段反转映射遗传算法。实验表明该算法对于动态TSP具有较好的求解效果。结论部分总结了全文主要工作及创新之处,分析了研究中的不足,展望了未来的研究方向。