以点0表示旅行商的出发城市，称为源点，点1,2丄，1表示m个旅行商需访
令
弧 (i,j) 不在线路上
问的城市。MTSP问题的数学模型可以表示为:
模型表示如下:
xij
弧(i,j)在线路上
min z
R i0 R
RR i0j0
dij xij
xij 1 j 0,1,L ,R
xij 1 i 0,1,L ,R j0
X (xij ) S xij 0或1 i, j 0,1,L ,R
式中：R m l 1;dij为增广费用。若用Cij (i,j 1,L ,1)表示旅行商经过对 应弧度(i, j)所花的费用，如时间、距离、花费等，那么给 q增加(m 1)行和 (m 1)列，每一新的行或列是 cij 的最后一行或列的复制，增广矩阵的其他元素 为无穷大，由此构成了增广费用 dij 。
一般MTSP中，旅行商访问I个城市必须满足以下2个条件。
条件 1：从指定城市出发， 对其他所有城市严格访问一次后返回原出发城市。 条件2： 一条有效路径严格由m条非平凡子路径(Nontrivial Subtours)组成。 所谓非平凡子路径是指该路径中除出发城市外，至少访问一个其他城市。
用遗传算法求解MTSP，可通过附加虚拟城市的方法把 MTSP转化为TSP。 将另外 (m 1)个旅行商理解为 (m 1)个虚拟城市，这 (m 1)个虚拟城市标号分 别为l 1,l 2,L ,l m 1,，它们与城市0具有相同的坐标(即相同位置)。在旅 行商访问路径中出现的每一个虚拟城市均表示旅行商返回出发城市， 从而组成一 个回路。每个回路表示MTSP中一个旅行商的旅行路径。需注意的是，为了避免 出现平凡子路径，必须假设 (m 1)个虚拟城市到原点的距离为
cij M0(i, j 0,l 1,L ,l m 1 ) , M 0为一无穷大的正数(即永远不能达到) ， 到其他
各点距离与原点一致，这样遗传算法就不会出现 0-0-0 的途径。将源点 0 复制(m 1)个，m个源点编号为0,1 1,L l m 1,每一个同源点0 —样与其他
点相连，而m个源点互相不连接，这样在结点集
0,1丄，1,1 1丄，1 m 1上,
可得到TSP线路，然后各源点合并成一个点。这样 线MTSP线路就分解成m个分 路。
初始化路径矩阵D 确定实际问题参数 对参数进仃编码 工 工 初始化群体X (0)
工 1 进行代数加
多旅行商问题模型
