《（最新）多旅行商问题模型.》由会员分享，可在线阅读，更多相关《（最新）多旅行商问题模型.（2页珍藏版）》请在金锄头文库上搜索。
1、以点0表示旅行商的出发城市，称为源点，点1,2, 问的城市。MTSP问题的数学模型可以表示为： ,l表示m个旅行商需访 弧(i,j)在线路上1 令xij 0 弧(i,j)不在线路上 模型表示如下： RR minz d ij x ij i0 j0 R x ij 1 i0 R x ij 1 j0 X (x ij )S x ij 0或1 j 0,1, i 0,1, ,R ,R i, j 0,1,R 式中：R ml 1;d ij 为增广费用。若用c ij (i, j 1,l)表示旅行商经过对 应弧度(i, j)所花的费用，如时间、距离、花费等，那么给c ij 增加(m1)行和 (m1)列，每一新的行或
2、列是c ij 的最后一行或列的复制，增广矩阵的其他元素 为无穷大，由此构成了增广费用d ij 。 一般 MTSP 中，旅行商访问l个城市必须满足以下 2 个条件。 条件 1： 从指定城市出发， 对其他所有城市严格访问一次后返回原出发城市。 条件2：一条有效路径严格由m条非平凡子路径(Nontrivial Subtours) 组成。 所谓非平凡子路径是指该路径中除出发城市外，至少访问一个其他城市。 用遗传算法求解 MTSP，可通过附加虚拟城市的方法把 MTSP 转化为 TSP。 将另外(m1)个旅行商理解为(m1)个虚拟城市，这(m1)个虚拟城市标号分 别为l 1,l 2,l m1,，它们与城市
3、 0 具有相同的坐标(即相同位置)。在旅 行商访问路径中出现的每一个虚拟城市均表示旅行商返回出发城市， 从而组成一 个回路。每个回路表示 MTSP 中一个旅行商的旅行路径。需注意的是，为了避免 出现平凡子路径，必须假设(m1)个虚拟城市到原点的距离为 c ij M 0 (i, j 0,l 1,l m1),M 0 为一无穷大的正数（即永远不能达到）， 到其他各点距离与原点一致，这样遗传算法就不会出现0-0-0 的途径。将源点0 复制(m1)个，m个源点编号为0,l 1,l m1,每一个同源点 0 一样与其他 点相连，而m个源点互相不连接，这样在结点集0,1,l,l 1,l m1上， 可得到 TSP 线路，然后各源点合并成一个点。这样 MTSP 线路就分解成m个分 线路。 初始化路径矩阵D 确定实际问题参数 对参数进行编码 初始化群体X(0) 进行代数加1 适应度评估 满足停止准则 否 遗传操作 （选择、交叉、变异） 是 结束
