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

The Genetic Algorithm Solving the MTSP which Path May be Part-iterative

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

In a connected graph G, the travelling salesman problem that salesman can go back a part of the path he traveled is studied, the existence of the problem result is proved and the result getting method using the shortest path between vertices of G to construct a completeness graph is given. The multiple travelling salesmen problem, which path may be part iterative, is discussed and its solution algorithm is given, the solution algorithm uses the “divide and rule” method combined with the genetic algorithm. The problems about the shortest time or shortest path of the multiple salesmen to finish their travelling tasks and how to configure the travelling tasks to salesmen in a limited travelling time are discussed. The importance to study the multiple travelling salesmen problem, which path may be part iterative, is presented.