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

维普资讯 一 第 20卷 第 2期 西 安 公 路 交 通 大 学 学 报 Vo1．20 NO．2 2000年 4月 JournalofXianHighwayUniversity Apr．2000 文 章编号 ；1007—4112(2O00)02—0084—06 具有局部重复路径 的多路旅行商 问题 的研究 李鸿墙，王新梅 O22 (西安 电子科技大学 综合业务 网国家重点实验 室 ．侠西 西安 710071) 摘 要 ：首先对连通 图上 允许旅 行商走回头路 的TSP的问题进行 了研 究 ，证 明了问题解 的存在性 ， 给 出了利用连通 图的顶 点间最短路径构造 完奎 图的求解方法 。然后 ，对连通 图上允许路径部分重复 的MTSP问题进行 了初步的研究；采取 “分治”的方法并结合遗传算法 ，设计 了求解路径部分重复 的MTSP问题 的有效算法。讨论 了关于求解多个旅行商完成任务的最短时问和最短路径 的问题 ； 并给 出了在 限定时间内完成任务的条件下 ，求最小分组 (人员配置)的问题 的方法 。可重复路径 的 MTSP问题的研究．在现实中有很大的使用价值 。诸如 ：交通运输、管道铺设、路线的选择、计算机 网络 的拓扑设计 、邮递员送信等 ，都可 以抽 象成 TSP或 MTSP问题来求解 。 关键词：坠坚壹遗缝 黾丝鲶 啥窒垄垣旦整 造竺墨．当 中图分类号 ：TN915．02 文献 标识码 ：A M PJ迭 The℃eneticAlgorithm SolvingtheMTSPwhich PathM avbePart—iterative L，Hong pei·W ANG X in mei (NationalKeyLab．ofISN．XidianUniveersity．XiaD 710071，China) Abstract：In aconnected—graphG ，thetravellingsalesmanproblem thatsalesman can gohack a partofthepathhetraveledisstudied，theexistenceoftheproblem resultisprovedandtheresult getting—rmethodusingtheshortest——pathbetweenverticesofG tOconstructacompletenessgraph is given．Themultipletravelling—salesmen—problem ，whichpathmaybepartiterative，isdiscussed and itssolution algorithm isgiven，the solution algorithm usesthe “divideand rule”method combinedwith t