TSPTW变体问题及其启发式算法
发布时间：2023-03-11 00:09
TSP问题即旅行商问题,是运筹学的著名问题之一,也是物流行业关键问题之一。随着客户对服务时间的要求,进而发展为带时间窗约束的旅行商问题(TSPTW),然而随着环境保护和节约能源的思想慢慢渗透到物流行业,该行业所要考虑的成本不再单单是时间、车辆行驶路程长度,还需要考虑车辆的油耗,这样考虑实时载重与当前载重行驶距离的变体TSPTW应运而生,该问题可在帮助物流行业控制成本的基础上控制油耗,为物流行业节约运输成本的同时满足其对减少碳排放量的需求。本文对以上问题构建数学模型并研究其求解算法。首先对该问题建立整数线性规划模型,但随着规模的增加,其求解时间急剧增大,因此,本文采用以下四种启发式算法求解该问题:采用改变了转移到下一节点期望函数的蚁群算法;采用轮盘赌选择算子、PMC交叉算子、倒位变异算子和适用于上述模型的适应度函数的遗传算法;采用Metropolis接受准则的模拟退火算法;采用以模型目标函数为适应度函数的粒子群算法;最后,应用SolomonTSPTW数据包中的rc208.3算例和rc203.2算例进行仿真试验,利用MATLAB 2017a软件对...
【文章页数】：91 页
【学位级别】：硕士
【文章目录】：
摘要
Abstract
第一章 绪论
1.1 研究背景及意义
1.2 旅行商问题起源、发展及其研究现状
1.3 本文的研究方法及主要内容
1.4 本章小结
第二章 变体TSPTW概述
2.1 旅行商问题(TSP)
2.1.1 TSP问题的定义
2.1.2 TSP问题数学模型
2.2 带时间窗的旅行商问题(TSPTW)
2.2.1 带时间窗的旅行商问题的组成要素
2.2.2 带时间窗的旅行商问题的数学模型
2.3 带时间窗的流旅行商问题(变体TSPTW)
2.3.1 带时间窗流旅行商问题的定义
2.3.2 带时间窗流旅行商问题的数学模型准备
2.4 本章小结
第三章 变体TSPTW求解算法研究
3.1 精确算法
3.2 启发式算法
3.2.1 传统启发式算法
3.2.2 现代启发式算法
3.3 蚁群优化算法
3.3.1 蚁群算法解决TSP问题的数学模型
3.3.2 蚁群优化算法流程图
3.4 遗传算法
3.4.1 遗传算法的相关概念
3.4.2 遗传算法工作流程
3.5 粒子群算法
3.5.1 粒子群算法的数学模型
3.5.2 粒子群算法的算法流程图
3.6 模拟退火算法
3.6.1 模拟退火过程描述
3.6.2 Metropolis接受准则
3.6.3 模拟退火算法的基本流程
3.7 常用算法概括与比较
3.8 本章小结
第四章 变体TSPTW的模型建立与算法设计
4.1 变体TSPTW模型构建
4.1.1 问题描述
4.1.2 基本假设
4.1.3 惩罚函数
4.1.4 定义变量
4.1.5 模型建立
4.2 蚁群算法设计
4.2.1 信息素调整策略
4.2.2 具体求解步骤
4.3 遗传算法设计
4.3.1 编解码
4.3.2 初始群体
4.3.3 选择算子
4.3.4 交叉算子
4.3.5 变异算子
4.3.6 适应度函数
4.3.7 终止进化规则
4.4 粒子群算法设计
4.4.1 粒子速度、位置和适应度函数的设计
4.4.2 粒子群算法具体求解步骤
4.5 模拟退火算法设计
4.5.1 算法环节及接受准则设计
4.5.2 模拟退火算法流程
4.6 本章小结
第五章 算例分析
5.1 算例说明
5.2 测试数据
5.3 模型参数设定
5.4 蚁群算法求解结果
5.4.1 参数设定
5.4.2 rc208.3算例试验结果
5.4.3 rc203.2算例试验结果
5.5 遗传算法求解结果
5.5.1 参数设定
5.5.2 rc208.3算例试验结果
5.5.3 rc203.2算例试验结果
5.6 粒子群算法求解结果
5.6.1 参数设定
5.6.2 rc208.3算例试验结果
5.6.3 rc203.2算例试验结果
5.7 模拟退火算法求解结果
5.7.1 参数设定
5.7.2 rc208.3算例试验结果
5.7.3 rc203.2算例试验结果
5.8 结果分析
5.9 本章小结
第六章 总结及展望
6.1 全文总结
6.2 研究展望
参考文献
附录
作者简介
致谢
本文编号：3758819
【文章页数】：91 页
【学位级别】：硕士
【文章目录】：
摘要
Abstract
第一章 绪论
1.1 研究背景及意义
1.2 旅行商问题起源、发展及其研究现状
1.3 本文的研究方法及主要内容
1.4 本章小结
第二章 变体TSPTW概述
2.1 旅行商问题(TSP)
2.1.1 TSP问题的定义
2.1.2 TSP问题数学模型
2.2 带时间窗的旅行商问题(TSPTW)
2.2.1 带时间窗的旅行商问题的组成要素
2.2.2 带时间窗的旅行商问题的数学模型
2.3 带时间窗的流旅行商问题(变体TSPTW)
2.3.1 带时间窗流旅行商问题的定义
2.3.2 带时间窗流旅行商问题的数学模型准备
2.4 本章小结
第三章 变体TSPTW求解算法研究
3.1 精确算法
3.2 启发式算法
3.2.1 传统启发式算法
3.2.2 现代启发式算法
3.3 蚁群优化算法
3.3.1 蚁群算法解决TSP问题的数学模型
3.3.2 蚁群优化算法流程图
3.4 遗传算法
3.4.1 遗传算法的相关概念
3.4.2 遗传算法工作流程
3.5 粒子群算法
3.5.1 粒子群算法的数学模型
3.5.2 粒子群算法的算法流程图
3.6 模拟退火算法
3.6.1 模拟退火过程描述
3.6.2 Metropolis接受准则
3.6.3 模拟退火算法的基本流程
3.7 常用算法概括与比较
3.8 本章小结
第四章 变体TSPTW的模型建立与算法设计
4.1 变体TSPTW模型构建
4.1.1 问题描述
4.1.2 基本假设
4.1.3 惩罚函数
4.1.4 定义变量
4.1.5 模型建立
4.2 蚁群算法设计
4.2.1 信息素调整策略
4.2.2 具体求解步骤
4.3 遗传算法设计
4.3.1 编解码
4.3.2 初始群体
4.3.3 选择算子
4.3.4 交叉算子
4.3.5 变异算子
4.3.6 适应度函数
4.3.7 终止进化规则
4.4 粒子群算法设计
4.4.1 粒子速度、位置和适应度函数的设计
4.4.2 粒子群算法具体求解步骤
4.5 模拟退火算法设计
4.5.1 算法环节及接受准则设计
4.5.2 模拟退火算法流程
4.6 本章小结
第五章 算例分析
5.1 算例说明
5.2 测试数据
5.3 模型参数设定
5.4 蚁群算法求解结果
5.4.1 参数设定
5.4.2 rc208.3算例试验结果
5.4.3 rc203.2算例试验结果
5.5 遗传算法求解结果
5.5.1 参数设定
5.5.2 rc208.3算例试验结果
5.5.3 rc203.2算例试验结果
5.6 粒子群算法求解结果
5.6.1 参数设定
5.6.2 rc208.3算例试验结果
5.6.3 rc203.2算例试验结果
5.7 模拟退火算法求解结果
5.7.1 参数设定
5.7.2 rc208.3算例试验结果
5.7.3 rc203.2算例试验结果
5.8 结果分析
5.9 本章小结
第六章 总结及展望
6.1 全文总结
6.2 研究展望
参考文献
附录
作者简介
致谢
本文编号：3758819
本文链接：https://www.wllwen.com/guanlilunwen/wuliuguanlilunwen/3758819.html
