模拟退火算法在带时间窗的车辆调度问题中应用

论文摘要

现代物流作为一种先进的组织方式和管理技术,被广泛认为是企业在降低物资消耗,提高劳动生产率之外的重要利润来源,在国民经济和社会发展中发挥着重要作用。在物流配送系统中,通过科学合理的方法确定运输路线和时间,不仅可以降低运作成本,还可以加快物质配送速度、提高运营效益和保证客户服务水平。物流配送中的车辆调度问题（Vehicle Routing Problem,简称VRP）是一个NP-hard问题,该问题由Dantzig和Ramser于1959年首次提出。由于很多问题都可以抽象为这一问题,很快便引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家以及运输计划制定者的极大重视,并一直是运筹学与组合优化领域的前沿与热点问题。在已有研究的基础上,本文研究了带时间窗的车辆调度问题（VehicleRouting Problem with Time Windows,简称VRPTW）,该问题可以简单描述为:使车辆从站点出发完成客户的配送需求,在满足容量和时间窗约束下,选择合适的路径,使得完成全部客户的配送需求所需的总的成本最小。本文分析VRPTW所具有的特点以及以往对该问题研究,在此基础上把模拟退火算法用到该问题的求解中。首先采用SWEEP算法构建初始路径,然后通过模拟退火算法求得满意解,在解的改进过程中采用2-interchange技术构建邻域。最后通过实验测试说明该算法能够求解一定规模的VRPTW问题,并对温度下降速度对算法的影响作了分析。

论文目录

• 摘要
• ABSTRACT
• 致谢
• 第一章 引言
• 1.1 研究背景
• 1.2 车辆调度问题的提出
• 1.3 本文的研究内容
• 第二章 车辆调度问题基本模型与算法
• 2.1 VRP与TSP的联系
• 2.2 VRP的研究现状
• 2.2.1 国外对VRP的研究
• 2.2.2 国内对VRP的研究
• 2.2.3 车辆调度问题的分类
• 2.3 车辆调度问题的基本模型与求解算法
• 2.3.1 车辆调度问题的基本模型
• 2.3.2 VRP常用的求解算法
• 2.4 本章小结
• 第三章 带时间窗车辆调度问题研究
• 3.1 引言
• 3.2 VRPTW问题建模
• 3.3 VRPTW问题求解算法
• 3.3.1 初始解算法
• 3.3.2 邻域交换技术
• 3.3.3 亚启发式算法
• 3.4 本章小结
• 第四章 求解VRPTW的两阶段模拟退火算法
• 4.1 约束处理
• 4.1.1 预处理过程中时间窗约束处理
• 4.1.2 节点路径分配时时间窗约束处理
• 4.2 两阶段模拟退火算法
• 4.2.1 初始解算法
• 4.2.2 邻域构造
• 4.2.3 模拟退火算法
• 4.3 实验结果与分析
• 4.4 本章小结
• 第五章 总结与展望
• 5.1 研究总结
• 5.2 研究展望
• 参考文献
• 攻读硕士学位期间发表的论文