具有局部重复路径的多路旅行商问题的研究

被引：7

作者：

李鸿培

王新梅

机构：

[1] 西安电子科技大学综合业务网国家重点实验室!陕西西安

来源：

西安公路交通大学学报 | 2000年 / 02期

关键词：

多路旅行商问题; 最短路径; 哈密尔顿回路; 遗传算法;

D O I：

10.19721/j.cnki.1671-8879.2000.02.025

中图分类号：

TN915.02? [];

学科分类号：

0810 ; 081001 ;

摘要：

首先对连通图上允许旅行商走回头路的 TSP的问题进行了研究 ,证明了问题解的存在性 ,给出了利用连通图的顶点间最短路径构造完全图的求解方法。然后 ,对连通图上允许路径部分重复的 MTSP问题进行了初步的研究 ;采取“分治”的方法并结合遗传算法 ,设计了求解路径部分重复的 MTSP问题的有效算法。讨论了关于求解多个旅行商完成任务的最短时间和最短路径的问题 ;并给出了在限定时间内完成任务的条件下 ,求最小分组 (人员配置 )的问题的方法。可重复路径的MTSP问题的研究 ,在现实中有很大的使用价值。诸如 :交通运输、管道铺设、路线的选择、计算机网络的拓扑设计、邮递员送信等 ,都可以抽象成 TSP或 MTSP问题来求解

引用

页码：84 / 89

页数：6