元启发式算法求解一些旅行商扩展问题

论文摘要

旅行商问题（Traveling Salesman Problem,TSP）是一个经典的组合优化问题,一直受到计算机科学和运筹学界广泛关注,在现代物流运输领域中发挥了重要的作用,具有重要的实际意义。本文研究了TSP文献中四个经典的旅行商扩展问题,即带酒店选择的旅行商问题（TSPHS）、带先进先出规则的取货派货旅行商问题（TSPPDF）、多商品取货派货旅行商问题（m-PDTSP）和簇旅行商问题（CTSP）,为它们分别设计了高效的元启发式算法,与文献中最好的算法进行对比,来评价所提出算法的性能和效率,并对提出算法的一些重要组成部分进行分析和讨论。本文的主要贡献包括:（1）针对TSPHS问题,本文提出了一个高效的基于动态规划的混合进化算法（HEA）。该算法包括三个重要组成部分:动态规划、三个交叉算子和两阶段的局部搜索。本文提出的动态规划方法为一个给定顾客旅行序列寻找最优的住宿酒店序列,将传统的TSP解转化为TSPHS解。同时,HEA算法使用三个专门的交叉算子,用于生成高质量的后代个体,在每次进化中,算法会自适应地选择合适的交叉算子去产生子代解。此外,HEA算法使用基于合法解和非法解同时搜索的两阶段局部搜索优化程序,有效地探索搜索空间。通过对文献中131个基准算例进行实验,并且与目前文献中求解该问题最好的启发式算法作比较,对提出的HEA算法进行评估。实验结果表示,所提出的HEA算法具有很大的优势和很强的竞争力。具体表现在,它有效的改进当前基准算例中24个大算例的历史最好解,匹配了104个算例的历史最好解。（2）针对TSPPDF问题,本文提出一种新的带多次重启策略的迭代搜索算法（MIS）。该算法的新颖性在于一个新的基于阈值的探索阶段和一个多次重启策略被嵌入到迭代局部搜索框架内。在基于阈值的探索阶段,一个劣质解被接受取代当前解,当且仅当它的目标值不超过给定阈值。阈值在搜索过程中动态地、自适应地调整大小。同时,一旦搜索被认为陷入深度局部最优陷阱,就为当前搜索生成新的搜索起点。从计算结果来看,MIS算法在42个基准算例上表现出非常大的竞争力。具体表现在:与文献中五个最近的求解TSPPDF问题最好的启发式算法比较,它能够报告20个算例新的最好解,也就是改进了已知的历史最好解,并且能够匹配其余22个算例的历史最好解。（3）针对m-PDTSP问题,本文提出了一种高效的基于种群的随机禁忌阈值搜索算法（PRTTA）。在该算法中,随机禁忌阈值搜索程序在一个混合阶段和一个更新阶段上交替进行搜索,用于局部优化,以达到搜索的集中性。高质量解构成的种群为随机禁忌阈值搜索提供多个搜索起点,以达到搜索的多样性。从计算结果的角度来看,PRTTA算法在文献中240个小算例和108个大算例上展示了非常大的竞争力。具体表现在:与文献中精确算法相比,在已知最优解的206个小算例中,它报告了204个最优解,并且对未知最优解的34个算例,它报告了30个新的最好解。与文献中最好的启发式算法相比,PRTTA算法改进了108个大算例中97个已知的最好解。（4）为了高效地求解CTSP问题,本文首先将CTSP问题转换为一个TSP问题,然后提出一个高效的混合进化算法来求解这个转化后的TSP问题。通过对文献中给出的基准算例进行大量的实验对比测试,结果表明,所提出的算法从解的质量上和算法的运行时间上都要远远优于文献中所有的启发式算法。特别是,它几乎为所有的中大型算例报告了新的最好解,同时为剩余的小算例报告了最优解。并且,在大部分算例上,所提出的算法比文献中最好的启发式算法快约3至10倍。以上研究成果表明,本文提出的这些优化算法分别是求解这些旅行商问题最高效的启发式算法,都超过了文献中最好的启发式算法。在今后的研究中,我们尝试应用这些算法去求解其它相关的旅行商问题或者车辆路径问题。

论文目录

文章来源

类型: 博士论文

作者: 陆永亮

导师: 吴庆华

关键词: 旅行商问题,动态规划,禁忌搜索,启发式算法,取货和派货

来源: 华中科技大学

年度: 2019

分类: 基础科学,经济与管理科学

专业: 数学,服务业经济

单位: 华中科技大学

基金: 导师吴庆华教授主持的国家自然科学基金青年项目“考虑劳动力管理下的车辆路径问题研究”,项目编号:71401059

分类号: O221.3;F719.2

DOI: 10.27157/d.cnki.ghzku.2019.000265

总页数: 126

文件大小: 2280K

下载量: 259

相关论文文献

• [1].聚散优化算法:一种新的启发式算法[J]. 计算机集成制造系统 2020(03)
• [2].几种具有代表性的启发式算法研究[J]. 电子制作 2016(02)
• [3].共享单车再平衡问题及其容差插入启发式算法[J]. 运筹与管理 2019(10)
• [4].单体型装配问题的启发式算法研究[J]. 数字技术与应用 2017(01)
• [5].圆形件下料顺序分组启发式算法的设计与实现[J]. 图学学报 2017(01)
• [6].装备维修器材生产路径决策的两阶启发式算法[J]. 国防科技大学学报 2020(05)
• [7].基于一种特设启发式算法的车辆优化调度问题研究[J]. 电视技术 2019(04)
• [8].求解带硬时间窗车辆路径问题的时差插入启发式算法[J]. 计算机应用 2012(11)
• [9].求解柔性工件调度问题的启发式算法[J]. 科技风 2018(22)
• [10].基于超启发式算法的备件供应网络结构优化[J]. 系统工程与电子技术 2020(03)
• [11].基于启发式算法的自动化跨运车作业调度[J]. 上海大学学报(自然科学版) 2017(03)
• [12].三层物流网络选址—路径优化及混合启发式算法研究[J]. 计算机应用研究 2017(08)
• [13].基于混合顺序启发式算法的一维下料问题[J]. 中国机械工程 2014(16)
• [14].分配问题的启发式算法求解[J]. 甘肃联合大学学报(自然科学版) 2009(03)
• [15].一种有效求解厌恶设施选址问题的混合启发式算法[J]. 北京化工大学学报(自然科学版) 2017(06)
• [16].基于混合启发式算法的设备混合布局问题[J]. 工业工程 2017(01)
• [17].启发式算法的孔群加工路线模糊多目标优化[J]. 现代制造工程 2016(04)
• [18].多目标飞机和旅客恢复分阶段启发式算法[J]. 计算机应用研究 2014(08)
• [19].时变车辆路径问题的启发式算法[J]. 系统工程学报 2012(02)
• [20].阿德兰启发式算法在加油站选址中的应用[J]. 价值工程 2009(06)
• [21].混合启发式算法在汽车调度中的应用[J]. 电子技术应用 2009(07)
• [22].基于启发式算法的检测资源分配研究[J]. 锻压装备与制造技术 2018(02)
• [23].一种求解两级累计式车辆路径问题的两阶段启发式算法[J]. 机电一体化 2014(04)
• [24].模块度优化启发式算法应用[J]. 现代电子技术 2012(19)
• [25].基于阿德兰启发式算法的邮政网点选址研究[J]. 邮政研究 2011(05)
• [26].订货批量问题改进的相关策略启发式算法与仿真分析[J]. 系统仿真学报 2008(18)
• [27].基于元启发式算法的复杂车辆路径问题研究[J]. 物流技术 2013(21)
• [28].元启发式算法在校车路径规划中的应用[J]. 地理空间信息 2013(05)
• [29].无等待流水调度问题迭代启发式算法[J]. 安徽师范大学学报(自然科学版) 2009(01)
• [30].城市消防站点布局的改进启发式算法[J]. 数学的实践与认识 2008(01)

标签：旅行商问题论文;  动态规划论文;  禁忌搜索论文;  启发式算法论文;  取货和派货论文;