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

作     者：李鸿培 王新梅 LI Hong-pei;WANG Xin-mei

作者机构：西安电子科技大学综合业务网国家重点实验室陕西西安710071 

基　　金：国家自然科学基金资助项目 !( 6 9972 0 35) 

出 版 物：《西安公路交通大学学报》 (Journal of Xi'an Highway University)

年 卷 期：2000年第20卷第2期

页      码：84-89页

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

主 题 词：最短路径 哈密尔顿回路 遗传算法 MTSP问题 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

D　O　I：10.3321/j.issn:1671-8879.2000.02.025

馆 藏 号：203473245...