导读:本文包含了广义旅行商论文开题报告文献综述及选题提纲参考文献,主要关键词:广义旅行商问题,进化算法,遗传算法,文化基因算法
广义旅行商论文文献综述
谭阳[1](2013)在《求解广义旅行商问题的若干进化算法研究》一文中研究指出广义旅行商问题(Generalized Traveling Salesman Problems,简称GTSP)是旅行商问题(Traveling Salesman Problems,简称TSP)的一个推广,是一个NP难问题,它有着更广泛的应用领域,同时求解更加困难。进化算法(EvolutionaryAlgorithm,简称EA)是受进化论启发而提出的一类随机搜索算法,对于传统计算方法难以处理的复杂问题,特别是对于求解NP难问题有很好的效果。目前,求解广义旅行商问题的方法主要分为传统搜索算法和进化算法。传统搜索算法搜索时间长,而进化算法的搜索能力和稳定性影响了其求解精度。本博士论文课题主要针对求解广义旅行商问题的进化算法进行了相关研究,设计了几种进化算法分别应用于第一类和第二类广义旅行商问题的求解。主要创新工作如下:(1)提出了一种新的基于遗传算法的文化基因算法对第一类广义旅行商问题进行求解。传统的遗传算法在求解广义旅行商问题中存在难以寻找高精度解的缺点,引入局部搜索算法能有效地提高求解的精度,但无约束的局部搜索将大大降低算法的求解效率。文中算法通过设置阈值开关和已搜索列表减少不必要的局部搜索,从而降低了整个算法的时间复杂度。此外,对文中算法的收敛性与混合染色体遗传算法的收敛性进行了对比分析。最后,用文中算法对TSP问题库中多个基准问题生成的第一类广义旅行商问题实例进行了数值仿真,结果表明,文中算法有效。(2)讨论了传统蚁群优化算法在求解广义旅行商问题上的不足,文中通过分析蚂蚁的生物特性,设计了一种存在离群蚁的蚁群优化算法对第一类广义旅行商问题进行求解。文中算法模仿了蚂蚁偏离蚁群行进的路线后重新寻找蚁群行进路线的行为,解决了传统蚁群优化算法在求解广义旅行商问题时解精度不高的问题。同时,为了避免过早地陷入局部最优,文中的算法结合了变异算子和局部搜索策略。最后,数值仿真实验结果验证了文中算法比传统蚁群优化算法更有效。(3)目前对第二类广义旅行商问题的研究很少,求解的方法则更少。文中首次为第二类广义旅行商问题设计了相应的局部搜索策略,并首次将蚁群优化算法拓展到求解第二类广义旅行商问题上。文中新设计的蚁群优化算法根据第二类广义旅行商问题的特点设计了新的人工蚂蚁访问策略,对影响算法搜索效果的参数和采用了自适应取值的方法,并结合了新设计的局部搜索策略和变异算子。数值仿真实验结果表明新设计的蚁群优化算法能有效地求解第二类广义旅行商问题。(4)针对目前第二类广义旅行商问题求解方法少、仅有的一些方法也存在运算复杂度高等缺陷的问题,通过分析两类广义旅行商问题权重矩阵的性质,提出了一种第二类广义旅行商问题权重矩阵重构的算法。第二类广义旅行商问题的权重矩阵经过重构后可以应用第一类广义旅行商问题的基于遗传算法的文化基因算法进行求解,从而间接求解了原第二类广义旅行商问题。通过这一方法,大大提高了第二类广义旅行商问题的求解精度,并降低了运算的复杂度。最后,采用文中提出的算法对TSP问题库中多个基准问题生成的第二类广义旅行商问题实例进行了测试,结果表明,该算法可以有效地求解第二类广义旅行商问题。(本文来源于《华南理工大学》期刊2013-04-01)
王玲丽[2](2012)在《随机存储下的有容量限制的广义旅行商问题》一文中研究指出在当今社会,电子商务在人们的生活中显得越来越重要,从事电商的企业也越来越多。外部,在线零售商们依然需要面对来自那些发展相对成熟的传统零售企业的竞争;内部,众多在线零售商们之间的竞争也不容小觑。因此,如何在激烈的竞争中脱颖而出,成了在线零售商们非常关心的问题。相较于传统零售企业,电商的特点主要表现在物流仓储以及配送方面,并且,仓储配送也是在线零售商挖掘新的利润空间的重要环节。物流仓储发展到今天,大多数仓库的存储环节虽然已按照存储单元进行了存储设备分区管理,但是为了提高仓库利用率,许多仓库的地堆区一个托盘存放众多项商品的情况依然存在,这导致了拣货作业寻找时间长,降低了拣货作业效率,同样的问题在搁板货架区域也依然存在。这种所谓“提高”仓库利用率的存储方法,会直接导致以下弊端:1、由于存储和拣货区库存没有进行有效地管理,这将直接导致拣货作业中断;2、拣货过程中一旦触发紧急补货任务,则需依赖熟练的工人进行寻找,导致作业变得复杂、低效。另外,在拣选环节,由于未设置订单池而进行即时下发拣选,致使任务下发连续性较差,经常会出现人员闲置问题,同时未将订单类型化处理,单、多件未严格区分下发任务,导致作业环节增加,影响作业效率提升。并且由于库区面积较大,拣货员在进行单一的任务时,仍然需要走完全场拣选,造成空走时间较长,拣货密度及拣货效率均比较低下。如何兼顾较高的仓库利用率,同时又能很快地给出最优拣货路径呢?在研究了众多电商的仓储模式后,我们发现了随机存储,其中以卓越亚马逊为此类仓库的代表。随机存储的存储策略能够使仓库的利用率得到提升,从而降低仓储成本。在这种存储策略下,对于接到订单后的订单预处理以及拣货路径的优化问题进行了研究。给出了有容量限制的广义旅行商问题的模型,并对模型进行了分析,通过对模型的推导,给出了该模型的下界,随后通过以CW-saving算法来给定初始解的变领域算法对其进行求解。最后通过求解算例证明算法的有效性。(本文来源于《上海交通大学》期刊2012-12-01)
王美华,田绪红,廖鸿翔[3](2009)在《求解广义旅行商问题的混合染色体遗传算法》一文中研究指出提出了针对广义旅行商问题(GTSP)的混合染色体遗传算法(HCGA)。目前,广义染色体遗传算法(GCGA)是求解GTSP问题的最好方法,但这种方法在编码设计上存在不足,使得算法全局搜索能力较差。在GCGA算法基础上,设计了二进制和整数混合编码的染色体,并更新了交叉和变异算子设计,得到改进算法HCGA。理论和实验结果都说明:HCGA比GCGA等多种算法具有更强的全局搜索能力。(本文来源于《计算机工程与应用》期刊2009年27期)
徐东镇[4](2007)在《蚁群算法及其在广义旅行商问题求解中的应用》一文中研究指出旅行商问题是一个经典的图论名题,广义旅行商问题则更具有重要的工程应用价值。对于旅行商问题,已有许多较成熟的求解方法,但对于广义旅行商问题,这方面的报道却较少。本文在深刻理解蚁群算法的算法原理、充分剖析蚁群算法程序的基础上,分析了已有的各种广义旅行商问题求解策略和方法的优缺点,将用于求解旅行商问题的蚁群算法扩展用于求解广义旅行商问题。M(蚂蚁数量)、α(信息启发式因子)、β(期望值启发式因子)、ρ(信息素残留系数)、Q(总信息量)是蚁群算法的重要控制参数,这五个参数对算法性能有很大影响,不仅影响算法的求解效率,而且影响算法的求解精度。本文通过大量算例分析研究了它们对算法求解效率和求解精度的影响,用于指导算法参数的最优选择论文最终通过一个工程应用实例验证了所开发的广义旅行商问题蚁群算法程序的正确性和实用性。(本文来源于《合肥工业大学》期刊2007-12-01)
赵曦,叶和平[5](2007)在《广义旅行商问题及其求解》一文中研究指出广义旅行商问题(Generalized Traveling Salesman Problem,简称GTSP)是比旅行商问题(Traveling Salesman Problem,简称TSP)更为复杂的一类组合优化问题,TSP可视为GTSP的特例.GTSP较TSP能提供更精确的实际问题模型,有着更广泛的应用领域,但相对于TSP的研究而言,至今GTSP的研究成果甚少.详细介绍了GTSP问题的定义与背景,应用领域及其求解方法,着重介绍了最新的GCGA算法,并对GTSP未来的研究提出了建议.(本文来源于《东莞理工学院学报》期刊2007年05期)
赵曦[6](2007)在《广义旅行商问题与旅行商问题的转化》一文中研究指出广义旅行商问题(Generalized Traveling Salesman Problem,简称GTSP)是比旅行商问题(Traveling Salesman Problem,简称TSP)更为复杂的一类组合优化问题,TSP可视为GTSP的特例。GTSP的应用领域更广,但相对于TSP的研究而言,GTSP的研究成果很少。本文介绍了GTSP问题的定义与背景,研究了GTSP与TSP的转化,提出了转化的优缺点和研究方向。(本文来源于《电脑知识与技术(学术交流)》期刊2007年05期)
赵曦,林健良,卢修泉,黄翰[7](2006)在《求解第二类广义旅行商问题的虚顶点遗传算法》一文中研究指出按照费用函数满足约束条件的不同,可以把广义旅行商问题(GeneralizedTravelingSalesmanProblem,简称GTSP)分为两类。目前,对GTSP解法的研究主要是面向费用函数满足叁角不等式的第一类问题,而对于费用函数不满足叁角不等式的第二类问题,则研究的比较少。文章针对第二类GTSP问题,提出了在广义染色体中加入虚顶点的新遗传算法。经过14个TSP问题库内的基准问题的测试表明,新算法是有效的。(本文来源于《计算机工程与应用》期刊2006年15期)
张雷,郑维敏[8](1996)在《广义旅行商问题、放映员问题和一类调度模型》一文中研究指出广义旅行商问题,既是旅行商问题的一个推广模型,又是新近出现的组合优化模型一一放映员问题的一种松驰.本文简介广义旅行商问题、放映员问题的研究进展和一类可转化的调度模型.(本文来源于《1996年中国控制会议论文集》期刊1996-09-01)
广义旅行商论文开题报告
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
在当今社会,电子商务在人们的生活中显得越来越重要,从事电商的企业也越来越多。外部,在线零售商们依然需要面对来自那些发展相对成熟的传统零售企业的竞争;内部,众多在线零售商们之间的竞争也不容小觑。因此,如何在激烈的竞争中脱颖而出,成了在线零售商们非常关心的问题。相较于传统零售企业,电商的特点主要表现在物流仓储以及配送方面,并且,仓储配送也是在线零售商挖掘新的利润空间的重要环节。物流仓储发展到今天,大多数仓库的存储环节虽然已按照存储单元进行了存储设备分区管理,但是为了提高仓库利用率,许多仓库的地堆区一个托盘存放众多项商品的情况依然存在,这导致了拣货作业寻找时间长,降低了拣货作业效率,同样的问题在搁板货架区域也依然存在。这种所谓“提高”仓库利用率的存储方法,会直接导致以下弊端:1、由于存储和拣货区库存没有进行有效地管理,这将直接导致拣货作业中断;2、拣货过程中一旦触发紧急补货任务,则需依赖熟练的工人进行寻找,导致作业变得复杂、低效。另外,在拣选环节,由于未设置订单池而进行即时下发拣选,致使任务下发连续性较差,经常会出现人员闲置问题,同时未将订单类型化处理,单、多件未严格区分下发任务,导致作业环节增加,影响作业效率提升。并且由于库区面积较大,拣货员在进行单一的任务时,仍然需要走完全场拣选,造成空走时间较长,拣货密度及拣货效率均比较低下。如何兼顾较高的仓库利用率,同时又能很快地给出最优拣货路径呢?在研究了众多电商的仓储模式后,我们发现了随机存储,其中以卓越亚马逊为此类仓库的代表。随机存储的存储策略能够使仓库的利用率得到提升,从而降低仓储成本。在这种存储策略下,对于接到订单后的订单预处理以及拣货路径的优化问题进行了研究。给出了有容量限制的广义旅行商问题的模型,并对模型进行了分析,通过对模型的推导,给出了该模型的下界,随后通过以CW-saving算法来给定初始解的变领域算法对其进行求解。最后通过求解算例证明算法的有效性。
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
广义旅行商论文参考文献
[1].谭阳.求解广义旅行商问题的若干进化算法研究[D].华南理工大学.2013
[2].王玲丽.随机存储下的有容量限制的广义旅行商问题[D].上海交通大学.2012
[3].王美华,田绪红,廖鸿翔.求解广义旅行商问题的混合染色体遗传算法[J].计算机工程与应用.2009
[4].徐东镇.蚁群算法及其在广义旅行商问题求解中的应用[D].合肥工业大学.2007
[5].赵曦,叶和平.广义旅行商问题及其求解[J].东莞理工学院学报.2007
[6].赵曦.广义旅行商问题与旅行商问题的转化[J].电脑知识与技术(学术交流).2007
[7].赵曦,林健良,卢修泉,黄翰.求解第二类广义旅行商问题的虚顶点遗传算法[J].计算机工程与应用.2006
[8].张雷,郑维敏.广义旅行商问题、放映员问题和一类调度模型[C].1996年中国控制会议论文集.1996