多旅行商问题模型_第1页
多旅行商问题模型_第2页
多旅行商问题模型_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

精品文档 1欢迎下载 以点0表示旅行商的出发城市 称为源点 点表示个旅行商需访1 2 l m 问的城市 MTSP问题的数学模型可以表示为 令 1 0 ij x 弧 i j 在线路上 弧 i j 不在线路上 模型表示如下 00 0 0 min 10 1 10 1 01 0 1 RR ijij ij R ij i R ij j ij ij zd x xjR xiR XxS xi jR 或 式中 为增广费用 若用表示旅行商经过1 ij Rmld 1 ij c i jl 对应弧度所花的费用 如时间 距离 花费等 那么给增加行 i j ij c 1 m 和列 每一新的行或列是的最后一行或列的复制 增广矩阵的其他元 1 m ij c 素为无穷大 由此构成了增广费用 ij d 一般MTSP中 旅行商访问 个城市必须满足以下 2 个条件 l 条件 1 从指定城市出发 对其他所有城市严格访问一次后返回原出发城 市 条件2 一条有效路径严格由条非平凡子路径 Nontrivial Subtours m 组成 所谓非平凡子路径是指该路径中除出发城市外 至少访问一个其他城市 用遗传算法求解MTSP 可通过附加虚拟城市的方法把MTSP转化为TSP 将 另外个旅行商理解为个虚拟城市 这个虚拟城市标号分别 1 m 1 m 1 m 为 它们与城市 0 具有相同的坐标 即相同位置 在旅1 2 1 lllm 行商访问路径中出现的每一个虚拟城市均表示旅行商返回出发城市 从而组成 一个回路 每个回路表示MTSP中一个旅行商的旅行路径 需注意的是 为了避 免出现平凡子路径 必须假设个虚拟城市到原点的距离为 1 m 为一无穷大的正数 即永远不能达到 00 0 1 1 ij cMi jllmM 到其他各点距离与原点一致 这样遗传算法就不会出现 0 0 0 的途径 将源点 精品文档 2欢迎下载 0 复制个 个源点编号为每一个同源点 0 一样与其 1 m m0 1 1 llm 他点相连 而个源点互相不连接 这样在结点集m 上 可得到TSP线路 然后各源点合并成一个点 0 1 1 1l llm 这样MTSP线路就分解成个分线路 m 初始化路径矩阵D 确定实际问题参数 对参数进行编码 0 X初始化群体 适应度评估 满足停止准则结束 遗传操作 选择 交叉 变异 是 否 进行代数加1 精品文档 3欢迎下载 欢迎您的下载 欢迎您的下载 资
人人文库> 全部分类> 应用文书 > 事务文书

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论