TSPTW变体问题及其启发式算法

摘要

TSP问题即旅行商问题;是运筹学的著名问题之一;也是物流行业关键问题之一。随着客户对服务时间的要求;进而发展为带时间窗约束的旅行商问题(TSPTW);然而随着环境保护和节约能源的思想慢慢渗透到物流行业;该行业所要考虑的成本不再单单是时间、车辆行驶路程长度;还需要考虑车辆的油耗;这样考虑实时载重与当前载重行驶距离的变体TSPTW应运而生;该问题可在帮助物流行业控制成本的基础上控制油耗;为物流行业节约运输成本的同时满足其对减少碳排放量的需求。 本文对以上问题构建数学模型并研究其求解算法。首先对该问题建立整数线性规划模型;但随着规模的增加;其求解时间急剧增大;因此;本文采用以下四种启发式算法求解该问题：采用改变了转移到下一节点期望函数的蚁群算法;采用轮盘赌选择算子、PMC交叉算子、倒位变异算子和适用于上述模型的适应度函数的遗传算法;采用 Metropolis接受准则的模拟退火算法;采用以模型目标函数为适应度函数的粒子群算法; 最后;应用SolomonTSPTW数据包中的rc_208.3算例和rc_203.2算例进行仿真试验;利用MATLAB 2017a软件对上述设计的算法对变体TSPTW问题的优化模型进行求解;并分别给出各算法的最低成本值和路径方案;然后针对各算法的试验结果进行分析;得到各算法这求解该问题优化模型的优越性和局限性;并验证本文基于变体TSPTW问题建立优化模型的合理性和有效性。

目录

第一个书签之前