（Symmetric-MTSP）和非对称模型（Asymmetric-MTSP）[6]。论文网

多旅行商问题是对 TSP 问题的推广。由于具有较强的实际背景，在组合最优化问题中非 常常见。用 MTSP 可以对许多实际的问题进行描述。例如，印刷过程中的调度问题[7]；人员 调度问题[9]；校车行驶路径问题[11]；访谈调度问题[12]；航路规划[13]；钢铁企业的板坯轧制规 划[14]。Betkas 对多旅行商问题的描述和求解方法有了很大的进展[15][16]。

以往学者们对于多旅行商问题的求解研究拓展比较少，局限于它的原始的定义。即使所 有旅行商行走路径总和最小最为研究问题的标准。而相对而言，求所有旅行商的路径最大值 的问题中，最小值的问题的研究却很冷门。本文提出了矩阵解码方法。用遗传算法来优化针 对所有旅行商旅行走过的路程的最大值，使其最小化的 MTSP 一类课题。这种方法对于求解 距离对称和非对称的多旅行商问题有很大帮助。本文针对距离非对称的多旅行商问题做深入 学习。并对其不同的交叉算子性能进行了详细对比。

在实际问题中，我们根据要实际情况做出调整。限制单个旅行商的费用（或路程）来优 化 [8][10]。因此，对所有此类 MTSP 问题进行研究具有实际意义。本文要解决的 MTSP 问题的 特点为最大路程最小。并且距离对称或者非对称的。本文提出了矩阵解码方法，而且用遗传 算法进行优化。从而确定每个城市被那个旅行商访问过。以及每个旅行商的在城市间的行走 具体路线。最终求解出一个最优的旅行商访问路线。使得在所有旅行商行完成规定的访问后， 路程的最大值最小。

美国 Michigan 大学的 Holland 教授所提出了遗传算法[17](Genetic Algorism, GA）。这种方 法能有效求解这类组合优化难题。这种算法的核心来自于达尔文进化论和门德尔松遗传学说

[18][19]。它模拟生物进化过程。从而可以从非常庞大的搜索空间中，筛选出相对较优秀的解。

因此遗传算法非常高效。而且具有强鲁棒性[20]。所以，遗传算法在求解旅行商问题和多旅行 商问题中广受欢迎，而且可靠简单。目前，用遗传算法求解多旅行商的问题时。大部分都是 距离对称的多旅行商问题。通常使用附加虚拟节点城市的方法。这样就可以将多旅行商问题 化简为旅行商问题。

1。1 多旅行商问题简介

“旅行商问题”又可以称为“旅行推销员问题”。是指一名推销员要拜访多个指定的地点， 并且在找到在每个预定的地点之后，再回到起点。最后使得所有路径之和最短问题。

从字面上，对旅行商问题可以解释为：有一个推销员要到 n 个城市运送货物。他要经过 所有城市，且所有路程之和最短。

旅行商问题由来已久，其最早的记载可以追溯到 1759 年。欧拉提出了的“骑士周游问题”。 寻求一条贯穿棋盘中的全部方格的路线。并且路径是环路，在每个方格只能经过一次。

旅行商问题的规则虽然简单，但是随着地点增多之后求解却越来越难。以 40 个地点为例。 如果先列举所有经过的路径，再确定其中的最短行程。那么我们要列举的总的路线之大，很 难精确的描述出来。这么多年来全世界的学者都在全力研究，希望找到一个高效的算法来解 决上述问题。TSP 问题可以应用物流配送公司。假设某公司送 n 个人订的货，要使速度最快， 即路线最短，怎样确定这条路线，如图 1。1 所示。

图 1。1 旅行商问题图示

枚举法求解多旅行商问题最为简单[21]。枚举法的解集具有多维、多极值的特点，并且解 空间可以无限大。并且列举的空间包含 n 个点的所有的排列，排列种类为（n-1）！。具体地说， 我们可以把 TSP 问题的解集看作是一个巨大的山地。其中各个山的海拔高度就是所研究的 TSP 问题的解。要研究 TSP 问题，就像是是在这个巨大的地形中不断攀登来寻找山谷或者山 峰。