赵新超，郭赛

多旅行商问题(multiple traveling salesman problem，MTSP)可直观描述为一个旅行商团队要分头遍历若干个城市，每个城市至少被一个旅行商访问一次且只访问一次，如何安排m(大于1)位旅行商遍历n(大于m)个城市，使得总的访问行程最小[1]。该问题最常见的应用领域是车间调度领域，在生产线上的作业调度通常被建模为一个旅行商问题(traveling salesman problem，TSP)。如果生产经营扩展到有多条平行线，工作可以分配，这个问题可以建模为一个多旅行商MTSP[2]；另一个经常被建模为多旅行商问题的就是车辆调度问题(VSP)[3]。车辆调度问题是指对一些车辆进行调度，所有的车辆离开并回到原地点，使得每个地方只能而且必须被访问一次。

由于多旅行商问题的复杂性，必须根据实际问题的大小采用启发式解决方案[4]。遗传算法(genetic algorithms，GA)[5]是一种基于生物自然选择和基因遗传学原理的高效并行、随机全局优化搜索算法。Keshavarz等[6]学者发现遗传算法对调度问题有很强的适应性，MTSP有效的遗传算子也激发了研究者的极大兴趣；张永库等[7]研究了改进的遗传算法在模糊聚类中的表现；Katayama等[8]提出的混合变异遗传算法在旅行商问题中的应用提高了遗传算法解决旅行商问题的性能。多旅行商问题在实际问题中有很广泛的应用。Huang等[9]研究了多旅行推销员问题在热轧规划中的应用；江贺等[10]研究了近年来出现的新NP-难解问题，即黑白旅行商问题(BWTSP)，给出了遗传算法解决问题的一种新思想；Trigui等[11]提出一种解决多机器人系统多目标多旅行推销员问题的模糊逻辑方法。……