多旅行商问题模型

,l表示m个旅行商需访

弧(i,j)在线路上1令xij

0 弧(i,j)不在线路上模型表示如下：

RRminzdijxiji0j0Rxij1i0Rxij1j0X(xij)Sxij0或1j0,1,i0,1,,R

,Ri,j0,1,,R,l)表示旅行商经过对

式中：Rml1;dij为增广费用。若用cij(i,j1,应弧度(i,j)所花的费用，如时间、距离、花费等，那么给cij增加(m1)行和

(m1)列，每一新的行或列是cij的最后一行或列的复制，增广矩阵的其他元素

为无穷大，由此构成了增广费用dij。

一般MTSP中，旅行商访问l个城市必须满足以下2个条件。 条件1：从指定城市出发，对其他所有城市严格访问一次后返回原出发城市。 条件2：一条有效路径严格由m条非平凡子路径(Nontrivial Subtours)组成。所谓非平凡子路径是指该路径中除出发城市外，至少访问一个其他城市。

用遗传算法求解MTSP，可通过附加虚拟城市的方法把MTSP转化为TSP。将另外(m1)个旅行商理解为(m1)个虚拟城市，这(m1)个虚拟城市标号分别为l1,l2,,lm1,，它们与城市0具有相同的坐标(即相同位置)。在旅

行商访问路径中出现的每一个虚拟城市均表示旅行商返回出发城市，从而组成一个回路。每个回路表示MTSP中一个旅行商的旅行路径。需注意的是，为了避免出现平凡子路径，必须假设(m1)个虚拟城市到原点的距离为

cijM0(i,j0,l1,,lm1),M0为一无穷大的正数（即永远不能达到），

到其他各点距离与原点一致，这样遗传算法就不会出现0-0-0的途径。将源点0复制(m1)个，m个源点编号为0,l1,lm1,每一个同源点0一样与其他

点相连，而m个源点互相不连接，这样在结点集0,1,,l,l1,,lm1上，

可得到TSP线路，然后各源点合并成一个点。这样MTSP线路就分解成m个分线路。

初始化路径矩阵D确定实际问题参数对参数进行编码初始化群体X(0)进行代数加1适应度评估满足停止准则否遗传操作（选择、交叉、变异）是结束