【作者】 刘冠佳；

【导师】 刘水强；

【作者基本信息】 长沙理工大学 ， 应用数学， 2011， 硕士

【摘要】 由旅行商问题(TSP)衍生出来多旅行商问题(M-TSP)是组合优化领域的经典问题之一,是人工智能中遇到的一个具有广泛的研究意义的课题.多旅行商问题的特点使其符合许多实际问题,现实中经常会出现类似多出发点多旅行商的问题,其环境的动态不确定性要求系统实时调整任务规划,算法的计算时间复杂度应该尽可能低.另外目前很多系统车载计算能力通常很有限.因此,有必要研究能满足多出发点多旅行商系统需要的任务规划方法.本文通过对模型的处理和社团结构的分析,设计了一类多旅行商路径均衡近似算法并推广到多出发点多旅行商问题的求解,同时基于此算法应用于Ad hoc网络的多路径路由中,取得了显著的优化效果.本文所做的主要工作如下：类多旅行商路径均衡规划算法.本文研究了多个旅行商旅行多个城市的路径规划问题,提出了基于系统科学中的”吸引子”意义下的路径规划算法.路径规划的目标是均衡各旅行商的旅行路径长度并使得路径总和得到优化.为此提出了一种求解该问题的启发式算法思想,并结合邻近点和最短路径设计了算法,同时算法的复杂度分析知该算法的计算时间复杂度较以往的要低.类多出发点多旅行商问题规划算法.本文提出了一种基于K-means聚类算法的多出发点多旅行商问题求解的新方法.算法定义了节点的吸引度,并通过节点吸引度矩阵进行子环游节点集的归类,然后对各子环游应用单旅行商启发式算法进行求解.针对多出发点多旅行商问题的实例进行实验表明此规划算法能很好的求解此类问题.Ad hoc网络中基于多旅行商问题的多路径路由算法.提出一种基于旅行商问题的多路径路由算法(TSPMR算法),TSPMR算法是对Leach算法的扩展而进行多路径路由,把整个网络分成多个簇,通过簇首收集和传输信息,并不断地进行簇首确定来降低能耗,簇内进行多路径路由,保证了路由的稳定性.更多还原

【Abstract】 the multiple traveling salesman problem (M-TSP) is one of the typical problems on the field of combinatorial optimization, deriving from the Traveling salesman problem,which is a significance research issue on the field of artificial intelligence. the characteristics of Multiple traveling salesman problem conform many practical problems, and the uncertainty of Multi-objective Traveling Salesman problem that we confront,requires system adjust mission planning timely, and the computation complexity should be as low as possible. Also the limited computing system is not enough to achieve the complexity process.So studing a new method to resolve this promblem is necessary.Based on the model of the processing and analysis of community structure, designing a kind of Multi-objective Traveling Salesman problem Mission Planning Algorithm and promoting to A kind of mission planning algorithm with multidepot multisalesmen problem, obtaining remarkable optimization results applied in Ad hoc network.The major work of this paper can be summarized as follows:a kind of Multi-objective Traveling Salesman problem Mission Planning Algo-rithm with Balanced Paths.The paper presents a mission planning algorithm for Multi-objective traveling salesman problem with an objective to balance the length of traveling path and make the sum of path optimization.The travel mission involves several cities that need to be passed by traveling salesman.This algorithm is based upon the "attractors" of systems science.In this paper,combining with the neigh-boring points and the shortest path algorithm,we design a heuristic algorithm for solving the problem which balancing the length of traveling path and making the sum of path optimization,At the same time,the computation time complexity of the algorithm is lower than the past.A kind of mission planning algorithm with multidepot multisalesmen problem. This paper presents a new solving method for multidepot multisalesmen problem based on K-means clustering algorithm. Algorithm defines the node attract and classies the set of the tour node according node attract matrix,then applies the heuristic algorithm of single traveling salesman to solve it.The experiments results with multidepot multisalesmen problem show that this mission planning algorithm can be effectively applied in solving such problemsmulti-path routing algorithm of Ad hoc networks based on multiple travel-ing salesman problem. Traveling salesman problem multi-path routing algorithm (TSPMR algorithm), is a multi-path routing of expansion Leach algorithm,mul-tiple clusters in the whole network, determine the cluster head to reduce energy consumption by collecting and transporting information, executing multi-path rout-ing to ensure routing stability within the cluster.更多还原