




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、优化组合问题论文:多旅行商近似算法研究与应用【中文摘要】由旅行商问题(TSP)衍生出来多旅行商问题(M-TSP)是组合优化领域的经典问题之一,是人工智能中遇到的一个具有广泛的研究意义的课题.多旅行商问题的特点使其符合许多实际问题,现实中经常会出现类似多出发点多旅行商的问题,其环境的动态不确定性要求系统实时调整任务规划,算法的计算时间复杂度应该尽可能低.另外目前很多系统车载计算能力通常很有限.因此,有必要研究能满足多出发点多旅行商系统需要的任务规划方法.本文通过对模型的处理和社团结构的分析,设计了一类多旅行商路径均衡近似算法并推广到多出发点多旅行商问题的求解,同时基于此算法应用于Ad hoc网络
2、的多路径路由中,取得了显著的优化效果.本文所做的主要工作如下:类多旅行商路径均衡规划算法.本文研究了多个旅行商旅行多个城市的路径规划问题,提出了基于系统科学中的”吸引子”意义下的路径规划算法.路径规划的目标是均衡各旅行商的旅行路径长度并使得路径总和得到优化.为此提出了一种求解该问题的启发式算法思想,并结合邻近点和最短路径设计了算法,同时算法的复杂度分析知该算法的计算时间复杂度较以往的要低.类多出发点多旅行商问题规划算法.本文提出了一种基于K-means聚类算法的多出发点多旅行商问题求解的新方法.算法定义了节点的吸引度,并通过节点吸引度矩阵进行子环游节点集的归类,然后对各子环游应用单旅行商启发式
3、算法进行求解.针对多出发点多旅行商问题的实例进行实验表明此规划算法能很好的求解此类问题.Ad hoc网络中基于多旅行商问题的多路径路由算法.提出一种基于旅行商问题的多路径路由算法(TSPMR算法),TSPMR算法是对Leach算法的扩展而进行多路径路由,把整个网络分成多个簇,通过簇首收集和传输信息,并不断地进行簇首确定来降低能耗,簇内进行多路径路由,保证了路由的稳定性.【英文摘要】the multiple traveling salesman problem (M-TSP) is one of the typical problems on the field of combinatorial
4、 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 th
5、at 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 proces
6、sing 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 maj
7、or 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
8、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 heurist
9、ic 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 pr
10、esents 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
11、 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 al
12、gorithm), 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.【关键词】优化组合问题 多旅行商问题
13、多出发点多旅行商问题 路径规划 路由算法【英文关键词】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 几种近似优化
14、算法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 数学模型的建
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年中国低压角式调节阀行业投资前景及策略咨询研究报告
- 2025年中国丁腈缝制手套行业投资前景及策略咨询研究报告
- 大学生机电考试题及答案
- 初三下册考试题及答案
- 出版发行行业大数据商业应用浅析
- 2025年金融机构风险管理数字化转型与风险管理团队优化报告
- 2025年金融风险管理:信用保险在供应链金融中的应用策略报告
- 2025至2030谷物烘干机行业发展趋势分析与未来投资战略咨询研究报告
- 2025年航空货运市场格局与航空货运企业市场拓展策略报告
- 2025届广东省揭阳市第一中学化学高二下期末复习检测模拟试题含解析
- 2025-2030中国电池行业发展分析及市场竞争格局与发展前景预测研究报告
- 社区矫正人员日常行为规范
- 农村自建房业主培训课件
- 财产申报表-被执行人用
- 一例肝硬化患者的护理查房课件
- 2025-2030中国光伏建筑一体化(BIPV)市场规模预测与竞争格局分析研究报告
- 《2025年普通高校在陕招生计划》
- 2025年广西壮族自治区三支一扶考试真题
- 宿舍管理员述职报告
- 2025年徐州市专业技术人员公需课程 - 心理调适
- 企业内部保密工作流程制度
评论
0/150
提交评论