旅行商问题(Traveling Salesman Problem，简称TSP问题)是组合数学中一个古老而又困难的问题。动态多目标TSP问题则是近年提出的在TSP问题上发展起来的新问题，它既有动态优化问题的特征，问题环境在时刻变化；又有多目标优化问题的特征，往往具有多个不能相互比较优劣的解同时存在，形成一个解空间。目前国际上只有一些对动态TSP问题或多目标TSP问题的研究，而对动态多目标TSP问题的研究几乎处于空白阶段，至今还没有见到有提出具体解法和实验结果的论文。因此研究动态多目标TSP问题的解法具有重大的开创性意义。鉴于概念上的空白，本文结合动态TSP问题和多目标TSP问题的概念，提出了动态多目标TSP问题的概念。本文在LKH算法的基础上，首次完整地提出一个求解动态多目标TSP问题的可行的算法——DMOLKH算法，而且在问题概念、算法可行性、算法性能等方面都做出了一定的分析。在求解动态多目标TSP问题的算法研究领域上踏出了重要的第一步。在DMOLKH算法中，包含以下几点核心思想：●简化候选集的建立，节省宝贵的时间进行更多的搜索。实验表明，此做法可提高搜索效果，问题规模越大，效果越明显。●建立混合候选集。实验表明混合候选集能包含绝大部分解集中路径上的边，从而能够最大限度地缩小搜索空间，在保证搜索质量的前提下获得较快的搜索速度。●动态调整候选集。经过动态调整，使混合候选集最终包含解集中所有路径上的边，保证了搜索质量。●每次采样后，以采样前得到的解／解集作为初始解／解集，充分利用了动态变化的连续性来提高搜索效率。●取消LKH算法中不搜索共有边的策略。对于动态多目标TSP问题，该策略对搜索效率只有极小的价值，却大大增加了运行时间。●搜索目标以“非劣化”方式进行，以“非劣化”代替LKH算法中的“优化”搜索方式，保证动态多目标TSP问题能找到尽可能全面的解集。●提出加速搜索算子，可在不损失短时间搜索效果的基础上提高搜索速度。以KroAB10、KroAB20和KroAB30作为测试问题来检验算法性能，所有城市位置每0.5秒变化一次，移动速度为50／秒，移动方向在开始计算时生成，并且在达到指定边界时随机改变。每个问题取10个采样结果，以发现率和有效率的统计结果作为评价指标。实验结果显示，对于两个目标10个城市的动态多目标TSP问题，能找到Pareto解集中100％的元素；对于两个目标20个城市，能找到69.2％的元素；对于两个目标30个城市，则有9.1％。总体来说，实验结果还是令人满意的。