优化组合问题论文：多旅行商近似算法研究与应用【中文摘要】由旅行商问题(TSP)衍生出来多旅行商问题(M-TSP)是组合优化领域的经典问题之一,是人工智能中遇到的一个具有广泛的研究意义的课题.多旅行商问题的特点使其符合许多实际问题,现实中经常会出现类似多出发点多旅行商的问题,其环境的动态不确定性要求系统实时调整任务规划,算法的计算时间复杂度应该尽可能低.另外目前很多系统车载计算能力通常很有限.因此,有必要研究能满足多出发点多旅行商系统需要的任务规划方法.本文通过对模型的处理和社团结构的分析,设计了一类多旅行商路径均衡近似算法并推广到多出发点多旅行商问题的求解,同时基于此算法应用于Ad hoc网络的多路径路由中,取得了显著的优化效果.本文所做的主要工作如下：类多旅行商路径均衡规划算法.本文研究了多个旅行商旅行多个城市的路径规划问题,提出了基于系统科学中的”吸引子”意义下的路径规划算法.路径规划的目标是均衡各旅行商的旅行路径长度并使得路径总和得到优化.为此提出了一种求解该问题的启发式算法思想,并结合邻近点和最短路径设计了算法,同时算法的复杂度分析知该算法的计算时间复杂度较以往的要低.类多出发点多旅行商问题规划算法.本文提出了一种基于K-means聚类算法的多出发点多旅行商问题求解的新方法.算法定义了节点的吸引度,并通过节点吸引度矩阵进行子环游节点集的归类,然后对各子环游应用单旅行商启发式算法进行求解.针对多出发点多旅行商问题的实例进行实验表明此规划算法能很好的求解此类问题.Ad hoc网络中基于多旅行商问题的多路径路由算法.提出一种基于旅行商问题的多路径路由算法(TSPMR算法),TSPMR算法是对Leach算法的扩展而进行多路径路由,把整个网络分成多个簇,通过簇首收集和传输信息,并不断地进行簇首确定来降低能耗,簇内进行多路径路由,保证了路由的稳定性.【英文摘要】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.【关键词】优化组合问题 多旅行商问题 多出发点多旅行商问题 路径规划 路由算法【英文关键词】combinational optimization problem multiple traveling salesman problem Multidepot multisalesmen problem path planning routing algorithm【目录】多旅行商近似算法研究与应用摘要5-6ABSTRACT6-7第一章 绪论10-181.1 引言10-111.2 优化组合问题11-131.2.1 组合优化问题数学模型11-121.2.2 旅行商问题的数学模型12-131.2.3 一类多旅行商问题131.3 几种近似优化算法13-161.3.1 蚁群算法13-141.3.2 遗传算法14-151.3.3 组织优化算法151.3.4 模拟退火算法15-161.4 本文主要研究内容16-18第二章 一类多旅行商路径均衡规划算法18-242.1 多旅行商问题的研究概述182.2 问题分析和模型建立18-192.2.1 多旅行商问题定义18-192.2.2 均衡旅行商路径规划问题及模型192.3 双目标旅行商问题的近似算法19-222.4 算法复杂性分析22-232.5 本章小结23-24第三章 一类多出发点多旅行商问题规划算法24-323.1 问题分析和模型建立24-253.1.1 多出发点多旅行商问题定义243.1.2 多出发点多旅行商路径规划问题及模型24-253.2 节点吸引度25-263.2.1 相邻节点间的吸引度25-263.2.2 非相邻两节点间的吸引度263.3 多出发点多旅行商近似算法26-273.4 算法实例及分析27-313.4.1 算法实例27-313.4.2 算法分析313.5 本章小结31-32第四章 基于多旅行商问题的移动Ad hoc网络路由算法32-384.1 Ad hoc网络路由算法研究概述32-334.2 相关数学模型建立及数据结构定义334.2.1 数学模型的建立334.2.2 相关数据结构的定义334.3 基于旅多行商问题的多路径路由算法33-354.3.1 网络簇首确定及其成员节点分簇33-344.3.2 网络簇维护34-354.3.3 网络簇内基于多旅行商问题的多路径路由发现选择方法354.3.4 路由维护过程354.4 算法分析35-364.5 本章小结36-38第五章 总结和展望38-405.1 本文工作总结38