遗传算法(GA)是引入自然选择和进化机制发展起来的全局概率搜索算法。正像达尔文所说的：“自然界中能够生存下来的物种不是那些最聪明的，也不是那些最强壮的，而是那些最能适应环境变化的物种”，遗传算法正是基于这一思想发展起来的。问题从自然中来，还要到自然中去寻找答案，遗传算法是一种智能算法，而且具有本质并行性的特点，他能够自组织、自适应和自学习，尤其适合于解决大规模复杂问题，而且已经有了很成功的应用。 旅行商问题(TSP)是图论中一个很著名的问题，也是计算机领域和数学领域的经典难题之一。问题描述为在给定城市中，找到一条访问所有城市一次且仅一次的最短回路。而动态TSP(DTSP)比一般的TSP更难，因为在DTSP中城市的位置是随着时间的变化而变化的。 随着计算环境的改变，从集中式计算到分布式计算再到移动计算，万维网服务、点对点系统以及网格计算的融合为互联网分布计算和从最近AD-hot网络到星际间分布式系统范围的移动计算应用提供了基础。最近，例如有线无线融合、轻巧性、大范围和微移动性、超容错性、互操作性和不可见性等一些新的特点被加入到了世界范围的通信和计算中，所有的这些都可以抽象为DTSP模型。 自从TSP被提出的两个半世纪以来，还没有人能够解决这个问题，由此可见求解TSP是困难的，但是DTSP比 TSP 还要难。实际上动态 TSP 是一个动态双目标优化问题，即求解质量与响应时间均要最小化，但是这两个目标之间是彼此矛盾的。目前已经有许多求解静态TSP的算法，但是对于动态TSP他们的效率就会下降，甚至根本起不到作用。而遗传算法是比较适合解决动态TSP的。 在本文中，将在三维空间里用遗传算法加上一些新的遗传算子如：动态种群初始化算法、路径区段优化算子、启发式变异算子以及改进的Inver-over算子和一些演化策略，如：杂交、变异串并行的混合控制策略来求解动态TSP；而且还引入了基因库的思想，大大缩小了搜索空间，提高了算法的搜索效率。实验数据结果表明，应用这些新算子和演化策略，可以得到令人满意的结果。而且我们的算法在动态的环境中能够较成功地获得近似最优解，证明了该算法的正确性和有效性。