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

发布时间：2021-12-17 01:34

　　旅行商问题（Traveling Salesman Problem,TSP）是一个经典的组合优化问题,一直受到计算机科学和运筹学界广泛关注,在现代物流运输领域中发挥了重要的作用,具有重要的实际意义。本文研究了TSP文献中四个经典的旅行商扩展问题,即带酒店选择的旅行商问题（TSPHS）、带先进先出规则的取货派货旅行商问题（TSPPDF）、多商品取货派货旅行商问题（m-PDTSP）和簇旅行商问题（CTSP）,为它们分别设计了高效的元启发式算法,与文献中最好的算法进行对比,来评价所提出算法的性能和效率,并对提出算法的一些重要组成部分进行分析和讨论。本文的主要贡献包括:（1）针对TSPHS问题,本文提出了一个高效的基于动态规划的混合进化算法（HEA）。该算法包括三个重要组成部分:动态规划、三个交叉算子和两阶段的局部搜索。本文提出的动态规划方法为一个给定顾客旅行序列寻找最优的住宿酒店序列,将传统的TSP解转化为TSPHS解。同时,HEA算法使用三个专门的交叉算子,用于生成高质量的后代个体,在每次进化中,算法会自适应地选择合适的交叉算子去产生子代解。此外,HEA算法使用基于合法解和非法解同时搜索的两... 

【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校

【文章页数】：126 页

【学位级别】：博士

【文章目录】：
摘要
Abstract
1 绪论
    1.1 研究背景和意义
    1.2 研究目标和方法
    1.3 本文的主要工作及其结构
    1.4 本文的主要创新点
2 国内外相关研究综述
    2.1 带酒店选择的旅行商问题
    2.2 带FIFO规则的取货派货旅行商问题
    2.3 多商品取货派货旅行商问题
    2.4 簇旅行商问题
    2.5 本章小结
3 基于动态规划的混合进化算法求解带酒店选择旅行商问题
    3.1 问题概述
    3.2 问题定义和数学模型
    3.3 求解TSPHS的混合进化算法
    3.4 计算实验
    3.5 分析与讨论
    3.6 本章小结
4 迭代搜索算法求解带FIFO规则的取货派货旅行商问题
    4.1 问题概述
    4.2 问题定义和数学模型
    4.3 求解TSPPDF的迭代搜索算法
    4.4 计算实验
    4.5 分析与讨论
    4.6 本章小结
5 随机禁忌阈值搜索算法求解多商品取货派货旅行商问题
    5.1 问题概述
    5.2 问题定义和数学模型
    5.3 求解m-PDTSP的带种群管理的随机禁忌阈值搜索算法
    5.4 计算实验
    5.5 分析与讨论
    5.6 本章小结
6 混合进化算法求解簇旅行商问题
    6.1 问题概述
    6.2 问题定义和数学模型
    6.3 提出的方法
    6.4 计算实验
    6.5 分析与讨论
    6.6 本章小结
7 总结和展望
    7.1 全文总结
    7.2 研究展望
致谢
参考文献
附录1 攻读博士学位期间发表的学术论文
附录2 攻读博士学位期间参与的科研项目
附录3 PRTTA算法在小算例集上的实验结果
附录4 PRTTA算法在大算例集上的实验结果
附录5 HEA算法在基准算例集上的实验结果


【参考文献】：
期刊论文
[1]求解配送\收集旅行商问题的模拟退火算法[J]. 谢秉磊,李良,郭耀煌.  系统工程理论方法应用. 2002(03)



本文编号：3539167